Voir la notice de l'article provenant de la source Numdam
We model the behavior of a lossy fifo-queue as a monoid of transformations that are induced by sequences of writing and reading. To have a common model for reliable and lossy queues, we split the alphabet of the queue into two parts: the forgettable letters and the letters that are transmitted reliably. We describe this monoid by means of a confluent and terminating semi-Thue system and then study some of the monoid’s algebraic properties. In particular, we characterize completely when one such monoid can be embedded into another as well as which trace monoids occur as submonoids. Surprisingly, these are precisely those trace monoids that embed into the direct product of two free monoids – which gives a partial answer to a question raised by Diekert et al. at STACS 1995.
Keywords: Lossy queue, transformation monoid
Köcher, Chris 1 ; Kuske, Dietrich 1 ; Prianychnykova, Olena 1
@article{ITA_2018__52_1_55_0,
author = {K\"ocher, Chris and Kuske, Dietrich and Prianychnykova, Olena},
title = {The inclusion structure of partially lossy queue monoids and their trace submonoids},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {55--86},
publisher = {EDP-Sciences},
volume = {52},
number = {1},
year = {2018},
doi = {10.1051/ita/2018003},
mrnumber = {3843155},
zbl = {1401.68080},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2018003/}
}
TY - JOUR AU - Köcher, Chris AU - Kuske, Dietrich AU - Prianychnykova, Olena TI - The inclusion structure of partially lossy queue monoids and their trace submonoids JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 55 EP - 86 VL - 52 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2018003/ DO - 10.1051/ita/2018003 LA - en ID - ITA_2018__52_1_55_0 ER -
%0 Journal Article %A Köcher, Chris %A Kuske, Dietrich %A Prianychnykova, Olena %T The inclusion structure of partially lossy queue monoids and their trace submonoids %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 55-86 %V 52 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2018003/ %R 10.1051/ita/2018003 %G en %F ITA_2018__52_1_55_0
Köcher, Chris; Kuske, Dietrich; Prianychnykova, Olena. The inclusion structure of partially lossy queue monoids and their trace submonoids. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 1, pp. 55-86. doi: 10.1051/ita/2018003
Cité par Sources :