Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The HOM problem is decidable

Autor
Godoy, G.; Giménez, O.
Tipus d'activitat
Article en revista
Revista
Journal of the ACM
Data de publicació
2013-07-18
Volum
60
Número
4
Pàgina inicial
Article 23
DOI
10.1145/2501600
URL
http://dl.acm.org/citation.cfm?id=2501600&CFID=749672533&CFTOKEN=30295445 Obrir en finestra nova
Resum
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 H and a regular tree language L represented by a tree automaton, whether H(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 lan...
Paraules clau
Decidability, Homomorphism, Regularity
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants