Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.530
URN: urn:nbn:de:0030-drops-44853
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4485/
Lohrey, Markus ; Zetzsche, Georg
On Boolean closed full trios and rational Kripke frames
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{lohrey_et_al:LIPIcs:2014:4485,
author = {Markus Lohrey and Georg Zetzsche},
title = {{On Boolean closed full trios and rational Kripke frames}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {530--541},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-65-1},
ISSN = {1868-8969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4485},
URN = {urn:nbn:de:0030-drops-44853},
doi = {10.4230/LIPIcs.STACS.2014.530},
annote = {Keywords: rational transductions, full trios, arithmetical hierarchy, Boolean operations}
}
| Keywords: | rational transductions, full trios, arithmetical hierarchy, Boolean operations | |
| Seminar: | 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) | |
| Issue date: | 2014 | |
| Date of publication: | 05.03.2014 |
