{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:19:24Z","timestamp":1725495564274},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540005322"},{"type":"electronic","value":"9783540364566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36456-0_3","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T23:07:03Z","timestamp":1194995223000},"page":"22-35","source":"Crossref","is-referenced-by-count":3,"title":["GIGs: Restricted Context-Sensitive Descriptive Power in Bounded Polynomial-Time"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 M.","family":"Casta\u00f1o","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,4,30]]},"reference":[{"issue":"4","key":"3_CR1","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"A. V. Aho","year":"1968","unstructured":"A. V. Aho. Indexed grammars-an extension of context-free grammars. Journal of the Association for Computing Machinery, 15(4):647\u2013671, 1968.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR2","unstructured":"T. Becker. HyTAG: a new type of Tree Adjoining Grammars for Hybrid Syntactic Representation of Free Order Languages. PhD thesis, University of Saarbruecken, 1993."},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/322290.322301","volume":"29","author":"R. Book","year":"1982","unstructured":"R. Book. Confluent and other types of thue systems. J. Assoc. Comput. Mach., 29:171\u2013182, 1982.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR4","unstructured":"P. Boullier. A cubic time extension of context-free grammars. Research Report RR-3611, INRIA, Rocquencourt, France, January 1999. 28 pages."},{"key":"3_CR5","unstructured":"J. Casta\u00f1o. Lr-2pda and global index grammars. Ms., Computer Science Dept. Brandeis University, available at http:\/\/www.cs.brandeis.edu\/~jcastano\/GIGs .ps, 2002."},{"issue":"3","key":"3_CR6","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1142\/S0129054196000191","volume":"7","author":"A. Cherubini","year":"1996","unstructured":"A. Cherubini, L. Breveglieri, C. Citrini, and S. Reghizzi. 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":"3_CR7","doi-asserted-by":"crossref","unstructured":"N. Chomsky and M.-P. Sch\u00fctzenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems, pages 118\u2013161. North-Holland, Amsterdam, The Netherlands, 1963.","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF00630918","volume":"8","author":"C. Culy","year":"1985","unstructured":"C. Culy. The complexity of the vocabulary of bambara. Linguistics and Philosophy, 8:345\u2013351, 1985.","journal-title":"Linguistics and Philosophy"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"J. Dassow and G. P\u0103un. Regulated Rewriting in Formal Language Theory. Springer, Berlin, Heidelberg, New York, 1989.","DOI":"10.1007\/978-3-642-74932-2"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"J. Dassow, G. P\u0103un, and A. Salomaa. Grammars with controlled derivations. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Vol. 2. Springer, Berlin, 1997.","DOI":"10.1007\/978-3-662-07675-0_3"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/362007.362035","volume":"13","author":"J. Earley","year":"1970","unstructured":"J. Earley. An Efficient Context-free Parsing Algorithm. Communications of the ACM, 13:94\u2013102, 1970.","journal-title":"Communications of the ACM"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"G. Gazdar. Applicability of indexed grammars to natural languages. In U. Reyle and C. Rohrer, editors, Natural Language Parsing and Linguistic Theories, pages 69\u201394. D. Reidel, Dordrecht, 1988.","DOI":"10.1007\/978-94-009-1337-0_3"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1145\/321466.321475","volume":"15","author":"S. Ginsburg","year":"1968","unstructured":"S. Ginsburg and M. Harrison. One-way nondeterministic real-time list-storage. Journal of the Association for Computing Machinery, 15, No. 3:428\u2013446, 1968.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR14","unstructured":"M. H. Harrison. Introduction to Formal Language Theory. Addison-Wesley Publishing Company, Inc., Reading, MA, 1978."},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"A. Joshi. Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural description? In D. Dowty, L. Karttunen, and A. Zwicky, editors, Natural language processing: psycholinguistic, computational and theoretical perspectives, pages 206\u2013250. Chicago University Press, New York, 1985.","DOI":"10.1017\/CBO9780511597855.007"},{"key":"3_CR16","first-page":"31","volume-title":"Foundational issues in natural language processing","author":"A. Joshi","year":"1991","unstructured":"A. Joshi, K. Vijay-Shanker, and D. Weir. The convergence of mildly contextsensitive grammatical formalisms. In Peter Sells, Stuart Shieber, and Thomas Wasow, editors, Foundational issues in natural language processing, pages 31\u201381. MIT Press, Cambridge, MA, 1991."},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"J. Michaelis and M. Kracht. Semilinearity as a syntactic invariant. In Christian Retor\u00e9, editor, LACL\u201996: First International Conference on Logical Aspects of Computational Linguistics, pages 329\u2013345. Springer-Verlag, Berlin, 1997.","DOI":"10.1007\/BFb0052165"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"S. Rajasekaran. Tree-adjoining language parsing in o(n6) time. SIAM J. of Computation, 25, 1996.","DOI":"10.1137\/S009753979326009X"},{"key":"3_CR19","unstructured":"G. Satta. Tree-adjoining grammar parsing and boolean matrix multiplication. Computational linguistics, 20, No. 2, 1994."},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"H. Seki, T. Matsumura, M. Fujii, and T. Kasami. On multiple context-free grammars; theor, 1991.","DOI":"10.1016\/0304-3975(91)90374-B"},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF00630917","volume":"8","author":"S.M. Shieber","year":"1985","unstructured":"S.M. Shieber. Evidence against the context-freeness of natural language. Linguistics and Philosophy, 8:333\u2013343, 1985.","journal-title":"Linguistics and Philosophy"},{"key":"3_CR22","series-title":"Lect Notes Comput Sci","first-page":"1328","volume-title":"Derivational minimalism","author":"E. P. Stabler","year":"1997","unstructured":"E. P. Stabler. Derivational minimalism. Lecture notes in computer science, 1328, 1997."},{"key":"3_CR23","first-page":"31","volume":"13","author":"M. Tomita","year":"1987","unstructured":"M. Tomita. An efficinte augmented-context-free parsing algorithm. Computational linguistics, 13:31\u201346, 1987.","journal-title":"Computational linguistics"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0019-9958(70)80005-5","volume":"17","author":"D. A. Walters","year":"1970","unstructured":"Daniel A. Walters. Deterministic context-sensitive languages: Part ii. Information and Control, 17:41\u201361, 1970.","journal-title":"Information and Control"},{"key":"3_CR25","unstructured":"C. Wartena. Grammars with composite storages. In Proceedings of the Conference on Logical Aspects of Computational Linguistics (LACL\u2019 98), pages 11\u201314, Grenoble, 1998."},{"key":"3_CR26","unstructured":"D. Weir. Characterizing mildly context-sensitive grammar formalisms. PhD thesis, University of Pennsylvania, 1988."},{"issue":"2","key":"3_CR27","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0304-3975(92)90124-X","volume":"104","author":"D. J. Weir","year":"1992","unstructured":"D. J. Weir. 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","Computational Linguistics and Intelligent Text Processing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36456-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T11:22:23Z","timestamp":1556968943000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36456-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540005322","9783540364566"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-36456-0_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}