liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct 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
Disjunctions, Independence, Refinements
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Institut für Informationssysteme, Technische Universität Wien, Wien, Austria.
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.)

Place, publisher, year, edition, pages
2002. Vol. 140, no 1-2, 153-173 p.
Keyword [en]
Constraint satisfaction, Disjunctive constraints, Tractability
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-13501DOI: 10.1016/S0004-3702(02)00224-2OAI: oai:DiVA.org:liu-13501DiVA: diva2:20871
Available from: 2003-01-18 Created: 2003-01-18 Last updated: 2017-02-23
In thesis
1. A Study in the Computational Complexity of Temporal Reasoning
Open this publication in new window or tab >>A Study in the Computational Complexity of Temporal Reasoning
2002 (English)Doctoral 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.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2002. 21 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 779
Keyword
temporal and spatial information, artificiell intelligens, algebra, tractable fragments, temporal formalisms, formalism STP
National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-4984 (URN)91-7373-440-3 (ISBN)
Public defence
2002-12-10, Estraden, Hus E, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Supervisors
Note
Article I is a revised and extended version of the following three papers: 1. Mathias Broxvall and Peter Jonsson. Towards a Complete Classification of Tractability in Point Algebras for Nonlinear Time. In Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP-99), pp. 129-143, Alexandria, VA, USA, Oct, 1999. 2. Mathias Broxvall and Peter Jonsson. Disjunctive Temporal Reasoning in Partially Ordered Time Structures. In Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000), pp. 464-469, Austin, Texas, USA, Aug, 2000. 3. Mathias Broxvall. The Point Algebra for Branching Time Revisited. In Proceedings of the Joint German/Austrian Conference on Artificial Intelligence (KI-2001), pp. 106-121, Vienna, Austria, Sep, 2001. --- Article II is a revised and extended version of the following paper: Mathias Broxvall, Peter Jonsson and Jochen Renz: Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints. In Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming (CP-2000), pp. 114-127, Singapore, Sep, 2000.Available from: 2003-01-18 Created: 2003-01-18 Last updated: 2012-01-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textLink to Ph.D. Thesis

Authority records BETA

Broxvall, MathiasJonsson, Peter

Search in DiVA

By author/editor
Broxvall, MathiasJonsson, Peter
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 114 hits
CiteExportLink to record
Permanent link

Direct 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