Skip to Main content Skip to Navigation
Theses

Caractérisation et programmation en théorie des langages et en logique des classes de complexité efficace des automates cellulaires

Abstract : Cellular automata constitute the model of parallel and local computation by excellence.As for any model of parallelism, their programming is known to be difficult. The computingpower of cellular automata, the simplest model of parallelism, is attested by the fact that manysignificant problems are computed in minimal time, called real-time, on cellular automata.The main result of this thesis is the demonstration of exact links (equivalences) between, on onehand, the descriptive complexity, essentially the definability in existential second order logic on Horn formulas, and, on the other hand, the real-time complexity classes of cellular automata.Beyond this characterization in logic of the complexity in minimal time, the thesis establishes a method of parallel programming. This method consists first of all in programming in our Horn ogics the induction solving a problem, then in a second step, in applying an automatic process leading to the program of the cellular automaton solving the problem. To justify the interest of the method, the thesis presents a set of logic programs for a representative variety of classical problems known to be computable in real-time on cellular automata.In addition, we prove various results linking the real time of cellular automata and formal grammars. Typically, any language generated by an algebraic grammar and, more generally, an Okhotin conjunctive grammar, is recognized in real-time on a 2-dimensional cellular automaton.
Document type :
Theses
Complete list of metadata

https://tel.archives-ouvertes.fr/tel-03093951
Contributor : Abes Star :  Contact
Submitted on : Monday, January 4, 2021 - 10:47:07 AM
Last modification on : Tuesday, January 5, 2021 - 3:37:07 AM
Long-term archiving on: : Monday, April 5, 2021 - 7:16:28 PM

File

sygal_fusion_28610-grente-theo...
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-03093951, version 1

Citation

Theo Grente. Caractérisation et programmation en théorie des langages et en logique des classes de complexité efficace des automates cellulaires. Arithmétique des ordinateurs. Normandie Université, 2020. Français. ⟨NNT : 2020NORMC214⟩. ⟨tel-03093951⟩

Share

Metrics

Record views

63

Files downloads

51