LIPIcs.STACS.2014.530.pdf
- Filesize: 0.54 MB
- 12 pages
Document
On Boolean closed full trios and rational Kripke frames
Authors
-
Part of:
Volume:
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2014-03-05
Cite AsGet BibTex
Markus Lohrey and Georg Zetzsche. On Boolean closed full trios and rational Kripke frames. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 530-541, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.530
https://doi.org/10.4230/LIPIcs.STACS.2014.530
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.
Keywords
- rational transductions
- full trios
- arithmetical hierarchy
- Boolean operations
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads