On the parameterized complexity of default logic and autoepistemic logic
2012 (English)In: Language and automata theory and applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings / [ed] Adrian-Horia Dediu, Carlos Martín-Vide, Berlin: Springer, 2012, 389-400 p.Conference paper (Refereed)
We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld et al. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XP nu), unless P = NP.
Place, publisher, year, edition, pages
Berlin: Springer, 2012. 389-400 p.
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7183 LNCS
Default logic, Existence problems, Fixed-parameter algorithms, Implication problem, Logspace, Parameterizations, Parameterized complexity, Simple structures, Space efficient algorithms, Algorithms, Formal logic
Computer and Information Science
IdentifiersURN: urn:nbn:se:hj:diva-31622DOI: 10.1007/978-3-642-28332-1_33ScopusID: 2-s2.0-84863410135ISBN: 9783642283314ISBN: 9783642283321OAI: oai:DiVA.org:hj-31622DiVA: diva2:957154
6th International Conference on Language and Automata Theory and Applications, LATA 2012; A Coruna; Spain; 5 March 2012 through 9 March 2012; Code 88895