Результаты исследований: Научные публикации в периодических изданиях › статья в журнале по материалам конференции › Рецензирование
On hardest languages for one-dimensional cellular automata. / Мрыхин, Михаил Кириллович; Охотин, Александр Сергеевич.
в: Information and Computation, Том 295, № A, 104891, 01.12.2023.Результаты исследований: Научные публикации в периодических изданиях › статья в журнале по материалам конференции › Рецензирование
}
TY - JOUR
T1 - On hardest languages for one-dimensional cellular automata
AU - Мрыхин, Михаил Кириллович
AU - Охотин, Александр Сергеевич
PY - 2023/12/1
Y1 - 2023/12/1
N2 - The existence of “hardest languages” in the sense of Greibach (“The hardest context-free language”, 1973) is investigated for two families of cellular automata. For one-way real-time cellular automata, also known as trellis automata, it is shown that there is no hardest language under reductions by deterministic finite transducers. For linear-time cellular automata, a hardest language under reductions by homomorphisms is constructed.
AB - The existence of “hardest languages” in the sense of Greibach (“The hardest context-free language”, 1973) is investigated for two families of cellular automata. For one-way real-time cellular automata, also known as trellis automata, it is shown that there is no hardest language under reductions by deterministic finite transducers. For linear-time cellular automata, a hardest language under reductions by homomorphisms is constructed.
KW - Cellular automata
KW - Finite transducers
KW - Hardest languages
KW - Homomorphisms
UR - https://www.mendeley.com/catalogue/7ca3d31f-898a-3b12-9dca-7d65b5218c55/
U2 - 10.1016/j.ic.2022.104891
DO - 10.1016/j.ic.2022.104891
M3 - Conference article
VL - 295
JO - Information and Computation
JF - Information and Computation
SN - 0890-5401
IS - A
M1 - 104891
T2 - 15th International Conference on Language and Automata Theory and Applications, LATA 2021
Y2 - 1 March 2021 through 5 March 2021
ER -
ID: 114079205