arXiv Open Access 2008

A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning

Manuel Bodirsky Jan Kara

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.AI cs.LO

Penulis (2)

Manuel Bodirsky

Jan Kara

Format Sitasi

APA MLA BibTeX

Bodirsky, M., Kara, J. (2008). A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning. https://arxiv.org/abs/0805.1473

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2008
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓