The HOM Problem is EXPTIME-Complete

DOI10.1137/140999104zbMath1348.68059OpenAlexW2468936326MaRDI QIDQ5895159

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

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 languagestree automatatransducers

Mathematics Subject Classification ID

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

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Set constraints and automata
• Undecidable properties of deterministic top-down tree transducers
• Recognizable tree-languages and nonlinear morphisms
• Ground reducibility is EXPTIME-complete
• Decidability of regularity and related properties of ground normal form languages
• Automata for reduction properties solving
• Tree acceptors and some of their applications
• Deciding Regularity of the Set of Instances of a Set of Terms with Regular Constraints is EXPTIME-Complete
• Encyclopedia of Database Systems
• TREE AUTOMATA WITH GLOBAL CONSTRAINTS
• Bottom-up and top-down tree transformations— a comparison
• Term Rewriting and All That
• Decidable Classes of Tree Automata Mixing Local and Global Constraints Modulo Flat Theories
• Transformations and translations from the point of view of generalized finite automata theory
• Classes of Tree Homomorphisms with Decidable Preservation of Regularity
• Algebraic automata and context-free sets
• Computing linearizations using test sets
• The HOM Problem is EXPTIME-Complete

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