Can I read Querying temporal and spatial constraint networks in PTIME☆☆A preliminary version of this paper appeared in the proceedings of AAAI-99. A different version of this paper (aimed at a database audience) appeared in the proceedings of the workshop STDBM99. on EtoBox?

Querying temporal and spatial constraint networks in PTIME☆☆A preliminary version of this paper appeared in the proceedings of AAAI-99. A different version of this paper (aimed at a database audience) appeared in the proceedings of the workshop STDBM99. by Manolis Koubarakis; Spiros Skiadopoulos is a Computer Science article available to read on EtoBox.

What is Querying temporal and spatial constraint networks in PTIME☆☆A preliminary version of this paper appeared in the proceedings of AAAI-99. A different version of this paper (aimed at a database audience) appeared in the proceedings of the workshop STDBM99. about?

We start with the assumption that temporal and spatial knowledge usually captured by constraint networks can be represented and queried more effectively by using the scheme of indefinite constraint databases. Because query evaluation in this scheme is in general a hard computational problem, we seek tractable instances of query evaluation. We assume that we have a class of constraints C with some reasonable computational and closure properties (the computational properties of interest are that the satisfiability problem and an appropriate version of the variable elimination problem for C should be solvable in PTIME). Under this assumption, we exhibit general classes of indefinite constraint databases and first-order modal queries for which query evaluation can be done with PTIME data complexity. We then search for tractable instances of C among the subclasses of Horn disjunctive linear constraints over the rationals. From previous research we know that the satisfiability problem for Horn disjunctive linear constraints is solvable in PTIME, but not the variable elimination problem. Thus we try to discover subclasses of Horn disjunctive linear constraints with tractable variable elim

Who reads Querying temporal and spatial constraint networks in PTIME☆☆A preliminary version of this paper appeared in the proceedings of AAAI-99. A different version of this paper (aimed at a database audience) appeared in the proceedings of the workshop STDBM99.?

Author

Manolis Koubarakis; Spiros Skiadopoulos

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0004-3702)

Published

2000

Language

EN

Field

Computer Science (Physical Sciences)