Comparing the succinctness of monadic query languages over finite trees

DOI10.1051/ITA:2004017MaRDI QIDQ4659888zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Nicole Schweikardt

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, http://www.numdam.org/item?id=ITA_2004__38_4_343_0/, https://eudml.org/doc/92747

zbMATH Keywords

finite automata on labelled finite treesfull modal mu-calculusmonadic datalogmonadic least fixed point logicmonadic second-order logicstratified monadic datalog

Mathematics Subject Classification ID

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

Recommendations

• Computer Science Logic
• The succinctness of first-order logic on linear orders
• Succinctness of Order-Invariant Logics on Depth-Bounded Structures
• Succinct definitions in the first order theory of graphs
• On the expressive power of monadic least fixed point logic

Cites work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• An n! lower bound on formula size
• Computer Science Logic
• First-order logic with two variables and unary temporal logic
• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 2080189 (Why is no real title available?)
• scientific article; zbMATH DE number 1500644 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Monadic Datalog and the expressive power of languages for web information extraction
• Monadic generalized spectra
• On logics with two variables
• Query automata over finite trees
• Reachability logic: an efficient fragment of transitive closure logic
• Structure and complexity of relational queries
• The complexity of first-order and monadic second-order logic revisited
• The succinctness of first-order logic on linear orders

Cited in

(6)

• Query-monotonic Turing reductions
• On the succinctness of some modal logics
• scientific article; zbMATH DE number 1501613 (Why is no real title available?)
• Computer Science Logic
• The succinctness of first-order logic on linear orders
• On the expressive power of monadic least fixed point logic

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4659888)