Parametrised complexity of satisfiability in temporal logic

Downloadstatistik des Dokuments (Auswertung nach COUNTER):

Luck, M.; Meier, A.; Schindler, I.: Parametrised complexity of satisfiability in temporal logic. In: ACM Transactions on Computational Logic 18 (2017), Nr. 1, 1. DOI: https://doi.org/10.1145/3001835

Version im Repositorium

Zum Zitieren der Version im Repositorium verwenden Sie bitte diesen DOI: https://doi.org/10.15488/1212

Zeitraum, für den die Download-Zahlen angezeigt werden:

Jahr: 
Monat: 

Summe der Downloads: 128




Kleine Vorschau
Zusammenfassung: 
We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and corresponding notions of treewidth and pathwidth are introduced. As an application for such structures, we present a classification in terms of parametrised complexity of the satisfiability problem, where we make use of Courcelle's famous theorem for recognition of certain classes of structures. Our classification shows a dichotomy between W[1]-hard and fixed-parameter tractable operator fragments almost independently of the chosen graph representation. The only fragments that are proven to be fixed-parameter tractable (FPT) are those that are restricted to the X operator. By investigating Boolean operator fragments in the sense of Post's lattice, we achieve the same complexity as in the unrestricted case if the set of available Boolean functions can express the function "negation of the implication." Conversely, we show containment in FPT for almost all other clones.© ACM 2017. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computational Logic 18 (2017), Nr. 1, 1. DOI: https://doi.org/10.1145/3001835.
Lizenzbestimmungen: Es gilt deutsches Urheberrecht. Das Dokument darf zum eigenen Gebrauch kostenfrei genutzt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.
Publikationstyp: Text
Publikationsstatus: acceptedVersion
Erstveröffentlichung: 2017
Die Publikation erscheint in Sammlung(en):Fakultät für Architektur und Landschaft

Verteilung der Downloads über den gewählten Zeitraum:

Herkunft der Downloads nach Ländern:

Pos. Land Downloads
Anzahl Proz.
1 image of flag of Germany Germany 107 83,59%
2 image of flag of Brazil Brazil 5 3,91%
3 image of flag of China China 4 3,12%
4 image of flag of United States United States 3 2,34%
5 image of flag of India India 3 2,34%
6 image of flag of France France 2 1,56%
7 image of flag of Japan Japan 1 0,78%
8 image of flag of Italy Italy 1 0,78%
9 image of flag of United Kingdom United Kingdom 1 0,78%
10 image of flag of Bulgaria Bulgaria 1 0,78%

Weitere Download-Zahlen und Ranglisten:


Hinweis

Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.

Suche im Repositorium


Durchblättern