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: | Berthé, V, Karimov, T, Nieuwveld, J, Ouaknine, J, Vahanwala, M, Worrell, J |
---|---|
Format: | Conference item |
Language: | English |
Published: |
2024
|
Similar Items
-
On the decidability of monadic first order logic in sequent calculus
by: Jean-Baptiste Joinet
Published: (2016-12-01) -
On the decidability of Metric Temporal Logic
by: Ouaknine, J, et al.
Published: (2005) -
Safety metric temporal logic is fully decidable
by: Ouaknine, J, et al.
Published: (2006) -
Decidability of a monadic subclass of modal logic S4
by: Stanislovas Norgėla
Published: (2002-12-01) -
ON THE DECIDABILITY AND COMPLEXITY OF METRIC TEMPORAL LOGIC OVER FINITE WORDS
by: Ouaknine, J, et al.
Published: (2007)