THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
From MaRDI portal
Publication:4179180
DOI10.1070/SM1977v032n02ABEH002376zbMath0396.20037MaRDI QIDQ4179180
Publication date: 1977
Published in: Mathematics of the USSR-Sbornik (Search for Journal in Brave)
20M05: Free semigroups, generators and relations, word problems
03B25: Decidability of theories and sets of sentences
68W99: Algorithms in computer science
Related Items
Towards parametrizing word equations, Codes and equations on trees, Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general, Equations over finite sets of words and equivalence problems in automata theory, Complexity of unification problems with associative-commutative operators, The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids, Simple second-order languages for which unification is undecidable, New techniques for proving the decidability of equivalence problem, A view of computability on term algebras, A unification algorithm for second-order monadic terms, Makanin's algorithm is not primitive recursive, Equational unification, word unification, and 2nd-order equational unification, Completion for unification, A decision algorithm for distributive unification, Word unification and transformation of generalized equations, Solvability of context equations with two context variables is decidable, \(\forall \exists^{5}\)-equational theory of context unification is undecidable, On the undecidability of second-order unification, Decidability of bounded second order unification, Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup, Decidability of bounded higher-order unification, Solving equations with sequence variables and sequence functions, The non-parametrizability of the word equation \(xyz=zvx\): a short proof, A theorem on generalizations of proofs, Two-variable word equations, On Conjugacy of Languages, Theories of orders on the set of words, Elementariness of a finite set of words is co-NP-complete, ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS, Equations on partial words, Towards Decidability of Conjugacy of Pairs and Triples, On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations, Meeting of the Association for Symbolic Logic, Stanford, California, 1985, Coding in the existential theory of concatenation, Decidability of the unification problem for second-order languages with unary functional symbols
