Journal articles

To appear.
  1. Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, and Magnus Wahlström. Almost Consistent Systems of Linear Equations. To appear in ACM Transactions on Algorithms.
2024.
  1. Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, and Zaneta Semanisinová. Complexity Classification Transfer for CSPs via Algebraic Products. SIAM Journal on Computing 53(5):1293-1353, 2024.
2023.
  1. Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, and George Osipov: Solving Infinite-Domain CSPs using the Patchwork Property. Artificial Intelligence 317:103880, 2023.

  2. Peter Jonsson and Victor Lagerkvist: General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs. Algorithmica 85(1):188-215, 2023.
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