{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:02:17Z","timestamp":1767139337241,"version":"build-2238731810"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Russian Ministry of Science and Higher Education","award":["075-15-2022-287"],"award-info":[{"award-number":["075-15-2022-287"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s00224-022-10108-6","type":"journal-article","created":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T10:06:57Z","timestamp":1669889217000},"page":"234-262","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Transformation of LL(k)-linear to LL(1)-linear Grammars"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3949-5640","authenticated-orcid":false,"given":"Ilya","family":"Olkhovsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,1]]},"reference":[{"key":"10108_CR1","unstructured":"Aho, A. V., Ullman, J. D.: The Theory of Parsing, Translation and Compiling, vol. 1, Parsing. Prentice-Hall (1972)"},{"key":"10108_CR2","doi-asserted-by":"crossref","unstructured":"de la Higuera, C., Oncina, J.: Inferring deterministic linear languages. In: Computational Learning Theory (COLT 2002, Sydney, Australia, July 8\u201310, 2002, LNCS 2375, 185\u2013200 (2002)","DOI":"10.1007\/3-540-45435-7_13"},{"key":"10108_CR3","doi-asserted-by":"crossref","unstructured":"Holzer, M., Lange, K. -J.: On the complexities of linear LL(1) and LR(1) grammars. In: Fundamentals of Computation Theory (FCT 1993, Hungary, August 23\u201327, 1993), LNCS 710, 299\u2013308 (1993)","DOI":"10.1007\/3-540-57163-9_25"},{"issue":"3","key":"10108_CR4","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(88)90047-6","volume":"29","author":"OH Ibarra","year":"1988","unstructured":"Ibarra, O. H., Jiang, T., Ravikumar, B.: Some subclasses of context-free languages in NC1. Inf. Process. Lett. 29(3), 111\u2013117 (1988)","journal-title":"Inf. Process. Lett."},{"key":"10108_CR5","doi-asserted-by":"publisher","first-page":"104778","DOI":"10.1016\/j.ic.2021.104778","volume":"286","author":"G Jir\u00e1skov\u00e1","year":"2022","unstructured":"Jir\u00e1skov\u00e1, G., Kl\u00edma, O.: On linear languages recognized by deterministic biautomata. Inf. Comput. 286, 104778 (2022)","journal-title":"Inf. Comput."},{"key":"10108_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF00289517","volume":"1","author":"DE Knuth","year":"1971","unstructured":"Knuth, D. E.: Top-down syntax analysis. Acta Inf. 1, 79\u2013110 (1971)","journal-title":"Acta Inf."},{"issue":"3","key":"10108_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF01946814","volume":"9","author":"R Kurki-Suonio","year":"1969","unstructured":"Kurki-Suonio, R.: Notes on top-down languages. BIT Numer. Math. 9(3), 225\u2013238 (1969)","journal-title":"BIT Numer. Math."},{"issue":"3","key":"10108_CR8","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1145\/321466.321477","volume":"15","author":"PMII Lewis","year":"1968","unstructured":"Lewis, P. M. II., Stearns, R. E.: Syntax-directed transduction. J. ACM 15(3), 465\u2013488 (1968)","journal-title":"J. ACM"},{"issue":"39","key":"10108_CR9","doi-asserted-by":"publisher","first-page":"5132","DOI":"10.1016\/j.tcs.2011.05.013","volume":"412","author":"A Okhotin","year":"2011","unstructured":"Okhotin, A.: Expressive power of LL(k) Boolean grammars. Theor. Comput. Sci. 412(39), 5132\u20135155 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"10108_CR10","doi-asserted-by":"crossref","unstructured":"Okhotin, A.: Underlying principles and recurring ideas of formal grammars. In: Language and Automata Theory and Applications (LATA 2018, Bar-Ilan near Tel Aviv, Israel, 9\u201311 April 2018), LNCS 10792, 36\u201359 (2018)","DOI":"10.1007\/978-3-319-77313-1_3"},{"key":"10108_CR11","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/S0019-9958(70)90446-8","volume":"17","author":"DJ Rosenkrantz","year":"1970","unstructured":"Rosenkrantz, D. J., Stearns, R. E.: Properties of deterministic top-down grammars. Inf. Control. 17, 226\u2013256 (1970)","journal-title":"Inf. Control."}],"updated-by":[{"DOI":"10.1007\/s00224-023-10120-4","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2023,2,11]],"date-time":"2023-02-11T00:00:00Z","timestamp":1676073600000}}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10108-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10108-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10108-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,14]],"date-time":"2023-03-14T06:08:50Z","timestamp":1678774130000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10108-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,1]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10108"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10108-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,1]]},"assertion":[{"value":"25 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2023","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00224-023-10120-4","URL":"https:\/\/doi.org\/10.1007\/s00224-023-10120-4","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}