Querying temporal and spatial constraint networks in PTIME

DOI10.1016/S0004-3702(00)00055-2zbMath0952.68043OpenAlexW1596054597MaRDI QIDQ1589478

Spiros Skiadopoulos, Manolis Koubarakis

Publication date: 12 December 2000

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(00)00055-2

zbMATH Keywords

computational complexity constraint databases constraint networks temporal reasoning spatial reasoning tractable reasoning

Mathematics Subject Classification ID

Database theory (68P15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (4)

A Logic of East and West ⋮ Solving multi-granularity temporal constraint networks ⋮ PTIME parametric verification of safety properties for reasonable linear hybrid automata ⋮ On the consistency of cardinal direction constraints

Cites Work

Maintaining knowledge about temporal intervals
The complexity of querying indefinite data about linearly ordered domains
Foundations of a functional approach to knowledge representation
Network-based heuristics for constraint-satisfaction problems
On the representation and querying of sets of possible worlds
Temporal constraint networks
A canonical form for generalized linear constraints
From local to global consistency
The problem of incomplete information in relational databases
Reasoning about qualitative temporal information
Reasoning about partially ordered events
A unifying approach to temporal constraint reasoning
On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
Qualitative representation of spatial knowledge
On point-based temporal disjointness
The complexity of query evaluation in indefinite temporal constraint databases
From local to global consistency in temporal constraint networks
Efficient algorithms for qualitative reasoning about time
On the computational complexity of querying bounds on differences constraints
Incomplete Information in Relational Databases
Deciding Linear Inequalities by Computing Loop Residues
A Sufficient Condition for Backtrack-Free Search
Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
Reasoning about temporal relations
Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item

This page was built for publication: Querying temporal and spatial constraint networks in PTIME