Comparing the succinctness of monadic query languages over finite trees
DOI10.1051/ita:2004017zbMath1067.03018MaRDI QIDQ4659888
Nicole Schweikardt, Martin Grohe
Publication date: 21 March 2005
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=ITA_2004__38_4_343_0
monadic second-order logic; monadic least fixed point logic; finite automata on labelled finite trees; full modal mu-calculus; monadic datalog; stratified monadic datalog
68P15: Database theory
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
03B25: Decidability of theories and sets of sentences
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03C13: Model theory of finite structures
Related Items
Cites Work
- Query automata over finite trees
- Structure and complexity of relational queries
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- The complexity of first-order and monadic second-order logic revisited
- On logics with two variables
- First-order logic with two variables and unary temporal logic
- Monadic generalized spectra
- Reachability logic: an efficient fragment of transitive closure logic
- An n ! lower bound on formula size
- Computer Science Logic
- The succinctness of first-order logic on linear orders
- Monadic datalog and the expressive power of languages for Web information extraction
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item