THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

Free semigroups, generators and relations, word problems (20M05) Decidability of theories and sets of sentences (03B25) Algorithms in computer science (68W99)

Related Items (75)

Equations in the Partial Semigroup of Words with Overlapping Products ⋮ Generating languages by a derivation procedure for elementary formal systems ⋮ Decidability of bounded second order unification ⋮ String theories involving regular membership predicates: from practice to theory and back ⋮ On equations in free semigroups with certain constraints on their solutions. ⋮ Simplifying the signature in second-order unification ⋮ Some independence results for equational unification ⋮ A theorem on generalizations of proofs ⋮ A unification algorithm for second-order monadic terms ⋮ Elementariness of a finite set of words is co-NP-complete ⋮ Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup ⋮ Makanin's algorithm is not primitive recursive ⋮ Meeting of the Association for Symbolic Logic, Stanford, California, 1985 ⋮ Equational unification, word unification, and 2nd-order equational unification ⋮ Unnamed Item ⋮ Unification properties of commutative theories: A categorical treatment ⋮ Efficient solving of the word equations in one variable ⋮ ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS ⋮ Towards more efficient methods for solving regular-expression heavy string constraints ⋮ Variants and satisfiability in the infinitary unification wonderland ⋮ An analysis of Makanin's algorithm deciding solvability of equations in free groups ⋮ Complete equational unification based on an extension of the Knuth-Bendix completion procedure ⋮ Makanin's algorithm for word equations-two improvements and a generalization ⋮ Algebraic and logical aspects of unification ⋮ Towards parametrizing word equations ⋮ New techniques for proving the decidability of equivalence problem ⋮ Coding in the existential theory of concatenation ⋮ On ``simple undecidable fragments of the positive theory of a free semigroup ⋮ The complexity of verbal languages over groups ⋮ First-order concatenation theory with bounded quantifiers ⋮ Unnamed Item ⋮ Simple linear string constraints ⋮ Completion for unification ⋮ Chain-Free String Constraints ⋮ Decidability of bounded higher-order unification ⋮ Solving equations with sequence variables and sequence functions ⋮ Equations on partial words ⋮ Two-variable word equations ⋮ SOLVING DIFFERENCE EQUATIONS IN SEQUENCES: UNIVERSALITY AND UNDECIDABILITY ⋮ What Is Essential Unification? ⋮ Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general ⋮ Graph unification and matching ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ Complexity of unification problems with associative-commutative operators ⋮ Z3str2: an efficient solver for strings, regular expressions, and length constraints ⋮ Anti-patterns for rule-based languages ⋮ Codes and equations on trees ⋮ Towards Decidability of Conjugacy of Pairs and Triples ⋮ Unnamed Item ⋮ Learners based on transducers ⋮ Decidability of the unification problem for second-order languages with unary functional symbols ⋮ Theories of orders on the set of words ⋮ Regular expression order-sorted unification and matching ⋮ Graph Logics with Rational Relations ⋮ On equations and first-order theory of one-relator monoids ⋮ A.D. Taimanov and model theory in Kazakhstan ⋮ On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations ⋮ A decision algorithm for distributive unification ⋮ On equality up-to constraints over finite trees, context unification, and one-step rewriting ⋮ On the relation between context and sequence unification ⋮ Profinite topologies ⋮ ОБ УРАВНЕНИЯХ И НЕРАВЕНСТВАХ В СЛОВАХ И ДЛИНАХ ⋮ Pattern Unification with Sequence Variables and Flexible Arity Symbols ⋮ Context unification with one context variable ⋮ On PSPACE generation of a solution set of a word equation and its applications ⋮ A view of computability on term algebras ⋮ The non-parametrizability of the word equation \(xyz=zvx\): a short proof ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ On the undecidability of second-order unification ⋮ Solvability of context equations with two context variables is decidable ⋮ Simple second-order languages for which unification is undecidable ⋮ Word unification and transformation of generalized equations ⋮ \(\forall \exists^{5}\)-equational theory of context unification is undecidable ⋮ On Conjugacy of Languages ⋮ Symbolic computation in Maude: some tapas

This page was built for publication: THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP