Standard

On Hardest Languages for One-Dimensional Cellular Automata. / Mrykhin, Mikhail; Okhotin, Alexander.

Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings. ed. / Alberto Leporati; Carlos Martín-Vide; Dana Shapira; Claudio Zandron. Springer Nature, 2021. p. 118-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12638 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Mrykhin, M & Okhotin, A 2021, On Hardest Languages for One-Dimensional Cellular Automata. in A Leporati, C Martín-Vide, D Shapira & C Zandron (eds), Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12638 LNCS, Springer Nature, pp. 118-130, 15th International Conference on Language and Automata Theory and Applications, LATA 2021, Milan, Italy, 1/03/21. https://doi.org/10.1007/978-3-030-68195-1_10

APA

Mrykhin, M., & Okhotin, A. (2021). On Hardest Languages for One-Dimensional Cellular Automata. In A. Leporati, C. Martín-Vide, D. Shapira, & C. Zandron (Eds.), Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings (pp. 118-130). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12638 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-68195-1_10

Vancouver

Mrykhin M, Okhotin A. On Hardest Languages for One-Dimensional Cellular Automata. In Leporati A, Martín-Vide C, Shapira D, Zandron C, editors, Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings. Springer Nature. 2021. p. 118-130. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-68195-1_10

Author

Mrykhin, Mikhail ; Okhotin, Alexander. / On Hardest Languages for One-Dimensional Cellular Automata. Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings. editor / Alberto Leporati ; Carlos Martín-Vide ; Dana Shapira ; Claudio Zandron. Springer Nature, 2021. pp. 118-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{32df631dde9c419987b0f513cbbc5b38,
title = "On Hardest Languages for One-Dimensional Cellular Automata",
abstract = "Since the famous construction of “the hardest context-free language” by Greibach (1973), the existence of hardest languages under homomorphic reductions has been investigated for quite a few language families. This paper shows that for one-way real-time cellular automata, also known as trellis automata, there is no hardest language, whereas for linear-time cellular automata, the hardest language is constructed.",
author = "Mikhail Mrykhin and Alexander Okhotin",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 15th International Conference on Language and Automata Theory and Applications, LATA 2021 ; Conference date: 01-03-2021 Through 05-03-2021",
year = "2021",
month = feb,
doi = "10.1007/978-3-030-68195-1_10",
language = "English",
isbn = "9783030681944",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "118--130",
editor = "Alberto Leporati and Carlos Mart{\'i}n-Vide and Dana Shapira and Claudio Zandron",
booktitle = "Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - On Hardest Languages for One-Dimensional Cellular Automata

AU - Mrykhin, Mikhail

AU - Okhotin, Alexander

N1 - Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021/2

Y1 - 2021/2

N2 - Since the famous construction of “the hardest context-free language” by Greibach (1973), the existence of hardest languages under homomorphic reductions has been investigated for quite a few language families. This paper shows that for one-way real-time cellular automata, also known as trellis automata, there is no hardest language, whereas for linear-time cellular automata, the hardest language is constructed.

AB - Since the famous construction of “the hardest context-free language” by Greibach (1973), the existence of hardest languages under homomorphic reductions has been investigated for quite a few language families. This paper shows that for one-way real-time cellular automata, also known as trellis automata, there is no hardest language, whereas for linear-time cellular automata, the hardest language is constructed.

UR - http://www.scopus.com/inward/record.url?scp=85104464215&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/62ae68ec-cb4d-3aa3-ae5f-36863f3534f9/

U2 - 10.1007/978-3-030-68195-1_10

DO - 10.1007/978-3-030-68195-1_10

M3 - Conference contribution

AN - SCOPUS:85104464215

SN - 9783030681944

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 118

EP - 130

BT - Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings

A2 - Leporati, Alberto

A2 - Martín-Vide, Carlos

A2 - Shapira, Dana

A2 - Zandron, Claudio

PB - Springer Nature

T2 - 15th International Conference on Language and Automata Theory and Applications, LATA 2021

Y2 - 1 March 2021 through 5 March 2021

ER -

ID: 78911531