{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:16Z","timestamp":1760202676897},"reference-count":65,"publisher":"Elsevier","isbn-type":[{"value":"9780444880741","type":"print"}],"license":[{"start":{"date-parts":[[1990,1,1]],"date-time":"1990-01-01T00:00:00Z","timestamp":631152000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1016\/b978-0-444-88074-1.50007-x","type":"book-chapter","created":{"date-parts":[[2014,6,30]],"date-time":"2014-06-30T06:35:27Z","timestamp":1404110127000},"page":"59-102","source":"Crossref","is-referenced-by-count":4,"title":["Context-Free Languages"],"prefix":"10.1016","author":[{"given":"J.","family":"BERSTEL","sequence":"first","affiliation":[]},{"given":"L.","family":"BOASSON","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib1","first-page":"18","article-title":"Group languages","volume":"4","author":"ANISIMOV","year":"1971","journal-title":"Kibernetika (Kiev)"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib2","series-title":"Langages Alg\u00e9briques","author":"AUTEBERT","year":"1987"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib3","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1051\/ita\/1979130403631","article-title":"Quelques probl\u00e8mes ouverts en th\u00e9orie des langages","volume":"13","author":"AUTEBERT","year":"1979","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib4","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1051\/ita\/1984180403271","article-title":"Langages de parentheses, langages NTS et homomorphismes inverses","volume":"18","author":"AUTEBERT","year":"1984","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib5","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0022-0000(87)90015-8","article-title":"Groups and NTS languages","volume":"35","author":"AUTEBERT","year":"1987","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib6","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0020-0190(87)90162-1","article-title":"Prefixes of infinite words and ambiguous context-free languages","volume":"25","author":"AUTEBERT","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib7","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1145\/322307.322315","article-title":"A generalization of Ogden's lemma","volume":"29","author":"BADER","year":"1982","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib8","doi-asserted-by":"crossref","first-page":"261","DOI":"10.2140\/pjm.1979.85.261","article-title":"Avoidable patterns in strings of symbols","volume":"85","author":"BEAN","year":"1979","journal-title":"Pacific J. Math."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib9","doi-asserted-by":"crossref","unstructured":"BEAUQUIER, J., Ambigu\u00eft\u00e9 forte. Proc. 5th Internat. Coll. on Automata, Languages and Programming, Lecture Notes in Computer Science Vol. 62, (Springer, Berlin, 1978) 52\u201362.","DOI":"10.1007\/3-540-08860-1_5"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib10","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(79)90015-X","article-title":"G\u00e9n\u00e9rateurs alg\u00e9briques et syst\u00e8mes de paires it\u00e9rantes","volume":"8","author":"BEAUQUIER","year":"1979","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib11","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0304-3975(87)90051-X","article-title":"On context-free generators","volume":"51","author":"BEAUQUIER","year":"1987","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib12","series-title":"Transductions and Context-Free Languages","author":"BERSTEL","year":"1979"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib13","doi-asserted-by":"crossref","unstructured":"BERSTEL, J., Properties of infinite words: recent results, in: R. Cori, B. Monien, eds., Proc. 6th Ann. Symp. STACS, Lecture Notes in Computer Science, Vol. 349 (Springer, Berlin, 1989) 36\u201346.","DOI":"10.1007\/BFb0028971"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(82)90128-1","article-title":"Position restricted grammar forms and grammars","volume":"17","author":"BLATTNER","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib15","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1051\/ita\/1985190201251","article-title":"Non-g\u00e9n\u00e9rateurs alg\u00e9briques et substitution","volume":"19","author":"BOASSON","year":"1985","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib16","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1051\/ita\/1987210100411","article-title":"Deterministic languages and nongenerators","volume":"21","author":"BOASSON","year":"1987","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib17","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/0022-0000(79)90004-7","article-title":"Reset machines","volume":"19","author":"BOOK","year":"1973","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib18","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(88)90009-6","article-title":"Uniformely growing k-th powerfree homomorphisms","volume":"23","author":"BRANDENBURG","year":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib19","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(88)90019-9","article-title":"On the intersection of stacks and queues","volume":"58","author":"BRANDENBURG","year":"1988","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib20","volume":"245","author":"COHEN","year":"1972"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib21","unstructured":"CRESTIN, J.P., Un langage non ambigu dont le carr\u00e9 est d'ambigu\u00eft\u00e9 non born\u00e9e, in: Proc. 1st Internat. Coll. on Automata, Languages and Programming (North-Holland, Amsterdam, 1973) 377\u2013390."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib22","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0304-3975(82)90023-8","article-title":"A sharp characterization of square-free morphisms","volume":"18","author":"CROCHEMORE","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib23","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/BF00263651","article-title":"Investigations on Hotz groups for arbitrary grammars","volume":"22","author":"DIEKERT","year":"1986","journal-title":"Acta Inform."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib24","unstructured":"DIEKERT, V. and A. M\u00d6BUS, Hotz-isomorphism theorems in formal language theory, in: Proc. 5th Ann. Symp. STACS, Lecture Notes in Computer Science, Vol. 294 (Springer, Berlin, 1988) 125\u2013135."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib25","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01388581","article-title":"The accessibility of finitely presented groups","volume":"81","author":"DUNWOODY","year":"1985","journal-title":"Invent. Math."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib26","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1051\/ita\/1983170100131","article-title":"On the separative power of E0L systems","volume":"17","author":"EHRENFEUCHT","year":"1983","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib27","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1051\/ita\/1985190100431","article-title":"Strong iterative pairs and the regularity of context-free languages","volume":"19","author":"EHRENFEUCHT","year":"1985","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib28","doi-asserted-by":"crossref","unstructured":"FLAJOLET, P., Ambiguity and transcendence, in: Proc. 12th Internat. Coll. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 194 (Springer, Berlin, 1985) 179\u2013188.","DOI":"10.1007\/BFb0015743"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib29","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0304-3975(87)90011-9","article-title":"Analytic models and ambiguity of context-free languages","volume":"49","author":"FLAJOLET","year":"1987","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib30","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF00625283","article-title":"On the Hotz group of a context-free grammar","volume":"18","author":"FROUGNY","year":"1982","journal-title":"Acta Inform."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib31","first-page":"19","article-title":"Some applications of the interchange lemma","volume":"25","author":"GABARR\u00d3","year":"1985","journal-title":"Bull. EATCS"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib32","series-title":"The Mathematical Theory of Context-Free Languages","author":"GINSBURG","year":"1966"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib33","series-title":"Algebraic and Automata-Theoretic Properties of Formal Languages","author":"GINSBURG","year":"1975"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib34","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0022-0000(75)80038-9","article-title":"Uniformly erasable families of languages","volume":"10","author":"GINSBURG","year":"1975","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib35","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(87)90098-6","article-title":"An infinite word language which is not co-CFL","volume":"24","author":"GRAZON","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib36","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/S0022-0000(69)80012-7","article-title":"Checking automata and one-way stack languages","volume":"3","author":"GREIBACH","year":"1969","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib37","unstructured":"HARING-SMITH, R.H., Groups and simple languages, Ph.D. Thesis, Univ. of Illinois at Urbana-Champaign, 1981."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib38","series-title":"Introduction to Formal Language Theory","author":"HARRISON","year":"1978"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib39","first-page":"65","article-title":"Normal form transformations of context-free grammars","volume":"4","author":"HOTZ","year":"1978","journal-title":"Acta Cybernet."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib40","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0304-3975(80)90040-7","article-title":"Eine neue Invariante f\u00fcr kontextfreie Sprachen","volume":"11","author":"HOTZ","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib41","volume":"14","author":"JANTZEN","year":"1988"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib42","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0012-365X(82)90123-6","article-title":"On the number of words in the language {w\u2208\u03a3*\u2223w = w\u223c}","volume":"40","author":"KEMP","year":"1980","journal-title":"Discrete Math."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib43","volume":"5","author":"KUICH","year":"1986"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib44","series-title":"Combinatorics on Words","author":"LOTHAIRE","year":"1983"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib45","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0020-0190(85)90073-0","article-title":"An infinite square-free co-CFL","volume":"20","author":"MAIN","year":"1985","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib46","unstructured":"MULLER, D.E. and P.E. SCHUPP, Pushdown automata, ends, second-order logic and reachability problems, in: Proc. 13th Ann. ACM Symp. on the Theory of Computing (1981) 46\u201354."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib47","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","article-title":"Groups, the theory of ends, and context-free languages","volume":"26","author":"MULLER","year":"1983","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib48","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","article-title":"The theory of ends, pushdown automata, and second-order logic","volume":"37","author":"MULLER","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib49","first-page":"34","article-title":"An annotated bibliography of pumping","volume":"17","author":"NIJHOLT","year":"1982","journal-title":"Bull. EATCS"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib50","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0214031","article-title":"An \u201cinterchange lemma\u201d for context-free languages","volume":"14","author":"OGDEN","year":"1985","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/B978-0-444-88074-1.50007-X_bib51","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1145\/28869.28881","article-title":"The equivalence problem for realtime dpda's","volume":"34","author":"OYAMAGUCHI","year":"1987","journal-title":"J. Assoc. Comp. Mach."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib52","first-page":"1","article-title":"Finite automata","volume":"B","author":"PERRIN","year":"1990"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib53","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1051\/ita\/1982160301911","article-title":"Repetitive strings are not context-free","volume":"16","author":"ROSS","year":"1982","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib54","series-title":"Real and Complex Analysis","author":"RUDIN","year":"1974"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib55","series-title":"Formal Languages","author":"SALOMAA","year":"1973"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib56","first-page":"59","article-title":"Formal languages and power series","volume":"B","author":"SALOMAA","year":"1990"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib57","doi-asserted-by":"crossref","first-page":"885","DOI":"10.2307\/2034080","article-title":"On a theorem of R. Jungen","volume":"13","author":"SCH\u00dcTZENBERGER","year":"1962","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib58","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-0000(85)90055-8","article-title":"The equivalence and inclusion problems for NTS languages","volume":"31","author":"S\u00c9NIZERGUES","year":"1985","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib59","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0304-3975(90)90048-M","article-title":"Some decision problems about controlled rewriting systems","volume":"71","author":"S\u00c9NIZERGUES","year":"1990","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib60","unstructured":"STALLINGS, J., Groups of cohomological dimension one, Proceedings of Symposia in Pure Mathematics, Vol. B (North-Holland, Amsterdam, 1990) 133\u2013191."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib61","first-page":"133","article-title":"Automata on infinite objects","volume":"B","author":"THOMAS","year":"1990"},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib62","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0304-3975(89)90096-0","article-title":"A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is realtime strict","volume":"64","author":"TOMITA","year":"1989","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib63","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/S0022-0000(71)80038-7","article-title":"Three theorems concerning principal AFL's","volume":"5","author":"ULLIAN","year":"1971","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib64","unstructured":"VALKEMA, E., On some relations between formal languages and groups, Proc. Categorical and Algebraic Methods in Computer Science and System Theory (1978) 116\u2013123."},{"key":"10.1016\/B978-0-444-88074-1.50007-X_bib65","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0020-0190(86)90114-6","article-title":"On the intersection of the class of linear context-free languages and the class of single-reset languages","volume":"23","author":"WAGNER","year":"1986","journal-title":"Inform. Process. Lett."}],"container-title":["Formal Models and Semantics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B978044488074150007X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:B978044488074150007X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T23:31:11Z","timestamp":1565566271000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/B978044488074150007X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9780444880741"],"references-count":65,"URL":"https:\/\/doi.org\/10.1016\/b978-0-444-88074-1.50007-x","relation":{},"subject":[],"published":{"date-parts":[[1990]]}}}