Search: onr:"swepub:oai:DiVA.org:liu-4984" >
A Study in the Comp...
A Study in the Computational Complexity of Temporal Reasoning
-
- Broxvall, Mathias, 1976- (author)
- Linköpings universitet,TCSLAB - Laboratoriet för teoretisk datalogi,Tekniska högskolan
-
- Jonsson, Peter (thesis advisor)
- Linköpings universitet,TCSLAB - Laboratoriet för teoretisk datalogi,Tekniska högskolan
-
- Nilsson, Ulf (thesis advisor)
- Linköpings universitet,TCSLAB - Laboratoriet för teoretisk datalogi,Tekniska högskolan
-
show more...
-
- Haraldsson, Anders (thesis advisor)
- Linköpings universitet,EIT - Education in Information Technology Group,Tekniska högskolan
-
show less...
-
(creator_code:org_t)
- ISBN 9173734403
- Linköping : Linköping University Electronic Press, 2002
- English 21 s.
-
Series: Linköping Studies in Science and Technology. Dissertations, 0345-7524 ; 779
- Related links:
-
https://liu.diva-por... (primary) (Raw object)
-
show more...
-
https://urn.kb.se/re...
-
show less...
Abstract
Subject headings
Close
- Reasoning about temporal and spatial information is a common task in computer science, especially in the field of artificial intelligence. The topic of this thesis is the study of such reasoning from a computational perspective. We study a number of different qualitative point based formalisms for temporal reasoning and provide a complete classification of computational tractability for different time models. We also develop more general methods which can be used for proving tractability and intractability of other relational algebras. Even though most of the thesis pertains to qualitative reasoning the methods employed here can also be used for quantitative reasoning. For instance, we introduce a tractable and useful extension to the quantitative point based formalism STP. This extension gives the algebra an expressibility which subsumes the largest tractable fragment of the augmented interval algebra and has a faster and simpler algorithm for deciding consistency.The use of disjunctions in temporal formalisms is of great interest not only since disjunctions are a key element in different logics but also since the expressibility can be greatly enhanced in this way. If we allow arbitrary disjunctions, the problems under consideration typically become intractable and methods to identify tractable fragments of disjunctive formalisms are therefore useful. One such method is to use the independence property. We present an automatic method for deciding this property for many relational algebras. Furthermore, we show how this concept can not only be used for deciding tractability of sets of relations but also to demonstrate intractability of relations not having this property. Together with other methods for making total classifications of tractability this goes a long way towards easing the task of classifying and understanding relational algebras.The tractable fragments of relational algebras are sometimes not expressive enough to model real-world problems and a backtracking solver is needed. For these cases we identify another property among relations which can be used to aid general backtracking based solvers to finnd solutions faster.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- temporal and spatial information
- artificiell intelligens
- algebra
- tractable fragments
- temporal formalisms
- formalism STP
- Computer science
- Datavetenskap
Publication and Content Type
- vet (subject category)
- dok (subject category)
Find in a library
To the university's database