{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T09:15:12Z","timestamp":1672478112440},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,8,13]],"date-time":"2008-08-13T00:00:00Z","timestamp":1218585600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s00224-008-9138-6","type":"journal-article","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T12:33:37Z","timestamp":1218544417000},"page":"311-339","source":"Crossref","is-referenced-by-count":4,"title":["W-Hierarchies Defined by Symmetric Gates"],"prefix":"10.1007","volume":"46","author":[{"given":"Michael","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Flum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,8,13]]},"reference":[{"key":"9138_CR1","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"K.A. Abrahamson","year":"1995","unstructured":"Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogs. Ann. Pure Appl. Log. 73, 235\u2013276 (1995)","journal-title":"Ann. Pure Appl. Log."},{"key":"9138_CR2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the parameterized complexity of short computation and factorization. Arch. Math. Log. 36, 321\u2013337 (1997)","journal-title":"Arch. Math. Log."},{"key":"9138_CR3","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.apal.2007.09.003","volume":"151","author":"Y. Chen","year":"2007","unstructured":"Chen, Y., Flum, J.: The parameterized complexity of maximality and minimality problems. Ann. Pure Appl. Log. 151, 22\u201361 (2007)","journal-title":"Ann. Pure Appl. Log."},{"key":"9138_CR4","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/j.tcs.2005.02.003","volume":"339","author":"Y. Chen","year":"2005","unstructured":"Chen, Y., Flum, J., Grohe, M.: Machine-based methods in parameterized complexity theory. Theor. Comput. Sci. 339, 167\u2013199 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9138_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9138_CR6","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M., Langston, M.A. (guest eds.): Special Issue on Parameterized Complexity, Part I and Part II. Comput. J. 51(1, 3) (2008)","DOI":"10.1093\/comjnl\/bxm111"},{"key":"9138_CR7","unstructured":"Downey, R.G., Fellows, M.R., Taylor, U.: The parameterized complexity of relational database queries and an improved characterization of W[1]. In: Bridges, D.S., Calude, C., Gibbons, P., Reeves, S., Witten, I.H. (eds.) Combin. Complex. Log. 39, 194\u2013213 (1996)"},{"key":"9138_CR8","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9138_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/11847250_14","volume-title":"Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC)","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized complexity of independence and domination on geometric graphs. In: Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC). LNCS, vol. 4169, pp. 154\u2013165. Springer, Berlin (2006)"},{"key":"9138_CR10","series-title":"EATCS Monographs on Theoretical Computer Science","volume-title":"Data Structures and Algorithms, Vol. 2: NP-Completeness and Graph Algorithms","author":"K. Melhorn","year":"1984","unstructured":"Melhorn, K.: Data Structures and Algorithms, Vol. 2: NP-Completeness and Graph Algorithms. EATCS Monographs on Theoretical Computer Science. Springer, Berlin (1984)"},{"key":"9138_CR11","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"key":"9138_CR12","doi-asserted-by":"crossref","unstructured":"Sipser, M.: Borel sets and circuit complexity. In: Proc. of the 15th Annual ACM Symposium on the Theory of Computing, pp. 61\u201369 (1983)","DOI":"10.1145\/800061.808733"},{"key":"9138_CR13","unstructured":"Spira, P.M.: On time hardware complexity tradeoffs for Boolean functions. In: Proceedings of the Fourth Hawaii International Symposium on System Sciences, pp. 525\u2013527 (1971)"},{"key":"9138_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(83)90011-X","volume":"16","author":"I. Wegener","year":"1983","unstructured":"Wegener, I.: Relating monotone formula size and monotone depth of Boolean functions. Inf. Process. Lett. 16, 41\u201342 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9138-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9138-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9138-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:36Z","timestamp":1558684296000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9138-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,13]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["9138"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9138-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,13]]}}}