Evaluating Datalog via tree automata and cycluits
From MaRDI portal
Publication:2322722
DOI10.1007/s00224-018-9901-2zbMath1430.68078arXiv1808.04663OpenAlexW3104480332WikidataQ128626663 ScholiaQ128626663MaRDI QIDQ2322722
Mikaël Monet, Pierre Bourhis, Pierre Senellart, Antoine Amarilli
Publication date: 5 September 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.04663
Database theory (68P15) Formal languages and automata (68Q45) Parameterized complexity, tractability and kernelization (68Q27)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Cyclic Boolean circuits
- Finding and counting given length cycles
- Hypertree decompositions and tractable queries
- Graph minors. III. Planar tree-width
- Treewidth computations. I: Upper bounds
- Decomposition by clique separators
- Simplicial decompositions of graphs: A survey of applications
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- An introduction to clique minimal separator decomposition
- Guarded fixed point logics and the monadic theory of countable trees.
- Optimal decomposition by clique separators
- Parametrized complexity theory.
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The semijoin algebra and the guarded fragment
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A lattice-theoretical fixpoint theorem and its applications
- Rewriting Guarded Negation Queries
- Monadic datalog over finite structures of bounded treewidth
- Games and Model Checking for Guarded Logics
- Degrees of acyclicity for hypergraphs and relational database schemes
- Monadic Datalog Containment
- Combined Tractability of Query Evaluation via Tree Automata and Cycluits
- The implication problem for functional and inclusion dependencies
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Provenance Circuits for Trees and Treelike Instances
- Query evaluation via tree-decompositions
- Analysis of cyclic combinational circuits
- Constraint solving via fractional edge covers
- The Implication Problem for Functional and Inclusion Dependencies is Undecidable
- Graph minors. II. Algorithmic aspects of tree-width
- Incomplete Information in Relational Databases
- Two-Way Tree Automata Solving Pushdown Games
- Effective interpolation and preservation in guarded logics
- A Step Up in Expressiveness of Decidable Fixpoint Logics
- Finding Regular Simple Paths in Graph Databases
- Monadic Datalog, Tree Validity, and Limited Access Containment
- An Indexing Framework for Queries on Probabilistic Graphs
- State-complexity of finite-state devices, state compressibility and incompressibility
- Programming Techniques: Regular expression search algorithm
- Depth-First Search and Linear Graph Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Datalog LITE
- Guarded Negation
This page was built for publication: Evaluating Datalog via tree automata and cycluits
