Change search
ReferencesLink to record
Permanent link

Direct link
On the parameterized complexity of default logic and autoepistemic logic
Universität Hannover, Germany.
Université de la Méditerranée, France.
TWT GmbH, Germany.
Universität Hannover, Germany.
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)
Abstract [en]

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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7183 LNCS
Keyword [en]
Default logic, Existence problems, Fixed-parameter algorithms, Implication problem, Logspace, Parameterizations, Parameterized complexity, Simple structures, Space efficient algorithms, Algorithms, Formal logic
National Category
Computer and Information Science
Identifiers
URN: 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
Conference
6th International Conference on Language and Automata Theory and Applications, LATA 2012; A Coruna; Spain; 5 March 2012 through 9 March 2012; Code 88895
Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2016-09-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schmidt, Johannes
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 3 hits
ReferencesLink to record
Permanent link

Direct link