Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic.
Mikolaj BojanczykPublished in: CoRR (2020)
Keyphrases
- monadic second order logic
- expressive power
- tree automata
- bounded tree width
- data complexity
- first order logic
- query language
- structured objects
- regular expressions
- databases
- attributed graphs
- finite automata
- propositional logic
- np complete
- special case
- data model
- relational calculus
- tree nodes
- knowledge base
- artificial intelligence
- machine learning