The HOM problem is EXPTIME-complete

DOI10.1137/140999104MaRDI QIDQ5895159zbMATH OpenOpenAlexFDO

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

Publication date 16 August 2016

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/102817

zbMATH Keywords

homomorphismsregular languagestransducerstree automata

Mathematics Subject Classification ID

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

Recommendations

• The HOM Problem is EXPTIME-Complete
• The HOM problem is decidable
• The HOM problem is decidable
• Deciding regularity of the set of instances of a set of terms with regular constraints is EXPTIME-complete
• Ground reducibility is EXPTIME-complete

Cites work

• Algebraic automata and context-free sets
• Automata for reduction properties solving
• Bottom-up and top-down tree transformations— a comparison
• Classes of Tree Homomorphisms with Decidable Preservation of Regularity
• Computing linearizations using test sets
• Decidability of regularity and related properties of ground normal form languages
• Decidable classes of tree automata mixing local and global constraints modulo flat theories
• Deciding regularity of the set of instances of a set of terms with regular constraints is EXPTIME-complete
• Encyclopedia of Database Systems
• Ground reducibility is EXPTIME-complete
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 1330134 (Why is no real title available?)
• scientific article; zbMATH DE number 1995182 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 794243 (Why is no real title available?)
• scientific article; zbMATH DE number 1405621 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• Recognizable tree-languages and nonlinear morphisms
• Set constraints and automata
• Term Rewriting and All That
• The HOM problem is decidable
• The HOM Problem is EXPTIME-Complete
• Transformations and translations from the point of view of generalized finite automata theory
• Tree acceptors and some of their applications
• Tree automata with global constraints
• Undecidable properties of deterministic top-down tree transducers

Cited in

(9)

• Ground reducibility is EXPTIME-complete
• QUIXO is EXPTIME-complete
• The HOM problem is decidable
• Deciding regularity of the set of instances of a set of terms with regular constraints is EXPTIME-complete
• Regular matching problems for infinite trees
• The HOM problem is decidable
• The HOM Problem is EXPTIME-Complete
• Theoretical computer science: computational complexity
• Weighted HOM-problem for nonnegative integers

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 Q5895159)