The HOM problem is decidable
| Autor: | Carme Àlvarez, Guillem Godoy, Omer Giménez, Lander Ramos |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Binary tree Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Regular language Tree homomorphism Trie Probabilistic automaton Regular tree grammar Tree automaton Nondeterministic finite automaton Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | STOC |
| DOI: | 10.1145/1806689.1806757 |
| Popis: | 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.Along the way, 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 languages represented by tree automata with equality constraints, and that the equivalence and inclusion problems are decidable for images of regular tree languages through tree homomorphisms.Our algorithms are based on the following constructions. We describe a simple transformation for converting a tree automaton with equality constraints into a tree automaton with inequality constraints recognizing the complementary language. We also define a new class of automata with arbitrary inequality constraints and a particular kind of equality constraints. An automaton of this new class essentially recognizes the intersection of a tree automaton with inequality constraints and the image of a regular tree language through a tree homomorphism. We prove decidability of emptiness and finiteness for this class by a pumping mechanism. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|