Change search
ReferencesLink to record
Permanent link

Direct link
Parameterized Modal Satisfiability
City University of New York.
2012 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 64, no 1, 38-55 p.Article in journal (Refereed) Published
Abstract [en]

We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem’s combinatorial explosion, beyond the number of propositional variables v. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by v and the modality depth is FPT, the running time’s dependence on the parameters is a tower of exponentials (unless P=NP). To overcome this limitation we propose pos- sible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails.

Place, publisher, year, edition, pages
2012. Vol. 64, no 1, 38-55 p.
Keyword [en]
Modal logic, Parameterized complexity, Satisfiability problems
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-58600DOI: 10.1007/s00453-011-9552-zISI: 000304395100004OAI: diva2:473407

QC 20130204

Available from: 2012-01-19 Created: 2012-01-05 Last updated: 2013-02-04Bibliographically approved

Open Access in DiVA

fulltext(212 kB)46 downloads
File information
File name FULLTEXT01.pdfFile size 212 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lampis, Michail
In the same journal
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 46 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 52 hits
ReferencesLink to record
Permanent link

Direct link