


Остановите войну!
for scientists:


default search action
Peter 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
- 2023
- [j67]Peter Jonsson, Victor Lagerkvist:
General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs. Algorithmica 85(1): 188-215 (2023) - 2022
- [j66]Christer Bäckström
, Peter Jonsson:
A framework for analysing state-abstraction methods. Artif. Intell. 302: 103608 (2022) - [j65]Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak:
Computational Short Cuts in Infinite Domain Constraint Satisfaction. J. Artif. Intell. Res. 75: 793-831 (2022) - [c70]Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov:
Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach. AAAI 2022: 3724-3732 - [i30]Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov, Magnus Wahlström:
Almost Consistent Systems of Linear Equations. CoRR abs/2208.02732 (2022) - [i29]Manuel Bodirsky, Peter Jonsson, Barnaby Martin, Antoine Mottet, Zaneta Semanisinová:
Complexity Classification Transfer for CSPs via Algebraic Products. CoRR abs/2211.03340 (2022) - [i28]Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak:
Computational Short Cuts in Infinite Domain Constraint Satisfaction. CoRR abs/2211.10144 (2022) - 2021
- [j64]Peter Jonsson, Victor Lagerkvist, George Osipov
:
Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms. Artif. Intell. 296: 103505 (2021) - [j63]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak
:
Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics. J. Artif. Intell. Res. 70: 169-204 (2021) - [j62]Alexander Shleyfman, Peter Jonsson:
Computational Complexity of Computing Symmetries in Finite-Domain Planning. J. Artif. Intell. Res. 70: 1183-1221 (2021) - [j61]Peter Jonsson, Victor Lagerkvist, Johannes Schmidt
, Hannes Uppman
:
The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems. Theor. Comput. Sci. 892: 1-24 (2021) - [j60]Peter Jonsson, Victor Lagerkvist, Biman Roy:
Fine-Grained Time Complexity of Constraint Satisfaction Problems. ACM Trans. Comput. Theory 13(1): 2:1-2:32 (2021) - [c69]Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak
, George Osipov:
Solving Infinite-Domain CSPs Using the Patchwork Property. AAAI 2021: 3715-3723 - [c68]Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak
, George Osipov:
Disjunctive Temporal Problems under Structural Restrictions. AAAI 2021: 3724-3732 - [c67]Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak
:
Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors. CP 2021: 32:1-32:20 - [i27]Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov:
Solving Infinite-Domain CSPs Using the Patchwork Property. CoRR abs/2107.01428 (2021) - 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