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...
| Main Authors: | , , , , , |
|---|---|
| Formato: | Conference item |
| Idioma: | English |
| Publicado em: |
Association for Computing Machinery
2024
|