License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2012.528
URN: urn:nbn:de:0030-drops-36953
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3695/
Wu, Zhilin
Commutative Data Automata
Abstract
Formalisms over infinite alphabets have recently received much focus in the community of theoretical computer science. Data automaton is a formal model for words over an infinite alphabet, that is, the product of a finite set of labels and an infinite set of data values, proposed by Bojanczyk, Muscholl, Schwentick et. al. in 2006.
A data automaton consists of two parts, a nondeterministic letter-to-letter transducer, and a class condition specified by a finite automaton, which acts as a condition on each subword of the outputs of the transducer in corresponding to a maximal set of positions with the same data value.
It is open whether the nonemptiness of data automata can be decided with elementary complexity, since this problem is equivalent to the reachability of petri nets. Very recently, a restriction of data automata with elementary complexity, called weak data automata, was proposed by Kara, Schwentick and Tan and its nonemptiness problem was shown to be in 2NEXPTIME.
In weak data automata, the class conditions are specified by some simple constraints on the number of occurrences of labels occurring in every class. The aim of this paper is to demonstrate that the commutativity of class conditions is the genuine reason accounting for the elementary complexity of weak data automata.
For this purpose, we define and investigate commutative data automata, which are data automata with class conditions restricted to commutative regular languages. We show that while the expressive power of commutative data automata is strictly stronger than that of weak data automata, the nonemptiness problem of this model can still be decided with elementary complexity, more precisely, in 3NEXPTIME. In addition, we extend the results to data omega-words and prove that the nonemptiness of commutative Büchi data automata can be decided in 4NEXPTIME. We also provide logical characterizations for commutative (Büchi) data automata, similar to those for weak (Büchi) data automata.
BibTeX - Entry
@InProceedings{wu:LIPIcs:2012:3695,
author = {Zhilin Wu},
title = {{Commutative Data Automata}},
booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
pages = {528--542},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-42-2},
ISSN = {1868-8969},
year = {2012},
volume = {16},
editor = {Patrick C{\'e}gielski and Arnaud Durand},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3695},
URN = {urn:nbn:de:0030-drops-36953},
doi = {10.4230/LIPIcs.CSL.2012.528},
annote = {Keywords: Data Automata, Commutative regular languages, Presburger arithmetic, Existential Monadic Second-order logic, B{\"u}chi automata}
}
|
Keywords: |
|
Data Automata, Commutative regular languages, Presburger arithmetic, Existential Monadic Second-order logic, Büchi automata |
|
Collection: |
|
Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
03.09.2012 |
