Rational, recognizable, and aperiodic sets in the partially lossy queue monoid

Köcher, Chris GND

Partially lossy queue monoids (or plq monoids) model the behavior of queues that can forget arbitrary parts of their content. While many decision problems on recognizable subsets in the plq monoid are decidable, most of them are undecidable if the sets are rational. In particular, in this monoid the classes of rational and recognizable subsets do not coincide. By restricting multiplication and iteration in the construction of rational sets and by allowing complementation we obtain precisely the class of recognizable sets. From these special rational expressions we can obtain an MSO logic describing the recognizable subsets. Moreover, we provide similar results for the class of aperiodic subsets in the plq monoid.

Cite

Citation style:
Rational, recognizable, and aperiodic sets in the partially lossy queue monoid, 2018. . 35th Symposium on Theoretical Aspects of Computer Science. https://doi.org/10.4230/LIPIcs.STACS.2018.45
Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:

Export