On Expansions of Monadic Second-Order Logic with Dynamical Predicates
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915404795871232 |
|---|---|
| author | Nieuwveld, Joris Ouaknine, Joël |
| author_facet | Nieuwveld, Joris Ouaknine, Joël |
| contents | Expansions of the monadic second-order (MSO) theory of the structure $\langle \mathbb{N} ; < \rangle$ have been a fertile and active area of research ever since the publication of the seminal papers of Büchi and Elgot & Rabin on the subject in the 1960s. In the present paper, we establish decidability of the MSO theory of $\langle \mathbb{N} ; <,P \rangle$, where $P$ ranges over a large class of unary ''dynamical'' predicates, i.e., sets of non-negative values assumed by certain integer linear recurrence sequences. One of our key technical tools is the novel concept of (effective) prodisjunctivity, which we expect may also find independent applications further afield. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16581 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Expansions of Monadic Second-Order Logic with Dynamical Predicates Nieuwveld, Joris Ouaknine, Joël Logic in Computer Science Number Theory 11B37 11J86 11B40 11K16 F.4.0; G.2.0 Expansions of the monadic second-order (MSO) theory of the structure $\langle \mathbb{N} ; < \rangle$ have been a fertile and active area of research ever since the publication of the seminal papers of Büchi and Elgot & Rabin on the subject in the 1960s. In the present paper, we establish decidability of the MSO theory of $\langle \mathbb{N} ; <,P \rangle$, where $P$ ranges over a large class of unary ''dynamical'' predicates, i.e., sets of non-negative values assumed by certain integer linear recurrence sequences. One of our key technical tools is the novel concept of (effective) prodisjunctivity, which we expect may also find independent applications further afield. |
| title | On Expansions of Monadic Second-Order Logic with Dynamical Predicates |
| topic | Logic in Computer Science Number Theory 11B37 11J86 11B40 11K16 F.4.0; G.2.0 |
| url | https://arxiv.org/abs/2507.16581 |