{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:07:42Z","timestamp":1775052462515,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642638633","type":"print"},{"value":"9783642591365","type":"electronic"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/978-3-642-59136-5_3","type":"book-chapter","created":{"date-parts":[[2011,7,18]],"date-time":"2011-07-18T15:00:17Z","timestamp":1311001217000},"page":"111-174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":108,"title":["Context-Free Languages and Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Jean-Michel","family":"Autebert","sequence":"first","affiliation":[]},{"given":"Jean","family":"Berstel","sequence":"additional","affiliation":[]},{"given":"Luc","family":"Boasson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,1,4]]},"reference":[{"key":"3_CR1","volume-title":"The Theory of Parsing, Translation and Compiling","author":"AV Aho","year":"1973","unstructured":"A. V. Aho and J. D. Ullman. The Theory of Parsing, Translation and Compiling., volume 1. Prentice-Hall, 1973."},{"key":"3_CR2","volume-title":"Th\u00e9orie des langages et des automates","author":"J-M Autebert","year":"1994","unstructured":"J.-M. Autebert. Th\u00e9orie des langages et des automates. Masson, 1994."},{"key":"3_CR3","volume-title":"Some observations on hardest context-free languages","author":"J-M Autebert","year":"1981","unstructured":"J.-M. Autebert, L. Boasson, and I. H. Sudborough. Some observations on hardest context-free languages. Technical Report 81\u201325, Rapport LITP, April 1981."},{"key":"3_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1","volume-title":"Transductionsand Context-Free Languages","author":"J Berstel","year":"1979","unstructured":"J. Berstel. Transductions\nand Context-Free Languages. Teubner Verlag, 1979."},{"key":"3_CR5","volume-title":"Fundamentals of Computing Theory","author":"M Blattner","year":"1977","unstructured":"M. Blattner and S. Ginsburg. Canonical forms of context-free grammars and position restricted grammar forms. In Karpinski, editor, Fundamentals of Computing Theory, volume 56 of Lect. Notes Comp. Sei., 1977."},{"issue":"6","key":"3_CR6","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/S0022-0000(73)80036-4","volume":"7","author":"L Boasson","year":"1973","unstructured":"L. Boasson. Two iteration theorems for some families of languages. J. Comput. System Sei., 7(6):583\u2013596, December 1973.","journal-title":"J. Comput. System Sei."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF00289506","volume":"2","author":"L Boasson","year":"1973","unstructured":"L. Boasson, J. P. Crestin, and M. Nivat. Familles de langages translatables et ferm\u00e9es par crochet. Acta Inform., 2:383\u2013393, 1973.","journal-title":"Acta Inform."},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(88)90009-6","volume":"23","author":"FJ Brandenburg","year":"1983","unstructured":"F. J. Brandenburg. On the intersection of stacks and queues. Theoret.\nComput. Sci., 23:69\u201382, 1983.","journal-title":"Theoret.Comput. Sci."},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","volume":"2","author":"N Chomsky","year":"1959","unstructured":"N. Chomsky. On certain formal properties of grammars. Inform. and Control, 2:137\u2013167, 1959.","journal-title":"Inform. and Control"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/S0049-237X(08)72023-8","volume-title":"Computerprogramming and formal systems","author":"N Chomsky","year":"1963","unstructured":"N. Chomsky and M. P. Sch\u00fctzenberger. The algebraic theory of context-free languages. In P. Bradford and D. Hirschberg, editors, Computer\nprogramming and formal systems, pages 118\u2013161. North-Holland (Amsterdam), 1963."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1145\/321637.321649","volume":"18","author":"SV Cole","year":"1971","unstructured":"S. V. Cole. Deterministic pushdown store machines and realtime computation. J. Assoc. Comput. Mach., 18:306\u2013328, 1971.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF01768471","volume":"11","author":"B Courcelle","year":"1977","unstructured":"B. Courcelle. On jump deterministic pushdown automata. Math. Systems Theory, 11:87\u2013109, 1977.","journal-title":"Math. Systems Theory"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0022-0000(75)80051-1","volume":"11","author":"A Cremers","year":"1975","unstructured":"A. Cremers and S. Ginsburg. Context-free grammar forms. J. Comput. System Sci., 11:86\u2013117, 1975.","journal-title":"J. Comput. System Sci."},{"key":"3_CR14","first-page":"217","volume-title":"The theory and application of pushdown store machines. In Mathematical Linguistics and Automatic Translation, NSF-IO","author":"RJ Evey","year":"1963","unstructured":"R. J. Evey. The theory and application of pushdown store machines. In Mathematical Linguistics and Automatic Translation, NSF-IO, pages 217\u2013255. Harvard University, May 1963."},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0012-365X(74)90020-X","volume":"10","author":"M Fliess","year":"1974","unstructured":"M. Fliess. Transductions de s\u00e9ries formelles. Discrete Math., 10:57\u201374, 1974.","journal-title":"Discrete Math."},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/321172.321179","volume":"10","author":"RW Floyd","year":"1963","unstructured":"R. W. Floyd. Syntactic analysis and operator precedence. J. Assoc. Comput. Mach., 10:313\u2013333, 1963.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR17","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S Ginsburg","year":"1966","unstructured":"S. Ginsburg. The Mathematical Theory of Context-Free Languages. McGraw-Hill, 1966."},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0304-3975(76)90004-9","volume":"2","author":"S Ginsburg","year":"1976","unstructured":"S. Ginsburg, J. Goldstine, and S. Greibach. Some uniformely erasable families of languages. Theoret. Comput. Sci., 2:29\u201344, 1976.","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-0000(67)80003-5","volume":"1","author":"S Ginsburg","year":"1967","unstructured":"S. Ginsburg and M. A. Harrison. Bracketed context-free languages. J. Comput. System Sei., 1:1\u201323, 1967.","journal-title":"J. Comput. System Sei."},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/321127.321132","volume":"9","author":"S Ginsburg","year":"1962","unstructured":"S. Ginsburg and H. G. Rice. Two families of languages related to ALGOL. J. Assoc. Comput. Mach., 9:350\u2013371, 1962.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1137\/0304034","volume":"4","author":"S Ginsburg","year":"1966","unstructured":"S. Ginsburg and E. Spanier. Finite-turn pushdown automata. SIAM J. Control, 4:429\u2013453, 1966.","journal-title":"SIAM J. Control"},{"key":"3_CR22","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/S0022-0000(68)80009-1","volume":"2","author":"S Ginsburg","year":"1968","unstructured":"S. Ginsburg and E. Spanier. Derivation-bounded languages. J. Comput. System Sei., 2:228\u2013250, 1968.","journal-title":"J. Comput. System Sei."},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S Greibach","year":"1973","unstructured":"S. Greibach. The hardest context-free language. SIAM J. Comput., 2:304\u2013310, 1973.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"3_CR24","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/321250.321254","volume":"12","author":"SA Greibach","year":"1965","unstructured":"S. A. Greibach. A new normal form theorem for context-free phrase structure grammars. J. Assoc. Comput. Mach., 12(1):42\u201352, 1965.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR25","first-page":"20","volume-title":"Jump pda\u2019s, deterministic context-free languages, principal afdl\u2019s and polynomial time recognition","author":"SA Greibach","year":"1973","unstructured":"S. A. Greibach. Jump pda\u2019s, deterministic context-free languages, principal afdl\u2019s and polynomial time recognition. In Proc. 5th Annual ACM Conf. Theory of Computing, pages 20\u201328, 1973."},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0203009","volume":"3","author":"SA Greibach","year":"1974","unstructured":"S. A. Greibach. Jump pda\u2019s and hierarchies of deterministic cf languages. SIAM J. Comput., 3:111\u2013127, 1974.","journal-title":"SIAM J. Comput."},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/S0019-9958(71)90095-7","volume":"19","author":"J Gruska","year":"1971","unstructured":"J. Gruska. A few remarks on the index of context-free grammars and languages. Inform. and Control, 19:216\u2013223, 1971.","journal-title":"Inform. and Control"},{"key":"3_CR28","volume-title":"Introduction to Formal Language Theory","author":"MA Harrison","year":"1978","unstructured":"M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978."},{"key":"3_CR29","volume-title":"Formal Languages and Their Relation to Automata","author":"JE Hoperoft","year":"1969","unstructured":"J. E. Hoperoft and J. D. Ullman. Formal Languages and Their Relation to Automata. Addison-Wesley, 1969."},{"key":"3_CR30","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"JE Hoperoft","year":"1979","unstructured":"J. E. Hoperoft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979."},{"issue":"1","key":"3_CR31","first-page":"65","volume":"4","author":"G Hotz","year":"1978","unstructured":"G. Hotz. Normal form transformations of context-free grammars. Acta Cybernetics, 4(1):65\u201384, 1978.","journal-title":"Acta Cybernetics"},{"key":"3_CR32","volume-title":"Formale Sprachen","author":"G Hotz","year":"1981","unstructured":"G. Hotz and K. Estenfeld. Formale Sprachen. B.I.-Wissenschaftsverlag, 1981."},{"issue":"10","key":"3_CR33","first-page":"507","volume":"25","author":"G Hotz","year":"1989","unstructured":"G. Hotz and T. Kretschmer. The power of the Greibach normal form. Elektron. Inforrnationsverarb. Kybernet., 25(10):507\u2013512, 1989.","journal-title":"Elektron. Inforrnationsverarb. Kybernet."},{"key":"3_CR34","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/S0019-9958(65)90426-2","volume":"8","author":"DE Knuth","year":"1965","unstructured":"D.E. Knuth. On the translation of languages from left to right. Inform. and Control, 8:607\u2013639, 1965.","journal-title":"Inform. and Control"},{"key":"3_CR35","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0019-9958(67)90564-5","volume":"11","author":"DE Knuth","year":"1967","unstructured":"D. E. Knuth. A characterization of parenthesis languages. Inform. and Control, 11:269\u2013289, 1967.","journal-title":"Inform. and Control"},{"key":"3_CR36","first-page":"36","volume-title":"Simple deterministic languages","author":"AJ Korenjack","year":"1966","unstructured":"A. J. Korenjack and J. E. Hoperoft. Simple deterministic languages. In Conference record of seventh annual symposium on switching and automata theory, pages 36\u201346, Berkeley, 1966."},{"key":"3_CR37","unstructured":"W. Kuich. Formal power series, chapter 9. This volume."},{"issue":"3","key":"3_CR38","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1145\/321466.321477","volume":"15","author":"PM Lewis","year":"1968","unstructured":"P. M. Lewis and R. E. Stearns. Syntax-directed transduction. J. Assoc. Comput. Mach., 15(3):465\u2013488, 1968.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"3_CR39","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1145\/321466.321477","volume":"15","author":"R Mc Naughton","year":"1968","unstructured":"R. McNaughton. Parenthesis grammars. J. Assoc. Comput. Mach., 14(3):490\u2013500, 1967.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR40","volume-title":"Transductions des langages de Chomsky, Ch. VI, mim\u00e9ographi\u00e9","author":"M Nivat","year":"1967","unstructured":"M. Nivat. Transductions des langages de Chomsky, Ch. VI,mim\u00e9ographi\u00e9. PhD thesis, Universit\u00e9 de Paris, 1967."},{"key":"3_CR41","doi-asserted-by":"publisher","first-page":"339","DOI":"10.5802\/aif.287","volume":"18","author":"M Nivat","year":"1968","unstructured":"M. Nivat. Transductions des langages de Chomsky. Annales de l\u2019Institut Fourier, 18:339\u2013456, 1968.","journal-title":"Annales de l\u2019Institut Fourier"},{"key":"3_CR42","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1145\/28869.28881","volume":"34","author":"M Oyamaguchi","year":"1987","unstructured":"M. Oyamaguchi. The equivalence problem for realtime dpda\u2019s. J. Assoc. Corn-put. Mach., 34:731\u2013760, 1987.","journal-title":"J. Assoc. Corn-put. Mach."},{"key":"3_CR43","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"RJ Parikh","year":"1966","unstructured":"R. J. Parikh. On context-free languages. J. Assoc. Comput. Mach., 13:570\u2013581, 1966.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR44","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1112\/jlms\/s2-6.4.663","volume":"6","author":"DL Pilling","year":"1973","unstructured":"D. L. Pilling. Commutative regular equations and Parikh\u2019s theorem. J. London Math. Soc., 6:663\u2013666, 1973.","journal-title":"J. London Math. Soc."},{"key":"3_CR45","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/321406.321412","volume":"14","author":"DJ Rosenkrantz","year":"1967","unstructured":"D. J. Rosenkrantz. Matrix equations and normal forms for context-free grammars. J. Assoc. Comput. Mach., 14:501\u2013507, 1967.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR46","first-page":"15","volume-title":"Pushdown automata with terminal languages","author":"J Sakarovitch","year":"1981","unstructured":"Jacques Sakarovitch. Pushdown automata with terminal languages. In Languages and Automata Symposium, number 421 in Publication RIMS, Kyoto University, pages 15\u201329, 1981."},{"key":"3_CR47","volume-title":"Formal Languages","author":"A Salomaa","year":"1973","unstructured":"A. Salomaa. Formal Languages. Academic Press, 1973."},{"key":"3_CR48","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0019-9958(63)90306-1","volume":"6","author":"MP Sch\u00fctzenberger","year":"1963","unstructured":"M. P. Sch\u00fctzenberger. On context-free languages and pushdown automata. Inform. and Control, 6:217\u2013255, 1963.","journal-title":"Inform. and Control"},{"key":"3_CR49","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-0000(85)90055-8","volume":"31","author":"G S\u00e9nizergues","year":"1985","unstructured":"G. S\u00e9nizergues. The equivalence and inclusion problems for NTS languages. J. Comput. System Sci., 31:303\u2013331, 1985.","journal-title":"J. Comput. System Sci."},{"key":"3_CR50","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0890-5401(89)90032-1","volume":"81","author":"G S\u00e9nizergues","year":"1989","unstructured":"G. S\u00e9nizergues. Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages. Inform. Comput., 81:265\u2013279, 1989.","journal-title":"Inform. Comput."},{"key":"3_CR51","first-page":"39","volume":"11","author":"E Shamir","year":"1967","unstructured":"E. Shamir. A representation theorem for algebraic and context-free power series in noncommuting variables. Inform. Comput., 11:39\u2013254, 1967.","journal-title":"Inform. Comput."},{"key":"3_CR52","volume-title":"Parsing Theory, Vol I. EATCS Monographs on Theoretical Computer Science","author":"S Sippu","year":"1988","unstructured":"S. Sippu and E. Soisalon-Soininen. Parsing Theory, Vol I. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1988."},{"key":"3_CR53","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0019-9958(74)90839-0","volume":"25","author":"L Valiant","year":"1974","unstructured":"L. Valiant. The equivalence problem for deterministic finite turn pushdown automata. Inform. and Control, 25:123\u2013133, 1974.","journal-title":"Inform. and Control"},{"key":"3_CR54","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1051\/ita\/1983170100031","volume":"17","author":"H Wechler","year":"1983","unstructured":"H. Wechler. Characterization of rational and algebraic power series. RA IRO Inform. Th\u00e9or., 17:3\u201311, 1983.","journal-title":"RA IRO Inform. Th\u00e9or."},{"key":"3_CR55","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1016\/S0019-9958(67)91032-7","volume":"10","author":"MK Yntema","year":"1967","unstructured":"M. K. Yntema. Inclusion relations among families of context-free languages. Inform. and Control, 10:572\u2013597, 1967.","journal-title":"Inform. and Control"}],"container-title":["Handbook of Formal Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-59136-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:06:13Z","timestamp":1767859573000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-59136-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783642638633","9783642591365"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-59136-5_3","relation":{},"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"4 January 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}