Linear size test sets for certain commutative languages

DOI10.1051/ITA:2001105MaRDI QIDQ3149085zbMATH OpenOpenAlexFDO

Authors 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, http://www.numdam.org/item?id=ITA_2001__35_5_453_0/, https://eudml.org/doc/222009

zbMATH Keywords

word equationsfinite commutative language

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Polynomial size test sets for commutative languages
• Parikh test sets for commutative languages
• Polynomial size test sets for context-free languages
• Polynomial size test sets for context-free languages
• Linearizing term rewriting systems using test sets
• Efficient constructions of test sets for regular and context-free languages
• scientific article; zbMATH DE number 176145
• Piecewise testable languages via combinatorics on words
• On languages piecewise testable in the strict sense

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1220049 (Why is no real title available?)
• scientific article; zbMATH DE number 1234888 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A proof of Ehrenfeucht's conjecture
• Checking sets, test sets, rich languages and commutatively closed languages
• Local and global cyclicity in free semigroups
• On binary equality sets and a solution to the test set conjecture in the binary case
• On the size of independent systems of equations in semigroups
• 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

Cited in

(6)

• scientific article; zbMATH DE number 1916668 (Why is no real title available?)
• Parikh test sets for commutative languages
• Periodicity forcing words
• Polynomial size test sets for commutative languages
• Polynomial size test sets for context-free languages
• scientific article; zbMATH DE number 176145 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3149085)