Monadic datalog over finite structures of bounded treewidth
From MaRDI portal
Publication:2946620
DOI10.1145/1838552.1838555zbMath1351.68110OpenAlexW2016416699WikidataQ59259568 ScholiaQ59259568MaRDI QIDQ2946620
Georg Gottlob, Fang Wei, Reinhard Pichler
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
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)
Related Items
Provenance Circuits for Trees and Treelike Instances, Containment of Monadic Datalog Programs via Bounded Clique-Width, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Courcelle's theorem -- a game-theoretic approach, Automata for the verification of monadic second-order graph properties, Unnamed Item, Practical algorithms for MSO model-checking on tree-decomposable graphs, D-FLAT: Declarative problem solving using tree decompositions and answer-set programming, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, Computations by fly-automata beyond monadic second-order logic, Evaluating Datalog via tree automata and cycluits, Structural tractability of enumerating CSP solutions
Uses Software