scientific article; zbMATH DE number 3577484

zbMath0371.20047MaRDI QIDQ4146913

Publication date: 1977

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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

Related Items (65)

An SMT solver for regular expressions and linear arithmetic over string length ⋮ Systems of word equations, polynomials and linear algebra: a new approach ⋮ Equations in free topoboolean algebra ⋮ On equations in free semigroups with certain constraints on their solutions. ⋮ The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem ⋮ On some algorithmic problems for groups and monoids ⋮ An algorithm for distributive unification ⋮ On the studies of Gennadii Semënovich Makanin on algorithmic questions of the theory of groups and semigroups ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Equations in virtually abelian groups: Languages and growth ⋮ Word equations in the context of string solving ⋮ Monadic simultaneous rigid E-unification and related problems ⋮ Solving trace equations using lexicographical normal forms ⋮ The word matching problem is undecidable for finite special string-rewriting systems that are confluent ⋮ Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup ⋮ Equations over free inverse monoids with idempotent variables ⋮ More Than 1700 Years of Word Equations ⋮ Implementation of Makanin's Algorithm ⋮ EDT0L solutions to equations in group extensions ⋮ Equations in free semigroups with involution and their relation to equations in free groups. ⋮ Equationally defined classes of semigroups ⋮ A decision procedure for string constraints with string/integer conversion and flat regular constraints ⋮ A solver for arrays with concatenation ⋮ On equations in free monoids and semigroups with restrictions on solutions ⋮ The Diophantine problem in some metabelian groups ⋮ A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings ⋮ Decision procedures for term algebras with integer constraints ⋮ Equations in Algebras ⋮ Word-mappings of level 2 ⋮ Solving word equations modulo partial commutations ⋮ Monadic simultaneous rigid \(E\)-unification ⋮ An Analysis and a Reproof of Hmelevskii’s Theorem ⋮ On systems of equations over free products of groups. ⋮ Proving convergence of self-stabilizing systems using first-order rewriting and regular languages ⋮ Generalizing proofs in monadic languages (with a postscript by Georg Kreisel). ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Finite degrees of ambiguity in pattern languages ⋮ Word equations in non-deterministic linear space ⋮ T-string unification: Unifying prefixes in non-classical proof methods ⋮ An efficient SMT solver for string constraints ⋮ On word equations in one variable ⋮ On the complexity of decidable cases of the commutation problem of languages ⋮ Solving word equations ⋮ On systems of word equations over three unknowns with at most six occurrences of one of the unknowns ⋮ On the Complexity of Solving Restricted Word Equations ⋮ Solving word equations ⋮ On maximal chains of systems of word equations ⋮ On the Solvability Problem for Restricted Classes of Word Equations ⋮ Definability in the Infix Order on Words ⋮ On systems of equations over free partially commutative groups ⋮ Identity Problems, Solvability of Equations and Unification in Varieties of Semigroups Related to Varieties of Groups ⋮ On the deficit of a finite set of words ⋮ Equations in groups ⋮ Unification problem in equational theories ⋮ Decidability and complexity of simultaneous rigid E-unification with one variable and related results ⋮ The hardness of solving simple word equations ⋮ Checking sets, test sets, rich languages and commutatively closed languages ⋮ Systems of equations over a free monoid and Ehrenfeucht's conjecture ⋮ Undecidability of a simple fragment of a positive theory with a single constant for a free semigroup of rank two ⋮ On positive and critical theories of some classes of rings ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ A decision procedure for string to code point conversion ⋮ Logic with equality: Partisan corroboration and shifted pairing ⋮ Positive theories of free monoids ⋮ One-variable word equations in linear time

This page was built for publication: