Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The HOM problem is decidable

Autor
Godoy, G.; Giménez, O.; Ramos, L.; Alvarez, C.
Tipus d'activitat
Document cientificotècnic
Data
2009-06
Codi
LSI-09-22-R
Repositori
http://hdl.handle.net/2117/87972 Obrir en finestra nova
Resum
We close affirmatively a question which has been open for 35 years: decidability of the HOM problem. The HOM problem consists in deciding, given a tree homomorphism $H$ and a regular tree languagle $L$ represented by a tree automaton, whether $H(L)$ is regular. For deciding the HOM problem, we develop new constructions and techniques which are interesting by themselves, and provide several significant intermediate results. For example, we prove that the universality problem is decidable for lang...
Citació
Godoy, G., Giménez, O., Ramos, L., Álvarez, C. "The HOM problem is decidable". 2009.
Paraules clau
Tree Automata, Tree Homomorphisms, Hom Problem
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius