Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [11 references]  Display  Hide  Download
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


Files produced by the author(s)



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⟩



Record views


Files downloads