The HOM problem is decidable

DOI10.1145/1806689.1806757zbMath1293.68186OpenAlexW2014118070MaRDI QIDQ2875176

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

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806757

zbMATH Keywords

homomorphismsregular languagestree automatatransducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Crossing the Syntactic Barrier: Hom-Disequalities for ${\mathcal H}_1$-Clauses ⋮ Solving the Weighted HOM-Problem With the Help of Unambiguity ⋮ Parameter reduction and automata evaluation for grammar-compressed trees ⋮ Tree Automata, (Dis-)Equality Constraints and Term Rewriting ⋮ Paths, tree homomorphisms and disequalities for -clauses ⋮ Projection for Büchi Tree Automata with Constraints between Siblings

This page was built for publication: The HOM problem is decidable