Monadic Datalog over finite structures of bounded treewidth

DOI10.1145/1838552.1838555MaRDI QIDQ2946620zbMATH OpenOpenAlexWikidataFDO

Authors Georg Gottlob, Reinhard Pichler, Fang Wei

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1838552.1838555

zbMATH Keywords

Datalogfixed-parameter tractabilitymonadic second-order logictree decompositiontreewidth

Mathematics Subject Classification ID

Logic in computer science (03B70) 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) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Counting and Enumeration Problems with Bounded Treewidth
• Fast Counting with Bounded Treewidth
• Containment of monadic Datalog programs via bounded clique-width
• A Practical Approach to Courcelle's Theorem
• Evaluating Datalog via tree automata and cycluits

Cited in

(17)

• Automata for the verification of monadic second-order graph properties
• Evaluating Datalog via tree automata and cycluits
• Structural tractability of enumerating CSP solutions
• Monadic Datalog Containment
• Extension complexity, MSO logic, and treewidth
• Provenance circuits for trees and treelike instances
• Containment of monadic Datalog programs via bounded clique-width
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• The monadic second-order logic evaluation problem on finite colored trees: a database-theoretic approach
• Courcelle's theorem -- a game-theoretic approach
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• D-FLAT: declarative problem solving using tree decompositions and answer-set programming
• Datalog programs and their persistency numbers
• Monadic Datalog and the expressive power of languages for web information extraction
• Computations by fly-automata beyond monadic second-order logic
• Structure-guided automated reasoning
• Enumeration of minimal hitting sets parameterized by treewidth

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Monadic Datalog over finite structures of bounded treewidth

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