The HOM Problem is EXPTIME-Complete

DOI10.1109/LICS.2012.36MaRDI QIDQ5892435zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• The HOM problem is EXPTIME-complete
• The HOM problem is decidable
• The HOM problem is decidable
• The Complexity of Homomorphism Indistinguishability
• Complexity of the homomorphism extension problem in the random case
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• On the Complexity of Holant Problems
• Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
• Ground reducibility is EXPTIME-complete
• On Exact Complexity of Subgraph Homeomorphism

Cited in

(10)

• Ground reducibility is EXPTIME-complete
• QUIXO is EXPTIME-complete
• Excessively duplicating patterns represent non-regular languages
• The HOM problem is decidable
• Deciding regularity of the set of instances of a set of terms with regular constraints is EXPTIME-complete
• Paths, tree homomorphisms and disequalities for H₁-clauses
• The HOM problem is decidable
• The HOM problem is EXPTIME-complete
• Solving the Weighted HOM-Problem With the Help of Unambiguity
• The weighted HOM-problem over fields

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892435)