\(\forall \exists^{5}\)-equational theory of context unification is undecidable
From MaRDI portal
Publication:1607219
DOI10.1016/S0304-3975(01)00190-6zbMath1026.68077OpenAlexW2060473848MaRDI QIDQ1607219
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
undecidabilityequational theorysecond-order unificationword unificationcontext unification problemoperator algorithmsquantified fragments
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Simple second-order languages for which unification is undecidable
- A unification algorithm for second-order monadic terms
- The undecidability of the second-order unification problem
- A decision algorithm for distributive unification
- Word unification and transformation of generalized equations
- On the undecidability of second-order unification
- Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
- Minimal and complete word unification
- Satisfiability of word equations with constants is in PSPACE
- Coding in the existential theory of concatenation
- THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
- Complexity of Makanin's algorithm
- On equality up-to constraints over finite trees, context unification, and one-step rewriting
- Concatenation as a basis for arithmetic
This page was built for publication: \(\forall \exists^{5}\)-equational theory of context unification is undecidable
