2026-07-25T03:04:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8483 2024-03-06T10:42:21Z ddc:004 open_access

Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid Köcher, Chris Partially Lossy Queues Transformation Monoid Rational Sets Recognizable Sets Aperiodic Sets MSO logic 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chris Köcher 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.45 urn:nbn:de:0030-drops-84839 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.45 eng https://creativecommons.org/licenses/by/3.0/legalcode