Tractable Planning with State Variables by Exploiting Structural Restrictions. - Peter Jonsson; Christer Bäckström (AAAI, 1994)

Planning with Abstraction Hierarchies can be Exponentially Less Efficient. - Christer Bäckström; Peter Jonsson (IJCAI, 1995)

Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report. - Thomas Drakengren; Peter Jonsson (AAAI/IAAI, Vol. 1, 1996)

On the Size of Reactive Plans. - Peter Jonsson; Christer Bäckström (AAAI/IAAI, Vol. 2, 1996)

A Linear-Programming Approach to Temporal Reasoning. - Peter Jonsson; Christer Bäckström (AAAI/IAAI, Vol. 2, 1996)

Tractable Subclasses of the Point-Interval Algebra: A Complete Classification. - Peter Jonsson; Thomas Drakengren; Christer Bäckström (KR, 1996)

Towards a Complete Classification of Tractability in Allen's Algebra. - Thomas Drakengren; Peter Jonsson (IJCAI, 1997)

Twenty-One Large Tractable Subclasses of Allen's Algebra. - Thomas Drakengren; Peter Jonsson (Artif. Intell., 1997)

A Nonapproximability Result for Finite Function Generation. - Peter Jonsson (Inf. Process. Lett., 1997)

Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time. - Thomas Drakengren; Peter Jonsson (J. Artif. Intell. Res., 1997)

A Complete Classification of Tractability in RCC-5. - Peter Jonsson; Thomas Drakengren (J. Artif. Intell. Res., 1997)

A Complete Classification of Tractability in Allen's Algebra Relative to Subsets of Basic Relations. - Thomas Drakengren; Peter Jonsson (Artif. Intell., 1998)

State-Variable Planning Under Structural Restrictions: Algorithms and Complexity. - Peter Jonsson; Christer Bäckström (Artif. Intell., 1998)

A Unifying Approach to Temporal Constraint Reasoning. - Peter Jonsson; Christer Bäckström (Artif. Intell., 1998)

Tractable Plan Existence Does Not Imply Tractable Plan Generation. - Peter Jonsson; Christer Bäckström (Ann. Math. Artif. Intell., 1998)

Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems. - Peter Jonsson (Inf. Process. Lett., 1998)

Reasoning About Set Constraints Applied to Tractable Inference in Intuitionistic Logic. - Thomas Drakengren; Peter Jonsson (J. Log. Comput., 1998)

Exploiting Bipartiteness to Identify Yet Another Tractable Subclass of CSP. - Marcus Bjäreland; Peter Jonsson (CP, 1999)

Towards a Complete Classification of Tractability in Point Algebras for Nonlinear Time. - Mathias Broxvall; Peter Jonsson (CP, 1999)

Some Results on the Complexity of Planning with Incomplete Information. - Patrik Haslum; Peter Jonsson (ECP, 1999)

Efficient planning for a miniature assembly line. - Inger Klein; Peter Jonsson; Christer Bäckström (Artif. Intell. Eng., 1999)

Computational Complexity of Relating Time Points with Intervals. - Peter Jonsson; Thomas Drakengren; Christer Bäckström (Artif. Intell., 1999)

Strong bounds on the approximability of two Pspace-hard problems in propositional planning. - Peter Jonsson (Ann. Math. Artif. Intell., 1999)

On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction - Peter Jonsson; Paolo Liberatore (Electron. Colloquium Comput. Complex., 1999)

Disjunctive Temporal Reasoning in Partially Ordered Models of Time. - Mathias Broxvall; Peter Jonsson (AAAI/IAAI, 2000)

Planning with Reduced Operator Sets. - Patrik Haslum; Peter Jonsson (AIPS, 2000)

Some Observations on Durations, Scheduling and Allen's Algebra. - Ola Angelsmark; Peter Jonsson (CP, 2000)

Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints. - Mathias Broxvall; Peter Jonsson; Jochen Renz (CP, 2000)

Towards efficient universal planning: A randomized approach. - Peter Jonsson; Patrik Haslum; Christer Bäckström (Artif. Intell., 2000)

Building tractable disjunctive constraints. - David A. Cohen; Peter Jeavons 001; Peter Jonsson; Manolis Koubarakis (J. ACM, 2000)

Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights. - Peter Jonsson (Theor. Comput. Sci., 2000)

A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. - Andrei A. Krokhin; Peter Jeavons 001; Peter Jonsson (IJCAI, 2001)

The complexity of constraints on intervals and lengths - Andrei A. Krokhin; Peter Jeavons 001; Peter Jonsson (Electron. Colloquium Comput. Complex., 2001)

Counting Satisfying Assignments in 2-SAT and 3-SAT. - Vilhelm Dahllöf; Peter Jonsson; Magnus Wahlström (COCOON, 2002)

Determining the Number of Solutions to Binary CSP Instances. - Ola Angelsmark; Peter Jonsson; Svante Linusson; Johan Thapper (CP, 2002)

Finite Domain Constraint Satisfaction Using Quantum Computation. - Ola Angelsmark; Vilhelm Dahllöf; Peter Jonsson (MFCS, 2002)

An algorithm for counting maximum weighted independent sets and its applications. - Vilhelm Dahllöf; Peter Jonsson (SODA, 2002)

Extending the Point Algebra into the Qualitative Algebra. - Andrei A. Krokhin; Peter Jonsson (TIME, 2002)

Disjunctions, independence, refinements. - Mathias Broxvall; Peter Jonsson; Jochen Renz (Artif. Intell., 2002)

Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems. - Ola Angelsmark; Peter Jonsson (CP, 2003)

Point algebras for temporal reasoning: Algorithms and complexity. - Mathias Broxvall; Peter Jonsson (Artif. Intell., 2003)

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. - Andrei A. Krokhin; Peter Jeavons 001; Peter Jonsson (J. ACM, 2003)

The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups. - Gustav Nordh; Peter Jonsson (COCOON, 2004)

An Algebraic Approach to the Complexity of Propositional Circumscription. - Gustav Nordh; Peter Jonsson (LICS, 2004)

Complexity classification in qualitative temporal constraint reasoning. - Peter Jonsson; Andrei A. Krokhin (Artif. Intell., 2004)

Constraint Satisfaction Problems on Intervals and Length. - Andrei A. Krokhin; Peter Jeavons 001; Peter Jonsson (SIAM J. Discret. Math., 2004)

Algorithms for four variants of the exact satisfiability problem. - Vilhelm Dahllöf; Peter Jonsson; Richard Beigel (Theor. Comput. Sci., 2004)

The complexity of counting homomorphisms seen from the other side. - Víctor Dalmau; Peter Jonsson (Theor. Comput. Sci., 2004)

Recognizing frozen variables in constraint satisfaction problems. - Peter Jonsson; Andrei A. Krokhin (Theor. Comput. Sci., 2004)

Adding clauses to poor man's logic (without increasing the complexity). - Peter Jonsson (J. Appl. Non Class. Logics, 2005)

Counting models for 2SAT and 3SAT formulae. - Vilhelm Dahllöf; Peter Jonsson; Magnus Wahlström (Theor. Comput. Sci., 2005)

Computational Complexity of Temporal Constraint Problems. - Thomas Drakengren; Peter Jonsson (Handbook of Temporal Reasoning in Artificial Intelligence, 2005)

Approximability of Integer Programming with Generalised Constraints. - Peter Jonsson; Fredrik Kuivinen; Gustav Nordh (CP, 2006)

Generalised Integer Programming Based on Logically Defined Relations. - Peter Jonsson; Gustav Nordh (MFCS, 2006)

The Approximability of Three-valued MAX CSP. - Peter Jonsson; Mikael Klasson; Andrei A. Krokhin (SIAM J. Comput., 2006)

Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. - Peter Jonsson; Andrei A. Krokhin; Fredrik Kuivinen (CSR, 2007)

Bounded Tree-Width and CSP-Related Problems. - Tommy Färnqvist; Peter Jonsson (ISAAC, 2007)

The Maximum Solution Problem on Graphs. - Peter Jonsson; Gustav Nordh; Johan Thapper (MFCS, 2007)

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. - Peter Jonsson; Andrei A. Krokhin (J. Comput. Syst. Sci., 2007)

Introduction to the Maximum SolutionProblem. - Peter Jonsson; Gustav Nordh (Complexity of Constraints, 2008)

Approximability Distance in the Space of H-Colourability Problems - Tommy Färnqvist; Peter Jonsson; Johan Thapper (CoRR, 2008)

The approximability of MAX CSP with fixed-value constraints. - Vladimir G. Deineko; Peter Jonsson; Mikael Klasson; Andrei A. Krokhin (J. ACM, 2008)

Computational complexity of auditing finite attributes in statistical databases. - Peter Jonsson; Andrei A. Krokhin (J. Comput. Syst. Sci., 2008)

MAX ONES Generalized to Larger Domains. - Peter Jonsson; Fredrik Kuivinen; Gustav Nordh (SIAM J. Comput., 2008)

Approximability Distance in the Space of H-Colourability Problems. - Tommy Färnqvist; Peter Jonsson; Johan Thapper (CSR, 2009)

Approximability of the Maximum Solution Problem for Certain Families of Algebras. - Peter Jonsson; Johan Thapper (CSR, 2009)

Semilinear Program Feasibility. - Manuel Bodirsky; Peter Jonsson; Timo von Oertzen (ICALP (2), 2009)

Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts - Robert Engström; Tommy Färnqvist; Peter Jonsson; Johan Thapper (CoRR, 2009)

Properties of an Approximability-related Parameter on Circular Complete Graphs. - Robert Engström; Tommy Färnqvist; Peter Jonsson; Johan Thapper (Electron. Notes Discret. Math., 2009)

Hard constraint satisfaction problems have hard gaps at location 1. - Peter Jonsson; Andrei A. Krokhin; Fredrik Kuivinen (Theor. Comput. Sci., 2009)

Approximating integer programs with positive right-hand sides. - Peter Jonsson; Johan Thapper (Inf. Process. Lett., 2010)

Approximability of Clausal Constraints. - Peter Jonsson; Gustav Nordh (Theory Comput. Syst., 2010)

Retractions to Pseudoforests. - Tomás Feder; Pavol Hell; Peter Jonsson; Andrei A. Krokhin; Gustav Nordh (SIAM J. Discret. Math., 2010)

Limits for Compact Representation of Plans. - Christer Bäckström; Peter Jonsson (ICAPS, 2011)

Min CSP on Four Elements: Moving beyond Submodularity. - Peter Jonsson; Fredrik Kuivinen; Johan Thapper (CP, 2011)

Discrete-Time Temporal Reasoning with Horn DLRs. - Peter Jonsson; Tomas Lööw (IJCAI, 2011)

All PSPACE-Complete Planning Problems Are Equal but Some Are More Equal than Others. - Christer Bäckström; Peter Jonsson (SOCS, 2011)

The Complexity of Planning Revisited - A Parameterized Analysis. - Christer Bäckström; Yue Chen; Peter Jonsson; Sebastian Ordyniak; Stefan Szeider (AAAI, 2012)

Macros, Reactive Plans and Compact Representations. - Christer Bäckström; Anders Jonsson 001; Peter Jonsson (ECAI, 2012)

From Macro Plans to Automata Plans. - Christer Bäckström; Anders Jonsson 001; Peter Jonsson (ECAI, 2012)

Abstracting Abstraction in Search with Applications to Planning. - Christer Bäckström; Peter Jonsson (KR, 2012)

Abstracting Abstraction in Search II: Complexity Analysis. - Christer Bäckström; Peter Jonsson (SOCS, 2012)

Essential Convexity and Complexity of Semi-Algebraic Constraints - Manuel Bodirsky; Peter Jonsson; Timo von Oertzen (Log. Methods Comput. Sci., 2012)

Algorithms and Limits for Compact Plan Representations. - Christer Bäckström; Peter Jonsson (J. Artif. Intell. Res., 2012)

Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction. - Manuel Bodirsky; Peter Jonsson; Timo von Oertzen (J. Log. Comput., 2012)

When Acyclicity Is Not Enough: Limitations of the Causal Graph. - Anders Jonsson 001; Peter Jonsson; Tomas Lööw (ICAPS, 2013)

Parameterized Complexity and Kernel Bounds for Hard Planning Problems. - Christer Bäckström; Peter Jonsson; Sebastian Ordyniak; Stefan Szeider (CIAC, 2013)

Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction. - Peter Jonsson; Victor Lagerkvist; Gustav Nordh (CP, 2013)

Bridging the Gap Between Refinement and Heuristics in Abstraction. - Christer Bäckström; Peter Jonsson (IJCAI, 2013)

Fast Detection of Unsolvable Planning Instances Using Local Consistency. - Christer Bäckström; Peter Jonsson; Simon Ståhlberg (SOCS, 2013)

Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis. - Peter Jonsson; Victor Lagerkvist; Gustav Nordh; Bruno Zanuttini (SODA, 2013)

Computational complexity of linear constraints over the integers. - Peter Jonsson; Tomas Lööw (Artif. Intell., 2013)

A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond. - Christer Bäckström; Peter Jonsson (J. Artif. Intell. Res., 2013)

Oversubscription Planning: Complexity and Compilability. - Meysam Aghighi; Peter Jonsson (AAAI, 2014)

Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis. - Peter Jonsson; Victor Lagerkvist; Johannes Schmidt 001; Hannes Uppman (MFCS (2), 2014)

Affine Consistency and the Complexity of Semilinear Constraints. - Peter Jonsson; Johan Thapper (MFCS (2), 2014)

Limitations of acyclic causal graphs for planning. - Anders Jonsson 001; Peter Jonsson; Tomas Lööw (Artif. Intell., 2014)

Automaton Plans. - Christer Bäckström; Anders Jonsson 001; Peter Jonsson (J. Artif. Intell. Res., 2014)

Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs. - Meysam Aghighi; Peter Jonsson; Simon Ståhlberg (AAAI, 2015)

Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs. - Peter Jonsson; Victor Lagerkvist (CP, 2015)

Constraint Satisfaction Problems around Skolem Arithmetic. - Christian Glaßer; Peter Jonsson; Barnaby Martin (CoRR, 2015)

Maximum Pagenumber-k Subgraph is NP-Complete. - Peter Jonsson; Marco Kuhlmann (CoRR, 2015)

An Approximability-related Parameter on Graphs - Properties and Applications. - Robert Engström; Tommy Färnqvist; Peter Jonsson; Johan Thapper (Discret. Math. Theor. Comput. Sci., 2015)

A complete parameterized complexity analysis of bounded planning. - Christer Bäckström; Peter Jonsson; Sebastian Ordyniak; Stefan Szeider (J. Comput. Syst. Sci., 2015)

Parsing to Noncrossing Dependency Graphs. - Marco Kuhlmann; Peter Jonsson (Trans. Assoc. Comput. Linguistics, 2015)

Constructing NP-intermediate problems by blowing holes with parameters of various properties. - Peter Jonsson; Victor Lagerkvist; Gustav Nordh (Theor. Comput. Sci., 2015)

Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis. - Meysam Aghighi; Christer Bäckström; Peter Jonsson; Simon Ståhlberg (ECAI, 2016)

Upper and Lower Time and Space Bounds for Planning. - Christer Bäckström; Peter Jonsson (ECAI, 2016)

Finite Unary Relations and Qualitative Constraint Satisfaction. - Peter Jonsson (ECAI, 2016)

The Complexity of Phylogeny Constraint Satisfaction. - Manuel Bodirsky; Peter Jonsson; Van Trung Pham (STACS, 2016)

Refining complexity analyses in planning by exploiting the exponential time hypothesis. - Meysam Aghighi; Christer Bäckström; Peter Jonsson; Simon Ståhlberg (Ann. Math. Artif. Intell., 2016)

Constraint satisfaction and semilinear expansions of addition over the rationals and the reals. - Peter Jonsson; Johan Thapper (J. Comput. Syst. Sci., 2016)

The Reducts of the homogeneous Binary Branching C-Relation. - Manuel Bodirsky; Peter Jonsson; Van Trung Pham (J. Symb. Log., 2016)

Time Complexity of Constraint Satisfaction via Universal Algebra. - Peter Jonsson; Victor Lagerkvist; Biman Roy (MFCS, 2017)

An initial study of time complexity in infinite-domain constraint satisfaction. - Peter Jonsson; Victor Lagerkvist (Artif. Intell., 2017)

Time and Space Bounds for Planning. - Christer Bäckström; Peter Jonsson (J. Artif. Intell. Res., 2017)

A Model-Theoretic View on Qualitative Constraint Reasoning. - Manuel Bodirsky; Peter Jonsson (J. Artif. Intell. Res., 2017)

Strong partial clones and the time complexity of SAT problems. - Peter Jonsson; Victor Lagerkvist; Gustav Nordh; Bruno Zanuttini (J. Comput. Syst. Sci., 2017)

Circuit satisfiability and constraint satisfaction around Skolem Arithmetic. - Christian Glaßer; Peter Jonsson; Barnaby Martin (Theor. Comput. Sci., 2017)

The Complexity of Phylogeny Constraint Satisfaction Problems. - Manuel Bodirsky; Peter Jonsson; Van Trung Pham (ACM Trans. Comput. Log., 2017)

Novel Structural Parameters for Acyclic Planning Using Tree Embeddings. - Christer Bäckström; Peter Jonsson; Sebastian Ordyniak (IJCAI, 2018)

Classification Transfer for Qualitative Reasoning Problems. - Manuel Bodirsky; Peter Jonsson; Barnaby Martin; Antoine Mottet (IJCAI, 2018)

Why are CSPs Based on Partition Schemes Computationally Hard?. - Peter Jonsson; Victor Lagerkvist (MFCS, 2018)

Constants and finite unary relations in qualitative constraint reasoning. - Peter Jonsson (Artif. Intell., 2018)

On the Complexity of CCG Parsing. - Marco Kuhlmann; Giorgio Satta; Peter Jonsson (Comput. Linguistics, 2018)

Tractability conditions for numeric CSPs. - Peter Jonsson; Johan Thapper (Theor. Comput. Sci., 2018)

A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs. - Christer Bäckström; Peter Jonsson; Sebastian Ordyniak (IJCAI, 2019)

Lower Bounds and Faster Algorithms for Equality Constraints. - Peter Jonsson; Victor Lagerkvist (IJCAI, 2020)

Fine-Grained Complexity of Temporal Problems. - Konrad K. Dabrowski; Peter Jonsson; Sebastian Ordyniak; George Osipov (KR, 2020)

Disjunctive Temporal Problems under Structural Restrictions. - Konrad K. Dabrowski; Peter Jonsson; Sebastian Ordyniak; George Osipov (AAAI, 2021)

Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors. - Peter Jonsson; Victor Lagerkvist; Sebastian Ordyniak (CP, 2021)

Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms. - Peter Jonsson; Victor Lagerkvist; George Osipov (Artif. Intell., 2021)

Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics. - Christer Bäckström; Peter Jonsson; Sebastian Ordyniak (J. Artif. Intell. Res., 2021)

Computational Complexity of Computing Symmetries in Finite-Domain Planning. - Alexander Shleyfman; Peter Jonsson (J. Artif. Intell. Res., 2021)

The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems. - Peter Jonsson; Victor Lagerkvist; Johannes Schmidt 001; Hannes Uppman (Theor. Comput. Sci., 2021)

Fine-Grained Time Complexity of Constraint Satisfaction Problems. - Peter Jonsson; Victor Lagerkvist; Biman Roy (ACM Trans. Comput. Theory, 2021)

Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach. - Konrad K. Dabrowski; Peter Jonsson; Sebastian Ordyniak; George Osipov (AAAI, 2022)

A framework for analysing state-abstraction methods. - Christer Bäckström; Peter Jonsson (Artif. Intell., 2022)

Computational Short Cuts in Infinite Domain Constraint Satisfaction. - Peter Jonsson; Victor Lagerkvist; Sebastian Ordyniak (J. Artif. Intell. Res., 2022)

Structurally Restricted Fragments of Numeric Planning - a Complexity Analysis. - Alexander Shleyfman; Daniel Gnad 001; Peter Jonsson (AAAI, 2023)

Planning over Integers: Compilations and Undecidability. - Daniel Gnad 001; Malte Helmert; Peter Jonsson; Alexander Shleyfman (ICAPS, 2023)

Parameterized Complexity Classification for Interval Constraints. - Konrad K. Dabrowski; Peter Jonsson; Sebastian Ordyniak; George Osipov; Marcin Pilipczuk; Roohani Sharma (IPEC, 2023)

Almost Consistent Systems of Linear Equations. - Konrad K. Dabrowski; Peter Jonsson; Sebastian Ordyniak; George Osipov; Magnus Wahlström (SODA, 2023)

General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs. - Peter Jonsson; Victor Lagerkvist (Algorithmica, 2023)

Solving infinite-domain CSPs using the patchwork property. - Konrad K. Dabrowski; Peter Jonsson; Sebastian Ordyniak; George Osipov (Artif. Intell., 2023)

CSPs with Few Alien Constraints. - Peter Jonsson; Victor Lagerkvist; George Osipov (CP, 2024)

Algorithms and Complexity of Difference Logic. - Konrad K. Dabrowski; Peter Jonsson; Sebastian Ordyniak; George Osipov (CoRR, 2024)

Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings. - Konrad K. Dabrowski; Peter Jonsson; Sebastian Ordyniak; George Osipov; Magnus Wahlström (CoRR, 2024)

Complexity Classification Transfer for CSPs via Algebraic Products. - Manuel Bodirsky; Peter Jonsson; Barnaby Martin; Antoine Mottet; Zaneta Semanisinová (SIAM J. Comput., 2024)