On the size of independent systems of equations in semigroups
From MaRDI portal
Publication:1351001
DOI10.1016/S0304-3975(96)00064-3zbMath0877.20039MaRDI QIDQ1351001
Wojciech Plandowski, Juhani Karhumäki
Publication date: 27 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
wordsfree monoidscompactness properties of free monoidscompactness properties of languagesindependent systems of equations
Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Related Items
Many aspects of defect theorems ⋮ Equations over the \(k\)-binomial monoids ⋮ ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS ⋮ A compactness property of the \(k\)-abelian monoids ⋮ Multiple constraints on three and four words ⋮ On systems of word equations over three unknowns with at most six occurrences of one of the unknowns ⋮ On maximal chains of systems of word equations ⋮ On the size of independent systems of equations in semigroups ⋮ Algebraic properties of word equations ⋮ Multiple factorizations of words and defect effect ⋮ Linear size test sets for certain commutative languages
Cites Work
- Systems of equations over a free monoid and Ehrenfeucht's conjecture
- The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
- A proof of Ehrenfeucht's conjecture
- Polynomial size test sets for context-free languages
- Rational sets in commutative monoids
- The descending chain condition on solution sets for systems of equations in groups
- Compactness of Systems of Equations in Semigroups
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item