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.
Mots-clés : Lossy queue, transformation monoid
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita/2018003/
[1] and , Verifying programs with unreliable channels. Inf. Comput. 127 (1996) 91–101. | DOI | MR | Zbl
[2] and , On communicating finite-state machines. J. ACM 30 (1983) 323–342. | DOI | MR | Zbl
[3] , , , , and , Word Processing in Groups. Jones and Barlett Publ., Boston, MA (1992). | MR | Zbl
[4] , and , Unreliable channels are easier to verify than perfect channels. Inf. Comput. 124 (1996) 20–31. | DOI | MR | Zbl
[5] and , Partial commutations and faithful rational transductions. Theor. Comput. Sci. 34 (1984) 241–254. | DOI | MR | Zbl
[6] and , Automates et commutations partielles. RAIRO:ITA 19 (1985) 21–32. | Numdam | MR | Zbl
[7] and , The ordinal recursive complexity of lossy channel systems, in LICS’08. IEEE Computer Society Press (2008) 205–216.
[8] , Combinatorics on Traces. Vol. 454 of Lecture Notes in Computer Science. Springer (1990). | MR | Zbl
[9] and , The Book of Traces. World Scientific (1995). | DOI | MR
[10] , and , On codings of traces, in STACS 95. Vol. 900 of Lecture Notes in Computer Science. Springer, Berlin, Heidelberg (1995) 385–396. | DOI | Zbl
[11] , Decidability of the termination problem for completely specified protocols. Distrib. Comput. 7 (1994) 129–135. | DOI
[12] and , Sequential grammars and automata with valences. Theor. Comput. Sci. 276 (2002) 377–405. | DOI | MR | Zbl
[13] , and , The monoid of queue actions. Semigroup Forum 95 (2017) 475–508. | DOI | MR | Zbl
[14] , and , The power of priority channel systems. Log. Methods Comput. Sci. 10 (2014). | MR | Zbl
[15] , Formal languages and groups as memory. Commun. Algebra 37 (2009) 193–208. | DOI | MR | Zbl
[16] , and , From automatic structures to automatic groups. Groups Geometry Dyn. 8 (2014) 157–198. | DOI | MR | Zbl
[17] and , Automatic presentations of structures, in Logic and Computational Complexity. Vol. 960 of Lecture Notes in Computer Science. Springer (1995) 367–392. | DOI | MR
[18] , Einbettungen in das Transformationsmonoid einer vergesslichen Warteschlange. Master’s Thesis, TU Ilmenau (2016).
[19] , Rational, recognizable, and aperiodic sets in the partially lossy queue monoid, in STACS’18. Vol. 96 of LIPIcs. Dagstuhl Publishing (2018) 45:1–45:14. | MR | Zbl
[20] and , The transformation monoid of a partially lossy queue, in CSR’17. Vol. 10304 of Lecture Notes in Computer Science. Springer (2017) 191–205. | DOI | MR | Zbl
[21] , Undecidability of the trace coding problem and some decidable cases. Theor. Comput. Sci. 310 (2004) 393–456. | DOI | MR | Zbl
[22] and , The trace monoids in the queue monoid and in the direct product of two free monoids, in DLT’16. Vol. 9840 of Lecture Notes in Computer Science. Springer (2016) 256–267. | DOI | MR | Zbl
[23] and , On verifying fair lossy channel systems, in MFCS’02. Vol. 2420 of Lecture Notes in Computer Science. Springer (2002) 543–555. | DOI | MR | Zbl
[24] , Concurrent program schemes and their interpretations. DAIMI Rep. Ser. 6 (1977).
[25] and , Rational subsets of polycyclic monoids and valence automata. Inf. Comput. 207 (2009) 1329–1339. | DOI | MR | Zbl
[26] , On a property of the class of n-colorable graphs. J. Comb. Theory (B) 16 (1974) 191–193. | DOI | MR | Zbl
Cité par Sources :
