{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:24:36Z","timestamp":1761611076515,"version":"3.43.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2001,12,1]],"date-time":"2001-12-01T00:00:00Z","timestamp":1007164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2001,12,1]],"date-time":"2001-12-01T00:00:00Z","timestamp":1007164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Grammars"],"published-print":{"date-parts":[[2001,12]]},"DOI":"10.1023\/a:1012228321223","type":"journal-article","created":{"date-parts":[[2002,12,23]],"date-time":"2002-12-23T07:42:15Z","timestamp":1040629335000},"page":"205-262","source":"Crossref","is-referenced-by-count":4,"title":["A Descriptive Characterisation of Indexed Grammars"],"prefix":"10.1007","volume":"4","author":[{"given":"Tore","family":"Langholm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"357619_CR1","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"A.V. Aho","year":"1968","unstructured":"Aho, A.V. Indexed grammars\u2014An 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":"357619_CR2","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R. Weak second order arithmetic and finite automata, Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 6: 66\u201392, 1960.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"357619_CR3","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"Doner, J. Tree acceptors and some of their applications, Journal of Computer and System Sciences, 4: 406\u2013451, 1970.","journal-title":"Journal of Computer and System Sciences"},{"key":"357619_CR4","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.-D. and J. Flum Finite Model Theory, Springer, Berlin, 1995."},{"key":"357619_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","volume":"98","author":"C.C. Elgot","year":"1961","unstructured":"Elgot, C.C. Decision problems of finite automata design and related arithmetics, Transactions of the American Mathematical Society, 98: 21\u201352, 1961.","journal-title":"Transactions of the American Mathematical Society"},{"key":"357619_CR6","unstructured":"Fischer, M.J. Grammars with macro-like productions, doctoral dissertation, Harvard University. Re-printed in Mathematical Linguistics and Automatic Translation, Harvard University Computation Laboratory Report NSF-22, 1968a."},{"key":"357619_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, M.J. Grammars with macro-like productions, IEEE Conference Record of the Ninth Annual Symposium on Switching and Automata Theory, 131-142, 1968b.","DOI":"10.1109\/SWAT.1968.12"},{"key":"357619_CR8","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/978-94-009-1337-0_3","volume-title":"Natural Language Parsing and Linguistic Theories","author":"G. Gazdar","year":"1988","unstructured":"Gazdar, G. Applicability of indexed grammars to natural languages. In Reyle, U. and C. Rohrer, Natural Language Parsing and Linguistic Theories, 69\u201394, Reidel, Dordrecht, 1988."},{"key":"357619_CR9","volume-title":"Handbook of Formal Languages","author":"F. G\u00e9cseg","year":"1997","unstructured":"G\u00e9cseg, F. and M. Steinby. Tree Languages. In Rozenberg, G. and A. Salomaa, editors, Handbook of Formal Languages, vol. 3, Springer, Berlin, 1997."},{"key":"357619_CR10","doi-asserted-by":"crossref","first-page":"61","DOI":"10.2977\/prims\/1195192738","volume":"9","author":"T. Hayashi","year":"1973","unstructured":"Hayashi, T. On derivation trees of indexed grammars-An extension of the uvwxy-theorem, Pub-lications of the Research Institute for Mathematical Sciences, Kyoto University, 9: 61\u201392, 1973.","journal-title":"Pub-lications of the Research Institute for Mathematical Sciences, Kyoto University"},{"key":"357619_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E. and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation, Addison\u2013Wesley, Reading, MA: 1979."},{"key":"357619_CR12","first-page":"173","volume-title":"The Mental Representation of Grammatical Relations","author":"R. Kaplan","year":"1982","unstructured":"Kaplan, R. and J. Bresnan. Lexical-Functional Grammar: A Formal System for Grammatical Representation. In Bresnan, J., editors, The Mental Representation of Grammatical Relations, MIT Press, Cambridge, MA: 173\u2013218, 1982."},{"key":"357619_CR13","series-title":"Formal Issues in Lexical-Functional Grammar","doi-asserted-by":"crossref","first-page":"297","DOI":"10.3115\/991635.991695","volume-title":"Proceedings of the 12th International Conference on Computational Linguistics (COLING'88)","author":"R. Kaplan","year":"1988","unstructured":"Kaplan, R. and J. Maxwell. An Algorithm for Functional Uncertainty, Proceedings of the 12th International Conference on Computational Linguistics (COLING'88): 297\u2013302, 1988. Re-printed in Dalrymple, M., R. Kaplan, J. Maxwell, and A. Zaenen, editors, Formal Issues in Lexical-Functional Grammar, CSLI Publications, Stanford, CA 1995: 177\u2013197."},{"key":"357619_CR14","series-title":"Formal Issues in Lexical-Functional Grammar","first-page":"17","volume-title":"Alternative Conceptions of Phrase Structure","author":"R. Kaplan","year":"1989","unstructured":"Kaplan, R. and A. Zaenen. Long-Distance Dependencies, Constituent Structure, and Functional Uncertainty. In Baltin, M. and A. Kroch, editors, Alternative Conceptions of Phrase Structure. Chicago University Press, Chicago, IL: 17\u201342, 1989. Reprinted in Dalrymple, M., R. Kaplan, J. Maxwell and A. Zaenen, editors, Formal Issues in Lexical-Functional Grammar, 137\u2013165, CSLI Publications, Stanford, CA, 1995"},{"key":"357619_CR15","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01048404","volume":"4","author":"M. Kracht","year":"1995","unstructured":"Kracht, M. Syntactic codes and grammar refinement, Journal of Logic, Language and Information, 4: 41\u201360, 359\u2013380, 1995.","journal-title":"Journal of Logic, Language and Information"},{"key":"357619_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BFb0022257","volume-title":"Computer Science Logic","author":"C. Lautemann","year":"1995","unstructured":"Lautemann, C., T. Schwentick and D. Th\u00e9rien. Logics for context-free languages. In Pacholsky, L. and J. Tiuryn, editors, Computer Science Logic, Lecture Notes in Computer Science 933, Springer, Berlin: 205\u2013216, 1995."},{"key":"357619_CR17","volume-title":"Elements of the Theory of Computation","author":"H.R. Lewis","year":"1981","unstructured":"Lewis, H.R. and C.H. Papadimitriou. Elements of the Theory of Computation, Prentice-Hall, Englewood Cliffs, NJ, 1981."},{"key":"357619_CR18","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/S0022-0000(74)80031-0","volume":"8","author":"T.S.E. Maibaum","year":"1974","unstructured":"Maibaum, T.S.E. A generalized approach to formal languages, Journal of Computer and System Sciences, 8: 409\u2013439, 1974.","journal-title":"Journal of Computer and System Sciences"},{"key":"357619_CR19","unstructured":"Marsh, W.E. Some conjectures on indexed languages, paper presented to the Association for Symbolic Logic meeting, Stanford University, July 15\u201319, 1985."},{"key":"357619_CR20","first-page":"1","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"Rabin, M.O. Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society, 141: 1\u201335, 1969.","journal-title":"Transactions of the American Mathematical Society"},{"key":"357619_CR21","unstructured":"Rogers, J. Studies in the Logic of Trees with Applications to Grammar Formalisms, doctoral dissertation, University of Delaware, 1994."},{"key":"357619_CR22","doi-asserted-by":"crossref","unstructured":"Rogers, J. A model-theoretic framework for theories of syntax, Proceedings of the 34th Annual Meeting of the ACL, 10\u201316, 1996.","DOI":"10.3115\/981863.981865"},{"key":"357619_CR23","volume-title":"A Descriptive Approach to Language-Theoretic Complexity","author":"J. Rogers","year":"1998","unstructured":"Rogers, J. A Descriptive Approach to Language-Theoretic Complexity, CSLI Publications, Stanford, CA, 1998."},{"key":"357619_CR24","doi-asserted-by":"crossref","unstructured":"Rounds, W.C. Context-free grammars on trees, First Annual ACM Symposium on Theory of Computing: 143-148, 1969.","DOI":"10.1145\/800169.805428"},{"key":"357619_CR25","doi-asserted-by":"crossref","unstructured":"Rounds, W.C. Tree-oriented proofs of some theorems on context-free and indexed languages Second Annual ACM Symposium on Theory of Computing: 109\u2013116, 1970a.","DOI":"10.1145\/800161.805156"},{"issue":"3","key":"357619_CR26","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF01695769","volume":"4","author":"W.C. Rounds","year":"1970","unstructured":"Rounds, W.C. Mappings and grammars on trees, Mathematical Systems Theory, 4(3): 257-287, 1970b.","journal-title":"Mathematical Systems Theory"},{"key":"357619_CR27","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0022-0000(67)80022-9","volume":"1","author":"J.W. Thatcher","year":"1967","unstructured":"Thatcher, J.W. Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, Journal of Computer and System Sciences, 1: 317\u2013322, 1967.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"357619_CR28","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"Thatcher, J.W. and J.B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic, Mathematical Systems Theory, 2(1): 57\u201381, 1968.","journal-title":"Mathematical Systems Theory"},{"key":"357619_CR29","unstructured":"Thomas, W. Languages, Automata and Logic. In Rozenberg, G. and A. Salomaa, editors, Handbook of Formal Languages, vol. 3, Springer, Berlin."}],"container-title":["Grammars"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1012228321223.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1012228321223\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1012228321223.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T05:56:38Z","timestamp":1754459798000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1012228321223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2001,12]]}},"alternative-id":["357619"],"URL":"https:\/\/doi.org\/10.1023\/a:1012228321223","relation":{},"ISSN":["1386-7393","1572-848X"],"issn-type":[{"type":"print","value":"1386-7393"},{"type":"electronic","value":"1572-848X"}],"subject":[],"published":{"date-parts":[[2001,12]]}}}