The HOM Problem is EXPTIME-Complete

DOI10.1109/LICS.2012.36zbMath1360.68551OpenAlexW2059186017MaRDI QIDQ5892435

Lander Ramos, Carles Creus, Guillem Godoy, Adrià Gascón

Publication date: 16 May 2017

Published in: 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/lics.2012.36

zbMATH Keywords

decision problemstree automatatree homomorphisms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Solving the Weighted HOM-Problem With the Help of Unambiguity ⋮ Excessively duplicating patterns represent non-regular languages ⋮ Paths, tree homomorphisms and disequalities for -clauses ⋮ The HOM Problem is EXPTIME-Complete

This page was built for publication: The HOM Problem is EXPTIME-Complete