{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T14:41:41Z","timestamp":1779374501766,"version":"3.53.1"},"reference-count":50,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1987,7,1]],"date-time":"1987-07-01T00:00:00Z","timestamp":552096000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":9513,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1987,7]]},"DOI":"10.1016\/0890-5401(87)90012-5","type":"journal-article","created":{"date-parts":[[2004,12,16]],"date-time":"2004-12-16T20:34:26Z","timestamp":1103229266000},"page":"64-89","source":"Crossref","is-referenced-by-count":10,"title":["The Dyck language D'1\u2217 is not generated by any matrix grammar of finite index"],"prefix":"10.1016","volume":"74","author":[{"given":"Brigitte","family":"Rozoy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/0890-5401(87)90012-5_BIB1","first-page":"61","article-title":"Some questions of phrase structure grammars","volume":"4","author":"Abraham","year":"1965","journal-title":"Comput. Lingustics"},{"key":"10.1016\/0890-5401(87)90012-5_BIB2","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1016\/S0022-0000(70)80027-7","article-title":"A characterization of two-way deterministic classes of languages","volume":"4","author":"Aho","year":"1970","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB3","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0019-9958(79)90642-9","article-title":"Deux familles de langages incomparables","volume":"43-2","author":"Beauquier","year":"1979","journal-title":"Inform. and Control"},{"key":"10.1016\/0890-5401(87)90012-5_BIB4","author":"Berstel","year":"1979"},{"key":"10.1016\/0890-5401(87)90012-5_BIB5","series-title":"Les s\u00e9ries rationnelles et leurs languages","author":"Berstel","year":"1984"},{"key":"10.1016\/0890-5401(87)90012-5_BIB6","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1016\/S0019-9958(67)90771-1","article-title":"An analog of a theorem on context-free languages","volume":"11","author":"Brainerd","year":"1968","journal-title":"Inform and Control"},{"key":"10.1016\/0890-5401(87)90012-5_BIB7","series-title":"Two-way finite generators","author":"Culik","year":"1985"},{"key":"10.1016\/0890-5401(87)90012-5_BIB8","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1137\/0210039","article-title":"Pumping lemmas for regular sets","volume":"10","author":"Ehrenfeucht","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(87)90012-5_BIB9_1","first-page":"13","article-title":"A pumping theorem for deterministic ETOL languages","volume":"2\u20139","author":"Ehrenfeucht","year":"1975","journal-title":"RAIRO Inform. Th\u00e9or"},{"issue":"4","key":"10.1016\/0890-5401(87)90012-5_BIB9_2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1051\/ita\/1977110402731","article-title":"On some context-free languages that are not deterministic ETOL languages","volume":"11","author":"Ehrenfeucht","year":"1977","journal-title":"RAIRO Inform. Theor."},{"key":"10.1016\/0890-5401(87)90012-5_BIB10","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1016\/S0019-9958(71)90483-9","article-title":"Two-Way sequential transduction and stack automata","volume":"18","author":"Ehrich","year":"1971","journal-title":"Inform. and Control."},{"key":"10.1016\/0890-5401(87)90012-5_BIB11","author":"Engelfriet","year":"1981"},{"key":"10.1016\/0890-5401(87)90012-5_BIB12_1","article-title":"Languages matriciels et principalit\u00e9","author":"Ferment","year":"1984"},{"key":"10.1016\/0890-5401(87)90012-5_BIB12_2","first-page":"151","article-title":"Principality results about some matrix languages families","volume":"Vol. 172","author":"Ferment","year":"1984"},{"issue":"No. 2","key":"10.1016\/0890-5401(87)90012-5_BIB13","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1145\/321386.321403","article-title":"One-way stack automata","volume":"14","author":"Ginsburg","year":"1967","journal-title":"J. Assoc. Comput. Math."},{"key":"10.1016\/0890-5401(87)90012-5_BIB14_1","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/S0022-0000(69)80012-7","article-title":"Cheeking automata and one-way stack languages","volume":"3","author":"Greibach","year":"1969","journal-title":"J. Comput. System. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB14_2","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/S0022-0000(72)80039-4","article-title":"Syntactic operators on full semi-AFLS","volume":"6","author":"Greibach","year":"1972","journal-title":"J. Comput. System. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB14_3","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(78)90020-8","article-title":"Remarks on blind and partially blind one-way multicounter machines","volume":"7","author":"Greibach","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB14_4","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(78)90035-X","article-title":"One-way finit visit automata","volume":"6","author":"Greibach","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB15","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/S0022-0000(69)80015-2","article-title":"Scattered context grammars","volume":"3","author":"Greibach","year":"1969","journal-title":"J. Comput. System. Sci."},{"issue":"No. 3","key":"10.1016\/0890-5401(87)90012-5_BIB16","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1137\/0211035","article-title":"The equivalence pb. for deterministic two-way sequential transducers is decideble","volume":"11","author":"Gurari","year":"1982","journal-title":"SIAM. J. Comput."},{"key":"10.1016\/0890-5401(87)90012-5_BIB17","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(79)90049-7","article-title":"Some decisions problems concerning sequential transducers and checking automata","volume":"18","author":"Ibarra","year":"1979","journal-title":"J. Comput. System. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB18_1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(78)90019-1","article-title":"On two-way sequential transductions of full semi-AFL's","volume":"7","author":"Ibarra","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB18_2","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/322047.322058","article-title":"Reversal-bounded multicounter machines and their decision problems","volume":"25","author":"Ibarra","year":"1978","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0890-5401(87)90012-5_BIB18_3","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/S0019-9958(70)80034-1","article-title":"Simple matrix languages","volume":"17","author":"Ibarra","year":"1970","journal-title":"Inform. and Control."},{"key":"10.1016\/0890-5401(87)90012-5_BIB19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0019-9958(74)80054-9","article-title":"Parallel context-free languages","volume":"24","author":"Krithivasan","year":"1974","journal-title":"Inform. and Control"},{"key":"10.1016\/0890-5401(87)90012-5_BIB20_1","article-title":"EDTOL, syst\u00e8mes ultralin\u00e9aires et op. associ\u00e9s","author":"Latteux","year":"1977"},{"issue":"No. 2","key":"10.1016\/0890-5401(87)90012-5_BIB20_2","doi-asserted-by":"crossref","DOI":"10.1016\/S0019-9958(79)90641-7","article-title":"Substitutions dans les EDTOL","volume":"42","author":"Latteux","year":"1979","journal-title":"Inform. and Control"},{"key":"10.1016\/0890-5401(87)90012-5_BIB20_3","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/BF00288769","article-title":"Sur les g\u00e9n\u00e9rateurs alg\u00e9briques ultralin\u00e9aires","volume":"13","author":"Latteux","year":"1980","journal-title":"Acta Inform."},{"key":"10.1016\/0890-5401(87)90012-5_BIB20_4","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0304-3975(81)90020-7","article-title":"A propos du lemme de substitution","volume":"14","author":"Latteux","year":"1981","journal-title":"Theoret. Comput. Sci."},{"issue":"No. 1","key":"10.1016\/0890-5401(87)90012-5_BIB20_5","doi-asserted-by":"crossref","DOI":"10.1016\/0022-0000(83)90018-1","article-title":"Languages \u00e0 un compteur","volume":"26","author":"Latteux","year":"1983","journal-title":"J. Comput. System. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB21","author":"Lothaire","year":"1983"},{"key":"10.1016\/0890-5401(87)90012-5_BIB22_1","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0019-9958(77)90163-2","article-title":"On the index of grammars and languages","volume":"35","author":"Pa\u00f9n","year":"1977","journal-title":"Inform. and Control"},{"issue":"No. 1","key":"10.1016\/0890-5401(87)90012-5_BIB22_2","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1051\/ita\/1980140101191","article-title":"Some consequence of a reslt of Ehrenfeucht and Rozenberg","volume":"14","author":"Pa\u00f9n","year":"1980","journal-title":"RAIRO Inform. Th\u00e9or."},{"issue":"No. 3","key":"10.1016\/0890-5401(87)90012-5_BIB22_3","doi-asserted-by":"crossref","DOI":"10.1016\/0022-0000(79)90035-7","article-title":"On the family of finite index matrix lang","volume":"18","author":"Pa\u00f9n","year":"1979","journal-title":"J. Comput. System. Sci."},{"issue":"No. 3","key":"10.1016\/0890-5401(87)90012-5_BIB22_4","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1051\/ita\/1982160302451","article-title":"On simple matrix languages versus scattered context languages","volume":"16","author":"Pa\u00f9n","year":"1982","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"10.1016\/0890-5401(87)90012-5_BIB23_1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0304-3975(85)90009-X","article-title":"Automates boustrophedons et mots infinis","volume":"35","author":"Pecuchet","year":"1985","journal-title":"Theoret. Comput. Sci."},{"issue":"No. 1","key":"10.1016\/0890-5401(87)90012-5_BIB23_2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1051\/ita\/1985190100711","article-title":"Automates boustrophedons, semi-groupe de Birget et mono\u00efde inversif libre","volume":"19","author":"Pecuchet","year":"1985","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"10.1016\/0890-5401(87)90012-5_BIB24_1","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/S0022-0000(72)80025-4","article-title":"Absolutely parallel grammars and two-way finite state transducers","volume":"6","author":"Rajlich","year":"1972","journal-title":"J. Comput. System. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB24_2","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/S0019-9958(75)90159-X","article-title":"Bounded crossing transducers","volume":"27","author":"Rajlich","year":"1975","journal-title":"Inform. and Control"},{"key":"10.1016\/0890-5401(87)90012-5_BIB25","author":"Rozenberg","year":"1980"},{"key":"10.1016\/0890-5401(87)90012-5_BIB26_1","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0019-9958(78)90050-5","article-title":"On ETOL system of finite index","volume":"38","author":"Rozenberg","year":"1978","journal-title":"Inform. and Control"},{"key":"10.1016\/0890-5401(87)90012-5_BIB26_2","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/S0019-9958(78)90635-6","article-title":"On the effect of the finite index restriction on several families of grammars","volume":"39","author":"Rozenberg","year":"1978","journal-title":"Inform. and Control"},{"key":"10.1016\/0890-5401(87)90012-5_BIB27_1","first-page":"371","article-title":"About two-way transducers","volume":"Vol. 199","author":"Rozoy","year":"1985"},{"issue":"No. 3","key":"10.1016\/0890-5401(87)90012-5_BIB27_2","first-page":"1","article-title":"Outils et r\u00e9sultats pour les transducteurs boustrophedons","volume":"20","author":"Rozoy","year":"1986","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"10.1016\/0890-5401(87)90012-5_BIB28_1","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1016\/S0019-9958(69)90164-8","article-title":"On the index of context-free grammars and languages","volume":"14","author":"Salomaa","year":"1969","journal-title":"Inform. and Control"},{"key":"10.1016\/0890-5401(87)90012-5_BIB28_2","author":"Salomaa","year":"1973"},{"key":"10.1016\/0890-5401(87)90012-5_BIB29","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1214\/aoms\/1177704860","article-title":"On a special case of regular events","volume":"32","author":"Schutzenberger","year":"1961","journal-title":"Ann. of Math."},{"key":"10.1016\/0890-5401(87)90012-5_BIB30","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/S0022-0000(71)80015-6","article-title":"Finite turn checking automata","volume":"5","author":"Siromoney","year":"1971","journal-title":"J. Comput. System. Sci."},{"key":"10.1016\/0890-5401(87)90012-5_BIB31","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/S0019-9958(74)91399-0","article-title":"Parallel context-free languages","volume":"26","author":"Skyum","year":"1974","journal-title":"Inform. and Control"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540187900125?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540187900125?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T01:26:08Z","timestamp":1548897968000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0890540187900125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,7]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,7]]}},"alternative-id":["0890540187900125"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(87)90012-5","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1987,7]]}}}