Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The HOM problem is EXPTIME-complete

Autor
Creus, C.; Gascon, A.; Godoy, G.; Ramos, L.
Tipus d'activitat
Presentació treball a congrés
Nom de l'edició
27th Annual ACM/IEEE Symposium on Logic in Computer Science
Any de l'edició
2012
Data de presentació
2012
Llibre d'actes
Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
Pàgina inicial
255
Pàgina final
264
DOI
https://doi.org/10.1109/LICS.2012.36 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/19252 Obrir en finestra nova
Resum
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...
Citació
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.
Paraules clau
Decision Problems, Tree Automata, Tree Homomorphisms
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

  • Creus Lopez, Carles  (autor ponent)
  • Gascon Caro, Adrian  (autor ponent)
  • Godoy Balil, Guillermo  (autor ponent)
  • Ramos, Lander  (autor ponent)