{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:33Z","timestamp":1725663273561},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540083535"},{"type":"electronic","value":"9783540372851"}],"license":[{"start":{"date-parts":[[1977,1,1]],"date-time":"1977-01-01T00:00:00Z","timestamp":220924800000},"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":[[1977]]},"DOI":"10.1007\/3-540-08353-7_125","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:24:54Z","timestamp":1330187094000},"page":"34-43","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Classification of the context-free languages"],"prefix":"10.1007","author":[{"given":"L.","family":"Boasson","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"3_CR1","unstructured":"Arnold: Systemes d'Equations dans le Magmo\u00efde. Ensembles Rationnels et Alg\u00e9briques d'Arbres. Th\u00e8se de Doctorat d'Etat \u2014 Lille I (1977)."},{"key":"3_CR2","unstructured":"Autebert J.M.: Quelques g\u00e9n\u00e9rateurs des Langages alg\u00e9briques. G.I. Fachtag\u00fcng (1973) \u2014 p 124\u2013131."},{"key":"3_CR3","unstructured":"Autebert J.M.: Non principalit\u00e9 du Cylindre des Langages \u00e0 Compteur (\u00e0 para\u00eetre dans Math. System Theory)."},{"key":"3_CR4","unstructured":"Beauquier J.: Contribution \u00e0 l'\u00e9tude de la complexit\u00e9 structurelle des langages alg\u00e9briques. Th\u00e8se de Doctorat d'Etat \u2014 Paris 7 (1977)."},{"key":"3_CR5","unstructured":"Beauquier J.: G\u00e9n\u00e9rateurs alg\u00e9briques non-ambigus in Automata, Languages and Programming (Edinbourg, 1976) p 66\u201373."},{"issue":"6","key":"3_CR6","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1016\/S0022-0000(73)80036-4","volume":"7","author":"L. Boasson","year":"1973","unstructured":"Boasson L.: Two iteration theorems for some families of languages. Jour. of Computer and System Sciences, 7, no 6 (1973), 583\u2013596.","journal-title":"Jour. of Computer and System Sciences"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(74)90050-7","volume":"2","author":"L. Boasson","year":"1973","unstructured":"Boasson L.: The inclusion of the substitution closure of linear and one-counter languages in the largest sub-AFL of the family of context-free languages is proper. Information Processing Letters 2 (1973), 135\u2013140.","journal-title":"Information Processing Letters"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Boasson L.: On the largest (full) sub-AFL of the context-free languages. Math. Foundations of Computer Sciences (1975), 194\u2013198.","DOI":"10.1007\/3-540-07389-2_195"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(76)90033-5","volume":"2","author":"L. Boasson","year":"1976","unstructured":"Boasson L.: Langages alg\u00e9briques, Paires it\u00e9rantes et transductions rationnelles Theoretical Computer Science, 2 (1976), 209\u2013223.","journal-title":"Theoretical Computer Science"},{"key":"3_CR10","first-page":"180","volume":"2","author":"L. Boasson","year":"1973","unstructured":"Boasson L. & Nivat M.: Sur diverses familles de langages ferm\u00e9es par transduction rationnelle. Acta informatica, 2 (1973), 180\u2013188.","journal-title":"Acta informatica"},{"key":"3_CR11","unstructured":"Boasson L. & Nivat M.: Le cylindre des langages lin\u00e9aires (\u00e0 para\u00eetre dans Math. System Theory)."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF00289506","volume":"2","author":"L. Boasson","year":"1973","unstructured":"Boasson L., Crestin J.P. & Nivat M.: Familles de langages translatables et ferm\u00e9es par crochet. Acta Informatica, 2 (1973), 383\u2013393.","journal-title":"Acta Informatica"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Chomsky N. & Sch\u00fctzenberger M.P.: The algebraic theory of context-free languages. Computer Programming and Formal Systems. North Holland (1963).","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"3_CR14","unstructured":"Courcelle B.: A representation of trees by languages. Theoretical Computer Sciences"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Courcelle B. & Nivat M.: Algebraic families of interpretations. 17 h annual symposium on foundations of Computer Science (1976), 137\u2013146.","DOI":"10.1109\/SFCS.1976.3"},{"key":"3_CR16","unstructured":"Cousineau G. & Rifflet J.M.: Sch\u00e9mas de programmes: probl\u00e8mes d'\u00e9quivalence et de complexit\u00e9. Th\u00e8se de 3e cycle \u2014 Paris 7 (1974)."},{"key":"3_CR17","unstructured":"Dauchet M.: Transductions inversibles de foret. Th\u00e8se de 3e cycle \u2014 Universit\u00e9 de Lille I (1975)."},{"key":"3_CR18","unstructured":"Fliess M.: Sur certaines familles de s\u00e9ries formelles. Th\u00e8se de doctorat d'Etat Universit\u00e9 Paris 7 (1972)."},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Friedman E.: Simple languages and free schemes. 17 th annual symposium on foundations of Computer Science (1976), 159\u2013165.","DOI":"10.1109\/SFCS.1976.28"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Ginsburg S.: The mathematical theory of context-free languages. Mc Graw Hill (1966).","DOI":"10.1145\/321312.321318"},{"key":"3_CR21","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1016\/S0019-9958(66)80019-0","volume":"9","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg S. & Greibach S.: Deterministic context-free languages. Information and Control, 9 (1966), 620\u2013648.","journal-title":"Information and Control"},{"key":"3_CR22","first-page":"285","volume":"113","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg S. & Greibach S.: Studies in abstract families of languages. Memoirs of the Amer. Math. Soc., 113 (1966), 285\u2013296.","journal-title":"Memoirs of the Amer. Math. Soc."},{"key":"3_CR23","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(70)80016-2","volume":"4","author":"S. Ginsburg","year":"1970","unstructured":"Ginsburg S. & Greibach S.: Principal AFL. Journ. of Computer and System Sciences 4 (1970), 308\u2013338.","journal-title":"Journ. of Computer and System Sciences"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/S0019-9958(70)80035-3","volume":"17","author":"S. Ginsburg","year":"1970","unstructured":"Ginsburg S. & Harrison M.: On the closure of AFL under reverseal. Information and Control, 17 (1970), 385\u2013409.","journal-title":"Information and Control"},{"key":"3_CR25","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0022-0000(71)80024-7","volume":"5","author":"S. Ginsburg","year":"1971","unstructured":"Ginsburg S. & Spanier E.H.: AFL with the semi-linear property. Jour. of Computer and System Sciences, 5 (1971), 365\u2013396.","journal-title":"Jour. of Computer and System Sciences"},{"key":"3_CR26","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/321495.321503","volume":"16","author":"S. Greibach","year":"1969","unstructured":"Greibach S.: An infinite hierarchy of context-free languages. Jour. of A.C.M., 16 (1969), 91\u2013106.","journal-title":"Jour. of A.C.M."},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01691106","volume":"4","author":"S. Greibach","year":"1970","unstructured":"Greibach S.: Chain of full AFL's. Math. System Theory, 4 (1970), 231\u2013242.","journal-title":"Math. System Theory"},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. Greibach","year":"1973","unstructured":"Greibach S.: The hardest context-free languages. Siam. Jour. on Computing, 2 (1973), 304\u2013310.","journal-title":"Siam. Jour. on Computing"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0203009","volume":"3","author":"S. Greibach","year":"1974","unstructured":"Greibach S.: Jump PDA's and hierarchies of deterministic context-free languages. Siam Jour. on Computing, 3 (1974), 111\u2013127.","journal-title":"Siam Jour. on Computing"},{"key":"3_CR30","unstructured":"Jacob G.: Repr\u00e9sentation et substitution matricielle dans la th\u00e9orie alg\u00e9brique des transductions. Th\u00e8se de doctorat d'Etat \u2014 Paris 7 (1975)."},{"key":"3_CR31","unstructured":"Latteux M.: Cones rationnels commutativement clos. (\u00e0 para\u00eetre dans RAIRO)."},{"key":"3_CR32","doi-asserted-by":"crossref","first-page":"339","DOI":"10.5802\/aif.287","volume":"18","author":"M. Nivat","year":"1968","unstructured":"Nivat M.: Transductions des langages de Chomsky. Annales de l'Institut Fourier, 18 (1968), 339\u2013456.","journal-title":"Annales de l'Institut Fourier"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Nivat M.: Transductions des langages de Chomsky (Ch. VI). Th\u00e8se de doctorat d'Etat \u2014 Paris (1967).","DOI":"10.5802\/aif.287"},{"key":"3_CR34","unstructured":"Nivat M.: On the interpretation of recursive polyadic schemes. Instituto Nazionale di Alta Matematica. Symposia mathematica, Vol. 15 (1974)."},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Ogden W.: Intercalation theorems for pushdown store and stack languages. Ph. D. Thesis \u2014 Standfard (1968).","DOI":"10.1145\/800169.805419"},{"key":"3_CR36","doi-asserted-by":"crossref","unstructured":"Sch\u00fctzenberger M.P.: Sur un langage \u00e9quivalent au langage de Dyck. In Logic, Methodology and philisophy of science \u2014 North Holland (1973), 197\u2013203.","DOI":"10.1016\/S0049-237X(09)70358-1"},{"key":"3_CR37","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1016\/S0019-9958(67)91032-7","volume":"10","author":"Y. K. Yntema","year":"1967","unstructured":"Yntema Y.K.: Inclusion relations among families of context-free languages. Information and control, 10 (1967), 572\u2013597.","journal-title":"Information and control"},{"key":"3_CR38","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1147\/rd.91.0047","volume":"9","author":"C. C. Elgot","year":"1962","unstructured":"Elgot C.C. & Me zei J.E.: On relations defined by generalized finite automata. IBM Jour. of Res. and Dev. 9 (1962), 47\u201368.","journal-title":"IBM Jour. of Res. and Dev."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1977"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08353-7_125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T11:53:06Z","timestamp":1713613986000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08353-7_125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083535","9783540372851"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-08353-7_125","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]},"assertion":[{"value":"24 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}