{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T23:12:31Z","timestamp":1767913951066,"version":"3.49.0"},"reference-count":31,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1973,3,1]],"date-time":"1973-03-01T00:00:00Z","timestamp":99792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,18]],"date-time":"2013-07-18T00:00:00Z","timestamp":1374105600000},"content-version":"vor","delay-in-days":14749,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Control"],"published-print":{"date-parts":[[1973,3]]},"DOI":"10.1016\/s0019-9958(73)90237-4","type":"journal-article","created":{"date-parts":[[2004,12,15]],"date-time":"2004-12-15T04:12:12Z","timestamp":1103083932000},"page":"139-162","source":"Crossref","is-referenced-by-count":44,"title":["Associate languages and derivational complexity of formal grammars and languages"],"prefix":"10.1016","volume":"22","author":[{"given":"Etsuro","family":"Moriya","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0019-9958(73)90237-4_bib1","first-page":"61","article-title":"Some questions of phrase structure grammars I","volume":"4","author":"\u00c1br\u00e1ham","year":"1965","journal-title":"Comput. Linguistics"},{"key":"10.1016\/S0019-9958(73)90237-4_bib2","article-title":"The concept of finite representability","author":"Altman","year":"1964"},{"key":"10.1016\/S0019-9958(73)90237-4_bib3","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0019-9958(65)90196-8","article-title":"Some problems of finite representability","volume":"8","author":"Altman","year":"1965","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib4","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0019-9958(63)90199-2","article-title":"Phrase\\3-structure languages, finite machines and channel capacity","volume":"6","author":"Banerji","year":"1963","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib5","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/S0022-0000(71)80025-9","article-title":"Time\\3-bounded grammars and their languages","volume":"5","author":"Book","year":"1971","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0019-9958(73)90237-4_bib6","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1016\/S0019-9958(67)90771-1","article-title":"An analog of a theorem about context-free languages","volume":"11","author":"Brainerd","year":"1968","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib7","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","article-title":"On certain formal properties of grammars","volume":"2","author":"Chomsky","year":"1959","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib8","series-title":"presented at IFIP Conference of 1971","article-title":"On the combinatorial complexity of context\\3-free grammars","author":"Fleck","year":"1971"},{"key":"10.1016\/S0019-9958(73)90237-4_bib9","article-title":"Grammaires ordonn\u00c9es-grammaires matricielles","author":"Friant","year":"1968"},{"key":"10.1016\/S0019-9958(73)90237-4_bib10","series-title":"Nouvelles caract\u00c9risations","article-title":"Langages ultralin\u00c9aires et superlin\u00c9aires","author":"Friant","year":"1968"},{"key":"10.1016\/S0019-9958(73)90237-4_bib11","series-title":"The Mathematical Theory of Context-Free Languages","author":"Ginsburg","year":"1966"},{"key":"10.1016\/S0019-9958(73)90237-4_bib12","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/S0019-9958(66)80016-5","article-title":"Mappings which preserve context-sensitive languages","volume":"9","author":"Ginsburg","year":"1966","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib13","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/0304034","article-title":"Finite-turn pushdown automata","volume":"4","author":"Ginsburg","year":"1966","journal-title":"SIAM J. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib14","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF01692513","article-title":"Control sets on grammars","volume":"2","author":"Ginsburg","year":"1968","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0019-9958(73)90237-4_bib15","first-page":"29","article-title":"On the complexity of derivations in phrase\\3-structure grammars","volume":"3","author":"Gladkij","year":"1964","journal-title":"Algebri i Logika Sem."},{"key":"10.1016\/S0019-9958(73)90237-4_bib16","doi-asserted-by":"crossref","first-page":"233","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."},{"key":"10.1016\/S0019-9958(73)90237-4_bib17","first-page":"22","article-title":"On a classification of context\\3-free languages","volume":"3","author":"Gruska","year":"1967","journal-title":"Kyberbetika"},{"key":"10.1016\/S0019-9958(73)90237-4_bib18","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/S0019-9958(69)90055-2","article-title":"Some classifications of context\\3-free languages","volume":"14","author":"Gruska","year":"1969","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib19","series-title":"Formal Languages and Their Relation to Automata","author":"Hopcroft","year":"1969"},{"key":"10.1016\/S0019-9958(73)90237-4_bib20","first-page":"480","article-title":"On control sets induced by grammars","author":"Jarvi","year":"1970","journal-title":"Ann. Acad. Sci. Fenn., Ser. A I."},{"key":"10.1016\/S0019-9958(73)90237-4_bib21","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/S0022-0000(70)80045-9","article-title":"An hierarchy between context\\3-free and context\\3-sensitive languages","volume":"4","author":"Kasai","year":"1970","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0019-9958(73)90237-4_bib22","series-title":"IEEE Conference Record of Seventh Annual Symposium on Switching and Automata Theory","first-page":"36","article-title":"Simple deterministic languages","author":"Korenjak","year":"1966"},{"key":"10.1016\/S0019-9958(73)90237-4_bib23","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/PGEC.1964.263815","article-title":"Decision problems of phrase structure grammars","volume":"EC-13","author":"Landweber","year":"1964","journal-title":"IEEE Trans. Electron. Computers"},{"key":"10.1016\/S0019-9958(73)90237-4_bib24","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/S0019-9958(64)90406-1","article-title":"A note on asymmetry in phrase\\3-structure grammars","volume":"7","author":"Matthews","year":"1964","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib25","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0019-9958(72)90287-2","article-title":"Some restrictive devices for context\\3-free grammars","volume":"20","author":"Mayer","year":"1972","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib26","series-title":"State grammars operating under the free interpretation","author":"Moriya","year":"1970"},{"key":"10.1016\/S0019-9958(73)90237-4_bib27","first-page":"541","article-title":"Linear automaton transformations","volume":"9","author":"Nerode","year":"1958"},{"key":"10.1016\/S0019-9958(73)90237-4_bib28","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/321495.321504","article-title":"Programmed grammars and classes of formal languages","volume":"16","author":"Rosenkrantz","year":"1969","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0019-9958(73)90237-4_bib29","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1016\/S0019-9958(69)90164-8","article-title":"On the index of context\\3-free grammars and languages","volume":"14","author":"Salomaa","year":"1969","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib30","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1016\/S0019-9958(70)90464-X","article-title":"Periodically time-variant context\\3-free grammars","volume":"17","author":"Salomaa","year":"1970","journal-title":"Inform. Control"},{"key":"10.1016\/S0019-9958(73)90237-4_bib31","first-page":"35","article-title":"On some restrictions on derivations in phrase\\3-structure grammars","volume":"2","author":"Stotskij","year":"1967","journal-title":"Akad. Nauk SSSR Nauchno-Techn. Inform. Ser."}],"container-title":["Information and Control"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0019995873902374?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0019995873902374?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T09:26:37Z","timestamp":1548926797000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0019995873902374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1973,3]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1973,3]]}},"alternative-id":["S0019995873902374"],"URL":"https:\/\/doi.org\/10.1016\/s0019-9958(73)90237-4","relation":{},"ISSN":["0019-9958"],"issn-type":[{"value":"0019-9958","type":"print"}],"subject":[],"published":{"date-parts":[[1973,3]]}}}