A model-theoretic characterization of monadic second-order logic on infinite words
| Authors |
|
|---|---|
| Publication date | 03-2017 |
| Journal | Journal of Symbolic Logic |
| Volume | Issue number | 82 | 1 |
| Pages (from-to) | 62-76 |
| Number of pages | 15 |
| Organisations |
|
| Abstract |
Monadic second order logic and linear temporal logic are two logical formalisms that can be used to describe classes of infinite words, i.e., first-order models based on the natural numbers with order, successor, and finitely many unary predicate symbols.
Monadic second order logic over infinite words (S1S) can alternatively be described as a first-order logic interpreted in P(ω), the power set Boolean algebra of the natural numbers, equipped with modal operators for ‘initial’, ‘next’ and ‘future’ states. We prove that the first-order theory of this structure is the model companion of a class of algebras corresponding to a version of linear temporal logic (LTL) without until. The proof makes crucial use of two classical, non-trivial results from the literature, namely the completeness of LTL with respect to the natural numbers, and the correspondence between S1S-formulas and Büchi automata. |
| Document type | Article |
| Note | © The Association for Symbolic Logic 2017 |
| Language | English |
| Published at | https://doi.org/10.1017/jsl.2016.70 |
| Published at | https://arxiv.org/abs/1503.08936 |
| Downloads |
1503.08936.pd
(Accepted author manuscript)
modeltheoretic_characterization_of_monadic_second_order_logic_on_infinite_words
(Final published version)
|
| Permalink to this page | |