{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:01:25Z","timestamp":1780743685255,"version":"3.54.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319108810","type":"print"},{"value":"9783319108827","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-10882-7_16","type":"book-chapter","created":{"date-parts":[[2014,9,11]],"date-time":"2014-09-11T06:54:19Z","timestamp":1410418459000},"page":"259-276","source":"Crossref","is-referenced-by-count":1,"title":["Context-Free Sequences"],"prefix":"10.1007","author":[{"given":"Didier","family":"Caucal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marion","family":"Le Gonidec","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"16_CR1","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"A. Aho","year":"1968","unstructured":"Aho, A.: Indexed grammars - an extension of context-free grammars. Journal of the Association for Computing Machinery\u00a015(4), 647\u2013671 (1968)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"16_CR2","unstructured":"Aho, A., Ullman, J.: Introduction to automata theory, languages and computation, p. 418. Addison-Wesley (1979), doi:A. Aho"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Allouche, J.-P., Shallit, J.: Automatic sequences: theory, applications, generalizations. Cambridge University Press (2003)","DOI":"10.1017\/CBO9780511546563"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Berstel, J.: On sets of numbers recognized by push-down automata. In: 13th Symposium on Switching and Automata Theory (SWAT - FOCS), pp. 200\u2013206. IEEE (1972)","DOI":"10.1109\/SWAT.1972.11"},{"key":"#cr-split#-16_CR5.1","doi-asserted-by":"crossref","unstructured":"Caucal, D.: On the regular structure of prefix rewriting. In: Arnold, A. (ed.) HCC11 2014. LNCS, pp. 87-102 (1990)","DOI":"10.1007\/3-540-52590-4_42"},{"key":"#cr-split#-16_CR5.2","doi-asserted-by":"crossref","unstructured":"Theoretical Computer Science\u00a0106, 61-86 (1992)","DOI":"10.1016\/0304-3975(92)90278-N"},{"key":"16_CR6","unstructured":"Caucal, D.: Deterministic graph grammars. In: Flum, J., Gr\u00e4del, E., Wilke, T. (eds.) Texts in Logic and Games 2, pp. 169\u2013250. Amsterdam University Press (2007)"},{"issue":"4","key":"16_CR7","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s00224-001-1015-5","volume":"34","author":"D. Caucal","year":"2001","unstructured":"Caucal, D., Knapik, T.: On internal presentation of regular graphs by prefix-recognizable graphs. Theory of Computing Systems\u00a034(4), 299\u2013336 (2001)","journal-title":"Theory of Computing Systems"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","volume":"2","author":"N. Chomsky","year":"1956","unstructured":"Chomsky, N.: Three models for the description of language. IRE Transactions on Information Theory\u00a02, 113\u2013124 (1956)","journal-title":"IRE Transactions on Information Theory"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/BF01706087","volume":"6","author":"A. Cobham","year":"1972","unstructured":"Cobham, A.: Uniform-tag sequences. Mathematical Systems Theory\u00a06, 164\u2013192 (1972)","journal-title":"Mathematical Systems Theory"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/BF01746527","volume":"3","author":"A. Cobham","year":"1969","unstructured":"Cobham, A.: On the base-dependence of sets of numbers recognizable by finite automata. Mathematical Systems Theory\u00a03, 186\u2013192 (1969)","journal-title":"Mathematical Systems Theory"},{"key":"16_CR11","unstructured":"Hamm, D.: Contributions to formal language theory: Fixed points, complexity, and context-free sequences, M.Sc. Thesis, University of Waterloo (1998)"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Kleene, S.: Representation of events in nerve nets and finite automata. In: Automata studies. Annals of Mathematics Studies, pp. 3\u201341. Princeton University Press (1956)","DOI":"10.1515\/9781400882618-002"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1051\/ita:2008012","volume":"42","author":"M. Gonidec Le","year":"2008","unstructured":"Le Gonidec, M.: Drunken man infinite words complexity. RAIRO - Theoretical Informatics and Applications\u00a042, 599\u2013613 (2008)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"issue":"1","key":"16_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2011.09.022","volume":"44","author":"M. Gonidec Le","year":"2012","unstructured":"Le Gonidec, M.: On the complexity of a family of k-context-free sequences. Theoretical Computer Science\u00a044(1), 47\u201354 (2012)","journal-title":"Theoretical Computer Science"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Applied Combinatorics on Words. Cambridge University Press (2005)","DOI":"10.1017\/CBO9781107341005"},{"key":"16_CR16","first-page":"1013","volume":"217","author":"A. Maslov","year":"1974","unstructured":"Maslov, A.: The hierarchy of indexed languages of an arbitrary level. Doklady Akademii Nauk SSSR\u00a0217, 1013\u20131016 (1974)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2008.02.018","volume":"400","author":"Y. Moshe","year":"2008","unstructured":"Moshe, Y.: On some questions regarding k-regular and k-context-free sequences. Theoretical Computer Science\u00a0400, 62\u201369 (2008)","journal-title":"Theoretical Computer Science"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D. Muller","year":"1985","unstructured":"Muller, D., Schupp, P.: The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science\u00a037, 51\u201375 (1985)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"16_CR19","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0020-0190(89)90108-7","volume":"31","author":"S. Yu","year":"1989","unstructured":"Yu, S.: A pumping lemma for deterministic context-free languages. Information Processing Letters\u00a031(1), 47\u201351 (1989)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-10882-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T21:36:50Z","timestamp":1558993010000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-10882-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319108810","9783319108827"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-10882-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}