[BibTeX] [RIS]
Branching Allen: Reasoning with intervals in branching time
Type of publication: Inproceedings
Citation: RagniWoelfl-a:04-branching
Booktitle: Spatial Cognition IV: Reasoning, Action, Interaction, International Conference Spatial Cognition 2004, Frauenchiemsee, Germany, October 11-13, 2004, Revised & Selected Papers
Series: Lecture Notes in Computer Science
Volume: 3343
Year: 2004
Pages: 323-343
Publisher: Springer; Berlin; http://www.springer.de
ISBN: 3-540-25048-4
URL: http://springerlink.metapress....
Abstract: Allen's interval calculus is one of the most prominent formalisms in the domain of qualitative spatial and temporal reasoning. Applications of this calculus, however, are restricted to domains that deal with linear flows of time. But how the fundamental ideas of Allen's calculus can be extended to other, weaker structures than linear orders has gained only little attention in the literature. In this paper we will investigate intervals in branching flows of time, which are of special interest for temporal reasoning, since they allow for representing indeterministic aspects of systems, scenarios, planning tasks, etc. As well, branching time models, i. e., treelike non-linear structures, do have interesting applications in the field of spatial reasoning, for example, for modeling traffic networks. In a first step we discuss interval relations for branching time, thereby comprising various sources from the literature. Then, in a second step, we present some new complexity results concerning constraint satisfaction problems of interval relations in branching time.
Userfields: bdsk-url-1={http://springerlink.metapress.com/openurl.asp?genre=article%7B&%7Dissn=0302-9743%7B&%7Dvolume=3343%7B&%7Dspage=323}, project={R2-BackSpace}, status={Reviewed},
Authors Ragni, Marco
Wölfl, Stefan
Editors Freksa, Christian
Knauff, Markus
Krieg-Brückner, Bernd
Nebel, Bernhard
Barkowsky, Thomas