skip to main content
Lingue:
Cerca la mia strategia di ricerca: Mostra risultati con: Mostra risultati con:

Model-checking problems as a basis for parameterized intractability

Flum, Jörg ; Grohe, Martin ; Libkin, Leonid

Logical methods in computer science, 2005-03-07, Vol.1 (1) [Rivista Peer Reviewed]

Fulltext disponibile

Citazioni Citato da
  • Titolo:
    Model-checking problems as a basis for parameterized intractability
  • Autore: Flum, Jörg ; Grohe, Martin
  • Altro autore/Curatore: Libkin, Leonid
  • Note di contenuto: Logical Methods in Computer Science, Volume 1, Issue 1 (March 7, 2005) lmcs:2272 Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For example, Downey and Fellow's W-hierarchy is of this form. But there are also classes, for example, the A-hierarchy, that are more naturally characterised in terms of model-checking problems for certain fragments of first-order logic. Downey, Fellows, and Regan were the first to establish a connection between the two formalisms by giving a characterisation of the W-hierarchy in terms of first-order model-checking problems. We improve their result and then prove a similar correspondence between weighted satisfiability and model-checking problems for the A-hierarchy and the W^*-hierarchy. Thus we obtain very uniform characterisations of many of the most important parameterized complexity classes in both formalisms. Our results can be used to give new, simple proofs of some of the core results of structural parameterized complexity theory.
  • Fa parte di: Logical methods in computer science, 2005-03-07, Vol.1 (1)
  • Lingua: Inglese
  • Tipo: Articolo
  • Identificativo: ISSN: 1860-5974
    EISSN: 1860-5974
    DOI: 10.2168/LMCS-1(1:2)2005
  • Fonte: Freely Accessible Science Journals
    Directory of Open Access Journals
    arXiv.org

Ricerca in corso nelle risorse remote ...