Standard

On hardest languages for one-dimensional cellular automata. / Мрыхин, Михаил Кириллович; Охотин, Александр Сергеевич.

в: Information and Computation, Том 295, № A, 104891, 01.12.2023.

Результаты исследований: Научные публикации в периодических изданияхстатья в журнале по материалам конференцииРецензирование

Harvard

APA

Vancouver

Author

BibTeX

@article{87337b79746e468a81cfba614f80b53e,
title = "On hardest languages for one-dimensional cellular automata",
abstract = "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.",
keywords = "Cellular automata, Finite transducers, Hardest languages, Homomorphisms",
author = "Мрыхин, {Михаил Кириллович} and Охотин, {Александр Сергеевич}",
year = "2023",
month = dec,
day = "1",
doi = "10.1016/j.ic.2022.104891",
language = "English",
volume = "295",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",
number = "A",
note = "15th International Conference on Language and Automata Theory and Applications, LATA 2021 ; Conference date: 01-03-2021 Through 05-03-2021",

}

RIS

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