Paper Info
Title
Two-way equational tree automata for AC-like theories: decidability and closure properties
Abstract
We study two-way tree automata modulo equational theories. We deal with the theories of Abelian groups (ACUM), idempotent commutative monoids (ACUI), and the theory of exclusive-or (ACUX), as well as some variants including the theory of commutative monoids (ACU). We show that the one-way automata for all these theories are closed under union and intersection, and emptiness is decidable. For two-way automata the situation is more complex. In all these theories except ACUI, we show that two-way automata can be effectively reduced to one-way automata, provided some care is taken in the definition of the so-called push clauses. (The ACUI case is open.) In particular, the two-way automata modulo these theories are closed under union and intersection, and emptiness is decidable. We also note that alternating variants have undecidable emptiness problem for most theories, contrarily to the non-equational case where alternation is essentially harmless.
Year
Venue
Keywords
2003
RTA
undecidable emptiness problem,two-way automata modulo,one-way automaton,acui case,commutative monoids,two-way tree automata modulo,equational theory,two-way equational tree automaton,two-way automaton,ac-like theory,idempotent commutative monoids,closure property,non-equational case,abelian group
Field
DocType
Volume
Abelian group,Discrete mathematics,Automata theory,Commutative property,Modulo,Algorithm,Decidability,Monoid,Tree automaton,Mathematics,Undecidable problem
Conference
2706
ISSN
ISBN
Citations 
0302-9743
3-540-40254-3
17
PageRank 
References 
Authors
0.78
11
1
Name
Order
Citations
PageRank
Kumar Neeraj Verma11718.87