^5-equational theory of context unification is undecidable

DOI10.1016/S0304-3975(01)00190-6MaRDI QIDQ1607219zbMATH OpenOpenAlexFDO

Authors Sergei Vorobyov

Publication date 31 July 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(01)00190-6

zbMATH Keywords

context unification problemequational theoryoperator algorithmsquantified fragmentssecond-order unificationundecidabilityword unification

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 1222595
• On equational theories, unification, and (un)decidability
• Unification in permutative equational theories is undecidable
• On unification: Equational theories are not bounded
• scientific article; zbMATH DE number 4041328
• scientific article; zbMATH DE number 7699425
• scientific article; zbMATH DE number 3930372
• The undecidability of the D_A-unification problem
• scientific article; zbMATH DE number 1405620
• The undecidability of simultaneous rigid E-unification

Cites work

• A decision algorithm for distributive unification
• A unification algorithm for second-order monadic terms
• Coding in the existential theory of concatenation
• Complexity of Makanin's algorithm
• Concatenation as a basis for arithmetic
• scientific article; zbMATH DE number 3924767 (Why is no real title available?)
• scientific article; zbMATH DE number 1189059 (Why is no real title available?)
• scientific article; zbMATH DE number 3462133 (Why is no real title available?)
• scientific article; zbMATH DE number 1222595 (Why is no real title available?)
• scientific article; zbMATH DE number 1114333 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3315195 (Why is no real title available?)
• Minimal and complete word unification
• On equality up-to constraints over finite trees, context unification, and one-step rewriting
• On the undecidability of second-order unification
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Satisfiability of word equations with constants is in PSPACE
• Simple second-order languages for which unification is undecidable
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• The undecidability of the second-order unification problem
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• Word unification and transformation of generalized equations

Cited in

(4)

• scientific article; zbMATH DE number 1722705 (Why is no real title available?)
• scientific article; zbMATH DE number 1189059 (Why is no real title available?)
• scientific article; zbMATH DE number 1222595 (Why is no real title available?)
• scientific article; zbMATH DE number 1341608 (Why is no real title available?)

This page was built for publication: \(\forall \exists^{5}\)-equational theory of context unification is undecidable

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