Some Computational Limits of Trellis Automata

Véronique Terrier 1
1 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : We investigate some computational limits of trellis automata. Reusing a counting argument introduced in [4], we show that: {x_1,..., x_n,y_1,...,y_n : x_iy_i ∈ {ab, ba, bb} for i = 1,. .. , n} is not a trellis language.[4]Ana¨ll Grandjean, Gaétan Richard, and Véronique Terrier. Linear functional classes over cellular automata. In Enrico Formenti, editor, Proceedings AUTOMATA & JAC 2012, pages 177–193, 2012
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01578301
Contributor : Référent Amacc Référent de l'Équipe Amacc - Laboratoire Greyc - Umr6072 <>
Submitted on : Tuesday, August 29, 2017 - 12:59:44 AM
Last modification on : Tuesday, April 2, 2019 - 1:33:48 AM

File

vergleich.pdf
Files produced by the author(s)

Identifiers

Citation

Véronique Terrier. Some Computational Limits of Trellis Automata. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.176-186, ⟨10.1007/978-3-319-58631-1_14⟩. ⟨hal-01578301⟩

Share

Metrics

Record views

218

Files downloads

124