liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 7 of 7
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1.
    Broxvall, Mathias
    Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
    A Method for Metric Temporal Reasoning2002In: Proceedings of the Eighteenth National Conference on Arti cial Intelligence (AAAI-02), Edmonton, Canada, 2002, 513-518 p.Conference paper (Refereed)
  • 2.
    Broxvall, Mathias
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    A Study in the Computational Complexity of Temporal Reasoning2002Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    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.

    List of papers
    1. Point Algebras for Temporal Reasoning: Algorithms and Complexity
    Open this publication in new window or tab >>Point Algebras for Temporal Reasoning: Algorithms and Complexity
    2003 (English)In: Artificial Intelligence, ISSN 0004-3702, Vol. 149, no 2, 179-220 p.Article in journal (Refereed) Published
    Abstract [en]

    We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.

    Keyword
    Temporal reasoning, Point algebras, Constraint satisfaction
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-13500 (URN)10.1016/S0004-3702(03)00075-4 (DOI)
    Available from: 2003-01-18 Created: 2003-01-18 Last updated: 2017-02-23
    2. Disjunctions, Independence, Refinements
    Open this publication in new window or tab >>Disjunctions, Independence, Refinements
    2002 (English)In: Artificial Intelligence, ISSN 0004-3702, Vol. 140, no 1-2, 153-173 p.Article in journal (Refereed) Published
    Abstract [en]

    An important question in constraint satisfaction is how to restrict the problem to ensure tractability (since the general problem is NP-hard). The use of disjunctions has proven to be a useful method for constructing tractable constraint classes from existing classes; the well-known ‘max-closed’ and ‘ORD-Horn’ constraints are examples of tractable classes that can be constructed this way. Three sufficient conditions (the guaranteed satisfaction property, 1-independence and 2-independence) that each ensure the tractability of constraints combined by disjunctions have been proposed in the literature. We show that these conditions are both necessary and sufficient for tractability in three different natural classes of disjunctive constraints. This suggests that deciding this kind of property is a very important task when dealing with disjunctive constraints. We provide a simple, automatic method for checking the 1-independence property—this method is applicable whenever the consistency of the constraints under consideration can be decided by path-consistency. Our method builds on a connection between independence and refinements (which is a way of reducing one constraint satisfaction problem to another.)

    Keyword
    Constraint satisfaction, Disjunctive constraints, Tractability
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-13501 (URN)10.1016/S0004-3702(02)00224-2 (DOI)
    Available from: 2003-01-18 Created: 2003-01-18 Last updated: 2017-02-23
    3. Constraint Satisfaction on In nite Domains: Composing Domains and Decomposing Constraints
    Open this publication in new window or tab >>Constraint Satisfaction on In nite Domains: Composing Domains and Decomposing Constraints
    2002 (English)In: Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR-2002), Toulouse, France, 2002, 509-520 p.Conference paper, Published paper (Refereed)
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-13502 (URN)
    Available from: 2003-01-18 Created: 2003-01-18 Last updated: 2009-02-09
    4. A Method for Metric Temporal Reasoning
    Open this publication in new window or tab >>A Method for Metric Temporal Reasoning
    2002 (English)In: Proceedings of the Eighteenth National Conference on Arti cial Intelligence (AAAI-02), Edmonton, Canada, 2002, 513-518 p.Conference paper, Published paper (Refereed)
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-13503 (URN)
    Available from: 2003-01-18 Created: 2003-01-18
  • 3.
    Broxvall, Mathias
    Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
    Constraint Satisfaction on In nite Domains: Composing Domains and Decomposing Constraints2002In: Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR-2002), Toulouse, France, 2002, 509-520 p.Conference paper (Refereed)
  • 4.
    Broxvall, Mathias
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Constraint Satisfaction on Infinite Domains: Composing Domains and Decomposing Constraints2002In: Proc. of the 8th Int'l Conference on Principles on Knowledge Representation and Reasoning (KR-2002), 2002Conference paper (Refereed)
  • 5.
    Broxvall, Mathias
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Point Algebras for Temporal Reasoning: Algorithms and Complexity2003In: Artificial Intelligence, ISSN 0004-3702, Vol. 149, no 2, 179-220 p.Article in journal (Refereed)
    Abstract [en]

    We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.

  • 6.
    Broxvall, Mathias
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Towards a complete classification of tractability in point algebras for nonlinear time1999In: Principles and Practice of Constraint Programming – CP’99: 5th International Conference, CP’99, Alexandria, VA, USA, October 11-14, 1999. Proceedings / [ed] Joxan Jaffar, Berlin: Springer, 1999, Vol. 1713, 129-143 p.Chapter in book (Refereed)
    Abstract [en]

    Efficient reasoning about temporal constraints over nonlinear time models is vital in numerous application areas, such as planning, distributed systems and cooperating agents. We identify all tractable subclasses of the point algebra for partially-ordered time and examine one large, nontrivial tractable subclass of the point algebra for branching time.

  • 7.
    Broxvall, Mathias
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Renz, Jochen
    Institut für Informationssysteme, Technische Universität Wien, Wien, Austria.
    Disjunctions, Independence, Refinements2002In: Artificial Intelligence, ISSN 0004-3702, Vol. 140, no 1-2, 153-173 p.Article in journal (Refereed)
    Abstract [en]

    An important question in constraint satisfaction is how to restrict the problem to ensure tractability (since the general problem is NP-hard). The use of disjunctions has proven to be a useful method for constructing tractable constraint classes from existing classes; the well-known ‘max-closed’ and ‘ORD-Horn’ constraints are examples of tractable classes that can be constructed this way. Three sufficient conditions (the guaranteed satisfaction property, 1-independence and 2-independence) that each ensure the tractability of constraints combined by disjunctions have been proposed in the literature. We show that these conditions are both necessary and sufficient for tractability in three different natural classes of disjunctive constraints. This suggests that deciding this kind of property is a very important task when dealing with disjunctive constraints. We provide a simple, automatic method for checking the 1-independence property—this method is applicable whenever the consistency of the constraints under consideration can be decided by path-consistency. Our method builds on a connection between independence and refinements (which is a way of reducing one constraint satisfaction problem to another.)

1 - 7 of 7
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf