On the decidability of monadic second-order logic with arithmetic predicates
We investigate the decidability of the monadic second-order (MSO) theory of the structure ❬N; <, P1, … , Pk❭, for various unary predicates P1, …, Pk ⊆ N. We focus in particular on ‘arithmetic’ predicates arising in the study of linear recurrence sequences, such as fixed-base powers Powk = {kn : n...
| Váldodahkkit: | , , , , , |
|---|---|
| Materiálatiipa: | Conference item |
| Giella: | English |
| Almmustuhtton: |
Association for Computing Machinery
2024
|