, 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
,
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 ,
It allows to define concepts (represented by predicates) inductively, as we have shown here, e.g., for the problems Palindrome ,
Foundations of Databases, 1995. ,
A one-dimensional real-time iterative multiplier, IEEE Trans. Electronic Computers, vol.14, issue.3, pp.394-399, 1965. ,
Definability by Horn Formulas and ,
URL : https://hal.archives-ouvertes.fr/hal-01494246
On real-time cellular automata and trellis automata, Acta Informatica, vol.21, issue.4, pp.393-407, 1984. ,
Real-time computation by n-dimensional iterative arrays of finite-state machine, IEEE Transactions on Computing, vol.18, pp.349-365, 1969. ,
Variations of the firing squad problem and applications, Inf. Process. Lett, vol.30, issue.3, pp.153-157, 1989. ,
Systolic trellis automata. I, International Journal Computer Mathematics, vol.15, issue.3-4, pp.195-212, 1984. ,
Signals on cellular automata, Collision-based Computing, pp.231-275, 1995. ,
Algorithmic tools on cellular automata, vol.32, pp.77-122 ,
One-way bounded cellular automata, Information and Control, vol.44, issue.3, pp.261-281, 1980. ,
Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, SIAM-AMS Proceedings, pp.43-73, 1974. ,
Generation of primes by one-dimensional real-time iterative array, Journal of the ACM, vol.12, pp.388-394, 1965. ,
Capturing complexity classes by fragments of second-order logic, Computer Science, vol.101, issue.1, pp.35-57, 1992. ,
, Finite Model Theory and Its Applications, 2007.
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.
Comparing 1d and 2d real time on cellular automata, 2016. ,
URL : https://hal.archives-ouvertes.fr/lirmm-01476808
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
Descriptive complexity for minimal time of cellular automata, LICS, pp.1-13, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-02020180
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
On one-way cellular arrays, SIAM Journal on Computing, vol.16, issue.6, pp.1135-1154, 1987. ,
Descriptive complexity, 1999. ,
Propositional logic -deduction and algorithms, volume 48 of Cambridge tracts in theoretical computer science, 1999. ,
Communication complexity, 1997. ,
Introduction to Parallel Architectures: Arrays, Trees, Hypercubes, 1991. ,
Elements of Finite Model Theory. Texts in Theoretical Computer Science, An EATCS Series, 2004. ,
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. ,
Computations on cellular automata, vol.32, pp.159-188 ,
URL : https://hal.archives-ouvertes.fr/hal-00578620
On the equivalence of linear conjunctive grammars and trellis automata, Theoretical Informatics and Applications, vol.38, issue.1, pp.69-88, 2004. ,
Conjunctive and boolean grammars: The true general case of the contextfree grammars, Computer Science Review, vol.9, pp.27-59, 2013. ,
, Distributed Computing : A Locality-Sensitive Approach. SIAM Monographs on Discrete Maths and Applications, 2000.
Cellular automata: Real-time equivalence between one-dimensional neighbor-2045 hoods, STACS 2005, pp.133-144, 2005. ,
, Handbook of Natural Computing, 2012.
Real-time language recognition by one-dimensional cellular automata, Journal of Computer and System Science, vol.6, pp.233-253, 1972. ,
Language not recognizable in real time by one-way cellular automata, Theoretical Computer Science, vol.156, issue.1-2, pp.281-287, 1996. ,
Two-dimensional cellular automata recognizer, Theoretical Computer Science, vol.218, issue.2, pp.325-346, 1999. ,
URL : https://hal.archives-ouvertes.fr/hal-00273998
Characterization of real time iterative array by alternating device. Theo-2055 retical, Computer Science, vol.290, issue.3, pp.2075-2084, 2003. ,
Two-dimensional cellular automata and deterministic on-line tessalation automata, Theoretical Computer Science, vol.301, issue.1-3, pp.167-186, 2003. ,
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
Language recognition by cellular automata, vol.32, pp.123-158 ,
URL : https://hal.archives-ouvertes.fr/hal-01086432
Some computational limits of trellis automata, Cellular Automata and Discrete Complex Systems, pp.176-186, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01578301