On the size of independent systems of equations in semigroups

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)

zbMATH Keywords

wordsfree monoidscompactness properties of free monoidscompactness properties of languagesindependent systems of equations

Mathematics Subject Classification ID

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