Reachability and connectivity queries in constraint databases
From MaRDI portal
Publication:1394800
DOI10.1016/S0022-0000(02)00034-XzbMath1026.68036OpenAlexW2714643361MaRDI QIDQ1394800
Luc Segoufin, Martin Grohe, Michael Benedikt, Leonid O. Libkin
Publication date: 25 June 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(02)00034-x
Related Items (4)
On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases ⋮ Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals ⋮ Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals ⋮ \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets
Cites Work
- The complexity of elementary algebra and geometry
- Model theory.
- Topological queries in spatial databases
- Description of the connected components of a semialgebraic set in single exponential time
- Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
- Adding a path connectedness operator to \(FO+poly(linear)\)
- Querying spatial databases via topological invariants
- O-minimal hybrid systems.
- Relational queries over interpreted structures
- Definable Sets in Ordered Structures. III
- Languages that Capture Complexity Classes
- Relational expressive power of constraint query languages
- First-Order Queries on Finite Structures Over the Reals
- Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Reachability and connectivity queries in constraint databases
