### The HOM problem is decidableThe HOM problem is decidable

Access Restriction
Subscribed

 Author Godoy, Guillem ♦ Gimnez, Omer Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Tree automata ♦ Homomorphisms ♦ Regular languages ♦ Transducers Abstract We close affirmatively a question that has been open for long time: decidability of the HOM problem. The HOM problem consists in determining, given a tree homomorphism $\textit{H}$ and a regular tree language $\textit{L}$ represented by a tree automaton, whether $\textit{H}(\textit{L})$ is regular. In order to decide the HOM problem, we develop new constructions and techniques that are interesting by themselves, and provide several significant intermediate results. For example, we prove that the universality problem is decidable for languages represented by tree automata with equality constraints, and that the equivalence and inclusion problems are decidable for images of regular languages through tree homomorphisms. Our contributions are based on the following new constructions. We describe a simple transformation for converting a tree automaton with equality constraints into a tree automaton with disequality constraints recognizing the complementary language. We also define a new class of tree automata with arbitrary disequality constraints and a particular kind of equality constraints. An automaton of this new class essentially recognizes the intersection of a tree automaton with disequality constraints and the image of a regular language through a tree homomorphism. We prove decidability of emptiness and finiteness for this class by a pumping mechanism. We combine the above constructions adequately to provide an algorithm deciding the HOM problem. This is the journal version of a paper presented in the 42nd ACM Symposium on Theory of Computing (STOC 2010). Here, we provide all proofs and examples. Moreover, we obtain better complexity results via the modification of some proofs and a careful complexity analysis. In particular, the obtained time complexity for the decision of HOM is a tower of three exponentials. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-09-04 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 4 Page Count 44 Starting Page 1 Ending Page 44

#### Open content in new tab

Source: ACM Digital Library