Decidable (Ac)counting with Parikh and Muller: Adding Presburger Arithmetic to Monadic Second-Order Logic over Tree-Interpretable Structures.
Luisa HerrmannVincent PethSebastian RudolphPublished in: CSL (2024)
Keyphrases
- monadic second order logic
- expressive power
- first order logic
- quantifier elimination
- presburger arithmetic
- regular expressions
- data complexity
- tree automata
- query language
- knowledge representation
- theorem proving
- databases
- inference rules
- finite state
- algebraic structure
- search algorithm
- pattern matching
- query evaluation
- database schema
- np complete