Polynomial size test sets for commutative languages

DOI10.1051/ITA/1997310302911zbMath0889.68091OpenAlexW48822877MaRDI QIDQ4361579

Ismo Hakala, Juha Kortelainen

Publication date: 28 October 1997

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

Full work available at URL: https://eudml.org/doc/92563

zbMATH Keywords

commutative language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Parikh test sets for commutative languages ⋮ Linear size test sets for certain commutative languages

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient constructions of test sets for regular and context-free languages
• A proof of Ehrenfeucht's conjecture
• On the system of word equations \(x^ i_ 1 x^ i_ 2\dots x^ i_ m=y^ i_ 1 y^ i_ 2\dots y^ i_ n\) \((i=1,2,\dots)\) in a free monoid
• Checking sets, test sets, rich languages and commutatively closed languages
• Polynomial size test sets for context-free languages
• Test sets for context free languages and algebraic systems of equations over a free monoid
• Test sets for homomorphism equivalence on context free languages

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