Are universality and inclusion of AC-recognizable languages decidable?
The source page states the original problem together with its recorded qualifications and progress updates as follows.
An AC-tree automaton as defined by [Ohsaki, 2002] is given by a signature , a set of AC-axioms (that is, associativity and commutativity) for some function symbols of , and a set of rewrite rules of the form
where the 's and 's are state symbols. Such an automaton accepts a term iff it rewrites modulo the given AC-axioms to some final state. denotes the language recognized by an AC-tree automaton ; a language is called AC-recognizable iff for some AC-tree automaton .
Are the following questions decidable? \begin{itemize}
-
Universality: Given an AC-tree automaton , is equal to the set of all ground terms over the given signature ?
-
Inclusion: Given AC-tree automata and , is a subset of ? \end{itemize}
It has been shown [Ohsaki, 2002] that emptiness of AC-recognizable languages is decidable. Furthermore, as a consequence of the results of [Ohsaki, 2002], universality and inclusion are decidable if transition rules of the form are not allowed (this is the sub-class of so-called regular AC tree-automata). However, both questions are still open in the general case.
Recorded progress.
The inclusion problem of AC-tree automata is undecidable~[Ohsaki, 2002]. Decidability of universality is still an open question.
