RAIRO-Theor. Inf. Appl. 42, 525-537 (2008)
DOI: 10.1051/ita:2008011

Parikh test sets for commutative languages

Stepán Holub

Charles University, Faculty of Mathematics and Physics, Department of Algebra, Sokolovská 83, 175 86 Praha, Czech Republic; holub@karlin.mff.cuni.cz

Published online: 3 June 2008

Abstract
A set is a Parikh test set of L if c(T) is a test set of c(L). We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters.

Mathematics Subject Classification. 68R15

Key words: Combinatorics on words -- test sets -- commutative languages.


© EDP Sciences 2008