The HOM problem is decidable

We provide an algorithm that, given a tree homomorphism H and a regular tree language L represented by a tree automaton, determines whether H(L) is regular. This settles a question that has been open for a long time.

Authors

• Guillem Godoy
• Omer Giménez
• Lander Ramos
• Carme Àlvarez

Keywords

• homomorphisms
• regular languages
• tree automata
• transducers