On Boolean closed full trios and rational Kripke frames

Lohrey, Markus; Zetzsche, Georg

doi:10.4230/LIPIcs.STACS.2014.530

Document

On Boolean closed full trios and rational Kripke frames

Authors Markus Lohrey, Georg Zetzsche

Part of: Volume: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2014-03-05

PDF

File

PDF

LIPIcs.STACS.2014.530.pdf

Filesize: 0.54 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2014.530
URN: urn:nbn:de:0030-drops-44853

Subject Classification

Keywords

rational transductions
full trios
arithmetical hierarchy
Boolean operations

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Markus Lohrey

Georg Zetzsche

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail