Combinatorics, Automata, and Number Theory (CANT) school-conference / Ecole-conférence de Combinatoire, d'Automates et de Théorie des Nombres (CANT)

Collection Combinatorics, Automata, and Number Theory (CANT) school-conference / Ecole-conférence de Combinatoire, d'Automates et de Théorie des Nombres (CANT)

Organisateur(s) Berthé, Valérie ; Rigo, Michel ; Stipulanti, Manon

Date(s) 29/09/2025 - 03/10/2025

URL associée https://conferences.cirm-math.fr/3355.html

3 5

On expansions of monadic second-order logic with power predicates - Lecture 2

Büchi famously established the decidability of the monadic secondorder (MSO) theory of the structure (N,<) in his 1962 seminal paper, in so doing bringing to light a profound connection between logic and automata theory. His work was quickly followed by further decidability results concerning expansions of (N,<) by various arithmetic predicates (such as powers of 2, powers of 3, perfect squares, factorial numbers, etc.), but only one at a time. These results, due to Elgot and Rabin, relied on the novel ""contraction method"", a form of effective profinite ultimate periodicity. Last year, exploiting and combining techniques from dynamical systems and number theory, Berthé et al. investigated the decidability (N,<) expanded with several power predicates simultaneously. This mini-course will review some of the key relevant classical techniques and results from the 1960s to today.

Informations sur la vidéo

Date de captation 30/09/2025
Date de publication 13/10/2025
Institut CIRM
Licence CC BY NC ND
Langue Anglais
Audience Chercheurs, Doctorants
Réalisateur(s) Guillaume Hennenfent
Format MP4

Données de citation

DOI 10.24350/CIRM.V.20392503
Citer cette vidéo Ouaknine, Joël (30/09/2025). On expansions of monadic second-order logic with power predicates - Lecture 2. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20392503
URL https://dx.doi.org/10.24350/CIRM.V.20392503

Domaine(s)

Bibliographie

BERTHÉ, Valérie, KARIMOV, Toghrul, NIEUWVELD, Joris, et al. The monadic theory of toric words. Theoretical Computer Science, 2025, vol. 1025, p. 114959. - https://doi.org/10.1016/j.tcs.2024.114959
BERTHÉ, Valérie, KARIMOV, Toghrul, NIEUWVELD, Joris, et al. On the decidability of monadic second-order logic with arithmetic predicates. In : Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science. 2024. p. 1-14. - https://doi.org/10.1007/978-3-031-97439-7_5
KARIMOV, Toghrul, LUCA, Florian, NIEUWVELD, Joris, et al. On the decidability of Presburger arithmetic expanded with powers. In : Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2025. p. 2755-2778. - https://doi.org/10.1137/1.9781611978322.89
BÈS, Alexis. A survey of arithmetical definability. A tribute to Maurice Boffa, 2002, p. 1-54. - https://hal.science/hal-00091580v1
ELGOT, Calvin C. et RABIN, Michael O. Decidability and undecidability of extensions of second (first) order theory of (generalized) successor1. The Journal of Symbolic Logic, 1966, vol. 31, no 2, p. 169-181. - https://doi.org/10.2307/2269808
BUCHI, J. Richard. On a decision method in restricted second order arithmetic. Proc. Internat. Congr. on Logic, Methodology and Philosophy of Science, 1960, 1960. - https://doi.org/10.2307/2271342