Journal articles
To appear.
-
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.
-
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.
-
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, and George Osipov:
Solving Infinite-Domain CSPs using the Patchwork Property. Artificial Intelligence 317:103880, 2023.
-
Peter Jonsson and Victor Lagerkvist:
General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs. Algorithmica 85(1):188-215, 2023.
2022.
-
Peter Jonsson, Victor Lagerkvist, and Sebastian Ordyniak:
Computational Short Cuts in Infinite Domain Constraint Satisfaction.
Journal of Artificial Intelligence Research 75:793-831, 2022.
-
Christer Bäckström and Peter Jonsson:
A Framework for Analysing State-Abstraction Methods.
Artificial Intelligence 302:103608, 2022.
2021.
-
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.
-
Peter Jonsson, Victor Lagerkvst, and George Osipov:
Acyclic Orders, Partition Schemes and CSPs: Unified Hardness Proofs and Improved Algorithms.
Artificial Intelligence 296:103505, 2021.
-
Alexander Shleyfman and Peter Jonsson:
Computational Complexity of Computing Symmetries in Finite-Domain Planning.
Journal of Artifical Intelligence Research 70:1183-1221, 2021.
link
-
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
-
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.
-
Marco Kuhlmann, Giorgio Satta, and Peter Jonsson:
On the Complexity of CCG Parsing.
Computational Linguistics 44(3), 2018.
link
-
Peter Jonsson and Johan Thapper:
Tractability Conditions for Numeric CSPs.
Theoretical Computer Science 715:21-34, 2018.
report
-
Peter Jonsson:
Constants and Finite Unary Relations in Qualitative Constraint Reasoning.
Artificial Intelligence 257:1-23, 2018.
pdf
2017
-
Christian Glaßer, Peter Jonsson, and Barnaby Martin:
Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic.
Theoretical Computer Science 703:18-36, 2017.
pdf
-
Christer Bäckström and Peter Jonsson:
Time and Space Bounds for Planning.
Journal of Artificial Intelligence Research 60:595-638, 2017.
link
-
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
-
Manuel Bodirsky and Peter Jonsson:
A Model-theoretical View on Qualitative Constraint Reasoning.
Journal of Artificial Intelligence Research 58:339-385, 2017.
link
-
Peter Jonsson and Victor Lagerkvist:
An Initial Study of Time Complexity in Infinite-domain
Constraint Satisfaction.
Artificial Intelligence 245:115-133, 2017.
pdf
-
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
-
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
-
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
-
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
-
Marco Kuhlmann and Peter Jonsson: Parsing to Noncrossing Dependency Graphs.
Transactions of the Association for Computational Linguistics 3:559-570, 2015.
pdf
-
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
-
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
-
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
-
Christer Bäckström, Anders Jonsson, and Peter Jonsson:
Automaton Plans.
Journal of Artificial Intelligence Research 51:255-291, 2014.
link
-
Anders Jonsson, Peter Jonsson, and Tomas Lööw:
Limitations of Acyclic Causal Graphs for Planning.
Artificial Intelligence 210:36-55, 2014.
pdf
2013
-
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
-
Peter Jonsson and Tomas Lööw:
Computational Complexity of Linear Constraints over the Integers.
Artificial Intelligence 195:44-62, 2013.
pdf
2012
-
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
-
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
-
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
-
Peter Jonsson and Johan Thapper:
Approximability of Integer Programs with Positive Right-hand Sides.
Information Processing Letters 110(10):351-355, 2010.
pdf
-
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
-
Peter Jonsson and Gustav Nordh:
Approximability of Clausal Constraints.
Theory of Computing Systems 46(2):370-395, 2010.
pdf
2009
-
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
-
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
-
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
-
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
-
Peter Jonsson, Fredrik Kuivinen, and Gustav Nordh:
Max Ones Generalized to Larger Domains.
SIAM Journal on Computing 38(1):329-365, 2008.
pdf
2007
-
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
-
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
-
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
-
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
-
Peter Jonsson and Andrei Krokhin:
Recognizing Frozen Variables in Constraint Satisfaction Problems.
Theoretical Computer Science 329(1-3):93-113, 2004.
postscript
-
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
-
Peter Jonsson and Andrei Krokhin:
Complexity Classification in Qualitative
Temporal Constraint Reasoning.
Artificial Intelligence 160(1-2):35-51, 2004. postscript
-
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
-
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
-
Mathias Broxvall and Peter Jonsson:
Point Algebras for Temporal Reasoning: Algorithms and Complexity.
Artificial Intelligence 149(2):179-220, 2003.
postscript
-
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
-
Mathias Broxvall, Peter Jonsson, and Jochen Renz:
Disjunctions, Independence, Refinements.
Artificial Intelligence 140(1-2):153-173, 2002.
postscript
2000
-
David Cohen, Peter Jeavons, Peter Jonsson, and Manolis Koubarakis:
Building Tractable Disjunctive Constraints.
Journal of the ACM 47(5):826-853, 2000.
postscript
-
Peter Jonsson:
Boolean Constraint Satisfaction: Complexity Results for Optimization
Problems with Arbitrary Weights.
Theoretical Computer Science 244(1-2):189-203, 2000.
postscript
-
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
-
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
-
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
-
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
-
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
-
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
-
Peter Jonsson:
Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems.
Information Processing Letters. 68(5):249-253, 1998.
postscript
-
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
-
Peter Jonsson and Christer Bäckström:
A Unifying Approach to Temporal Constraint Reasoning.
Artificial Intelligence 102(1):143-155, 1998.
postscript
-
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
-
Peter Jonsson:
A Nonapproximability Result for Finite Function Generation.
Information Processing Letters 63:143-145, 1997.
postscript
-
Thomas Drakengren and Peter Jonsson:
Twenty-One Large Tractable Subclasses of Allen's Algebra.
Artificial Intelligence 93:297-319, 1997.
postscript
-
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
-
Peter Jonsson and Thomas Drakengren:
A Complete Classification of Tractability in RCC-5.
Journal of Artificial Intelligence Research 6:211-221, 1997.
paper