2026-07-21T19:26:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4485 2024-03-06T10:35:07Z ddc:004 open_access

On Boolean closed full trios and rational Kripke frames Lohrey, Markus Zetzsche, Georg rational transductions full trios arithmetical hierarchy Boolean operations A Boolean closed full trio is a class of languages that is closed under the Boolean operations (union, intersection, and complementation) and rational transductions. It is well-known that the regular languages constitute such a Boolean closed full trio. It is shown here that every such language class that contains any non-regular language already includes the whole arithmetical hierarchy (and even the one relative to this language). A consequence of this result is that aside from the regular languages, no full trio generated by one language is closed under complementation. Our construction also shows that there is a fixed rational Kripke frame such that assigning an arbitrary non-regular language to some variable allows the definition of any language from the arithmetical hierarchy in the corresponding Kripke structure using multimodal logic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Lohrey and Georg Zetzsche 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.530 urn:nbn:de:0030-drops-44853 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.530 eng https://creativecommons.org/licenses/by/3.0/legalcode