6 papers · 1 filter
Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
Victor Lagerkvist, Johanna Groven, Leif Eriksson
The region connection calculus () and Allen's interval algebra () are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n…
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to…
Solving Quantified Boolean Formulas with Few Existential Variables
Leif Eriksson, Victor Lagerkvist, George Osipov +3
The quantified Boolean formula (QBF) problem is an important decision problem generally viewed as the archetype for PSPACE-completeness. Many problems of central interest in AI are…
Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning
Leif Eriksson, Victor Lagerkvist
Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning with numerous applications in artificial intelligence. Recently, there has been a s…
A Fast Algorithm for Consistency Checking Partially Ordered Time
Leif Eriksson, Victor Lagerkvist
Partially ordered models of time occur naturally in applications where agents or processes cannot perfectly communicate with each other, and can be traced back to the seminal work…
A Multivariate Complexity Analysis of Qualitative Reasoning Problems
Leif Eriksson, Victor Lagerkvist
Qualitative reasoning is an important subfield of artificial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning…