The Monadic Theory of Toric Words
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913948937224192 |
|---|---|
| author | Berthé, Valérie Karimov, Toghrul Ouaknine, Joël Vahanwala, Mihir Worrell, James |
| author_facet | Berthé, Valérie Karimov, Toghrul Ouaknine, Joël Vahanwala, Mihir Worrell, James |
| contents | For which unary predicates $P_1, \ldots, P_m$ is the MSO theory of the structure $\langle \mathbb{N}; <, P_1, \ldots, P_m \rangle$ decidable? We survey the state of the art, leading us to investigate combinatorial properties of almost-periodic, morphic, and toric words. In doing so, we show that if each $P_i$ can be generated by a toric dynamical system of a certain kind, then the attendant MSO theory is decidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_04895 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Monadic Theory of Toric Words Berthé, Valérie Karimov, Toghrul Ouaknine, Joël Vahanwala, Mihir Worrell, James Logic in Computer Science For which unary predicates $P_1, \ldots, P_m$ is the MSO theory of the structure $\langle \mathbb{N}; <, P_1, \ldots, P_m \rangle$ decidable? We survey the state of the art, leading us to investigate combinatorial properties of almost-periodic, morphic, and toric words. In doing so, we show that if each $P_i$ can be generated by a toric dynamical system of a certain kind, then the attendant MSO theory is decidable. |
| title | The Monadic Theory of Toric Words |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2311.04895 |