Containment of Monadic Datalog Programs via Bounded Clique-Width

DOI10.1007/978-3-662-47666-6_34zbMath1440.68054OpenAlexW2399482328MaRDI QIDQ3449494

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

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

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

Related Items (3)

Reasoning about integrity constraints for tree-structured data ⋮ Eliminating Recursion from Monadic Datalog Programs on Trees ⋮ Conjunctive query containment over trees using schema information

Uses Software

• XPath
• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Learnability and definability in trees and similar structures
• Recursive queries and context-free graph grammars
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Tree acceptors and some of their applications
• Monadic Datalog and Regular Tree Pattern Queries
• Monadic datalog over finite structures of bounded treewidth
• Optimizing Conjunctive Queries over Trees Using Schema Information
• Equivalence of Datalog queries is undecidable
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• Monadic datalog and the expressive power of languages for Web information extraction
• Generalized finite automata theory with an application to a decision problem of second-order logic
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Containment of Monadic Datalog Programs via Bounded Clique-Width