On the Decidability of Monadic Second-Order Logic with Arithmetic Predicates.
Valérie BerthéToghrul KarimovJoris NieuwveldJoël OuaknineMihir VahanwalaJames WorrellPublished in: LICS (2024)
Keyphrases
- monadic second order logic
- quantifier free
- first order logic
- expressive power
- data complexity
- description logics
- query answering
- quantifier elimination
- tree automata
- regular expressions
- knowledge representation
- query language
- structured data
- user defined
- datalog programs
- rewrite systems
- incomplete information
- data sets
- data exchange
- set theory
- type checking
- optimal solution