**(funded by the Austrian Science Fund (FWF) under grant P25518)**

The project has officially started on 2013-05-01 and will have a duration of three years.

TopReasoning is a fundamental task in Computer Science. It is concerned with the derivation of conclusions from some data or knowledge base. It has many interesting applications - especially in Artificial Intelligence - such as answer-set programming, reasoning on the web with description logics, belief revision, argumentation, diagnosis, etc. These areas have received vivid research interest in recent years. Strong theoretical foundations have been laid and algorithms have been presented which, at least in theory, solve the most common computational tasks in these areas. However, in practice, it has turned out that the high inherent complexity of most of these tasks is a severe obstacle to the application of these algorithms to problem instances of realistic size. To this date, the high computational complexity of reasoning tasks has not been satisfactorily solved.

Over the past decade, Parameterized Complexity Theory has evolved as a promising way of dealing with high complexity. The primary goal of a parameterized complexity analysis for some hard problem is to identify so-called fixed-parameter tractable fragments, i.e., to identify problem parameters that allow for the efficient solution of intractable problems in case these parameters are small. The tools of Parameterized Complexity Theory have been successfully applied to many areas of Computer Science - above all to hard problems in Graph Theory. However, the application of these techniques to hard reasoning problems is still in its infancy.

In this project, we want to extend the successful application of parameterized complexity techniques to the area of Artificial Intelligence and Reasoning. In the first place, we will thus initiate a systematic exploration of possible problem parameters and analyze their potential in finding tractable fragments of otherwise intractable reasoning problems. We will then harness the results of the Parameterized Complexity study to develop new efficient algorithms for fragments of hard reasoning problems and to identify directions for the improvement of existing solution methods for these problems.

Top- A Parameterized Complexity Analysis of Generalized CP-Nets In Proceedings of the 7th Multidisciplinary Workshop on Advances in Preference Handling (M-Pref'13), 2013.

[ BibTeX ] - Backdoors to Abduction In CoRR, abs/1304.5961, 2013.

[ BibTeX ] - Computational Aspects of Nearly Single-Peaked Electorates In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI-13), 2013.

[ BibTeX ] - Conformant Planning as a Benchmark for QBF-Solvers In Proc. of the International Workshop on Quantified Boolean Formulas (QBF 2013) colocated with SAT 2013, pages 1-5, 2013.

[ BibTeX ] - Global State Checker: Towards SAT-Based Reachability Analysis of Communicating State Machines In Proc. of the 10th Model-Driven Engineering, Verification, and Validation Workshop (MoDeVVa 2013) colocated with MODELS 2013, pages 31-40, CEUR Workshop Proceedings , 2013.

[ BibTeX ] - Incomplete Preferences in Single-Peaked Electorates In Proceedings of the 7th Multidisciplinary Workshop on Advances in Preference Handling (M-Pref'13), 2013.

[ BibTeX ] - Parameterized Complexity of Optimal Planning: A Detailed Map In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-13), AAAI Press, 2013.

[ BibTeX ] - The computational landscape of permutation patterns In CoRR, abs/1301.0340, 2013, To appear in Pure and Applied Mathematics.

[ BibTeX ]

Last updated: 2013-10-30 17:20