{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:58:36Z","timestamp":1743040716214,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319120263"},{"type":"electronic","value":"9783319120270"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12027-0_1","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T22:22:51Z","timestamp":1416003771000},"page":"3-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Parsing Approach to SAT"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 M.","family":"Casta\u00f1o","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,12]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Barton, G.E.: Computational complexity in two-level morphology. In: Proc. of the 24th ACL, pp. 53\u201359, New York (1986)","DOI":"10.3115\/981131.981140"},{"key":"1_CR2","unstructured":"Biere, A., Heule, M., van Maaren H., Walsh, T. (eds): Handbook of Satisfiability. IOS Press (2009)"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Zeit. Math. Logik. Grund. Math., 66\u201392 (1960)","DOI":"10.1002\/malq.19600060105"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s10849-004-2113-y","volume":"13","author":"J Casta\u00f1o","year":"2004","unstructured":"Casta\u00f1o, J.: Global index grammars and descriptive power. Journal of Logic, Language and Information 13, 403\u2013419 (2004)","journal-title":"Journal of Logic, Language and Information"},{"issue":"3","key":"1_CR5","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1142\/S0129054196000191","volume":"7","author":"A Cherubini","year":"1996","unstructured":"Cherubini, A., Breveglieri, L., Citrini, C., Reghizzi, S.: Multipushdown languages and grammars. International Journal of Foundations of Computer Science 7(3), 253\u2013292 (1996)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"1_CR6","volume-title":"Handbook of Formal Languages","author":"J Dassow","year":"1997","unstructured":"Dassow, J., P\u0103un, G., Salomaa, A.: Grammars with controlled derivations. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 2. Springer, Berlin (1997)"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/362007.362035","volume":"13","author":"J Earley","year":"1970","unstructured":"Earley, J.: An Efficient Context-free Parsing Algorithm. Communications of the ACM 13, 94\u2013102 (1970)","journal-title":"Communications of the ACM"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"Elgot, C.C.: Decision problems of automata design and related arithmetics. Transactions of the American Mathematical Society (1961)","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"1_CR9","first-page":"276","volume-title":"In: Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, HLT 2010","author":"C G\u00f3mez-Rodr\u00edguez","year":"2010","unstructured":"G\u00f3mez-Rodr\u00edguez, C., Kuhlmann, M., Satta, G.: Efficient parsing of well-nested linear context-free rewriting systems. In: Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, HLT 2010, pp. 276\u2013284. Association for Computational Linguistics, Stroudsburg (2010)"},{"issue":"2","key":"1_CR10","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/S0022-0000(74)80052-8","volume":"8","author":"NA Khabbaz","year":"1974","unstructured":"Khabbaz, N.A.: A geometric hierarchy of languages. Journal of Computer and System Sciences 8(2), 142\u2013157 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"337","DOI":"10.3115\/976909.979660","volume-title":"In: Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics","author":"P Neuhaus","year":"1997","unstructured":"Neuhaus, P., Broker, N.: The complexity of recognition of linguistically adequate dependency grammars. In: Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics, pp. 337\u2013343. Association for Computational Linguistics, Madrid (1997)"},{"issue":"2","key":"1_CR12","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00288959","volume":"15","author":"PW Purdom Jr","year":"1981","unstructured":"Purdom Jr, P.W., Brown, C.A.: Parsing extended LR(k) grammars. Acta Informatica 15(2), 115\u2013127 (1981)","journal-title":"Acta Informatica"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Ristad, E.S.: Computational complexity of current GPSG theory. In: Proc. of the 24th ACL, pp. 30\u201339, New York (1986)","DOI":"10.3115\/981131.981137"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Satta, G.: Recognition of Linear Context-Free Rewriting Systems. In: ACL, pp. 89\u201395 (1992)","DOI":"10.3115\/981967.981979"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Satta, G.: Some computational complexity results for synchronous context-free grammars. In: Proceedings of HLT\/EMNLP 2005, pp. 803\u2013810 (2005)","DOI":"10.3115\/1220575.1220676"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoretical Computer. Science, 191\u2013229 (1991)","DOI":"10.1016\/0304-3975(91)90374-B"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0743-1066(95)00035-I","volume":"24","author":"S Shieber","year":"1995","unstructured":"Shieber, S., Schabes, Y., Pereira, F.: Principles and implementation of deductive parsing. Journal of Logic Programming 24, 3\u201336 (1995)","journal-title":"Journal of Logic Programming"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Sikkel, K.: Parsing schemata. Springer (1997)","DOI":"10.1007\/978-3-642-60541-3"},{"key":"1_CR19","first-page":"31","volume":"13","author":"M Tomita","year":"1987","unstructured":"Tomita, M.: An efficiente augmented-context-free parsing algorithm. Computational Linguistics 13, 31\u201346 (1987)","journal-title":"Computational Linguistics"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"La Torre, S., Madhusudan, P., Parlato, G.: A robust class of context-sensitive languages. In: LICS, pp. 161\u2013170. IEEE Computer Society (2007)","DOI":"10.1109\/LICS.2007.9"},{"key":"1_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/3-540-45061-0_6","volume-title":"Automata, Languages and Programming","author":"MY Vardi","year":"2003","unstructured":"Vardi, M.Y.: Logic and Automata: A Match Made in Heaven. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 64\u201365. Springer, Heidelberg (2003)"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0022-0000(86)90026-7","volume":"32","author":"MY Vardi","year":"1986","unstructured":"Vardi, M.Y., Wolper, P.: Automata-theoretic techniques for modal logics of programs. J. Comput. Syst. Sci. 32, 183\u2013221 (1986)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1_CR23","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s00224-007-9053-2","volume":"42","author":"C Wartena","year":"2008","unstructured":"Wartena, C.: Storage products and linear control of derivations. Theory of Computing Systems 42(2), 157\u2013186 (2008)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"1_CR24","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0304-3975(92)90124-X","volume":"104","author":"D Weir","year":"1992","unstructured":"Weir, D.: A geometric hierarchy beyond context-free languages. Theoretical Computer Science 104(2), 235\u2013261 (1992)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Advances in Artificial Intelligence -- IBERAMIA 2014"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12027-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:08:06Z","timestamp":1676419686000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12027-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319120263","9783319120270"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12027-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"12 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}