Linear size test sets for certain commutative languages

DOI10.1051/ita:2001105zbMath1010.68103OpenAlexW2121340062MaRDI QIDQ3149085

Juha Kortelainen, Štěpán Holub

Publication date: 24 September 2002

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2001__35_5_453_0

zbMATH Keywords

word equationsfinite commutative language

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (2)

Parikh test sets for commutative languages ⋮ Periodicity forcing words

Cites Work

• On binary equality sets and a solution to the test set conjecture in the binary case
• A proof of Ehrenfeucht's conjecture
• On the size of independent systems of equations in semigroups
• Checking sets, test sets, rich languages and commutatively closed languages
• On the system of word equations \(x_{0} u^{i}_{1} x_{1} u^{i}_{2} x_{2} u^{i}_{3} x_{3}=y_{0} v^{i}_{1} y_{1} v^{i}_{2} y_{2} v^{i}_{3} y_{3}\) \((i=0,1,2,\ldots)\) in a free monoid
• Polynomial size test sets for commutative languages
• Local and global cyclicity in free semigroups
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Linear size test sets for certain commutative languages