Journal article
The monadic theory of toric words
- Abstract:
- For which unary predicates P1,,…,Pm is the MSO theory of the structure ⟨N; ⟨,P1,…,Pm⟩ 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 Pi can be generated by a toric dynamical system of a certain kind, then the attendant MSO theory is decidable. We give various applications of toric words, including the recent result of [1] that the MSO theory of ⟨N; ⟨, {2n : n ∈ N}, {3n : n ∈ N}⟩ is decidable.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 1.2MB, Terms of use)
-
- Publisher copy:
- 10.1016/j.tcs.2024.114959
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- https://ror.org/0439y7842
- Grant:
- EP/X033813/1
- Publisher:
- Elsevier
- Journal:
- Theoretical Computer Science More from this journal
- Volume:
- 1025
- Article number:
- 114959
- Publication date:
- 2024-11-14
- Acceptance date:
- 2024-11-07
- DOI:
- EISSN:
-
1879-2294
- ISSN:
-
0304-3975
- Language:
-
English
- Keywords:
- Pubs id:
-
2069400
- Local pid:
-
pubs:2069400
- Deposit date:
-
2025-02-04
Terms of use
- Copyright holder:
- Berthé et al.
- Copyright date:
- 2024
- Rights statement:
- © 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record