Issue |
RAIRO-Theor. Inf. Appl.
Volume 52, Number 1, January–March 2018
|
|
---|---|---|
Page(s) | 55 - 86 | |
DOI | https://doi.org/10.1051/ita/2018003 | |
Published online | 18 July 2018 |
The inclusion structure of partially lossy queue monoids and their trace submonoids★
Fachgebiet Automaten und Logik, Technische Universität Ilmenau,
98684
Ilmenau, Germany.
* Corresponding author: dietrich.kuske@tu-ilmenau.de
Received:
14
July
2017
Accepted:
20
March
2018
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.
Mathematics Subject Classification: 68Q70 / 20M35
Key words: Lossy queue / transformation monoid
© 2018, EDP Sciences
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.