Peter Jonsson

According to our database1, Peter Jonsson authored at least 127 papers between 1994 and 2018.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Tractability conditions for numeric CSPs.
Theor. Comput. Sci., 2018

On the Complexity of CCG Parsing.
Computational Linguistics, 2018

Constants and finite unary relations in qualitative constraint reasoning.
Artif. Intell., 2018

A Refined Understanding of Cost-Optimal Planning with Polytree Causal Graphs.
Proceedings of the Eleventh International Symposium on Combinatorial Search, 2018

Why are CSPs Based on Partition Schemes Computationally Hard?.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Classification Transfer for Qualitative Reasoning Problems.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Novel Structural Parameters for Acyclic Planning Using Tree Embeddings.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

2017
The Complexity of Phylogeny Constraint Satisfaction Problems.
ACM Trans. Comput. Log., 2017

Circuit satisfiability and constraint satisfaction around Skolem Arithmetic.
Theor. Comput. Sci., 2017

Strong partial clones and the time complexity of SAT problems.
J. Comput. Syst. Sci., 2017

A Model-Theoretic View on Qualitative Constraint Reasoning.
J. Artif. Intell. Res., 2017

Time and Space Bounds for Planning.
J. Artif. Intell. Res., 2017

An initial study of time complexity in infinite-domain constraint satisfaction.
Artif. Intell., 2017

Time Complexity of Constraint Satisfaction via Universal Algebra.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016
The Reducts of the homogeneous Binary Branching C-Relation.
J. Symb. Log., 2016

Constraint satisfaction and semilinear expansions of addition over the rationals and the reals.
J. Comput. Syst. Sci., 2016

Refining complexity analyses in planning by exploiting the exponential time hypothesis.
Ann. Math. Artif. Intell., 2016

The Complexity of Phylogeny Constraint Satisfaction.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Finite Unary Relations and Qualitative Constraint Satisfaction.
Proceedings of the ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, 2016

Upper and Lower Time and Space Bounds for Planning.
Proceedings of the ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, 2016

Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis.
Proceedings of the ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands, 2016

2015
Constructing NP-intermediate problems by blowing holes with parameters of various properties.
Theor. Comput. Sci., 2015

Parsing to Noncrossing Dependency Graphs.
TACL, 2015

A complete parameterized complexity analysis of bounded planning.
J. Comput. Syst. Sci., 2015

An Approximability-related Parameter on Graphs - Properties and Applications.
Discrete Mathematics & Theoretical Computer Science, 2015

Maximum Pagenumber-k Subgraph is NP-Complete.
CoRR, 2015

Constraint Satisfaction Problems around Skolem Arithmetic.
CoRR, 2015

Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs.
Proceedings of the Principles and Practice of Constraint Programming, 2015

Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014
Automaton Plans.
J. Artif. Intell. Res., 2014

Limitations of acyclic causal graphs for planning.
Artif. Intell., 2014

Affine Consistency and the Complexity of Semilinear Constraints.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Oversubscription Planning: Complexity and Compilability.
Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014

2013
A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond.
J. Artif. Intell. Res., 2013

Computational complexity of linear constraints over the integers.
Artif. Intell., 2013

Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Fast Detection of Unsolvable Planning Instances Using Local Consistency.
Proceedings of the Sixth Annual Symposium on Combinatorial Search, 2013

Bridging the Gap Between Refinement and Heuristics in Abstraction.
Proceedings of the IJCAI 2013, 2013

Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction.
Proceedings of the Principles and Practice of Constraint Programming, 2013

Parameterized Complexity and Kernel Bounds for Hard Planning Problems.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

When Acyclicity Is Not Enough: Limitations of the Causal Graph.
Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, 2013

2012
Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction.
J. Log. Comput., 2012

Algorithms and Limits for Compact Plan Representations.
J. Artif. Intell. Res., 2012

Essential Convexity and Complexity of Semi-Algebraic Constraints
Logical Methods in Computer Science, 2012

Abstracting Abstraction in Search II: Complexity Analysis.
Proceedings of the Fifth Annual Symposium on Combinatorial Search, 2012

Abstracting Abstraction in Search with Applications to Planning.
Proceedings of the Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, 2012

From Macro Plans to Automata Plans.
Proceedings of the ECAI 2012, 2012

Macros, Reactive Plans and Compact Representations.
Proceedings of the ECAI 2012, 2012

The Complexity of Planning Revisited - A Parameterized Analysis.
Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012

2011
All PSPACE-Complete Planning Problems Are Equal but Some Are More Equal than Others.
Proceedings of the Fourth Annual Symposium on Combinatorial Search, 2011

Discrete-Time Temporal Reasoning with Horn DLRs.
Proceedings of the IJCAI 2011, 2011

Min CSP on Four Elements: Moving beyond Submodularity.
Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

Limits for Compact Representation of Plans.
Proceedings of the 21st International Conference on Automated Planning and Scheduling, 2011

2010
Retractions to Pseudoforests.
SIAM J. Discrete Math., 2010

Approximability of Clausal Constraints.
Theory Comput. Syst., 2010

Approximating integer programs with positive right-hand sides.
Inf. Process. Lett., 2010

2009
Hard constraint satisfaction problems have hard gaps at location 1.
Theor. Comput. Sci., 2009

Properties of an Approximability-related Parameter on Circular Complete Graphs.
Electronic Notes in Discrete Mathematics, 2009

Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts
CoRR, 2009

Semilinear Program Feasibility.
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

Approximability of the Maximum Solution Problem for Certain Families of Algebras.
Proceedings of the Computer Science, 2009

Approximability Distance in the Space of H-Colourability Problems.
Proceedings of the Computer Science, 2009

2008
MAX ONES Generalized to Larger Domains.
SIAM J. Comput., 2008

Computational complexity of auditing finite attributes in statistical databases.
J. Comput. Syst. Sci., 2008

The approximability of MAX CSP with fixed-value constraints.
J. ACM, 2008

Approximability Distance in the Space of H-Colourability Problems
CoRR, 2008

Introduction to the Maximum SolutionProblem.
Proceedings of the Complexity of Constraints, 2008

2007
Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.
J. Comput. Syst. Sci., 2007

The Maximum Solution Problem on Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Bounded Tree-Width and CSP-Related Problems.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems.
Proceedings of the Computer Science, 2007

2006
The Approximability of Three-valued MAX CSP.
SIAM J. Comput., 2006

Generalised Integer Programming Based on Logically Defined Relations.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Approximability of Integer Programming with Generalised Constraints.
Proceedings of the Principles and Practice of Constraint Programming, 2006

2005
Computational Complexity of Temporal Constraint Problems.
Proceedings of the Handbook of Temporal Reasoning in Artificial Intelligence, 2005

Counting models for 2SAT and 3SAT formulae.
Theor. Comput. Sci., 2005

Adding clauses to poor man's logic (without increasing the complexity).
Journal of Applied Non-Classical Logics, 2005

2004
Recognizing frozen variables in constraint satisfaction problems.
Theor. Comput. Sci., 2004

The complexity of counting homomorphisms seen from the other side.
Theor. Comput. Sci., 2004

Algorithms for four variants of the exact satisfiability problem.
Theor. Comput. Sci., 2004

Constraint Satisfaction Problems on Intervals and Length.
SIAM J. Discrete Math., 2004

Complexity classification in qualitative temporal constraint reasoning.
Artif. Intell., 2004

An Algebraic Approach to the Complexity of Propositional Circumscription.
Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups.
Proceedings of the Computing and Combinatorics, 10th Annual International Conference, 2004

2003
Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra.
J. ACM, 2003

Point algebras for temporal reasoning: Algorithms and complexity.
Artif. Intell., 2003

Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems.
Proceedings of the Principles and Practice of Constraint Programming, 2003

2002
Disjunctions, independence, refinements.
Artif. Intell., 2002

Extending the Point Algebra into the Qualitative Algebra.
Proceedings of the 9th International Symposium on Temporal Representation and Reasoning, 2002

An algorithm for counting maximum weighted independent sets and its applications.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Finite Domain Constraint Satisfaction Using Quantum Computation.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Determining the Number of Solutions to Binary CSP Instances.
Proceedings of the Principles and Practice of Constraint Programming, 2002

Counting Satisfying Assignments in 2-SAT and 3-SAT.
Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001
The complexity of constraints on intervals and lengths
Electronic Colloquium on Computational Complexity (ECCC), 2001

A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation.
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001

2000
Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights.
Theor. Comput. Sci., 2000

Building tractable disjunctive constraints.
J. ACM, 2000

Towards efficient universal planning: A randomized approach.
Artif. Intell., 2000

Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints.
Proceedings of the Principles and Practice of Constraint Programming, 2000

Some Observations on Durations, Scheduling and Allen's Algebra.
Proceedings of the Principles and Practice of Constraint Programming, 2000

Planning with Reduced Operator Sets.
Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, 2000

Disjunctive Temporal Reasoning in Partially Ordered Models of Time.
Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30, 2000

1999
On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction
Electronic Colloquium on Computational Complexity (ECCC), 1999

Strong bounds on the approximability of two Pspace-hard problems in propositional planning.
Ann. Math. Artif. Intell., 1999

Computational Complexity of Relating Time Points with Intervals.
Artif. Intell., 1999

Efficient planning for a miniature assembly line.
AI in Engineering, 1999

Some Results on the Complexity of Planning with Incomplete Information.
Proceedings of the Recent Advances in AI Planning, 5th European Conference on Planning, 1999

Towards a Complete Classification of Tractability in Point Algebras for Nonlinear Time.
Proceedings of the Principles and Practice of Constraint Programming, 1999

Exploiting Bipartiteness to Identify Yet Another Tractable Subclass of CSP.
Proceedings of the Principles and Practice of Constraint Programming, 1999

1998
Reasoning About Set Constraints Applied to Tractable Inference in Intuitionistic Logic.
J. Log. Comput., 1998

Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems.
Inf. Process. Lett., 1998

Tractable Plan Existence Does Not Imply Tractable Plan Generation.
Ann. Math. Artif. Intell., 1998

A Unifying Approach to Temporal Constraint Reasoning.
Artif. Intell., 1998

State-Variable Planning Under Structural Restrictions: Algorithms and Complexity.
Artif. Intell., 1998

A Complete Classification of Tractability in Allen's Algebra Relative to Subsets of Basic Relations.
Artif. Intell., 1998

1997
A Complete Classification of Tractability in RCC-5.
J. Artif. Intell. Res., 1997

Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time.
J. Artif. Intell. Res., 1997

A Nonapproximability Result for Finite Function Generation.
Inf. Process. Lett., 1997

Twenty-One Large Tractable Subclasses of Allen's Algebra.
Artif. Intell., 1997

Towards a Complete Classification of Tractability in Allen's Algebra.
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, 1997

1996
Tractable Subclasses of the Point-Interval Algebra: A Complete Classification.
Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning (KR'96), 1996

A Linear-Programming Approach to Temporal Reasoning.
Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, 1996

On the Size of Reactive Plans.
Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, 1996

Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report.
Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, 1996

1995
Planning with Abstraction Hierarchies can be Exponentially Less Efficient.
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995

1994
Tractable Planning with State Variables by Exploiting Structural Restrictions.
Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31, 1994


  Loading...