A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning
| dc.creator | Bodirsky, Manuel | |
| dc.creator | Kara, Jan | |
| dc.date | 2008-05-10 | |
| dc.date | 2009-04-11 | |
| dc.date.accessioned | 2026-07-07T13:02:03Z | |
| dc.date.available | 2026-07-07T13:02:03Z | |
| dc.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. | |
| dc.description | 19 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/0805.1473 | |
| dc.identifier | http://arxiv.org/abs/0805.1473 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/226351 | |
| dc.subject | Artificial Intelligence | |
| dc.subject | Logic in Computer Science | |
| dc.subject | I.2.4 | |
| dc.title | A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning | |
| dc.type | text |