Parikh test sets for commutative languages
RAIRO - Theoretical Informatics and Applications (2008)
- Volume: 42, Issue: 3, page 525-537
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topHolub, Štěpán. "Parikh test sets for commutative languages." RAIRO - Theoretical Informatics and Applications 42.3 (2008): 525-537. <http://eudml.org/doc/250323>.
@article{Holub2008,
abstract = {
A set T ⊆ L 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.
},
author = {Holub, Štěpán},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Combinatorics on words; test sets; commutative languages.; test sets of quadratic size},
language = {eng},
month = {6},
number = {3},
pages = {525-537},
publisher = {EDP Sciences},
title = {Parikh test sets for commutative languages},
url = {http://eudml.org/doc/250323},
volume = {42},
year = {2008},
}
TY - JOUR
AU - Holub, Štěpán
TI - Parikh test sets for commutative languages
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/6//
PB - EDP Sciences
VL - 42
IS - 3
SP - 525
EP - 537
AB -
A set T ⊆ L 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.
LA - eng
KW - Combinatorics on words; test sets; commutative languages.; test sets of quadratic size
UR - http://eudml.org/doc/250323
ER -
References
top- Ismo Hakala and Juha Kortelainen, Polynomial size test sets for commutative languages. RAIRO-Theor. Inf. Appl.31 (1997) 291–304.
- Štěpán Holub and Juha Kortelainen, Linear size test sets for certain commutative languages. RAIRO-Theor. Inf. Appl.35 (2001) 453–475.
- Michel Latteux, Rational cones and commutations. In Machines, languages, and complexity (Smolenice, 1988). Lect. Notes Comput. Sci.381 (1989) 37–54.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.