{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:44:24Z","timestamp":1777596264226,"version":"3.51.4"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:p> This paper establishes an analogue of Greibach\u2019s hardest language theorem (\u201cThe hardest context-free language\u201d, SIAM J. Comp., 1973, http:\/\/dx.doi.org\/10.1137\/0202025 ) for the classical family of LL([Formula: see text]) languages. The first result is that there is a language [Formula: see text] defined by an LL(1) grammar in the Greibach normal form, to which every language [Formula: see text] defined by an LL(1) grammar in the Greibach normal form can be reduced by a homomorphism, that is, [Formula: see text] if and only if [Formula: see text]. Then it is shown that this statement does not hold for the full class of LL([Formula: see text]) languages. The other hardest language theorem is then established in the following form: there is a language [Formula: see text] defined by an LL(1) grammar in the Greibach normal form, such that, for every language [Formula: see text] defined by an LL([Formula: see text]) grammar, with [Formula: see text], there exists a homomorphism [Formula: see text], for which [Formula: see text] if and only if [Formula: see text] [Formula: see text] [Formula: see text], where [Formula: see text] is a new symbol. The results lead to two robust language families: the closures of the languages defined by LL(1) grammars in the Greibach normal form under inverse homomorphisms and under inverse finite transductions. <\/jats:p>","DOI":"10.1142\/s012905412344001x","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T03:41:46Z","timestamp":1678074106000},"page":"289-319","source":"Crossref","is-referenced-by-count":1,"title":["The Hardest LL(k) Language"],"prefix":"10.1142","volume":"34","author":[{"given":"Mikhail","family":"Mrykhin","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, St. Petersburg State University, 14th Line V. O., 29, Saint Petersburg 199178, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, St. Petersburg State University, 14th Line V. O., 29, Saint Petersburg 199178, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2023,3,6]]},"reference":[{"issue":"1","key":"S012905412344001XBIB001","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01768474","volume":"11","author":"Autebert J.-M.","year":"1977","journal-title":"Mathematical Systems Theory"},{"key":"S012905412344001XBIB002","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1016\/j.ic.2014.03.003","volume":"237","author":"Barash M.","year":"2014","journal-title":"Information and Computation"},{"key":"S012905412344001XBIB003","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF01768473","volume":"11","author":"Boasson L.","year":"1977","journal-title":"Mathematical Systems Theory"},{"issue":"3","key":"S012905412344001XBIB004","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1051\/ita\/1979130302411","volume":"13","author":"\u010cul\u00edk II K.","year":"1979","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"issue":"6","key":"S012905412344001XBIB005","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1016\/S0019-9958(66)80019-0","volume":"9","author":"Ginsburg S.","year":"1966","journal-title":"Information and Control"},{"issue":"4","key":"S012905412344001XBIB006","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"Greibach S. A.","year":"1973","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"S012905412344001XBIB007","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0203009","volume":"3","author":"Greibach S. A.","year":"1974","journal-title":"SIAM Journal on Computing"},{"key":"S012905412344001XBIB008","first-page":"36","volume-title":"7th Annual Symposium on Switching and Automata Theory","author":"Korenjak A. J.","year":"1966"},{"issue":"3","key":"S012905412344001XBIB009","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF01946814","volume":"9","author":"Kurki-Suonio R.","year":"1969","journal-title":"BIT Numerical Mathematics"},{"issue":"7","key":"S012905412344001XBIB010","doi-asserted-by":"crossref","first-page":"1049","DOI":"10.1142\/S0129054113400303","volume":"24","author":"Lehtinen T.","year":"2013","journal-title":"International Journal of Foundations of Computer Science"},{"key":"S012905412344001XBIB011","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1007\/978-3-030-10801-4_25","volume-title":"SOFSEM 2019: Theory and Practice of Computer Science","author":"Makarov V.","year":"2019"},{"key":"S012905412344001XBIB012","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1007\/978-3-030-68195-1_10","volume-title":"Language and Automata Theory and Applications","author":"Mrykhin M.","year":"2021"},{"key":"S012905412344001XBIB013","author":"Mrykhin M.","journal-title":"Information and Computation"},{"issue":"4","key":"S012905412344001XBIB015","first-page":"519","volume":"6","author":"Okhotin A.","year":"2001","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"1","key":"S012905412344001XBIB016","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.ic.2004.03.006","volume":"194","author":"Okhotin A.","year":"2004","journal-title":"Information and Computation"},{"key":"S012905412344001XBIB017","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/978-3-319-98654-8_4","volume-title":"Developments in Language Theory","author":"Okhotin A.","year":"2018"},{"key":"S012905412344001XBIB018","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2018.11.001","volume":"266","author":"Okhotin A.","year":"2019","journal-title":"Information and Computation"},{"key":"S012905412344001XBIB019","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/S0019-9958(70)90446-8","volume":"17","author":"Rosenkrantz D. J.","year":"1970","journal-title":"Information and Control"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905412344001X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T07:53:31Z","timestamp":1679298811000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S012905412344001X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2]]},"references-count":18,"journal-issue":{"issue":"02n03","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10.1142\/S012905412344001X"],"URL":"https:\/\/doi.org\/10.1142\/s012905412344001x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2]]}}}