Conferences & Workshops
2016

Peter Jonsson:
Finite Unary Relations and Qualitative Constraint
Satisfaction.
In Proceedings of the 22nd Europen Conference on Artificial Intelligence (ECAI2016), The Hague, Holland. To appear.

Christer Bäckström and Peter Jonsson:
Upper and Lower Time and Space Bounds for Planning.
In Proceedings of the 22nd Europen Conference on Artificial Intelligence (ECAI2016), The Hague, Holland. To appear.

Meysam Aghighi, Christer Bäckström, Peter Jonsson, and Simon Ståhlberg:
Analysing Approximability and Heuristics in Planning
Using the Exponentialtime Hypothesis.
In Proceedings of the 22nd Europen Conference on Artificial Intelligence (ECAI2016), The Hague, Holland. To appear.

Christian Glaßer, Peter Jonsson, and Barnaby Martin:
Circuit Satisfiability and Constraint Satisfaction Problems around Skolem Arithmetic.
In Proceedings of the 12th Conference on Computability in Europe (CiE2016), pp. 323332. Paris, France, Jul, 2016. pdf

Manuel Bodirsky, Peter Jonsson, and Trung Van Pham:
The Complexity of Phylogeny Constraint Satisfaction.
In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS2016), pp. 20:120:13. Orléans, France, Feb, 2016. pdf
2015

Peter Jonsson and Victor Lagerkvist:
Upper and Lower Bounds on the Time Complexity of Infinitedomain CSPs.
In Proceedings of the 21st International Conference on Principles and
Practice of Constraint Programming (CP2015), pp. 183199. Cork, Ireland, AugSep, 2015. pdf

Meysam Aghighi, Peter Jonsson, and Simon Ståhlberg:
Tractable Costoptimal Planning over Restricted Polytree Causal Graphs.
In Proceedings of the 29th AAAI
Conference on Artificial Intelligence (AAAI2015), pp. 32253231.
Austin, Texas, USA, Jan, 2015. link
2014

Peter Jonsson, Victor Lagerkvist, Johannes Schmidt, and Hannes Uppman:
Relating the Time Complexity of Optimization Problems in Light of the Exponentialtime Hypothesis.
In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS2014), pp. 408419.
Budapest, Hungary, Aug, 2014. pdf

Peter Jonsson and Johan Thapper:
Affine Consistency and the Complexity of Semilinear Constraints.
In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS2014), pp. 420431.
Budapest, Hungary, Aug, 2014. pdf

Meysam Aghighi and Peter Jonsson:
Oversubscription Planning: Complexity and Compilability.
In Proceedings of the 28th AAAI
Conference on Artificial Intelligence (AAAI2014),
pp. 22212227.
Quebéc City, Quebéc, Canada, Jul, 2014.
link
2013

Peter Jonsson, Victor Lagerkvist, and Gustav Nordh:
Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction.
In Proceedings of the 19th International Conference on Principles and
Practice of Constraint Programming (CP2013), pp. 398414.
Uppsala, Sweden, Sep, 2013. pdf

Christer Bäckström and Peter Jonsson:
Bridging the Gap Between Refinement and Heuristics in Abstraction.
In Proceedings of the 23rd International Joint
Conference on Artificial Intelligence (IJCAI2013), pp. 22612267.
Beijing, China, Aug, 2013. pdf

Christer Bäckström, Peter Jonsson, and Simon Ståhlberg:
Fast Detection of Unsolvable Planning Instances Using Local Consistency.
In Proceedings of the 6th Annual Symposium on Combinatorial Search (SoCS2013), 2937.
Leavenworth, WA, USA, Jul, 2013.
pdf

Anders Jonsson, Peter Jonsson, and Tomas Lööw:
When Acyclicity is Not Enough: Limitations of the Causal Graph.
In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS2013). Rome, Italy, Jun, 2013.
pdf

Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider:
Parameterized Complexity and Kernel Bounds for Hard Planning Problems.
In Proceedings of the 8th International Conference on Algorithms and
Complexity (CIAC2013), pp. 1324.
Barcelona, Spain, May, 2013.
pdf

Peter Jonsson, Victor Lagerkvist, Gustav Nordh, and Bruno Zanuttini:
Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis.
In Proceedings of the 24th Annual ACMSIAM Symposium on Discrete Algorithms
(SODA2013), pp. 12641277. New Orleans, LA, USA, Jan, 2013.
pdf
2012

Christer Bäckström, Anders Jonsson, and Peter Jonsson:
From Macro Plans to Automata Plans.
In Proceedings of the 20th European
Conference on Artificial Intelligence (ECAI2012), pp. 9196.
Montpellier, France, Aug, 2012.
pdf

Christer Bäckström, Anders Jonsson, and Peter Jonsson:
Macros, Reactive Plans and Compact Representations.
In Proceedings of the 20th European
Conference on Artificial Intelligence (ECAI2012), pp. 8590.
Montpellier, France, Aug, 2012.
pdf

Christer Bäckström and Peter Jonsson:
Abstracting Abstraction in Search II: Complexity Analysis.
In Proceedings of the 5th Annual Symposium on Combinatorial Search (SoCS2012), pp. 1017. Niagara Falls, Canada, Jul, 2012. pdf

Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider:
The Complexity of Planning Revisited  A Parameterized Analysis.
In Proceedings of the 26th (US) National
Conference on Artificial Intelligence (AAAI2012), pp. 17351741.
Toronto, Canada, Jul, 2012.
pdf

Christer Bäckström and Peter Jonsson:
Abstracting Abstraction in Search with Applications to Planning.
In Proceedings of the 13th International Conference on
Principles of Knowledge Representation and Reasoning (KR2012), pp. 446456. Rome, Italy, Jun, 2012.
pdf
2011

Peter Jonsson, Fredrik Kuivinen, and Johan Thapper:
Min CSP on Four Elements: Moving Beyond Submodularity.
In Proceedings of the 17th International Conference on Principles and
Practice of Constraint Programming (CP2011), pp. 438453.
Perugia, Italy, Sep, 2011.
pdf

Christer Bäckström and Peter Jonsson:
All PSPACEcomplete Planning Problems are Equal but some are more Equal than Others.
In Proceedings of the 4th Annual Symposium on Combinatorial Search (SoCS2011), pp. 1017. Barcelona, Spain, Jul, 2011.
pdf

Peter Jonsson and Tomas Lööw:
Discretetime Temporal Reasoning with Horn DLRs.
In Proceedings of the 22nd International Joint
Conference on Artificial Intelligence (IJCAI2011),
pp. 931936. Barcelona, Spain, Jul, 2011.
pdf

Christer Bäckström and Peter Jonsson:
Limits for Compact Representations of Plans.
In Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS2011), pp. 1825. Freiburg, Germany, Jun, 2011.
pdf
2009

Peter Jonsson and Johan Thapper:
Approximability of the Maximum Solution Problem for Certain Families of Algebras.
In Proceedings of the 4th International Computer Science Symposium in Russia (CSR2009), pp. 215226, Novosibirsk, Russia, Aug, 2009. pdf

Tommy Färnqvist, Peter Jonsson, and Johan Thapper:
Approximability Distance in the Space of HColourability Problems.
In Proceedings of the 4th International Computer Science Symposium in Russia (CSR2009), pp. 92104, Novosibirsk, Russia, Aug, 2009.
pdf

Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen:
Semilinear Program Feasibility.
In Proceedings of the 36th International Colloquium on Automata, Languages, and
Programming (ICALP2009), pp. 7990, Rhodes, Greece, Jul, 2009.
2007

Tommy Färnqvist and Peter Jonsson:
Bounded Treewidth and CSPrelated Problems.
In Proceedings of the 18th International Symposium
on Algorithms and Computation (ISAAC2007), pp. 632643,
Sendai, Japan, Dec, 2007. pdf

Peter Jonsson, Andrei Krokhin, and Fredrik Kuivinen:
Ruling out Polynomialtime Approximation Schemes for Hard Constraint Satisfaction Problems.
In Proceedings of the 2nd International Computer Science Symposium in Russia (CSR2007), pp. 182193,
Ekaterinburg, Russia, Sep, 2007. pdf

Peter Jonsson, Gustav Nordh, and Johan Thapper:
The Maximum Solution Problem on Graphs.
In Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS2007), pp. 228239,
Ceský Krumlov, Czech Republic, Aug, 2007. pdf
2006

Peter Jonsson, Fredrik Kuivinen, and Gustav Nordh:
Approximability of Integer Programming with Generalised Constraints.
In Proceedings of the 12th International Conference on Principles and
Practice of Constraint Programming (CP2006), pp. 256270, Nantes, France, Sep, 2006.
postscript (report version)

Peter Jonsson and Gustav Nordh:
Generalised Integer Programming Based on Logically Defined Relations.
In Proceedings of the 31st International Symposium on Mathematical
Foundations of Computer Science (MFCS2006), pp. 549560, Stará Lesná, Slovakia, AugSep, 2006. pdf
2005

Vladimir Deineko, Peter Jonsson, Mikael Klasson, and Andrei Krokhin:
Supermodularity on Chains and Complexity of Maximum Constraint Satisfaction Problems.
In Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroCOMB2005), pp. 5156, Berlin, Germany, Sep, 2005. postscript
2004

Gustav Nordh and Peter Jonsson:
The Complexity of Counting Solutions to Systems of Equations Over Finite Semigroups.
In Proceedings of the 10th Annual International Computing and
Combinatorics Conference (COCOON2004), pp. 370379, Jeju Island, Korea, Aug, 2004. postscript

Gustav Nordh and Peter Jonsson:
An Algebraic Approach to the Complexity of Propositional Circumscription.
In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS2004), pp. 367376, Turku, Finland, Jul, 2004.
postscript
2003

Ola Angelsmark and Peter Jonsson:
Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems.
In Proceedings of the 9th International Conference on Principles and
Practice of Constraint Programming (CP2003), pp. 8195, Kinsale, County Cork, Ireland, SepOct, 2003.
postscript
2002

Ola Angelsmark, Peter Jonsson, Svante Linusson, and Johan Thapper:
Determining the Number of Solutions to Binary CSP Instances.
In Proceedings of the 8th International Conference on Principles and
Practice of Constraint Programming (CP2002), pp. 327340, Ithaca, NY, USA, Sep, 2002.
postscript

Ola Angelsmark, Vilhelm Dahllöf, and Peter Jonsson:
Finite Domain Constraint Satisfaction Using Quantum Computation.
In Proceedings of the 27th International Symposium on Mathematical
Foundations of Computer Science (MFCS2002), pp. 93103, WarsawOtwock, Poland, Aug, 2002.
postscript

Vilhelm Dahllöf, Peter Jonsson, and Magnus Wahlström:
Counting Satisfying Assignments in 2SAT and 3SAT.
In Proceedings of the 8th Annual International Computing and
Combinatorics Conference (COCOON2002), pp. 535543, Singapore, Aug, 2002.
postscript

Andrei Krokhin and Peter Jonsson: Extending the Point Algebra
into the Qualitative Algebra.
In Proceedings of the 9th International Symposium on Temporal
Representation and Reasoning (TIME2002), pp. 2835, Manchester, UK,
Jul, 2002.
postscript

Andrei Krokhin, Peter Jeavons, and Peter Jonsson: The Complexity of
Constraints on Intervals and Lengths.
In Proceedings of the 19th International Symposium on Theoretical
Aspects of Computer Science (STACS2002), pp. 443454, Antibes
JuanlesPins, France, Mar, 2002.
postscript

Vilhelm Dahllöf and Peter Jonsson:
An Algorithm for Counting Maximum Weighted Independent Sets and its
Applications.
In Proceedings of the 13th Annual ACMSIAM Symposium on Discrete Algorithms
(SODA2002), pp. 292298, San Francisco, CA, USA, Jan, 2002.
postscript
2001

Andrei Krokhin, Peter Jeavons, and Peter Jonsson:
A Complete Classification of Complexity in Allen's Algebra in the
Presence of a NonTrivial Basic Relation.
In Proceedings of the 17th International Joint
Conference on Artificial Intelligence (IJCAI01),
pp. 8388, Seattle, WA, USA, Aug, 2001.
postscript
2000

Mathias Broxvall, Peter Jonsson, and Jochen Renz:
Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints.
In Proceedings of the 6th International
Conference on Principles and Practice of Constraint
Programming (CP2000), pp. 114127, Singapore, Sep, 2000.
postscript

Ola Angelsmark and Peter Jonsson:
Some Observations on Durations, Scheduling and Allen's Algebra.
In Proceedings of the 6th International
Conference on Principles and Practice of Constraint
Programming (CP2000), pp. 484488, Singapore, Sep, 2000.
postscriptlong version

Mathias Broxvall and Peter Jonsson:
Disjunctive Temporal Reasoning in Partially Ordered Time Structures.
In Proceedings of the 17th (US) National
Conference on Artificial Intelligence (AAAI2000),
pp. 464469, Austin, TX, USA, JulAug, 2000.
postscript

Patrik Haslum and Peter Jonsson:
Planning with Reduced Operator Sets.
In Proceedings of the 5th International
Conference on Artificial Intelligence Planning and Scheduling (AIPS2000), pp. 150158, Breckenridge, CO, USA, Apr, 2000.
postscript
1999

Mathias Broxvall and Peter Jonsson:
Towards a Complete Classification of Tractability in Point Algebras for
Nonlinear Time.
In Proceedings of the 5th International
Conference on Principles and Practice of Constraint
Programming (CP99), pp. 129143, Alexandria, VA, USA, Oct, 1999.
postscript

Marcus Bjäreland and Peter Jonsson:
Exploiting Bipartiteness to Identify Yet Another Tractable Subclass of CSP.
In Proceedings of the 5th International
Conference on Principles and Practice of Constraint Programming (CP99), pp. 118128, Alexandria, VA, USA, Oct, 1999.
postscript

Patrik Haslum and Peter Jonsson:
Some Results on the Complexity of Planning with Incomplete Information.
In Proceedings of the 5th European
Conference on Planning (ECP99), Durham, UK, Sep, 1999.
postscript
1997

Thomas Drakengren and Peter Jonsson:
Towards a Complete Classification of Tractability in Allen's Algebra.
In Proceedings of the 15th International Joint
Conference on Artificial Intelligence (IJCAI97), pp. 14661471, Nagoya, Japan, Aug, 1997.
postscript
1996

Inger Klein, Peter Jonsson, and Christer Bäckström:
Automatic Synthesis of Control Programs in
Polynomial Time for an Assembly Line.
In Proceedings of the IEEE Conference on Decision
and Control (CDC96), Kobe, Japan, Dec, 1996.
postscript

Peter Jonsson, Thomas Drakengren, and Christer Bäckström:
Tractable Subclasses of the PointInterval Algebra:
A Complete Classification.
In Proceedings of the 5th International Conference on
Principles on Knowledge Representation and Reasoning (KR96), pp. 352363, Cambridge, MA, USA, Oct, 1996.
note

Thomas Drakengren and Peter Jonsson:
Tractable Subclasses of Allen's Interval Algebra: Preliminary Report.
In Proceedings of the 13th (US) National Conference on
Artificial Intelligence (AAAI96), pp. 389394, Portland, OR, USA, Aug, 1996. postscript

Peter Jonsson and Christer Bäckström:
A LinearProgramming Approach to Temporal Reasoning.
In Proceedings of the 13th (US) National Conference on
Artificial Intelligence (AAAI96), pp. 12351240, Portland, OR, USA, Aug, 1996.
postscript

Peter Jonsson and Christer Bäckström:
On the Size of Reactive Plans.
In Proceedings of the 13th (US) National Conference on
Artificial Intelligence (AAAI96), pp. 11821187, Portland, OR, USA, Aug, 1996.
postscript

Peter Jonsson and Christer Bäckström:
Tractable Plan Existence Does Not Imply Tractable
Plan Generation.
In 4th International Symposium of AI and Mathematics, Ft. Lauderdale, FL, USA, Jan., 1996.
postscript
1995

Peter Jonsson and Christer Bäckström:
Incremental Planning.
In New Directions in AI Planning: EWSP'953rd
European Workshop on Planning, pp. 7990, Assisi, Italy, Sep, 1995.
postscript

Inger Klein, Peter Jonsson, and Christer Bäckström:
Tractable Planning for an Assembly Line.
In New Directions in AI Planning: EWSP'953rd
European Workshop on Planning, pp. 313324, Assisi, Italy, Sep, 1995.
postscript

Christer Bäckström and Peter Jonsson:
Planning with Abstraction Hierarchies can be
Exponentially Less Efficient.
In Proceedings of the 14th International Joint
Conference on Artificial Intelligence (IJCAI95), Montreal, PQ, Canada, Aug, 1995.
postscript
1994

Peter Jonsson and Christer Bäckström:
Complexity Results for StateVariable Planning under Mixed
Syntactical and Structural Restrictions.
In Proceedings of the 6th International Conference on
Artificial Intelligence: Methodology, Systems,
Applications (AIMSA94), Sofia, Bulgaria, Sep, 1994.
postscript

Peter Jonsson and Christer Bäckström:
Tractable Planning with State Variables by Exploiting
Structural Restrictions.
In Proceedings of the 12th (US) National Conference on
Artificial Intelligence (AAAI94), pp. 9981003, Seattle, WA, USA, JulAug, 1994.
postscript