Journal articles

2022.
  1. Peter Jonsson, Victor Lagerkvist, and Sebastian Ordyniak: Computational Short Cuts in Infinite Domain Constraint Satisfaction. Journal of Artificial Intelligence Research 75:793-831, 2022.

  2. Christer Bäckström and Peter Jonsson: A Framework for Analysing State-Abstraction Methods. Artificial Intelligence 302:103608, 2022.

2021.
  1. Peter Jonsson, Victor Lagerkvst, Johannes Schmidt, and Hannes Uppman: The Exponential-Time Hypothesis and the Relative Complexity of Optimization and Logical Reasoning Problems. Theoretical Computer Science 892:1-24, 2021.

  2. Peter Jonsson, Victor Lagerkvst, and George Osipov: Acyclic Orders, Partition Schemes and CSPs: Unified Hardness Proofs and Improved Algorithms. Artificial Intelligence 296:103505, 2021.

  3. Alexander Shleyfman and Peter Jonsson: Computational Complexity of Computing Symmetries in Finite-Domain Planning. Journal of Artifical Intelligence Research 70:1183-1221, 2021. link

  4. Peter Jonsson, Victor Lagerkvst, and Biman Roy: Fine-Grained Time Complexity of Constraint Satisfaction Problems. ACM Transactions on Computation Theory 13(1):2(1)-2(32), 2021. link

  5. Christer Bäckström, Peter Jonsson, and Sebastian Ordyniak: Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics. Journal of Artificial Intelligence Research 70:169-204, 2021. link
2018.
  1. Marco Kuhlmann, Giorgio Satta, and Peter Jonsson: On the Complexity of CCG Parsing. Computational Linguistics 44(3), 2018. link

  2. Peter Jonsson and Johan Thapper: Tractability Conditions for Numeric CSPs. Theoretical Computer Science 715:21-34, 2018. report

  3. Peter Jonsson: Constants and Finite Unary Relations in Qualitative Constraint Reasoning. Artificial Intelligence 257:1-23, 2018. pdf

2017
  1. Christian Glaßer, Peter Jonsson, and Barnaby Martin: Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic. Theoretical Computer Science 703:18-36, 2017. pdf

  2. Christer Bäckström and Peter Jonsson: Time and Space Bounds for Planning. Journal of Artificial Intelligence Research 60:595-638, 2017. link

  3. Manuel Bodirsky, Peter Jonsson, and Trung Van Pham: Complexity of Phylogeny Constraint Satisfaction Problems. ACM Transactions on Computational Logic 18(3) 23:1-23:42, 2017. report version

  4. Manuel Bodirsky and Peter Jonsson: A Model-theoretical View on Qualitative Constraint Reasoning. Journal of Artificial Intelligence Research 58:339-385, 2017. link

  5. Peter Jonsson and Victor Lagerkvist: An Initial Study of Time Complexity in Infinite-domain Constraint Satisfaction. Artificial Intelligence 245:115-133, 2017. pdf

  6. Peter Jonsson, Victor Lagerkvist, Gustav Nordh, and Bruno Zanuttini: Strong Partial Clones and the Time Complexity of SAT Problems. Journal of Computer and System Sciences 84:52-78, 2017. pdf

2016
  1. Manuel Bodirsky, Peter Jonsson, and Trung Van Pham: The Reducts of the Homogeneous Binary Branching C-relation. Journal of Symbolic Logic 81(4):1255-1297, 2016. report version

  2. Meysam Aghighi, Christer Bäckström, Peter Jonsson, and Simon Ståhlberg: Refining Complexity Analyses in Planning by Exploiting the Exponential Time Hypothesis. Annals of Mathematics and Artificial Intelligence 78(2):157-175, 2016. link

  3. Peter Jonsson and Johan Thapper: Constraint Satisfaction and Semilinear Expansions of Addition over the Rationals and the Reals. Journal of Computer and System Sciences 82(5):912-928, 2016. report version

2015
  1. Marco Kuhlmann and Peter Jonsson: Parsing to Noncrossing Dependency Graphs. Transactions of the Association for Computational Linguistics 3:559-570, 2015. pdf

  2. Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider: A Complete Parameterized Complexity Analysis of Bounded Planning. Journal of Computer and System Sciences 81(7):1311-1332, 2015. report version

  3. Peter Jonsson, Victor Lagerkvist, and Gustav Nordh: Constructing NP-intermediate Problems by Blowing Holes with Parameters of Various Properties. Theoretical Computer Science 581:67-82, 2015. pdf

  4. Robert Engström, Tommy Färnqvist, Peter Jonsson, and Johan Thapper: An Approximability-related Parameter on Graphs - Properties and Applications. Discrete Mathematics and Theoretical Computer Science. 17(1):33-66, 2015. link

2014
  1. Christer Bäckström, Anders Jonsson, and Peter Jonsson: Automaton Plans. Journal of Artificial Intelligence Research 51:255-291, 2014. link

  2. Anders Jonsson, Peter Jonsson, and Tomas Lööw: Limitations of Acyclic Causal Graphs for Planning. Artificial Intelligence 210:36-55, 2014. pdf
2013
  1. Christer Bäckström and Peter Jonsson: A Refined View of Causal Graphs and Component Sizes: SP-closed Graph Classes and Beyond. Journal of Artificial Intelligence Research 47:575-611, 2013. link

  2. Peter Jonsson and Tomas Lööw: Computational Complexity of Linear Constraints over the Integers. Artificial Intelligence 195:44-62, 2013. pdf
2012
  1. Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen: Essential Convexity and Complexity of Semi-algebraic Constraints. Logical Methods in Computer Science 8(4):article 5. link

  2. Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen: Horn versus Full First-order: Complexity Dichotomies in Algebraic Constraint Satisfaction. Journal of Logic and Computation 22:643-660, 2012. pdf

  3. Christer Bäckström and Peter Jonsson: Algorithms and Limits for Compact Plan Representation. Journal of Artificial Intelligence Research 44:141-177, 2012. link
2010
  1. Peter Jonsson and Johan Thapper: Approximability of Integer Programs with Positive Right-hand Sides. Information Processing Letters 110(10):351-355, 2010. pdf

  2. Tomás Feder, Pavol Hell, Peter Jonsson, Andrei Krokhin, and Gustav Nordh: Retractions to Pseudoforests. SIAM Journal on Discrete Mathematics 24(1):101-112, 2010. pdf

  3. Peter Jonsson and Gustav Nordh: Approximability of Clausal Constraints. Theory of Computing Systems 46(2):370-395, 2010. pdf

2009
  1. Robert Engström, Tommy Färnqvist, Peter Jonsson, and Johan Thapper: Properties of an Approximability-related Parameter on Circular Complete Graphs. Electronic Notes in Discrete Mathematics 35:115-120, 2009. pdf

  2. Peter Jonsson, Andrei Krokhin, and Fredrik Kuivinen: Hard Constraint Satisfaction Problems have Hard Gaps at Location 1. Theoretical Computer Science 410(38-40):3856-3874, 2009. pdf

2008
  1. Vladimir Deineko, Peter Jonsson, Mikael Klasson, and Andrei Krokhin: The Approximability of Max CSP with Fixed-value Constraints. Journal of the ACM 55:article 4, 2008. pdf

  2. Peter Jonsson and Andrei Krokhin: Computational Complexity of Auditing Finite Attributes in Statistical Databases. Journal of Computer and System Sciences 74:898-909, 2008. pdf

  3. Peter Jonsson, Fredrik Kuivinen, and Gustav Nordh: Max Ones Generalized to Larger Domains. SIAM Journal on Computing 38(1):329-365, 2008. pdf

2007
  1. Peter Jonsson and Andrei Krokhin: Maximum H-colourable Subdigraphs and Constraint Optimization with Arbitrary Weights. Journal of Computer and System Sciences 73(5):691-702, 2007. pdf

2006
  1. Peter Jonsson, Mikael Klasson, and Andrei Krokhin: The Approximability of Three-valued Max CSP. SIAM Journal on Computing 35(3):1329-1349, 2006. postscript

2005
  1. Peter Jonsson: Adding Clauses to Poor Man's Logic (without Increasing the Complexity). Journal of Applied Non-Classical Logics 15(3):341-357, 2005. postscript

  2. Vilhelm Dahllöf, Peter Jonsson, and Magnus Wahlström: Counting Models for 2SAT and 3SAT Formulae. Theoretical Computer Science 332(1-3):265-291, 2005. postscript / note

2004
  1. Peter Jonsson and Andrei Krokhin: Recognizing Frozen Variables in Constraint Satisfaction Problems. Theoretical Computer Science 329(1-3):93-113, 2004. postscript

  2. Víctor Dalmau and Peter Jonsson: The Complexity of Counting Homomorphisms Seen from the Other Side. Theoretical Computer Science 329(1-3):315-323, 2004. postscript

  3. Peter Jonsson and Andrei Krokhin: Complexity Classification in Qualitative Temporal Constraint Reasoning. Artificial Intelligence 160(1-2):35-51, 2004. postscript

  4. Vilhelm Dahllöf, Peter Jonsson, and Richard Beigel: Algorithms for Four Variants of the Exact Satisfiability Problem. Theoretical Computer Science 320(2-3):373-394, 2004. postscript / note

  5. Andrei Krokhin, Peter Jeavons, and Peter Jonsson: Constraint Satisfaction Problems on Intervals and Lengths. SIAM Journal on Discrete Mathematics 17(3):453-477, 2004. postscript

2003
  1. Mathias Broxvall and Peter Jonsson: Point Algebras for Temporal Reasoning: Algorithms and Complexity. Artificial Intelligence 149(2):179-220, 2003. postscript

  2. Andrei Krokhin, Peter Jeavons, and Peter Jonsson: Reasoning about Temporal Relations: The Tractable Subalgebras of Allen's Interval Algebra. Journal of the ACM 50(5):591-640, 2003. postscript

2002
  1. Mathias Broxvall, Peter Jonsson, and Jochen Renz: Disjunctions, Independence, Refinements. Artificial Intelligence 140(1-2):153-173, 2002. postscript

2000
  1. David Cohen, Peter Jeavons, Peter Jonsson, and Manolis Koubarakis: Building Tractable Disjunctive Constraints. Journal of the ACM 47(5):826-853, 2000. postscript

  2. Peter Jonsson: Boolean Constraint Satisfaction: Complexity Results for Optimization Problems with Arbitrary Weights. Theoretical Computer Science 244(1-2):189-203, 2000. postscript

  3. Peter Jonsson, Patrik Haslum, and Christer Bäckström: Towards Efficient Universal Planning—A Randomized Approach. Artificial Intelligence 117(1):1-29, 2000. postscript

1999
  1. Peter Jonsson: Strong Bounds on the Approximability of Two PSPACE-Hard Problems in Propositional Planning. Annals of Mathematics and Artificial Intelligence 26:133-147, 1999. postscript

  2. Peter Jonsson, Thomas Drakengren, and Christer Bäckström: Computational Complexity of Relating Time Points with Intervals. Artificial Intelligence 109(1-2):273-295, 1999. postscript

  3. Inger Klein, Peter Jonsson, and Christer Bäckström: Efficient Planning for a Miniature Assembly Line. Artificial Intelligence in Engineering 13(1):69-81, 1999.

1998
  1. Thomas Drakengren and Peter Jonsson: Reasoning About Set Constraints Applied to Tractable Inference in Intuitionistic Logic. Journal of Logic and Computation 8(6):855-875, 1998. postscript

  2. Thomas Drakengren and Peter Jonsson: A Complete Classification of Tractability in Allen's Algebra Relative to Subsets of Basic Relations. Artificial Intelligence 106(2):205-219, 1998. postscript

  3. Peter Jonsson: Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems. Information Processing Letters. 68(5):249-253, 1998. postscript

  4. Peter Jonsson and Christer Bäckström: Tractable Plan Existence Does Not Imply Tractable Plan Generation. Annals of Mathematics and Artificial Intelligence 22(3-4):281-296, 1998. postscript

  5. Peter Jonsson and Christer Bäckström: A Unifying Approach to Temporal Constraint Reasoning. Artificial Intelligence 102(1):143-155, 1998. postscript

  6. Peter Jonsson and Christer Bäckström: State-Variable Planning Under Structural Restrictions: Algorithms and Complexity. Artificial Intelligence 100(1-2):125-176, 1998. postscript

1997
  1. Peter Jonsson: A Nonapproximability Result for Finite Function Generation. Information Processing Letters 63:143-145, 1997. postscript

  2. Thomas Drakengren and Peter Jonsson: Twenty-One Large Tractable Subclasses of Allen's Algebra. Artificial Intelligence 93:297-319, 1997. postscript

  3. Thomas Drakengren and Peter Jonsson: Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time. Journal of Artificial Intelligence Research 7:25-45, 1997. paper

  4. Peter Jonsson and Thomas Drakengren: A Complete Classification of Tractability in RCC-5. Journal of Artificial Intelligence Research 6:211-221, 1997. paper