Equations in free semigroups

zbMath0326.02032MaRDI QIDQ1225612

Ju. I. Hmelevskii

Publication date: 1976

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Word problems, etc. in computability and recursion theory (03D40) Applications of computability and recursion theory (03D80) Representation problems (11D85) Diophantine equations (11D99)

Related Items (30)

Systems of word equations, polynomials and linear algebra: a new approach ⋮ Word equations in the context of string solving ⋮ The expressibility of languages and relations by word equations ⋮ The origins of combinatorics on words ⋮ Unnamed Item ⋮ Word equations of paths ⋮ Implementation of Makanin's Algorithm ⋮ Systems of equations over a finite set of words and automata theory ⋮ Equations in free semigroups with involution and their relation to equations in free groups. ⋮ On the Solution Sets of Entire Systems of Word Equations ⋮ Makanin's algorithm for word equations-two improvements and a generalization ⋮ Towards parametrizing word equations ⋮ Coding in the existential theory of concatenation ⋮ An Analysis and a Reproof of Hmelevskii’s Theorem ⋮ Equations on partial words ⋮ Two-variable word equations ⋮ Multiple constraints on three and four words ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ Solving word equations ⋮ On systems of word equations over three unknowns with at most six occurrences of one of the unknowns ⋮ Solving word equations ⋮ On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations ⋮ ОБ УРАВНЕНИЯХ И НЕРАВЕНСТВАХ В СЛОВАХ И ДЛИНАХ ⋮ Explicit solutions of certain orientable quadratic equations in free groups ⋮ On PSPACE generation of a solution set of a word equation and its applications ⋮ The non-parametrizability of the word equation \(xyz=zvx\): a short proof ⋮ Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ Solvability of context equations with two context variables is decidable ⋮ Word unification and transformation of generalized equations

This page was built for publication: Equations in free semigroups