, After Step 4, one may consider that each clause is of one of the following forms (1-3): 1. an initialization clause x = y ? ? ? R(x, y), where ? is ? x = y ? Odd

. Odd,

. Odd, . Leftborder, . Rightborder, . Startleftbranch, . Startrightbranch et al., Let ? Culik denote the formula ?? Culik ?x, y ?. By construction, ? Culik belongs to incl-ESO-IND. From Lemma 13 and the 1880 previous characterization of a + b + ba + , we deduce the following proposition: Proposition 4. For any word w ? {a, b} + , we have the equivalence: w ? Culik iff w |= ? Culik

. Datalog, It allows to define concepts (represented by predicates) inductively, as we have shown here, e.g., for the problems Palindrome

S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

A. J. Atrubin, A one-dimensional real-time iterative multiplier, IEEE Trans. Electronic Computers, vol.14, issue.3, pp.394-399, 1965.

N. Bacquey, E. Grandjean, and F. Olive, Definability by Horn Formulas and
URL : https://hal.archives-ouvertes.fr/hal-01494246

C. Choffrut, K. Culik, and I. I. , On real-time cellular automata and trellis automata, Acta Informatica, vol.21, issue.4, pp.393-407, 1984.

S. N. Cole, Real-time computation by n-dimensional iterative arrays of finite-state machine, IEEE Transactions on Computing, vol.18, pp.349-365, 1969.

K. Culik, Variations of the firing squad problem and applications, Inf. Process. Lett, vol.30, issue.3, pp.153-157, 1989.

K. Culik, J. Gruska, and A. Salomaa, Systolic trellis automata. I, International Journal Computer Mathematics, vol.15, issue.3-4, pp.195-212, 1984.

M. Delorme and J. Mazoyer, Signals on cellular automata, Collision-based Computing, pp.231-275, 1995.

M. Delorme and J. Mazoyer, Algorithmic tools on cellular automata, vol.32, pp.77-122

C. R. Dyer, One-way bounded cellular automata, Information and Control, vol.44, issue.3, pp.261-281, 1980.

R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, SIAM-AMS Proceedings, pp.43-73, 1974.

C. Patrick and . Fischer, Generation of primes by one-dimensional real-time iterative array, Journal of the ACM, vol.12, pp.388-394, 1965.

E. Grädel, Capturing complexity classes by fragments of second-order logic, Computer Science, vol.101, issue.1, pp.35-57, 1992.

E. Grädel, G. Phokion, L. Kolaitis, M. Libkin, J. Marx et al., Finite Model Theory and Its Applications, 2007.

A. Grandjean, Differences between 2d neighborhoods according to real time computation
URL : https://hal.archives-ouvertes.fr/lirmm-01693188

, Developments in Language Theory, pp.198-209, 2017.

A. Grandjean and V. Poupet, Comparing 1d and 2d real time on cellular automata, 2016.
URL : https://hal.archives-ouvertes.fr/lirmm-01476808

A. Grandjean and V. Poupet, A linear acceleration theorem for 2d cellular automata on all complete neighborhoods, 43rd International Colloquium on Automata, Languages, and Programming, vol.55, pp.1-115, 2016.
URL : https://hal.archives-ouvertes.fr/lirmm-01476809

E. Grandjean and T. Grente, Descriptive complexity for minimal time of cellular automata, LICS, pp.1-13, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02020180

E. Grandjean and F. Olive, A logical approach to locality in pictures languages, Journal of Computer and System Science, vol.82, issue.6, pp.959-1006, 2016.
URL : https://hal.archives-ouvertes.fr/hal-00786148

H. Oscar, T. Ibarra, and . Jiang, On one-way cellular arrays, SIAM Journal on Computing, vol.16, issue.6, pp.1135-1154, 1987.

N. Immerman, Descriptive complexity, 1999.

K. Hans, T. Büning, and . Lettmann, Propositional logic -deduction and algorithms, volume 48 of Cambridge tracts in theoretical computer science, 1999.

E. Kushilevitz and N. Nisan, Communication complexity, 1997.

F. Leighton, Introduction to Parallel Architectures: Arrays, Trees, Hypercubes, 1991.

L. Libkin, Elements of Finite Model Theory. Texts in Theoretical Computer Science, An EATCS Series, 2004.

J. Mazoyer, A six-state minimal time solution to the firing squad synchronization prob-2035 lem, Theoretical Computer Science, vol.50, issue.2, pp.183-238, 1987.

J. Mazoyer and J. Yunès, Computations on cellular automata, vol.32, pp.159-188
URL : https://hal.archives-ouvertes.fr/hal-00578620

A. Okhotin, On the equivalence of linear conjunctive grammars and trellis automata, Theoretical Informatics and Applications, vol.38, issue.1, pp.69-88, 2004.

A. Okhotin, Conjunctive and boolean grammars: The true general case of the contextfree grammars, Computer Science Review, vol.9, pp.27-59, 2013.

D. Peleg, Distributed Computing : A Locality-Sensitive Approach. SIAM Monographs on Discrete Maths and Applications, 2000.

V. Poupet, Cellular automata: Real-time equivalence between one-dimensional neighbor-2045 hoods, STACS 2005, pp.133-144, 2005.

G. Rozenberg, T. Bäck, and J. N. Kok, Handbook of Natural Computing, 2012.

A. R. Smith, Real-time language recognition by one-dimensional cellular automata, Journal of Computer and System Science, vol.6, pp.233-253, 1972.

V. Terrier, Language not recognizable in real time by one-way cellular automata, Theoretical Computer Science, vol.156, issue.1-2, pp.281-287, 1996.

V. Terrier, Two-dimensional cellular automata recognizer, Theoretical Computer Science, vol.218, issue.2, pp.325-346, 1999.
URL : https://hal.archives-ouvertes.fr/hal-00273998

V. Terrier, Characterization of real time iterative array by alternating device. Theo-2055 retical, Computer Science, vol.290, issue.3, pp.2075-2084, 2003.

V. Terrier, Two-dimensional cellular automata and deterministic on-line tessalation automata, Theoretical Computer Science, vol.301, issue.1-3, pp.167-186, 2003.

V. Terrier, Low complexity classes of multidimensional cellular automata, Theor. Comput. Sci, vol.369, issue.1-3, pp.142-156, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00238437

V. Terrier, Language recognition by cellular automata, vol.32, pp.123-158
URL : https://hal.archives-ouvertes.fr/hal-01086432

V. Terrier, Some computational limits of trellis automata, Cellular Automata and Discrete Complex Systems, pp.176-186, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01578301