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: | , , , , , |
---|---|
Format: | Conference item |
Language: | English |
Published: |
2024
|