Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Parameterized Modal Satisfiability
City University of New York.
2012 (Engelska)Ingår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 64, nr 1, 38-55 s.Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2012. Vol. 64, nr 1, 38-55 s.
Nyckelord [en]
Modal logic, Parameterized complexity, Satisfiability problems
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:kth:diva-58600DOI: 10.1007/s00453-011-9552-zISI: 000304395100004OAI: oai:DiVA.org:kth-58600DiVA: diva2:473407
Anmärkning

QC 20130204

Tillgänglig från: 2012-01-19 Skapad: 2012-01-05 Senast uppdaterad: 2013-02-04Bibliografiskt granskad

Open Access i DiVA

fulltext(212 kB)79 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 212 kBChecksumma SHA-512
5793155dcd0c46f060c3157bcb2cedb4ed6b248c2ed9cfd9fb3887f7ec5ba7c58ec752df8765e1e45819a69119c50e30d92229d0a2b0b61f997d7ac060edd050
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Lampis, Michail
I samma tidskrift
Algorithmica
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 79 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

Altmetricpoäng

Totalt: 225 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf