DocumentCode
3092749
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
fYear
2012
fDate
25-28 June 2012
Firstpage
255
Lastpage
264
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Logic in Computer Science (LICS), 2012 27th Annual IEEE Symposium on
Conference_Location
Dubrovnik
ISSN
1043-6871
Print_ISBN
978-1-4673-2263-8
Type
conf
DOI
10.1109/LICS.2012.36
Filename
6280444
Link To Document