Querying Temporal Constraint Networks in PTIME

Westart with the assumption that temporal knowledgeusually captured by constraint networks can be represented and queried more effectively by using the schemeof indefinite constraint databases proposed by Koubarakis. Althoughquery evaluation in this scheme is in general a hard computational problem, we demonstrate that there are several interesting cases where query evaluation can be done in PTIME. Thesetractability results are original and subsumeprevious results by van Beck, Brusoni, Console andTerenziani.

Authors

• Manolis Koubarakis National and Kapodistrian University of Athens
• University of Athens
• Spiros Skiadopoulos
• National Technical University of Athens

Keywords

No keywords are indexed for this paper.