On the decidability of monadic second-order logic with arithmetic predicates

DOI10.1145/3661814.3662119MaRDI QIDQ6970269zbMATH OpenFDO

Authors Valérie Berthé, Toghrul Karimov, Joël Ouaknine, Mihir Vahanwala, James Worrell

Publication date 18 June 2025

Full work available at URL https://doi.org/10.1145/3661814.3662119

zbMATH Keywords

cutting sequencesdecidabilitylinear recurrence sequencesmonadic second-order logictoric words

Mathematics Subject Classification ID

Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Recurrences (11B37) Formal languages and automata (68Q45)

Cites work

• Almost periodic sequences.
• An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II
• Automatic Sequences
• Complexity of sequences defined by billiard in the cube
• Complexity of trajectories in rectangular billiards
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• Decidability and undecidability of theories with a predicate for the primes
• Decidable Theories of the Ordering of Natural Numbers with Unary Predicates
• Definability in the monadic second-order theory of successor
• Directional complexity of the hypercubic billiard
• Distribution modulo one and Diophantine approximation
• Fourier-Motzkin elimination and its dual
• scientific article; zbMATH DE number 4071018 (Why is no real title available?)
• scientific article; zbMATH DE number 44695 (Why is no real title available?)
• scientific article; zbMATH DE number 1169378 (Why is no real title available?)
• scientific article; zbMATH DE number 1973372 (Why is no real title available?)
• scientific article; zbMATH DE number 1467843 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3232021 (Why is no real title available?)
• Kronecker's approximation theorem
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• Old and new results on normality
• ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• On the complexity of algebraic numbers. I: Expansions in integer bases
• On the decidability of monadic second-order logic with arithmetic predicates
• On the equation $y^m = P(x)$
• Restricted Set-Theoretical Definitions in Arithmetic
• Substitutions in dynamics, arithmetics and combinatorics
• The Complexity of theA B CProblem
• The monadic theory of morphic infinite words and generalizations

Cited in

(4)

• On the decidability of monadic second-order logic with arithmetic predicates
• On the expansion of monadic second-order logic with Cantor-Bendixson rank and order type predicates
• On expansions of monadic second-order logic with dynamical predicates
• Tree representations of infinite words and their logical properties

This page was built for publication: On the decidability of monadic second-order logic with arithmetic predicates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970269)