Etienne Grandjean

Professor emeritus (professeur émérite) of Computer Science at the University of Caen Normandy

UNICAEN - GREYC

Biography

After being an "Assistant" in Mathematics at the University of Lyon 1 (1982-1985), I became a "Maître de conférences" (1985-1990), then a Professor (1990-2018) in Computer Science at the University of Caen. Since 2018, I am a Professor emeritus.

Interests

My obsession is to tie together fine-grained computational complexity and logical definability (also called descriptive complexity) as closely as possible.
For this, it is necessary to understand and study in a precise way the model of computation:
RAM for the sequential algorithms, cellular automaton for the parallel and local algorithms.
Such researches can help to better formalize algorithms and analyze/understand their complexity.
It can also help to design parallel and local programs of optimal complexity, based on logical induction.

Minimal and robust complexity

Deterministic and nondeterministic linear time
The RAM computation model and its robustness
Descriptive complexity of linear time
Minimal complexity of enumeration problems.

Picture languages and cellular automata

Descriptive complexity of recognizable picture languages
Descriptive complexity of real time and linear time of cellular automata
Design optimal programs of cellular automata by induction in logic.

Education

Thèse d'Etat 1984 Univ. Lyon 1 under the supervision of Jacques Stern

(complementary thesis under the supervision of Michel Waldschmidt)
Thèse de 3ème cycle 1976 Univ. Paris 6 under the supervision of Roland Fraïssé
DEA (Master of Logic) 1975 Univ. Paris 7 and Paris 6
Maîtrise de Mathématiques 1974 Univ. Paris 13

Recent or submitted publications

Etienne Grandjean and Louis Jachiet:
Which arithmetic operations can be performed in constant time in the RAM model with addition?
CoRR abs/2206.13851 (2022).

Théo Grente and Etienne Grandjean:
Conjunctive grammars, cellular automata and logic.
AUTOMATA 2021:8:1-8:19.

Etienne Grandjean, Théo Grente and Véronique Terrier:
Inductive definitions in logic versus programs of real-time cellular automata.
hal-02474520v1 (2020).
Accepted under minor corrections by Theoretical Computer Science.

Etienne Grandjean and Théo Grente:
Descriptive complexity for minimal time of cellular automata.
LICS 2019: 1-13.

Nicolas Bacquey, Etienne Grandjean and Frédéric Olive:
Definability by Horn formulas and linear time on cellular automata.
ICALP 2017: 99:1-99:14.

Etienne Grandjean, Frédéric Olive:
A logical approach to locality in pictures languages.
J. Comput. Syst. Sci. 82(6): 959-1006 (2016)