Change search
ReferencesLink to record
Permanent link

Direct link
On notions of regularity for data languages
Umeå University, Faculty of Science and Technology, Department of Computing Science. (NFL)
2010 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 411, no 4-5, 702-715 p.Article in journal (Refereed) Published
Abstract [en]

With motivation from considerations in XML database theory and model checking, data strings have been introduced as an extension of finite alphabet strings which carry, at each position, a symbol and a data value from an infinite domain. Previous work has shown that it is difficult to come up with an expressive yet decidable automaton model for data languages. Recently, such a model, data automata, was introduced. This paper introduces a simpler but equivalent model and investigates its expressive power, algorithmic and closure properties, and some extensions.

Place, publisher, year, edition, pages
2010. Vol. 411, no 4-5, 702-715 p.
National Category
Computer Science
URN: urn:nbn:se:umu:diva-35539DOI: 10.1016/j.tcs.2009.10.009OAI: diva2:344984
Available from: 2010-08-23 Created: 2010-08-23 Last updated: 2010-10-10Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Björklund, Henrik
By organisation
Department of Computing Science
In the same journal
Theoretical Computer Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 38 hits
ReferencesLink to record
Permanent link

Direct link