Title :
The HOM Problem is EXPTIME-Complete
Author :
Creus, Carles ; Gascón, Adrià ; Godoy, Guillem ; Ramos, Lander
Author_Institution :
Dept. de Llenguatges i Sist. Inf., Univ. Politec. de Catalunya, Barcelona, Spain
Abstract :
The HOM problem questions whether the image of a given regular tree language through a given tree homomorphism is also regular. Decidability of HOM is an important theoretical question which was open for a long time. Recently, HOM has been proved decidable with a triple exponential time algorithm. In this paper we obtain an exponential time algorithm for this problem, and conclude that it is EXPTIME-complete. The proof builds upon previous results and techniques on tree automata with constraints.
Keywords :
automata theory; computational complexity; decidability; formal languages; trees (mathematics); EXPTIME-complete; HOM problem; decidability; regular tree language; tree automata; tree homomorphism; triple exponential time algorithm; Automata; Computer science; Context; Image recognition; Polynomials; Transducers; Vegetation; Decision Problems; Tree Automata; Tree Homomorphisms;
Conference_Titel :
Logic in Computer Science (LICS), 2012 27th Annual IEEE Symposium on
Conference_Location :
Dubrovnik
Print_ISBN :
978-1-4673-2263-8
DOI :
10.1109/LICS.2012.36
