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

DOI10.1142/S012905410000003XzbMATH Open1319.68127OpenAlexW2061902761MaRDI QIDQ5249028FDOQ5249028

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

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

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)

Cites Work

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

Cited In (4)

• Normalization properties for shallow TRS and innermost rewriting
• Harald Ganzinger's legacy: contributions to logics and programming
• Title not available (Why is that?)
• 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)