Arrow Research search

Author name cluster

Thomas Drakengren

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
1 author row

Possible papers

10

AIJ Journal 1999 Journal Article

Computational complexity of relating time points with intervals

  • Peter Jonsson
  • Thomas Drakengren
  • Christer Bäckström

Several algebras have been proposed for reasoning about qualitative constraints over the time line. One of these algebras is Vilain's point–interval algebra, which can relate time points with time intervals. Apart from being a stand-alone qualitative algebra, it is also used as a subalgebra in Meiri's approach to temporal reasoning, which combines reasoning about metric and qualitative temporal constraints over both time points and time intervals. While the satisfiability problem for the full point–interval algebra is known to be NP-complete, not much is known about its 4294967296 subclasses. This article completely determines the computational complexity of these subclasses and it identifies all of the maximal tractable subalgebras—five in total.

Details DOI

IJCAI Conference 1999 Conference Paper

Expressive Reasoning about Action in Nondeterministic Polynomial Time

  • Thomas Drakengren
  • Marcus Bjaeland

The rapid development of efficient heuristics for deciding satisfiability for propositional logic motivates thorough investigations of the usability of NP-complete problems in general. In this paper we introduce a logic of action and change which is expressive in the sense that it can represent most propositional benchmark examples in the literature, and some new examples involving parallel composition of actions, and actions that may or may not be executed. We prove that satisfiability of a scenario in this logic is NP-complete, and that it subsumes an NP-complete logic (which in turn includes a nontrivial polynomial-time fragment) previously introduced by Drakengren and Bjareland.

PDF

AIJ Journal 1999 Journal Article

Reasoning about action in polynomial time

  • Thomas Drakengren
  • Marcus Bjäreland

Although many formalisms for reasoning about action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this article are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for reasoning about action, and NP-completeness results for the unrestricted problems. Many interesting reasoning problems can be modelled, involving nondeterminism, concurrency and memory of actions. The reasoning process is proved to be sound and complete.

Details DOI

AIJ Journal 1998 Journal Article

A complete classification of tractability in Allen's algebra relative to subsets of basic relations

  • Thomas Drakengren
  • Peter Jonsson

We characterise the set of subalgebras of Allen's algebra which have a tractable satisfiability problem, and in addition contain certain basic relations. The conclusion is that no tractable subalgebra dial is not known in the literature can contain more than the three basic relations (≡), (b) and (b⪰), where b ϵ d, o, s, f. This means that concerning algebras for specifying complete knowledge about temporal information, there is no hope of finding yet unknown classes with much expressivity. We also classify completely some cases where we cannot even express complete information (but close to complete), showing that there are exactly two maximal tractable algebras containing the relation (≺ ≻), exactly two containing the relation (≺ ≻ m m≤), and exactly three containing the relation (≺ m). The algebras containing (≺ ≻) can express the notion of sequentiality; thus we have a complete characterization of tractable inference using that notion.

Details DOI

IJCAI Conference 1997 Conference Paper

Reasoning about Action in Polynomial Time

  • Thomas Drakengren
  • Marcus Bjdreland

Although many formalisms for reasoning about action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this paper are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for reasoning about action, and NP-completeness results for the unrestricted problems. Many interesting reasoning problems can be modelled, involving nondeterminism, concurrency and memory of actions. The reasoning process is proved to be sound and complete.

PDF

IJCAI Conference 1997 Conference Paper

Towards a Complete Classification of Tractability in Allen's Algebra

  • Thomas Drakengren
  • Peter Jonsson

We characterise the set of subalgebras of Allen's algebra which have a tractable satisfiability problem, and in addition contain certain basic relations. The conclusion is that no tractable subalgebra that is not known in the literature can contain more than the three basic relations This means that concerning algebras for specifying complete knowledge about temporal informa­ tion, there is no hope of finding yet unknown classes with much expressivity. Furthermore, we show that there are exactly two maximal tractable algebras which contain the relation Both of these algebras can express the notion of sequentially; thus we have a com­ plete characterisation of tractable inference us­ ing that notion.

PDF

AIJ Journal 1997 Journal Article

Twenty-one large tractable subclasses of Allen's algebra

  • Thomas Drakengren
  • Peter Jonsson

This paper continues Nebel and Bürckert's investigation of Allen's interval algebra by presenting nine more maximal tractable subclasses of the algebra (provided that P ≠ NP), in addition to their previously reported ORD-Horn subclass. Furthermore, twelve tractable subclasses are identified, whose maximality is not decided. Four of them can express the notion of sequentiality between intervals, which is not possible in the ORD-Horn algebra. All of the algebras are considerably larger than the ORD-Horn subclass. The satisfiability algorithm, which is common for all the algebras, is shown to be linear. Furthermore, the path consistency algorithm is shown to decide satisfiability of interval networks using any of the algebras.

Details DOI

AAAI Conference 1996 Conference Paper

Maximal Tractable Subclasses of Allen’s Interval Algebra: Preliminary Report

  • Thomas Drakengren

This paper continues Nebel and Biirckert’ s investigation of Allen’ s interval algebra by presenting nine more maximal tractable subclasses of the algebra (provided that P # NP), in addition to their previously reported ORD-HO~PEsubclass. Furthermore, twelve tractable subclasses are identified, whose maximality is not decided. Four of these can express the notion of sequentiality between intervals, which is not possible in the ORD-Horn algebra. The satisfiability algorithm, which is common for all the algebras, is shown to be linear.

PDF Details

TCS Journal 1996 Journal Article

Uniqueness of Scott's reflexive domain in Pω

  • Thomas Drakengren

The extensional model in Pω for the pure λ-calculus, found by Scott in 1976, does not seem to have been much used, although it is more concrete than the D ∞ models found by Scott in 1969. The main results presented in this paper are that the model in Pω is actually isomorphic to one of the simplest D ∞ models, and that this domain is unique, in the sense that it is the only nontrivial solution to the retract equation d = do→d, using the specific codings of the Pω model.

Details DOI