Some Computational Limits of Trellis Automata

Véronique Terrier (1)

1 Equipe AMACC - Laboratoire GREYC - UMR6072

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

Domains: Computer Science [cs]; Computational Complexity [cs.CC]

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⟩