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

DOI10.1142/S012905410000003XMaRDI QIDQ5249028zbMATH OpenOpenAlexFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Decidability of theories and sets of sentences (03B25)

Recommendations

• The undecidability of simultaneous rigid E-unification
• scientific article; zbMATH DE number 517077
• scientific article; zbMATH DE number 1552529
• Rigid E-unification: NP-completeness and applications to equational matings
• scientific article; zbMATH DE number 1614698
• Efficient algorithms for bounded rigid \(E\)-unification
• scientific article; zbMATH DE number 1110839
• Theorem proving with bounded rigid \(E\)-unification
• Decidability and complexity of simultaneous rigid E-unification with one variable and related results
• Monadic simultaneous rigid \(E\)-unification and related problems

Cites work

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

Cited in

(4)

• Normalization properties for shallow TRS and innermost rewriting
• Harald Ganzinger's legacy: contributions to logics and programming
• scientific article; zbMATH DE number 1405649 (Why is no real title available?)
• The undecidability of simultaneous rigid E-unification

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

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