Comparing the succinctness of monadic query languages over finite trees

DOI10.1051/ita:2004017zbMath1067.03018OpenAlexW2136195897MaRDI 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 logicmonadic least fixed point logicfinite automata on labelled finite treesfull modal mu-calculusmonadic datalogstratified monadic datalog

Mathematics Subject Classification ID

Database theory (68P15) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13)

Related Items (2)

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

This page was built for publication: Comparing the succinctness of monadic query languages over finite trees