RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION

DOI10.1142/S012905410000003XzbMath1319.68127OpenAlexW2061902761MaRDI QIDQ5249028

Harald Ganzinger, Florent Jacquemard, Margus Veanes

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905410000003x

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Harald Ganzinger’s Legacy: Contributions to Logics and Programming ⋮ Normalization properties for shallow TRS and innermost rewriting

Cites Work

• Simple second-order languages for which unification is undecidable
• Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
• The undecidability of the second-order unification problem
• Bottom-up tree pushdown automata: Classification and connection with rewrite systems
• Haskell overloading is DEXPTIME-complete
• Relationships between nondeterministic and deterministic tape complexities
• Tree acceptors and some of their applications
• Alternation

This page was built for publication: RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION