DOI

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.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 15th International Conference, LATA 2021, Proceedings
EditorsAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
PublisherSpringer Nature
Pages118-130
Number of pages13
ISBN (Print)9783030681944
DOIs
StatePublished - Feb 2021
Event15th International Conference on Language and Automata Theory and Applications, LATA 2021 - Milan, Italy
Duration: 1 Mar 2021 → 5 Mar 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12638 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Language and Automata Theory and Applications, LATA 2021
Country/TerritoryItaly
CityMilan
Period1/03/21 → 5/03/21

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78911531