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

zbMATH Keywords

monadic second-order logic; monadic least fixed point logic; finite automata on labelled finite trees; full modal mu-calculus; monadic datalog; stratified monadic datalog

Mathematics Subject Classification ID

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

On the succinctness of some modal logics, On the expressive power of monadic least fixed point logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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