{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:36:04Z","timestamp":1753889764361,"version":"3.41.2"},"reference-count":17,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2005,3,7]],"date-time":"2005-03-07T00:00:00Z","timestamp":1110153600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Most parameterized complexity classes are defined in terms of a parameterized\nversion of the Boolean satisfiability problem (the so-called weighted\nsatisfiability problem). For example, Downey and Fellow's W-hierarchy is of\nthis form. But there are also classes, for example, the A-hierarchy, that are\nmore naturally characterised in terms of model-checking problems for certain\nfragments of first-order logic.\n  Downey, Fellows, and Regan were the first to establish a connection between\nthe two formalisms by giving a characterisation of the W-hierarchy in terms of\nfirst-order model-checking problems. We improve their result and then prove a\nsimilar correspondence between weighted satisfiability and model-checking\nproblems for the A-hierarchy and the W^*-hierarchy. Thus we obtain very uniform\ncharacterisations of many of the most important parameterized complexity\nclasses in both formalisms.\n  Our results can be used to give new, simple proofs of some of the core\nresults of structural parameterized complexity theory.<\/jats:p>","DOI":"10.2168\/lmcs-1(1:2)2005","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T12:12:44Z","timestamp":1121256764000},"source":"Crossref","is-referenced-by-count":10,"title":["Model-Checking Problems as a Basis for Parameterized Intractability"],"prefix":"10.46298","volume":"Volume 1, Issue 1","author":[{"given":"Joerg","family":"Flum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0292-9142","authenticated-orcid":false,"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2005,3,7]]},"reference":[{"key":"10.2168\/LMCS-1(1:2)2005_abrdowfel95","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00034-Z"},{"key":"10.2168\/LMCS-1(1:2)2005_cheflu03","doi-asserted-by":"publisher","DOI":"10.1007\/b13224"},{"key":"10.2168\/LMCS-1(1:2)2005_dowfel95b","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792228228"},{"key":"10.2168\/LMCS-1(1:2)2005_dowfel95","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"10.2168\/LMCS-1(1:2)2005_dowfel98","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00101-1"},{"year":"1999","author":"Downey","key":"10.2168\/LMCS-1(1:2)2005_dowfel99"},{"key":"10.2168\/LMCS-1(1:2)2005_dowfelreg98","doi-asserted-by":"crossref","unstructured":"R.G. Downey, M.R. Fellows, and K. Regan. Descriptive complexity and theW-hierarchy. In P. Beame and S. Buss, editors,Proof Complexity and Feasible Arithmetic, volume 39 ofAMS-DIMACS Volume Series, pages 119-134. AMS, 1998.","DOI":"10.1090\/dimacs\/039\/07"},{"key":"10.2168\/LMCS-1(1:2)2005_dowfeltay96","unstructured":"R.G. Downey, M.R. Fellows, and U. Taylor. The parameterized complexity of relational database queries and an improved characterization ofW[1]. In D.S. Bridges, C. Calude, P. Gibbons, S. Reeves, and I.H. Witten, editors,Combinatorics, Complexity, and Logic - Proceedings of DMTCS '96, pages 194-213. Springer-Verlag, 1996."},{"key":"10.2168\/LMCS-1(1:2)2005_fag74","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor,Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, pages 43-73, 1974."},{"key":"10.2168\/LMCS-1(1:2)2005_flufrigro02","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"10.2168\/LMCS-1(1:2)2005_flugro01","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"10.2168\/LMCS-1(1:2)2005_frigro03","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"10.2168\/LMCS-1(1:2)2005_gro01c","doi-asserted-by":"crossref","unstructured":"M. Grohe. The parameterized complexity of database queries. InProceedings of the 20th ACM Symposium on Principles of Database Systems, pages 82-92, 2001.","DOI":"10.1145\/375551.375564"},{"key":"10.2168\/LMCS-1(1:2)2005_licpnu85","doi-asserted-by":"crossref","unstructured":"O. Lichtenstein and A. Pnueli. Finite state concurrent programs satisfy their linear specification. InProceedings of the Twelfth ACM Symposium on the Principles of Programming Languages, pages 97-107, 1985.","DOI":"10.1145\/318593.318622"},{"key":"10.2168\/LMCS-1(1:2)2005_siscla84","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3837"},{"key":"10.2168\/LMCS-1(1:2)2005_sto74","unstructured":"L.J. Stockmeyer.The Complexity of Decision Problems in Automata Theory. PhD thesis, Department of Electrical Engineering, MIT, 1974."},{"key":"10.2168\/LMCS-1(1:2)2005_var82","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi. The complexity of relational query languages. InProceedings of the 14th ACM Symposium on Theory of Computing, pages 137-146, 1982.","DOI":"10.1145\/800070.802186"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2272\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2272\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:11:14Z","timestamp":1681243874000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2272"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3,7]]},"references-count":17,"URL":"https:\/\/doi.org\/10.2168\/lmcs-1(1:2)2005","relation":{"is-same-as":[{"id-type":"arxiv","id":"cs\/0502005","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0502005","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2005,3,7]]},"article-number":"2272"}}