Decidable (Ac)counting with Parikh and Muller: Adding Presburger Arithmetic to Monadic Second-Order Logic over Tree-Interpretable Structures.
Luisa HerrmannSebastian RudolphPublished in: CoRR (2023)
Keyphrases
- monadic second order logic
- expressive power
- first order logic
- quantifier elimination
- presburger arithmetic
- data complexity
- regular expressions
- tree automata
- query language
- transitive closure
- theorem proving
- algebraic structure
- incomplete information
- query answering
- inference rules
- pattern matching
- data model
- conjunctive queries
- artificial intelligence
- constraint databases
- search space