Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
The Hardest LL(k) Language. / Mrykhin, Mikhail; Okhotin, Alexander.
Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings. ред. / Nelma Moreira; Rogério Reis. Springer Nature, 2021. стр. 304-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 12811 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - The Hardest LL(k) Language
AU - Mrykhin, Mikhail
AU - Okhotin, Alexander
N1 - Publisher Copyright: © 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - This paper establishes an analogue of Greibach’s hardest language theorem (“The hardest context-free language”, SIAM J. Comp., 1973) for the subfamily of LL languages. The first result is that there is a language L0 defined by an LL(1) grammar in the Greibach normal form, to which every language L defined by an LL(1) grammar in the Greibach normal form can be reduced by a homomorphism, that is, w∈ L if and only if h(w) ∈ L0. Then it is shown that this statement does not hold for LL(k) languages. The second hardest language theorem is then established in the following form: there is a language L0 defined by an LL(1) grammar in the Greibach normal form, such that, for every language L defined by an LL(k) grammar, there exists a homomorphism h, for which w∈ L if and only if h(w$ ) ∈ L0, where $ is a new symbol.
AB - This paper establishes an analogue of Greibach’s hardest language theorem (“The hardest context-free language”, SIAM J. Comp., 1973) for the subfamily of LL languages. The first result is that there is a language L0 defined by an LL(1) grammar in the Greibach normal form, to which every language L defined by an LL(1) grammar in the Greibach normal form can be reduced by a homomorphism, that is, w∈ L if and only if h(w) ∈ L0. Then it is shown that this statement does not hold for LL(k) languages. The second hardest language theorem is then established in the following form: there is a language L0 defined by an LL(1) grammar in the Greibach normal form, such that, for every language L defined by an LL(k) grammar, there exists a homomorphism h, for which w∈ L if and only if h(w$ ) ∈ L0, where $ is a new symbol.
UR - http://www.scopus.com/inward/record.url?scp=85113203405&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/740f0faa-b507-30e3-93cb-641a46761d6f/
U2 - 10.1007/978-3-030-81508-0_25
DO - 10.1007/978-3-030-81508-0_25
M3 - Conference contribution
AN - SCOPUS:85113203405
SN - 9783030815073
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 304
EP - 315
BT - Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings
A2 - Moreira, Nelma
A2 - Reis, Rogério
PB - Springer Nature
T2 - 25th International Conference on Developments in Language Theory, DLT 2021
Y2 - 16 August 2021 through 20 August 2021
ER -
ID: 85900779