Loading...
Loading...

Go to the content (press return)

The HOM problem is EXPTIME-complete

Author
Creus, C.; Gascon, A.; Godoy, G.; Ramos, L.
Type of activity
Presentation of work at congresses
Name of edition
27th Annual ACM/IEEE Symposium on Logic in Computer Science
Date of publication
2012
Presentation's date
2012
Book of congress proceedings
Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
First page
255
Last page
264
DOI
https://doi.org/10.1109/LICS.2012.36 Open in new window
Repository
http://hdl.handle.net/2117/19252 Open in new window
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...
Citation
Creus, C. [et al.]. The HOM problem is EXPTIME-complete. A: IEEE Logic in Computer Science. "Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012". 2012, p. 255-264.
Keywords
Decision Problems, Tree Automata, Tree Homomorphisms
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

  • Creus Lopez, Carles  (author and speaker )
  • Gascon Caro, Adrian  (author and speaker )
  • Godoy Balil, Guillermo  (author and speaker )
  • Ramos, Lander  (author and speaker )