Voir la notice de l'article provenant de la source Numdam
A shuffle ideal is a language which is a finite union of languages of the form where is a finite alphabet and the ’s are letters. We show how to represent shuffle ideals by special automata and how to compute these representations. We also give a temporal logic characterization of shuffle ideals and we study its expressive power over infinite words. We characterize the complexity of deciding whether a language is a shuffle ideal and we give a new quadratic algorithm for this problem. Finally we also present a characterization by subwords of the minimal automaton of a shuffle ideal and study the complexity of basic operations on shuffle ideals.
@article{ITA_2002__36_4_359_0,
author = {H\'eam, Pierre-Cyrille},
title = {On shuffle ideals},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {359--384},
publisher = {EDP-Sciences},
volume = {36},
number = {4},
year = {2002},
doi = {10.1051/ita:2003002},
mrnumber = {1965422},
zbl = {1034.68056},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2003002/}
}
TY - JOUR AU - Héam, Pierre-Cyrille TI - On shuffle ideals JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2002 SP - 359 EP - 384 VL - 36 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2003002/ DO - 10.1051/ita:2003002 LA - en ID - ITA_2002__36_4_359_0 ER -
%0 Journal Article %A Héam, Pierre-Cyrille %T On shuffle ideals %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2002 %P 359-384 %V 36 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2003002/ %R 10.1051/ita:2003002 %G en %F ITA_2002__36_4_359_0
Héam, Pierre-Cyrille. On shuffle ideals. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 4, pp. 359-384. doi: 10.1051/ita:2003002
Cité par Sources :