{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:53Z","timestamp":1759638653637},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540581406"},{"type":"electronic","value":"9783540484424"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58140-5_10","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:18:49Z","timestamp":1330269529000},"page":"89-100","source":"Crossref","is-referenced-by-count":19,"title":["The parameterized complexity of some problems in logic and linguistics"],"prefix":"10.1007","author":[{"given":"Rodney G.","family":"Downey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruce M.","family":"Kapron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael T.","family":"Hallett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H. Todd","family":"Wareham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"10_CR1","first-page":"374","volume-title":"Lecture Notes in Computer Science","author":"K. Abrahamson","year":"1993","unstructured":"K. Abrahamson, R. Downey and M. Fellows, \u201cFixed-Parameter Intractability II,\u201d Proc. 10th Symposium on Theoretical Aspects of Computer Science (STACS) (1993), 374\u2013385, Springer-Verlag, Berlin, Lecture Notes in Computer Science."},{"key":"10_CR2","volume-title":"Computational Complexity and Natural Language","author":"G. Barton","year":"1987","unstructured":"G. Barton, R. Berwick, and E. Ristad, Computational Complexity and Natural Language, MIT Press, Cambridge, MA, 1987."},{"key":"10_CR3","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1074.001.0001","volume-title":"The Acquisition of Syntactic Knowledge","author":"R. Berwick","year":"1985","unstructured":"R. Berwick, The Acquisition of Syntactic Knowledge, MIT Press, Cambridge, MA, 1985."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, R. Downey, M. Fellows and H. T. Wareham, \u201cThe Parameterized Complexity of Sequence Alignment and Consensus,\u201d Proceedings of the Fifth Symposium on Combinatorial Pattern Matching (CPM) 1994, to appear.","DOI":"10.1007\/3-540-58094-8_2"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, M. Fellows and M. Hallett, \u201cBeyond NP-Completeness for Problems of Bounded Width: Hardness for the W Hierarchy,\u201d Proceedings of the ACM Symposium on the Theory of Computing (STOC) 1994, to appear.","DOI":"10.1145\/195058.195229"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"L. Cai and J. Chen, \u201cOn the Amount of Nondeterminism and the Power of Verifying,\u201d to appear in Proc. International Conference on the Mathematical Foundations of Computer Science (MFCS), 1993.","DOI":"10.1007\/3-540-57182-5_23"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"L. Cai and J. Chen, \u201cOn Fixed-Parameter Tractability and Approximability of NP-hard Optimization Problems,\u201d to appear in Proc. Israeli Conf. on Theoretical Computer Science (ISTCS), 1993.","DOI":"10.1109\/ISTCS.1993.253478"},{"key":"10_CR8","unstructured":"L. Cai, J. Chen, R. G. Downey and M. R. Fellows, \u201cParameterized Complexity and Finite Advice,\u201d to appear in Proc. Asian Logic Conference, 1993."},{"key":"10_CR9","volume-title":"The Sound Pattern of English","author":"N. Chomsky","year":"1968","unstructured":"N. Chomsky and M. Halle, The Sound Pattern of English, Harper and Row, New York, 1968."},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"M. Davis, \u201cUnsolvable Problems,\u201d in the Handbook of Mathematical Logic, J. Barwise (ed.), Elsevier, 1977, p. 580.","DOI":"10.1016\/S0049-237X(08)71115-7"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"R. G. Downey, P. A. Evans and M. R. Fellows, \u201cParameterized Learning Complexity,\u201d to appear in Proc. Sixth ACM Workshop on Computational Learning Theory (COLT), 1993.","DOI":"10.1145\/168304.168311"},{"key":"10_CR12","first-page":"161","volume":"87","author":"R. G. Downey","year":"1992","unstructured":"R. G. Downey and M. R. Fellows, \u201cFixed Parameter Tractability and Completeness,\u201d Congr. Num., 87 (1992) 161\u2013187.","journal-title":"Congr. Num."},{"key":"10_CR13","unstructured":"R. G. Downey and M. R. Fellows, \u201cFixed Parameter Tractability and Completeness I: Basic Results,\u201d to appear in SIAM J. Comp."},{"key":"10_CR14","unstructured":"R. G. Downey and M. R. Fellows, \u201cFixed Parameter Tractability and Completeness II: On Completeness for W[1],\u201d to appear in Theoretical Computer Science A."},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows, \u201cFixed Parameter Intractability (Extended Abstract),\u201d Proceedings of the Seventh Annual IEEE Conference on Structure in Complexity Theory (1992), 36\u201349.","DOI":"10.1109\/SCT.1992.215379"},{"key":"10_CR16","unstructured":"R. G. Downey and M. R. Fellows, \u201cFixed Parameter Tractability and Completeness III: Some Structural Aspects of the W-Hierarchy,\u201d to appear in Proc. 1992 Dagstuhl Workshop on Structural Complexity Theory (Cambridge University Press)."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows, \u201cParameterized Computational Feasibility,\u201d to appear in Proc. Second Cornell Workshop on Feasible Mathematics (Birkhauser, Boston).","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"10_CR18","unstructured":"R. G. Downey and M. R. Fellows, Parameterized Complexity, monograph in preparation."},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"M. R. Fellows, M. T. Hallett and H. T. Wareham, \u201cDNA Physical Mapping: Three Ways Difficult,\u201d to appear in Proc. First European Symposium on Algorithms, 1993.","DOI":"10.1007\/3-540-57273-2_52"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and N. Koblitz, \u201cFixed-Parameter Complexity and Cryptography,\u201d Proceedings of the Tenth International Conference on Algebraic Algorithms and Error-Correcting Codes (AAECC 10), Springer-Verlag, Lecture Notes in Computer Science, 1993.","DOI":"10.1007\/3-540-56686-4_38"},{"key":"10_CR21","volume-title":"Problem Book in Phonology","author":"M. Halle","year":"1983","unstructured":"M. Halle and G. Clements, Problem Book in Phonology, MIT Press, Cambridge, MA, 1983."},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"F. Henglein and H. G. Mairson, \u201cThe Complexity of Type Inference for Higher-Order Typed Lambda Calculi.\u201d In Proc. Symp. on Principles of Programming Languages (POPL) (1991), 119\u2013130.","DOI":"10.1145\/99583.99602"},{"key":"10_CR23","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0166-218X(92)90208-R","volume":"36","author":"A. Kornai","year":"1992","unstructured":"A. Kornai and Z. Tuza, \u201cNarrowness, Pathwidth and Their Application in Natural Language Processing,\u201d Discrete Applied Mathematics 36 (1992), 87\u201392.","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"P. G. Kolaitis and M. N. Thakur, \u201cApproximation Properties of NP Minimization Classes,\u201d Proc. 6th Structure in Complexity Theory Conference (1991), 353\u2013366.","DOI":"10.1109\/SCT.1991.160280"},{"key":"10_CR25","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0022-0000(80)90027-6","volume":"21","author":"H. R. Lewis","year":"1980","unstructured":"H. R. Lewis, \u201cComplexity Results for Classes of Quantificational Formulas,\u201d J. Computer and Systems Sciences 21 (1980), 317\u2013353.","journal-title":"J. Computer and Systems Sciences"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"O. Lichtenstein and A. Pneuli, \u201cChecking that Finite-State Concurrent Programs Satisfy Their Linear Specification,\u201d in Proc. 12th Ann. ACM Symp. on Principles of Programming Languages (1985), 97\u2013107.","DOI":"10.1145\/318593.318622"},{"key":"10_CR27","unstructured":"C. H. Papadimitriou and M. Yannakakis, \u201cOn the Complexity of Computing the V-C Dimension,\u201d Proceedings of the 1993 IEEE Conf. on Structure in Complexity Theory, (1993)."},{"key":"10_CR28","volume-title":"The Language Complexity Game","author":"E. Ristad","year":"1993","unstructured":"E. Ristad, The Language Complexity Game, MIT Press, Cambridge, MA, 1993."},{"key":"10_CR29","unstructured":"E. Ristad, \u201cComplexity of the Simplified Segmental Phonology\u201d, CS-TR-388-92, revised May 1993. Submitted to Computational Linguistics."},{"key":"10_CR30","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1017\/S0140525X00079577","volume":"13","author":"J. Tsotsos","year":"1990","unstructured":"J. Tsotsos, \u201cAnalyzing Vision at the Complexity Level\u201d, Behavioral and Brain Sciences, 13, 423\u2013469, 1990.","journal-title":"Behavioral and Brain Sciences"}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58140-5_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:17:12Z","timestamp":1605647832000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58140-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540581406","9783540484424"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-58140-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}