Ändra sökning
Avgränsa sökresultatet
123 1 - 50 av 103
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Aghighi, Meysam
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Bäckström, Christer
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Ståhlberg, Simon
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis2016Ingår i: ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, IOS Press, 2016, Vol. 285, s. 184-192Konferensbidrag (Refereegranskat)
    Abstract [en]

    Cost-optimal planning has become a very well-studied topic within planning. Needless to say, cost-optimal planning has proven to be computationally hard both theoretically and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it from an approximation point of view. Even though such studies may be valuable in themselves, additional motivation is provided by the fact that there is a very close link between approximability and the performance of heuristics used in heuristic search. The aim of this paper is to analyse approximability (and indirectly the performance of heuristics) with respect to lower time bounds. That is, we are not content by merely classifying problems into complexity classes - we also study their time complexity. This is achieved by replacing standard complexity-theoretic assumptions (such as P not equal NP) with the exponential time hypothesis (ETH). This enables us to analyse, for instance, the performance of the h(+) heuristic and obtain general trade-off results that correlate approximability bounds with bounds on time complexity.

  • 2.
    Aghighi, Meysam
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Bäckström, Christer
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Ståhlberg, Simon
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Refining complexity analyses in planning by exploiting the exponential time hypothesis2016Ingår i: Annals of Mathematics and Artificial Intelligence, ISSN 1012-2443, E-ISSN 1573-7470, Vol. 78, nr 2, s. 157-175Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The use of computational complexity in planning, and in AI in general, has always been a disputed topic. A major problem with ordinary worst-case analyses is that they do not provide any quantitative information: they do not tell us much about the running time of concrete algorithms, nor do they tell us much about the running time of optimal algorithms. We address problems like this by presenting results based on the exponential time hypothesis (ETH), which is a widely accepted hypothesis concerning the time complexity of 3-SAT. By using this approach, we provide, for instance, almost matching upper and lower bounds onthe time complexity of propositional planning.

  • 3.
    Aghighi, Meysam
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Oversubscription planning: Complexity and compilability2014Ingår i: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AI Access Foundation , 2014, Vol. 3, s. 2221-2227Konferensbidrag (Refereegranskat)
    Abstract [en]

    Many real-world planning problems are oversubscription problems where all goals are not simultaneously achievable and the planner needs to find a feasible subset. We present complexity results for the so-called partial satisfaction and net benefit problems under various restrictions; this extends previous work by van den Briel et al. Our results reveal strong connections between these problems and with classical planning. We also present a method for efficiently compiling oversubscription problems into the ordinary plan existence problem; this can be viewed as a continuation of earlier work by Keyder and Geffner.

  • 4.
    Aghighi, Meysam
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Ståhlberg, Simon
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs2015Ingår i: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015Konferensbidrag (Refereegranskat)
    Abstract [en]

    Causal graphs are widely used to analyze the complexity of planning problems. Many tractable classes have been identified with their aid and state-of-the-art heuristics have been derived by exploiting such classes. In particular, Katz and Keyder have studied causal graphs that are hourglasses (which is a generalization of forks and inverted-forks) and shown that the corresponding cost-optimal planning problem is tractable under certain restrictions. We continue this work by studying polytrees (which is a generalization of hourglasses) under similar restrictions. We prove tractability of cost-optimal planning by providing an algorithm based on a novel notion of variable isomorphism. Our algorithm also sheds light on the k-consistency procedure for identifying unsolvable planning instances. We speculate that this may, at least partially, explain why merge-and-shrink heuristics have been successful for recognizing unsolvable instances.

  • 5.
    Angelsmark, Ola
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Dahllöf, Vilhelm
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Jonsson, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Finite Domain Constraint Satisfaction Using Quantum Computation2002Ingår i: Mathematical Foundations of Computer Science, 27th International Symposium MFCS-2002,2002, Heidelberg: Springer Verlag , 2002, s. 93-Konferensbidrag (Refereegranskat)
    Abstract [en]

    We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in time, where d is size of the domain of the variables and n the number of variables. For the case of d=3 we provide a method to obtain an upper time bound of . Also for d=5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185^n) time.

  • 6.
    Angelsmark, Ola
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Improved algorithms for counting solutions in constraint satisfaction problems2003Ingår i: Principles and Practice of Constraint Programming, 9th International Conference CP 2003,2003, Springer, 2003, Vol. 2833, s. 81-95Konferensbidrag (Refereegranskat)
    Abstract [en]

    Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to binary CSP s which has a time complexity ranging from O ((d/4 . alpha(4))(n)) to O((alpha + alpha(5) + [d/4 - 1] . alpha(4))(n)) (where alpha approximate to 1.2561) depending on the domain size d greater than or equal to 3. This is substantially faster than previous algorithms, especially for small d. We also provide an algorithm for counting k-colourings in graphs and its running time ranges from O ([log(2) k](n)) to O ([log(2) k + 1](n)) depending on k greater than or equal to 4. Previously, only an O(1.8171(n)) time algorithm for counting 3-colourings were known, and we improve this upper bound to O(1.7879(n)).

  • 7.
    Angelsmark, Ola
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Jonsson, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Linusson, Svante
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Tillämpad matematik.
    Thapper, Johan
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Matematiska institutionen, Tillämpad matematik.
    Determining the Number of Solutions to Binary CSP Instances2002Ingår i: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002, Heidelberg: Springer Verlag , 2002, s. 327-Konferensbidrag (Refereegranskat)
    Abstract [en]

    Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge. 

  • 8.
    Bjäreland, Marcus
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning.
    Jonsson, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Exploiting bipartiteness to identify yet another tractable subclass of CSP1999Ingår i: Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP), Springer , 1999, Vol. 1713, s. 118-128Konferensbidrag (Refereegranskat)
    Abstract [en]

    The class of constraint satisfaction problems (CSPs) over finite domains has been shown to be NP-complete, but many tractable subclasses have been identified in the literature. In this paper we are interested in restrictions on the types of constraint relations in CSP instances. By a result of Jeavons et al. we know that a key to the complexity of classes arising from such restrictions is the closure properties of the sets of relations. It has been shown that sets of relations that are closed under constant, majority, affine, or associative, commutative, and idempotent (ACI) functions yield tractable subclasses of CSP. However, it has been unknown whether other closure properties may generate tractable subclasses. In this paper we introduce a class of tractable (in fact, SL-complete) CSPs based on bipartite graphs. We show that there are members of this class that are not closed under constant, majority, affine, or ACI functions, and that it, therefore, is incomparable with previously identified classes.

  • 9.
    Bodirsky, Manuel
    et al.
    Technical University of Dresden, Germany.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    A Model-Theoretic View on Qualitative Constraint Reasoning2017Ingår i: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 58, s. 339-385Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Qualitative reasoning formalisms are an active research topic in artificial intelligence. In this survey we present a model-theoretic perspective on qualitative constraint reasoning and explain some of the basic concepts and results in an accessible way. In particular, we discuss the significance of omega-categoricity for qualitative reasoning, of primitive positive interpretations for complexity analysis, and of Datalog as a unifying language for describing local consistency algorithms.

  • 10.
    Bodirsky, Manuel
    et al.
    Technical University of Dresden, Germany.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Pham Trung, Van
    Vienna University of Technology, Austria.
    THE REDUCTS OF THE HOMOGENEOUS BINARY BRANCHING C-RELATION2016Ingår i: Journal of Symbolic Logic (JSL), ISSN 0022-4812, E-ISSN 1943-5886, Vol. 81, nr 4, s. 1255-1297Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Let (L; C) be the (up to isomorphism unique) countable homogeneous structure carrying a binary branching C-relation. We study the reducts of (L; C), i.e., the structures with domain L that are first-order definable in (L; C). We show that up to existential interdefinability, there are finitely many such reducts. This implies that there are finitely many reducts up to first-order interdefinability, thus confirming a conjecture of Simon Thomas for the special case of (L; C). We also study the endomorphism monoids of such reducts and show that they fall into four categories.

  • 11. Bodirsky, Manuel
    et al.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system.
    Van Pham, Trung
    The Complexity of Phylogeny Constraint Satisfaction2016Konferensbidrag (Refereegranskat)
  • 12.
    Bodirsky, Manuel
    et al.
    Technical University of Dresden, Germany.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Van Pham, Trung
    Vietnam Academy of Science and Technology, Hanoi, Vietnam.
    The Complexity of Phylogeny Constraint Satisfaction Problems2017Ingår i: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 18, nr 3, artikel-id 23Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We systematically study the computational complexity of a broad class of computational problems in phylogenetic reconstruction. The class contains, for example, the rooted triple consistency problem, forbidden subtree problems, the quartet consistency problem, and many other problems studied in the bioinformatics literature. The studied problems can be described as constraint satisfaction problems, where the constraints have a first-order definition over the rooted triple relation. We show that every such phylogeny problem can be solved in polynomial time or is NP-complete. On the algorithmic side, we generalize a well-known polynomial-time algorithm of Aho, Sagiv, Szymanski, and Ullman for the rooted triple consistency problem. Our algorithm repeatedly solves linear equation systems to construct a solution in polynomial time. We then show that every phylogeny problem that cannot be solved by our algorithm is NP-complete. Our classification establishes a dichotomy for a large class of infinite structures that we believe is of independent interest in universal algebra, model theory, and topology. The proof of our main result combines results and techniques from various research areas: a recent classification of the model-complete cores of the reducts of the homogeneous binary branching C-relation, Leebs Ramsey theorem for rooted trees, and universal algebra.

  • 13.
    Bodirsky, Manuel
    et al.
    Ecole Polytechnique, Palaiseau, France.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    von Oertzen, Timo
    Max-Planck-Institute for Human Development, Berlin, Germany and University of Virginia, Charlottesville, USA..
    Essential Convexity and Complexity of Semi-algebraic Constraints2012Ingår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 8, nr 4Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Let \Gamma be a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets. In this article, we study the computational complexity of constraint satisfaction problem (CSP) for \Gamma: the problem to decide whether a given primitive positive sentence is true in \Gamma. We focus on those structures \Gamma that contain the relations \leq, {(x,y,z) | x+y=z} and {1}. Hence, all CSPs studied in this article are at least as expressive as the feasibility problem for linear programs. The central concept in our investigation is essential convexity: a relation S is essentially convex if for all a,b\inS, there are only finitely many points on the line segment between a and b that are not in S. If \Gamma contains a relation S that is not essentially convex and this is witnessed by rational points a,b, then we show that the CSP for \Gamma is NP-hard. Furthermore, we characterize essentially convex relations in logical terms. This different view may open up new ways for identifying tractable classes of semi-algebraic CSPs. For instance, we show that if \Gamma is a first-order expansion of (R;*,+), then the CSP for \Gamma can be solved in polynomial time if and only if all relations in \Gamma are essentially convex (unless P=NP).

  • 14.
    Bodirsky, Manuel
    et al.
    Ecole Polytechnique, Palaiseau, France.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    von Oertzen, Timo
    University of Virginia, USA.
    Horn versus Full First-order: Complexity Dichotomies in Algebraic Constraint Satisfaction2012Ingår i: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 22, nr 3, s. 643-660Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain fundamental algebraic structures Delta, we prove definability dichotomy theorems of the following form: for every first-order expansion Gamma of Delta, either Gamma has a quantifier-free Horn definition in Delta, or there is an element d of Gamma such that all non-empty relations in Gamma contain a tuple of the form (d,...,d), or all relations with a first-order definition in Delta have a primitive positive definition in Gamma. The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations. As concrete examples, we investigate fundamental algebraic constraint satisfaction problems. The first class consists of all first-order expansions of (Q;+). The second class is the affine variant of the first class. In both cases, we obtain full dichotomies by utilising our general methods.

  • 15.
    Bodirsky, Manuel
    et al.
    CNRS/LIX, École Polytechnique, 91128 Palaiseau, France.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    von Oertzen, Timo
    Max-Planck-Institute for Human Development, Königin-Luise-Strasse 5, 14195, Berlin.
    Semilinear Program Feasibility2009Ingår i: Automata, Languages and Programming, Berlin / Heidelberg: Springer , 2009, s. 79-90Konferensbidrag (Refereegranskat)
    Abstract [en]

    We study logical techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems (CSPs). For the fundamental algebraic structure where are the real numbers and L 1,L 2,... is an enumeration of all linear relations with rational coefficients, we prove that a semilinear relation R (i.e., a relation that is first-order definable with linear inequalities) either has a quantifier-free Horn definition in Γ or the CSP for is NP-hard. The result implies a complexity dichotomy for all constraint languages that are first-order expansions of Γ: the corresponding CSPs are either in P or are NP-complete depending on the choice of allowed relations. We apply this result to two concrete examples (generalised linear programming and metric temporal reasoning) and obtain full complexity dichotomies in both cases.

  • 16.
    Broxvall, Mathias
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Point Algebras for Temporal Reasoning: Algorithms and Complexity2003Ingår i: Artificial Intelligence, ISSN 0004-3702, Vol. 149, nr 2, s. 179-220Artikel i tidskrift (Refereegranskat)
    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.

  • 17.
    Broxvall, Mathias
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Towards a complete classification of tractability in point algebras for nonlinear time1999Ingår i: 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, s. 129-143Kapitel i bok, del av antologi (Refereegranskat)
    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.

  • 18.
    Broxvall, Mathias
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Renz, Jochen
    Institut für Informationssysteme, Technische Universität Wien, Wien, Austria.
    Disjunctions, Independence, Refinements2002Ingår i: Artificial Intelligence, ISSN 0004-3702, Vol. 140, nr 1-2, s. 153-173Artikel i tidskrift (Refereegranskat)
    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.)

  • 19.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Chen, Yue
    Vienna University of Technology, Austria.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Ordyniak, Sebastian
    Vienna University of Technology, Austria.
    Szeider, Stefan
    Vienna University of Technology, Austria.
    The Complexity of Planning Revisited - A Parameterized Analysis2012Ingår i: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, 2012, s. 1735-1741Konferensbidrag (Refereegranskat)
    Abstract [en]

    The early classifications of the computational complexity of planning under various restrictions in STRIPS (Bylander) and SAS+ (B¨ackstr¨om and Nebel) have influenced following research in planning in many ways. We go back and reanalyse their subclasses, but this time using the more modern tool of parameterized complexity analysis. This provides new results that together with the old results give a more detailed picture of the complexity landscape. We demonstrate separation results not possible with standard complexity theory, which contributes to explaining why certain cases of planning haveseemed simpler in practice than theory has predicted. In particular, we show that certain restrictions of practical interest are tractable in the parameterized sense of the term, and that a simple heuristic is sufficient to make a well-known partialorder planner exploit this fact.

  • 20.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Anders
    University of Pompeu Fabra, Spain.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Automaton Plans2014Ingår i: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 51, s. 255-291Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Macros have long been used in planning to represent subsequences of operators. Macros can be used in place of individual operators during search, sometimes reducing the effort required to find a plan to the goal. Another use of macros is to compactly represent long plans. In this paper we introduce a novel solution concept called automaton plans in which plans are represented using hierarchies of automata. Automaton plans can be viewed as an extension of macros that enables parameterization and branching. We provide several examples that illustrate how automaton plans can be useful, both as a compact representation of exponentially long plans and as an alternative to sequential solutions in benchmark domains such as LOGISTICS and GRID. We also compare automaton plans to other compact plan representations from the literature, and find that automaton plans are strictly more expressive than macros, but strictly less expressive than HTNs and certain representations allowing efficient sequential access to the operators of the plan.

  • 21.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Anders
    Universitat Pompeu Fabra, Barcelona, Spain.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    From Macro Plans to Automata Plans2012Ingår i: ECAI 2012. 20th European Conference on Artificial Intelligence, 27-31 2012,  August, Montpellier, France, 2012, s. 91-96Konferensbidrag (Refereegranskat)
    Abstract [en]

    Macros have a long-standing role in planning as a tool for representing repeating subsequences of operators. Macros are useful both for guiding search towards a solution and for representing plans compactly. In this paper we introduce automata plans which consist of hierarchies of finite state automata. Automata plans can be viewed as an extension of macros that enables parametrization and branching. We provide several examples of the utility of automata plans, and prove that automata plans are strictly more expressive than macro plans. We also prove that automata plans admit polynomialtime sequential access of the operators in the underlying “flat” plan, and identify a subset of automata plans that admit polynomial-time random access. Finally, we compare automata plans with other representations allowing polynomial-time sequential access.

  • 22.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Anders
    Universitat Pompeu Fabra, Barcelona, Spain.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Macros, Reactive Plans and Compact Representations2012Ingår i: ECAI 2012. 20th European Conference on Artificial Intelligence 27-31 August 2+12, Montpellier, France / [ed] Luc De Raedt, Christian Bessiere, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz, Peter Lucas, 2012, s. 85-90Konferensbidrag (Refereegranskat)
    Abstract [en]

    The use and study of compact representations of objects is widespread in computer science. AI planning can be viewed as the problem of finding a path in a graph that is implicitly described by a compact representation in a planning language. However, compact representations of the path itself (the plan) have not received much attention in the literature. Although both macro plans and reactive plans can be considered as such compact representations, little emphasis has been placed on this aspect in earlier work. There are also compact plan representations that are defined by their access properties, for instance, that they have efficient random access or efficient sequential access. We formally compare two such concepts with macro plans and reactive plans, viewed as compact representations, and provide a complete map of the relationships between them.

  • 23.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond2013Ingår i: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 47, s. 575-611Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.

  • 24.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Abstracting Abstraction in Search II: Complexity Analysis2012Ingår i: Proceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012 / [ed] Daniel Borrajo, Ariel Felner, Richard Korf, Maxim Likhachev, Carlos Linares Lopez, Wheeler Ruml, and Nathan Sturtevant, AAAI Press, 2012, s. 10-17Konferensbidrag (Refereegranskat)
    Abstract [en]

    Modelling abstraction as a function from the original state space to an abstract state space is a common approach in combinatorial search. Sometimes this is too restricted, though, and we have previously proposed a framework using a more flexible concept of transformations between labelled graphs. We also proposed a number of properties to describe and classify such transformations. This framework enabled the modelling of a number of different abstraction methods in a way that facilitated comparative analyses. It is of particular interest that these properties can be used to capture the concept of refinement without backtracking between levels; how to do this has been an open question for at least twenty years. In this paper, we continue our previous research by analysing the complexity of testing the various transformation properties for both explicit and implicit graph representations.

  • 25.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Abstracting Abstraction in Search with Applications to Planning2012Ingår i: Proceedings, Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, AAAI Press, 2012, s. 446-456Konferensbidrag (Refereegranskat)
    Abstract [en]

    Abstraction has been used in search and planning from the very beginning of AI. Many different methods and formalisms for abstraction have been proposed in the literature but they have been designed from various points of view and with varying purposes. Hence, these methods have been notoriously difficult to analyse and compare in a structured way. In order to improve upon this situation, we present a coherent and flexible framework for modelling abstraction (and abstraction-like) methods based on transformations on labelled graphs. Transformations can have certain method properties that are inherent in the abstraction methods and describe their fundamental modelling characteristics, and they can have certain instance properties that describe algorithmic and computational characteristics of problem instances. The usefulness of the framework is demonstrated by applying it to problems in both search and planning. First, we show that we can capture many search abstraction concepts (such as avoidance of backtracking between levels) and that we can put them into a broader context. We further model five different abstraction concepts from the planning literature. Analysing what method properties they have highlights their fundamental differences and similarities. Finally, we prove that method properties sometimes imply instance properties. Taking also those instance properties into account reveals important information about computational aspects of the five methods.

  • 26.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Algorithms and Limits for Compact Plan Representations2012Ingår i: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 44, s. 141-177Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Compact representations of objects is a common concept in computer science. Automated planning can be viewed as a case of this concept: a planning instance is a compact implicit representation of a graph and the problem is to find a path (a plan) in this graph. While the graphs themselves are represented compactly as planning instances, the paths are usually represented explicitly as sequences of actions. Some cases are known where the plans always have compact representations, for example, using macros. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. In addition to this, we show that our results have consequences for what can be gained from reformulating planning into some other problem. As a contrast to this we also prove a number of positive results, demonstrating restricted cases where plans do have useful compact representations, as well as proving that macro plans have favourable access properties. Our results are finally discussed in relation to other relevant contexts.

  • 27.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    All PSPACE-complete Planning Problems are Equal but some are more Equal than Others2011Ingår i: Proceedings, The Fourth International Symposium on Combinatorial Search (SoCS-2011) / [ed] Daniel Borrajo, Maxim Likhachev, Carlos Linares Lopez, AAAI Press, 2011, s. 10-17Konferensbidrag (Refereegranskat)
    Abstract [en]

    Complexity analysis of planning is problematic. Even very simple planning languages are PSPACE-complete, yet cannot model many simple problems naturally. Many languages with much more powerful features are also PSPACE-complete. It is thus difficult to separate planning languages in a useful way and to get complexity figures that better reflect reality.This paper introduces new methods for complexity analysis of planning and similar combinatorial search problems, in order to achieve more precision and complexity separations than standard methods allow. Padding instances with the solution size yields a complexity measure that is immune to this factor and reveals other causes of hardness, that are otherwise hidden. Further combining this method with limited nondeterminism improves the precision, making even finer separations possible. We demonstrate with examples how these methods can narrow the gap between theory and practice.

  • 28.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Bridging the Gap Between Refinement and Heuristics in Abstraction2013Ingår i: IJCAI'13 Proceedings of the Twenty-Third international joint conference on Artificial Intelligence, AAAI Press, 2013, s. 2261-2267Konferensbidrag (Refereegranskat)
    Abstract [en]

    There are two major uses of abstraction in planning and search: refinement (where abstract solutions are extended into concrete solutions) and heuristics (where abstract solutions are used to compute heuristics for the original search space). These two approaches are usually viewed as unrelated in the literature. It is reasonable to believe, though, that they are related, since they are both intrinsically based on the structure of abstract search spaces. We take the first steps towards formally investigating their relationships, employing our recently introduced framework for analysing and comparing abstraction methods. By adding some mechanisms for expressing metric properties, we can capture concepts like admissibility and consistency of heuristics. We present an extensive study of how such metric properties relate to the properties in the original framework, revealing a number of connections between the refinement and heuristic approaches. This also provides new insights into, for example, Valtorta's theorem and spurious states.

  • 29.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Limits for compact representations of plans2011Ingår i: ICAPS 2011 : proceedings of the twenty-first international conference on automated planning and scheduling : annual ICAPS conference : Jun 2011, Freiburg, Germany / [ed] Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp, Malte Helmert, AAAI Press, 2011, s. 18-25Konferensbidrag (Refereegranskat)
    Abstract [en]

    Most planning formalisms allow instances with shortest plans of exponential length. While such instances are problematic, they are usually unavoidable and can occur in practice. There are several known cases of restricted planning problems where plans can be exponential but always have a compact (ie. polynomial) representation, often using recursive macros. Such compact representations are important since exponential plans are difficult both to use and to understand. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. Further, we show that it is unlikely to get around this by reformulating planning into some other problem. The results are discussed in the context of abstraction, macros and plan explanation.

  • 30.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Time and Space Bounds for Planning2017Ingår i: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 60, s. 595-638Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem (CSP) have been thoroughly analysed in this respect. We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time and thus require O (2(cn)) time for some c amp;gt; 0. In many cases, we can even prove closely matching upper and lower bounds; for every epsilon amp;gt; 0, the problem can be solved in time O (2((1+epsilon)n)) but not in time O (2((1-epsilon)n)). Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space. In particular, we show that depth-first search may sometimes be a viable option for planning under severe space constraints.

  • 31.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Upper and Lower Time and Space Bounds for Planning2016Ingår i: ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, IOS PRESS , 2016, Vol. 285, s. 716-724Konferensbidrag (Refereegranskat)
    Abstract [en]

    There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem have been thoroughly analysed in this respect. We provide a number of upper and lower bound results for both plan satisfiability (PSAT) and length-optimal planning (LOP), with an emphasis on monotone planning (where actions have only positive effects) which is used in, for instance, h(+) and similar heuristics. Let v and a be the number of variables and actions, respectively. We consider both restrictions on the number and polarity of preconditions and effects of actions and the PUBS restrictions in SAS(+). For all such classes, we show that PSAT and LOP is either tractable or cannot be solved in subexponential time 2(o(v)) or time 2(o(a)), unless the so-called Exponential Time Hypothesis (ETH) is false. There is also a sharp transition: monotone LOP can be solved in time 2(o(v)) if a is an element of o(v/log v) but not if a is an element of Omega(v). We also study upper bounds and discuss the trade-off between time and space, providing a polynomial-space algorithm for monotone LOP that beats depth-first search in most cases. This raises the important question how lower bounds are affected by polynomial space restrictions.

  • 32.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Ordyniak, Sebastian
    Masaryk University, Czech Republic.
    Szeider, Stefan
    Vienna University of Technology, Austria.
    A complete parameterized complexity analysis of bounded planning2015Ingår i: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 81, nr 7, s. 1311-1332Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Backstrom and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. (C) 2015 Elsevier Inc. All rights reserved.

  • 33.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Ordyniak, Sebastian
    Masaryk University, Brno, Czech Republic.
    Szeider, Stefan
    Vienna University of Technolgy, Austria.
    Parameterized Complexity and Kernel Bounds for Hard Planning Problems2013Ingår i: Algorithms and Complexity: 8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings / [ed] Paul G. Spirakis & Maria Serna, Springer Berlin/Heidelberg, 2013, s. 13-24Konferensbidrag (Refereegranskat)
    Abstract [en]

    The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the parameter) and Bäckström et al. (2012) picked up this line of research and provided an extensive parameterized analysis under various restrictions, leaving open only one stubborn case. We continue this work and provide a full classification. In particular, we show that the case when actions have no preconditions and at most e postconditions is fixed-parameter tractable if e ≤ 2 and W[1]-complete otherwise. We show fixed-parameter tractability by a reduction to a variant of the Steiner Tree problem; this problem has been shown fixed-parameter tractable by Guo et al. (2007). If a problem is fixed-parameter tractable, then it admits a polynomial-time self-reduction to instances whose input size is bounded by a function of the parameter, called the kernel. For some problems, this function is even polynomial which has desirable computational implications. Recent research in parameterized complexity has focused on classifying fixed-parameter tractable problems on whether they admit polynomial kernels or not. We revisit all the previously obtained restrictions of planning that are fixed-parameter tractable and show that none of them admits a polynomial kernel unless the polynomial hierarchy collapses to its third level.

  • 34.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Ståhlberg, Simon
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
    Fast Detection of Unsolvable Planning Instances Using Local Consistency2013Ingår i: Proceedings of the Sixth International Symposium on Combinatorial Search, AAAI Press, 2013, s. 29-37Konferensbidrag (Refereegranskat)
    Abstract [en]

    There has been a tremendous advance in domain-independent planning over the past decades, and planners have become increasingly efficient at finding plans. However, this has not been paired by any corresponding improvement in detecting unsolvable instances. Such instances are obviously important but largely neglected in planning. In other areas, such as constraint solving and model checking, much effort has been spent on devising methods for detecting unsolvability. We introduce a method for detecting unsolvable planning instances that is loosely based on consistency checking in constraint programming. Our method balances completeness against efficiency through a parameter k: the algorithm identifies more unsolvable instances but takes more time for increasing values of k. We present empirical data for our algorithm and some standard planners on a number of unsolvable instances, demonstrating that our method can be very efficient where the planners fail to detect unsolvability within reasonable resource bounds. We observe that planners based on the h^m heuristic or pattern databases are better than other planners for detecting unsolvability. This is not a coincidence since there are similarities (but also significant differences) between our algorithm and these two heuristic methods.

  • 35.
    Cohen, D
    et al.
    University of London.
    Jeavons, P
    University of Oxford.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Koubarakis, M
    Technical Unversity of Crete.
    Building tractable disjunctive constraints2000Ingår i: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 47, nr 5, s. 826-853Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified.

  • 36.
    Dahllöf, Vilhelm
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    An Algorithm for Counting Maximum Weighted Independent Sets and its Applications2002Ingår i: Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2002), ACM-SIAM , 2002Konferensbidrag (Refereegranskat)
  • 37.
    Dahllöf, Vilhelm
    et al.
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Jonsson, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Beigel, R.
    Department of Computer Science, Temple University, 1805 N Broad St Fl 4, Philadelphia, PA 19122, United States.
    Algorithms for four variants of the exact satisfiability problem2004Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 320, nr 2-3, s. 373-394Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We present four polynomial space and exponential time algorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1.1120n) (where n is the number of variables) time algorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1.1907n) time algorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1.1193n) and O(1.2299n) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1.1487n) time algorithm. We also present an O(1.2190n) time algorithm for the general problem of counting the number of models for EXACT SATISFIABILITY, presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix. © 2004 Elsevier B.V. All rights reserved.

  • 38.
    Dahllöf, Vilhelm
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Wahlström, Magnus
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Counting Satisfying Assignments in 2-SAT and 3-SAT2003Konferensbidrag (Övrigt vetenskapligt)
    Abstract [en]

    We present an O(1.3247n) algorithm for counting the number of satisfying assignments for instances of 2-SAT and an O(1.6894n) algorithm for instances of 3-SAT. This is an improvement compared to the previously best known algorithms running in O(1.381n) and O(1.739n) time, respectively.

  • 39.
    Dahllöf, Wilhelm
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB. Linköpings universitet, Tekniska högskolan.
    Wahlström, Magnus
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB. Linköpings universitet, Tekniska högskolan.
    Counting models for 2sat and 3sat formulae2005Ingår i: Theoretical Computer Science, ISSN 0304-3975, Vol. 332, nr 1-3, s. 265-291Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561n) and O(1.6737n) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting non-weighted models for 2SAT and 3SAT, which run in O(1.3247n) and O(1.6894n) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices.

  • 40.
    Dalmau, Victor
    et al.
    Departament de Tecnologia Universitat Pompeu Fabra.
    Jonsson, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    The Complexity of Counting Homomorphisms Seen from the Other Side2004Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 329, s. 315-323Artikel i tidskrift (Refereegranskat)
  • 41. Deineko, Vladimir
    et al.
    Jonsson, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Klasson, Mikael
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Krokhin, Andrei
    Supermodularity on chains and complexity of maximum constraint satisfaction problems2005Ingår i: Proceedings of the European Conference on Combinatorics, Graph Theory and Applications Eurocomb 05,2005, DMTCS , 2005, s. 51-Konferensbidrag (Refereegranskat)
  • 42.
    Deineko, Vladimir
    et al.
    University of Warwick.
    Jonsson, Peter
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Klasson, Mikael
    Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
    Krokhin, Andrei
    University of Durham.
    The approximability of Max CSP with fixed-value constraints2008Ingår i: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 55, nr 4Artikel i tidskrift (Refereegranskat)
  • 43. Engstrom, Robert
    et al.
    Färnqvist, Tommy
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Thapper, Johan
    University of Paris Est Marne La Vallee, France.
    An Approximability-related Parameter on Graphs - Properties and Applications2015Ingår i: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, ISSN 1462-7264, Vol. 17, nr 1, s. 33-66Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (MAX H-COL), which is a restriction of the general maximum constraint satisfaction problem (MAX CSP) to a single, binary, and symmetric relation. Using known approximation ratios for MAX k-CUT, we obtain general asymptotic approximability results for MAX H-COL for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Samal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as MAX H-COL.

  • 44.
    Engström, Robert
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Färnqvist, Tommy
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Thapper, Johan
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Properties of an Approximability-related Parameter on Circular Complete Graphs2009Ingår i: Electronic Notes in Discrete Mathematics, ISSN 1571-0653, E-ISSN 1571-0653, Vol. 35, s. 115-120Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The instances of the Weighted Maximum H-Colourable Subgraph problem (Max H-Col) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=Kk this problem is equivalent to Max k-cut. Färnqvist et al. have introduced a parameter on the space of graphs that allows close study of the approximability properties of Max H-Col. Here, we investigate the properties of this parameter on circular complete graphs Kp/q, where 2p/q3. The results are extended to K4-minor-free graphs. We also consider connections with Šámal's work on fractional covering by cuts: we address, and decide, two conjectures concerning cubical chromatic numbers.

  • 45.
    Feder, Tomas
    et al.
    Stanford University.
    Hell, Pavol
    Simon Fraser University.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Krokhin, Andrei
    University of Durham.
    Nordh, Gustav
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Retractions To Pseudoforests2010Ingår i: SIAM JOURNAL ON DISCRETE MATHEMATICS, ISSN 0895-4801, Vol. 24, nr 1, s. 101-112Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    For a fixed graph H, let RET(H) denote the problem of deciding whether a given input graph is retractable to H. We classify the complexity of RET(H) when H is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of RET(H) for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems.

  • 46.
    Färnqvist, Tommy
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Bounded Tree-Width and CSP-Related Problems2007Ingår i: Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. Proceedings / [ed] Takeshi Tokuyama, Springer Berlin/Heidelberg, 2007, s. 632-643Kapitel i bok, del av antologi (Refereegranskat)
    Abstract [en]

    We study the complexity of structurally restricted homomorphism and constraint satisfaction problems. For every class of relational structures C , let LHom be the problem of deciding whether a structure A Î CA has a homomorphism to a given arbitrary structure B, when each element in A is only allowed a certain subset of elements of B as its image. We prove, under a certain complexity-theoretic assumption, that this list homomorphism problem is solvable in polynomial time if and only if all structures in C have bounded tree-width. The result is extended to the connected list homomorphism, edge list homomorphism, minimum cost homomorphism and maximum solution problems. We also show an inapproximability result for the minimum cost homomorphism problem.

  • 47.
    Färnqvist, Tommy
    et al.
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Thapper, Johan
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Approximability Distance in the Space of H-Colourability Problems2009Ingår i: COMPUTER SCIENCE - THEORY AND APPLICATIONS, ISSN 0302-9743, Vol. 5675, s. 92-104Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. We Study the approximability properties of the Weigh feel Maximum H-Colourable Subgraph problem (MAX H-COL). The instances of this problem are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H note that for H = K-k this problem is equivalent to MAX k-CUT. To this end, we introduce a metric structure on the space of graphs which allows us to extend previously known approximability results to larger classes of graphs. Specifically, the approximation algorithms for MAX CUT by Goemans and Williamson and MAX k-CUT by Frieze and Jerrum can he used to yield non-trivial approximation results for MAX H-COL For a variety of graphs, we show near-optimality results under the Unique Games Conjecture. We also use our method for comparing the performance of Frieze andamp; Jerrums algorithm with Hastads approximation algorithm for general MAX 2-CSP. This comparison is, in most cases, favourable to Frieze andamp; Jerrum.

  • 48.
    Glasser, Christian
    et al.
    University of Wurzburg, Germany.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Martin, Barnaby
    Middlesex University, England.
    Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic2016Ingår i: Pursuit of the Universal, SPRINGER INT PUBLISHING AG , 2016, Vol. 9709, s. 323-332Konferensbidrag (Refereegranskat)
    Abstract [en]

    We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Gla beta er et al. [16] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits-involving complement, intersection, union and multiplication-to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [16] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, (N; x), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete.

  • 49.
    Glasser, Christian
    et al.
    Julius Maximilian University, Germany.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Martin, Barnaby
    University of Durham, England.
    Circuit satisfiability and constraint satisfaction around Skolem Arithmetic2017Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 703, s. 18-36Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glasser et al. [1] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits-involving complement, intersection, union and multiplication-to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [1] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, (N; x), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete. (C) 2017 Elsevier B.V. All rights reserved.

  • 50.
    Haslum, Patrik
    et al.
    Linköpings universitet, Institutionen för datavetenskap, KPLAB - Laboratoriet för kunskapsbearbetning. Linköpings universitet, Tekniska högskolan.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi. Linköpings universitet, Tekniska högskolan.
    Planning with Reduced Operator Sets2000Ingår i: Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS) / [ed] Steve Chien, Subbarao Kambhampati, Craig A. Knoblock, AAAI Press , 2000, s. 150-158Konferensbidrag (Refereegranskat)
    Abstract [en]

    Classical propositional STRIPS planning is nothing but the search for a path in the state transition graph induced by the operators in the planning problem. What makes the problem hard is the size and the sometimes adverse structure of this graph. We conjecture that the search for a plan would be more efficient if there were only a small number of paths from the initial state to the goal state. To verify this conjecture, we define the notion of reduced operator sets and describe ways of finding such reduced sets. We demonstrate that some state-of-the-art planners run faster using reduced operator sets.

123 1 - 50 av 103
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf