A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Buerkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) this language cannot be solved by Datalog or by establishing local consistency.
19 pages, 1 figure

Keywords

Artificial Intelligence, Logic in Computer Science, I.2.4

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/226351

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0805.1473
 http://arxiv.org/abs/0805.1473

Collections

arXiv