[Submit a comment] [RTALooP home] [Index] [Previous] [Next]  [Postscript] [PDF] [BibTeX Source] [LaTeX Source] 
Originator: Hitoshi Ohsaki [OT02]
Date: July 2002
Summary: Are universality and inclusion of ACrecognizable languages decidable?
An ACtree automaton as defined by [Ohs01] is given by a signature Σ, a set of ACaxioms (that is, associativity and commutativity) for some function symbols of Σ, and a set of rewrite rules R of the form

where the q’s and p’s are state symbols. Such an automaton accepts a term t iff it rewrites t modulo the given ACaxioms to some final state. L(A) denotes the language recognized by an ACtree automaton A; a language L is called ACrecognizable iff L=L(A) for some ACtree automaton A.
Are the following questions decidable?
It has been shown [OT02] that emptiness of ACrecognizable languages is decidable. Furthermore, as a consequence of the results of [ZL03], universality and inclusion are decidable if transition rules of the form f(q_{1},…,q_{n}) → f(p_{1},…,p_{n}) are not allowed (this is the subclass of socalled regular AC treeautomata). However, both questions are still open in the general case.
The inclusion problem of ACtree automata is undecidable [OTTR05]. Decidability of universality is still an open question.
[Submit a comment] [RTALooP home] [Index] [Previous] [Next]  [Postscript] [PDF] [BibTeX Source] [LaTeX Source] 