Google
Google Scholar
Semantic Scholar
MS Academic
CiteSeerX
ORCIDPeter Jonsson
Person information
- affiliation: Linköping University, Sweden
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2020
[c66]Peter Jonsson, Victor Lagerkvist:
Lower Bounds and Faster Algorithms for Equality Constraints. IJCAI 2020: 1784-1790- [c65]Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov:
Fine-Grained Complexity of Temporal Problems. KR 2020: 284-293
2010 – 2019
- 2019
- [c64]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak:
A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs. IJCAI 2019: 6126-6130 - 2018
- [j59]Peter Jonsson:
Constants and finite unary relations in qualitative constraint reasoning. Artif. Intell. 257: 1-23 (2018) - [j58]Marco Kuhlmann, Giorgio Satta, Peter Jonsson:
On the Complexity of CCG Parsing. Comput. Linguistics 44(3) (2018) - [j57]Peter Jonsson, Johan Thapper:
Tractability conditions for numeric CSPs. Theor. Comput. Sci. 715: 21-34 (2018) - [c63]Manuel Bodirsky, Peter Jonsson, Barnaby Martin
, Antoine Mottet:
Classification Transfer for Qualitative Reasoning Problems. IJCAI 2018: 1256-1262 - [c62]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak:
Novel Structural Parameters for Acyclic Planning Using Tree Embeddings. IJCAI 2018: 4653-4659 - [c61]Peter Jonsson, Victor Lagerkvist:
Why are CSPs Based on Partition Schemes Computationally Hard?. MFCS 2018: 43:1-43:15 - [c60]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak:
A Refined Understanding of Cost-Optimal Planning with Polytree Causal Graphs. SOCS 2018: 19-27 - [i26]Barnaby Martin, Peter Jonsson, Manuel Bodirsky, Antoine Mottet:
Classification transfer for qualitative reasoning problems. CoRR abs/1805.02038 (2018) - 2017
- [j56]Peter Jonsson, Victor Lagerkvist:
An initial study of time complexity in infinite-domain constraint satisfaction. Artif. Intell. 245: 115-133 (2017) - [j55]Manuel Bodirsky, Peter Jonsson:
A Model-Theoretic View on Qualitative Constraint Reasoning. J. Artif. Intell. Res. 58: 339-385 (2017) - [j54]Christer Bäckström, Peter Jonsson:
Time and Space Bounds for Planning. J. Artif. Intell. Res. 60: 595-638 (2017) - [j53]Peter Jonsson, Victor Lagerkvist, Gustav Nordh, Bruno Zanuttini:
Strong partial clones and the time complexity of SAT problems. J. Comput. Syst. Sci. 84: 52-78 (2017) - [j52]Christian Glaßer, Peter Jonsson, Barnaby Martin:
Circuit satisfiability and constraint satisfaction around Skolem Arithmetic. Theor. Comput. Sci. 703: 18-36 (2017) - [j51]Manuel Bodirsky, Peter Jonsson, Van Trung Pham:
The Complexity of Phylogeny Constraint Satisfaction Problems. ACM Trans. Comput. Log. 18(3): 23:1-23:42 (2017) - [c59]Peter Jonsson, Victor Lagerkvist, Biman Roy:
Time Complexity of Constraint Satisfaction via Universal Algebra. MFCS 2017: 17:1-17:15 - [i25]Marco Kuhlmann, Giorgio Satta, Peter Jonsson:
On the Complexity of CCG Parsing. CoRR abs/1702.06594 (2017) - [i24]Peter Jonsson, Victor Lagerkvist, Biman Roy:
Time Complexity of Constraint Satisfaction via Universal Algebra. CoRR abs/1706.05902 (2017) - 2016
- [j50]Meysam Aghighi, Christer Bäckström, Peter Jonsson, Simon Ståhlberg:
Refining complexity analyses in planning by exploiting the exponential time hypothesis. Ann. Math. Artif. Intell. 78(2): 157-175 (2016) - [j49]Peter Jonsson, Johan Thapper:
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals. J. Comput. Syst. Sci. 82(5): 912-928 (2016) - [j48]Manuel Bodirsky, Peter Jonsson, Van Trung Pham:
The Reducts of the homogeneous Binary Branching C-Relation. J. Symb. Log. 81(4): 1255-1297 (2016) - [c58]Christian Glaßer, Peter Jonsson, Barnaby Martin:
Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic. CiE 2016: 323-332 - [c57]Peter Jonsson:
Finite Unary Relations and Qualitative Constraint Satisfaction. ECAI 2016: 37-45 - [c56]Meysam Aghighi, Christer Bäckström, Peter Jonsson, Simon Ståhlberg:
Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis. ECAI 2016: 184-192 - [c55]Christer Bäckström, Peter Jonsson:
Upper and Lower Time and Space Bounds for Planning. ECAI 2016: 716-724 - [c54]Manuel Bodirsky, Peter Jonsson, Van Trung Pham:
The Complexity of Phylogeny Constraint Satisfaction. STACS 2016: 20:1-20:13 - 2015
- [j47]Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper:
An Approximability-related Parameter on Graphs - Properties and Applications. Discret. Math. Theor. Comput. Sci. 17(1): 33-66 (2015) - [j46]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider:
A complete parameterized complexity analysis of bounded planning. J. Comput. Syst. Sci. 81(7): 1311-1332 (2015) - [j45]Marco Kuhlmann, Peter Jonsson:
Parsing to Noncrossing Dependency Graphs. Trans. Assoc. Comput. Linguistics 3: 559-570 (2015) - [j44]Peter Jonsson, Victor Lagerkvist, Gustav Nordh:
Constructing NP-intermediate problems by blowing holes with parameters of various properties. Theor. Comput. Sci. 581: 67-82 (2015) - [c53]Meysam Aghighi, Peter Jonsson, Simon Ståhlberg:
Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs. AAAI 2015: 3225-3231 - [c52]Peter Jonsson, Victor Lagerkvist:
Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs. CP 2015: 183-199 - [i23]Manuel Bodirsky, Peter Jonsson, Van Trung Pham:
The Complexity of Phylogeny Constraint Satisfaction. CoRR abs/1503.07310 (2015) - [i22]Christian Glaßer, Peter Jonsson, Barnaby Martin:
Constraint Satisfaction Problems around Skolem Arithmetic. CoRR abs/1504.04181 (2015) - [i21]Peter Jonsson, Marco Kuhlmann:
Maximum Pagenumber-k Subgraph is NP-Complete. CoRR abs/1504.05908 (2015) - [i20]Peter Jonsson, Johan Thapper:
Constraint Satisfaction and Semilinear Expansions of Addition over the Rationals and the Reals. CoRR abs/1506.00479 (2015) - 2014
- [j43]Anders Jonsson, Peter Jonsson, Tomas Lööw:
Limitations of acyclic causal graphs for planning. Artif. Intell. 210: 36-55 (2014) - [j42]Christer Bäckström, Anders Jonsson, Peter Jonsson:
Automaton Plans. J. Artif. Intell. Res. 51: 255-291 (2014) - [c51]Meysam Aghighi, Peter Jonsson:
Oversubscription Planning: Complexity and Compilability. AAAI 2014: 2221-2227 - [c50]Peter Jonsson, Victor Lagerkvist, Johannes Schmidt, Hannes Uppman:
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis. MFCS (2) 2014: 408-419 - [c49]Peter Jonsson, Johan Thapper:
Affine Consistency and the Complexity of Semilinear Constraints. MFCS (2) 2014: 420-431 - [i19]Christer Bäckström, Peter Jonsson:
Algorithms and Limits for Compact Plan Representations. CoRR abs/1401.5848 (2014) - [i18]Christer Bäckström, Peter Jonsson:
A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond. CoRR abs/1402.0588 (2014) - [i17]Peter Jonsson, Victor Lagerkvist, Johannes Schmidt, Hannes Uppman:
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis. CoRR abs/1406.3247 (2014) - 2013
- [j41]Peter Jonsson, Tomas Lööw:
Computational complexity of linear constraints over the integers. Artif. Intell. 195: 44-62 (2013) - [j40]Christer Bäckström, Peter Jonsson:
A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond. J. Artif. Intell. Res. 47: 575-611 (2013) - [c48]Anders Jonsson, Peter Jonsson, Tomas Lööw:
When Acyclicity Is Not Enough: Limitations of the Causal Graph. ICAPS 2013 - [c47]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider:
Parameterized Complexity and Kernel Bounds for Hard Planning Problems. CIAC 2013: 13-24 - [c46]Peter Jonsson, Victor Lagerkvist, Gustav Nordh:
Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction. CP 2013: 398-414 - [c45]Christer Bäckström, Peter Jonsson:
Bridging the Gap Between Refinement and Heuristics in Abstraction. IJCAI 2013: 2261-2267 - [c44]Christer Bäckström, Peter Jonsson, Simon Ståhlberg:
Fast Detection of Unsolvable Planning Instances Using Local Consistency. SOCS 2013 - [c43]Peter Jonsson, Victor Lagerkvist, Gustav Nordh, Bruno Zanuttini:
Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis. SODA 2013: 1264-1277 - [i16]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider:
A Complete Parameterized Complexity Analysis of Bounded Planning. CoRR abs/1310.7828 (2013) - 2012
- [j39]Manuel Bodirsky, Peter Jonsson, Timo von Oertzen:
Essential Convexity and Complexity of Semi-Algebraic Constraints. Log. Methods Comput. Sci. 8(4) (2012) - [j38]Christer Bäckström, Peter Jonsson:
Algorithms and Limits for Compact Plan Representations. J. Artif. Intell. Res. 44: 141-177 (2012) - [j37]Manuel Bodirsky, Peter Jonsson, Timo von Oertzen:
Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction. J. Log. Comput. 22(3): 643-660 (2012) - [c42]Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider:
The Complexity of Planning Revisited - A Parameterized Analysis. AAAI 2012 - [c41]Christer Bäckström, Anders Jonsson, Peter Jonsson:
Macros, Reactive Plans and Compact Representations. ECAI 2012: 85-90 - [c40]Christer Bäckström, Anders Jonsson, Peter Jonsson:
From Macro Plans to Automata Plans. ECAI 2012: 91-96 - [c39]Christer Bäckström, Peter Jonsson:
Abstracting Abstraction in Search with Applications to Planning. KR 2012 - [c38]Christer Bäckström, Peter Jonsson:
Abstracting Abstraction in Search II: Complexity Analysis. SOCS 2012 - [i15]Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider:
The Complexity of Planning Revisited - A Parameterized Analysis. CoRR abs/1208.2566 (2012) - [i14]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider:
Parameterized Complexity and Kernel Bounds for Hard Planning Problems. CoRR abs/1211.0479 (2012) - 2011
- [c37]Christer Bäckström, Peter Jonsson:
Limits for Compact Representation of Plans. ICAPS 2011 - [c36]Peter Jonsson, Fredrik Kuivinen, Johan Thapper:
Min CSP on Four Elements: Moving beyond Submodularity. CP 2011: 438-453 - [c35]Peter Jonsson, Tomas Lööw:
Discrete-Time Temporal Reasoning with Horn DLRs. IJCAI 2011: 931-936 - [c34]Christer Bäckström, Peter Jonsson:
All PSPACE-Complete Planning Problems Are Equal but Some Are More Equal than Others. SOCS 2011 - [i13]Peter Jonsson, Fredrik Kuivinen, Johan Thapper:
Min CSP on Four Elements: Moving Beyond Submodularity. CoRR abs/1102.2880 (2011) - 2010
- [j36]Peter Jonsson, Johan Thapper:
Approximating integer programs with positive right-hand sides. Inf. Process. Lett. 110(10): 351-355 (2010) - [j35]Peter Jonsson, Gustav Nordh:
Approximability of Clausal Constraints. Theory Comput. Syst. 46(2): 370-395 (2010) - [j34]Tomás Feder, Pavol Hell, Peter Jonsson, Andrei A. Krokhin, Gustav Nordh:
Retractions to Pseudoforests. SIAM J. Discret. Math. 24(1): 101-112 (2010) - [i12]Manuel Bodirsky, Peter Jonsson, Timo von Oertzen:
Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction. CoRR abs/1005.1141 (2010)
2000 – 2009
- 2009
- [j33]Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper:
Properties of an Approximability-related Parameter on Circular Complete Graphs. Electron. Notes Discret. Math. 35: 115-120 (2009) - [j32]Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen:
Hard constraint satisfaction problems have hard gaps at location 1. Theor. Comput. Sci. 410(38-40): 3856-3874 (2009) - [c33]Tommy Färnqvist, Peter Jonsson, Johan Thapper:
Approximability Distance in the Space of H-Colourability Problems. CSR 2009: 92-104 - [c32]Peter Jonsson, Johan Thapper:
Approximability of the Maximum Solution Problem for Certain Families of Algebras. CSR 2009: 215-226 - [c31]Manuel Bodirsky, Peter Jonsson, Timo von Oertzen:
Semilinear Program Feasibility. ICALP (2) 2009: 79-90 - [i11]Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper:
Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts. CoRR abs/0904.4600 (2009) - 2008
- [j31]Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
The approximability of MAX CSP with fixed-value constraints. J. ACM 55(4): 16:1-16:37 (2008) - [j30]Peter Jonsson, Andrei A. Krokhin:
Computational complexity of auditing finite attributes in statistical databases. J. Comput. Syst. Sci. 74(5): 898-909 (2008) - [j29]Peter Jonsson, Fredrik Kuivinen, Gustav Nordh:
MAX ONES Generalized to Larger Domains. SIAM J. Comput. 38(1): 329-365 (2008) - [c30]Peter Jonsson, Gustav Nordh:
Introduction to the Maximum SolutionProblem. Complexity of Constraints 2008: 255-282 - [i10]Tommy Färnqvist, Peter Jonsson, Johan Thapper:
Approximability Distance in the Space of H-Colourability Problems. CoRR abs/0802.0423 (2008) - 2007
- [j28]Peter Jonsson, Andrei A. Krokhin:
Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. Syst. Sci. 73(5): 691-702 (2007) - [c29]Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen:
Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. CSR 2007: 182-193 - [c28]Tommy Färnqvist, Peter Jonsson:
Bounded Tree-Width and CSP-Related Problems. ISAAC 2007: 632-643 - [c27]Peter Jonsson, Gustav Nordh, Johan Thapper:
The Maximum Solution Problem on Graphs. MFCS 2007: 228-239 - [i9]Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen:
Hard constraint satisfaction problems have hard gaps at location 1. CoRR abs/0712.1532 (2007) - 2006
- [j27]Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
The Approximability of Three-valued MAX CSP. SIAM J. Comput. 35(6): 1329-1349 (2006) - [c26]Peter Jonsson, Fredrik Kuivinen, Gustav Nordh:
Approximability of Integer Programming with Generalised Constraints. CP 2006: 256-270 - [c25]Peter Jonsson, Gustav Nordh:
Generalised Integer Programming Based on Logically Defined Relations. MFCS 2006: 549-560 - [i8]Peter Jonsson, Fredrik Kuivinen, Gustav Nordh:
Approximability of Integer Programming with Generalised Constraints. CoRR abs/cs/0602047 (2006) - [i7]Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
The approximability of MAX CSP with fixed-value constraints. CoRR abs/cs/0602075 (2006) - 2005
- [j26]Peter Jonsson:
Adding clauses to poor man's logic (without increasing the complexity). J. Appl. Non Class. Logics 15(3): 341-357 (2005) - [j25]Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström:
Counting models for 2SAT and 3SAT formulae. Theor. Comput. Sci. 332(1-3): 265-291 (2005) - [r1]Thomas Drakengren, Peter Jonsson:
Computational Complexity of Temporal Constraint Problems. Handbook of Temporal Reasoning in Artificial Intelligence 2005: 197-218 - 2004
- [j24]Peter Jonsson, Andrei A. Krokhin:
Complexity classification in qualitative temporal constraint reasoning. Artif. Intell. 160(1-2): 35-51 (2004) - [j23]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
Constraint Satisfaction Problems on Intervals and Length. SIAM J. Discret. Math. 17(3): 453-477 (2004) - [j22]Vilhelm Dahllöf, Peter Jonsson, Richard Beigel:
Algorithms for four variants of the exact satisfiability problem. Theor. Comput. Sci. 320(2-3): 373-394 (2004) - [j21]Peter Jonsson, Andrei A. Krokhin:
Recognizing frozen variables in constraint satisfaction problems. Theor. Comput. Sci. 329(1-3): 93-113 (2004) - [j20]Víctor Dalmau, Peter Jonsson:
The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci. 329(1-3): 315-323 (2004) - [c24]Gustav Nordh, Peter Jonsson:
The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups. COCOON 2004: 370-379 - [c23]Gustav Nordh, Peter Jonsson:
An Algebraic Approach to the Complexity of Propositional Circumscription. LICS 2004: 367-376 - [i6]Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
The approximability of three-valued MAX CSP. CoRR abs/cs/0412042 (2004) - 2003
- [j19]Mathias Broxvall, Peter Jonsson:
Point algebras for temporal reasoning: Algorithms and complexity. Artif. Intell. 149(2): 179-220 (2003) - [j18]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. J. ACM 50(5): 591-640 (2003) - [c22]Ola Angelsmark, Peter Jonsson:
Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems. CP 2003: 81-95 - [i5]Andrei A. Krokhin, Peter Jonsson:
Recognizing Frozen Variables in Constraint Satisfaction Problems. Electron. Colloquium Comput. Complex.(062) (2003) - 2002
- [j17]Mathias Broxvall, Peter Jonsson, Jochen Renz:
Disjunctions, independence, refinements. Artif. Intell. 140(1/2): 153-173 (2002) - [c21]Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström:
Counting Satisfying Assignments in 2-SAT and 3-SAT. COCOON 2002: 535-543 - [c20]Ola Angelsmark, Peter Jonsson, Svante Linusson, Johan Thapper:
Determining the Number of Solutions to Binary CSP Instances. CP 2002: 327-340 - [c19]Ola Angelsmark, Vilhelm Dahllöf, Peter Jonsson:
Finite Domain Constraint Satisfaction Using Quantum Computation. MFCS 2002: 93-103 - [c18]Vilhelm Dahllöf, Peter Jonsson:
An algorithm for counting maximum weighted independent sets and its applications. SODA 2002: 292-298 - [c17]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
The Complexity of Constraints on Intervals and Lengths. STACS 2002: 443-454 - [c16]Andrei A. Krokhin, Peter Jonsson:
Extending the Point Algebra into the Qualitative Algebra. TIME 2002: 28-35 - 2001
- [c15]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. IJCAI 2001: 83-88 - [i4]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
The complexity of constraints on intervals and lengths. Electron. Colloquium Comput. Complex.(077) (2001) - 2000
- [j16]Peter Jonsson, Patrik Haslum, Christer Bäckström:
Towards efficient universal planning: A randomized approach. Artif. Intell. 117(1): 1-29 (2000) - [j15]David A. Cohen, Peter Jeavons, Peter Jonsson, Manolis Koubarakis:
Building tractable disjunctive constraints. J. ACM 47(5): 826-853 (2000) - [j14]Peter Jonsson:
Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights. Theor. Comput. Sci. 244(1-2): 189-203 (2000) - [c14]Mathias Broxvall, Peter Jonsson:
Disjunctive Temporal Reasoning in Partially Ordered Models of Time. AAAI/IAAI 2000: 464-469 - [c13]Patrik Haslum, Peter Jonsson:
Planning with Reduced Operator Sets. AIPS 2000: 150-158 - [c12]Mathias Broxvall, Peter Jonsson, Jochen Renz:
Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints. CP 2000: 114-127 - [c11]Ola Angelsmark, Peter Jonsson:
Some Observations on Durations, Scheduling and Allen's Algebra. CP 2000: 484-488
1990 – 1999
- 1999
- [j13]Inger Klein, Peter Jonsson, Christer Bäckström:
Efficient planning for a miniature assembly line. Artif. Intell. Eng. 13(1): 69-81 (1999) - [j12]Peter Jonsson, Thomas Drakengren, Christer Bäckström:
Computational Complexity of Relating Time Points with Intervals. Artif. Intell. 109(1-2): 273-295 (1999) - [j11]Peter Jonsson:
Strong bounds on the approximability of two Pspace-hard problems in propositional planning. Ann. Math. Artif. Intell. 26(1-4): 133-147 (1999) - [c10]Marcus Bjäreland, Peter Jonsson:
Exploiting Bipartiteness to Identify Yet Another Tractable Subclass of CSP. CP 1999: 118-128 - [c9]