Containment of monadic Datalog programs via bounded clique-width

DOI10.1007/978-3-662-47666-6_34MaRDI QIDQ3449494zbMATH OpenOpenAlexFDO

Authors Mikołaj Bojańczyk, Filip Murlak, Adam Witkowski

Publication date 4 November 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-47666-6_34

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Logic programming (68N17) Database theory (68P15) Logic in computer science (03B70)

Recommendations

• Monadic datalog and regular tree pattern queries
• Monadic datalog and regular tree pattern queries
• Monadic Datalog, tree validity, and limited access containment
• Monadic Datalog Containment
• Monadic Datalog over finite structures of bounded treewidth

Cites work

• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Equivalence of Datalog queries is undecidable
• Finding Branch-Decompositions and Rank-Decompositions
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Learnability and definability in trees and similar structures
• Linear time solvable optimization problems on graphs of bounded clique-width
• Monadic Datalog and the expressive power of languages for web information extraction
• Monadic Datalog over finite structures of bounded treewidth
• Monadic datalog and regular tree pattern queries
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• Optimizing Conjunctive Queries over Trees Using Schema Information
• Recursive queries and context-free graph grammars
• Tree acceptors and some of their applications
• Upper bounds to the clique width of graphs

Cited in

(9)

• Monadic datalog and regular tree pattern queries
• Eliminating recursion from monadic datalog programs on trees
• Monadic Datalog Containment
• Monadic Datalog over finite structures of bounded treewidth
• Reasoning about integrity constraints for tree-structured data
• Monadic datalog and regular tree pattern queries
• Conjunctive query containment over trees using schema information
• On Bounded Database Schemes and Bounded Horn-Clause Programs
• Monadic Datalog, tree validity, and limited access containment

Describes a project that uses

Uses Software

• Datalog
• XPath

This page was built for publication: Containment of monadic Datalog programs via bounded clique-width

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