Etienne Grandjean

Publication Activity (10 Years)

Years Active: 1982-2024
Publications (10 Years): 7

Top Topics

Chaotic Dynamics

Cellular Automata

Top Venues

J. Comput. Syst. Sci.

Publications

Etienne Grandjean, Théo Grente, Véronique Terrier
Inductive definitions in logic versus programs of real-time cellular automata. Theor. Comput. Sci. 987 (2024)
Etienne Grandjean, Louis Jachiet
Which arithmetic operations can be performed in constant time in the RAM model with addition? CoRR (2022)
Théo Grente, Etienne Grandjean
Conjunctive Grammars, Cellular Automata and Logic. AUTOMATA (2021)
Etienne Grandjean, Théo Grente
Descriptive complexity for minimal time of cellular automata. LICS (2019)
Etienne Grandjean, Théo Grente
Descriptive complexity for minimal time of cellular automata. CoRR (2019)
Nicolas Bacquey, Etienne Grandjean, Frédéric Olive
Definability by Horn Formulas and Linear Time on Cellular Automata. ICALP (2017)
Etienne Grandjean, Frédéric Olive
A logical approach to locality in pictures languages. J. Comput. Syst. Sci. 82 (6) (2016)
Etienne Grandjean, Frédéric Olive, Gaétan Richard
Descriptive complexity for pictures languages (extended abstract) CoRR (2012)
Etienne Grandjean, Frédéric Olive
Descriptive complexity for pictures languages. CSL (2012)
Guillaume Bagan, Arnaud Durand, Etienne Grandjean, Frédéric Olive
Computing the jth solution of a first-order query. RAIRO Theor. Informatics Appl. 42 (1) (2008)
Guillaume Bagan, Arnaud Durand, Etienne Grandjean
On Acyclic Conjunctive Queries and Constant Delay Enumeration. CSL (2007)
Arnaud Durand, Etienne Grandjean
First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log. 8 (4) (2007)
Arnaud Durand, Etienne Grandjean
The complexity of acyclic conjunctive queries revisited CoRR (2006)
Philippe Chapdelaine, Etienne Grandjean
Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes CoRR (2006)
Arnaud Durand, Etienne Grandjean
First-order queries on structures of bounded degree are computable with constant delay CoRR (2005)
Régis Barbanchon, Etienne Grandjean
The Minimal Logically-Defined NP-Complete Problem. STACS (2004)
Etienne Grandjean, Frédéric Olive
Graph properties checkable in linear time in the number of vertices. J. Comput. Syst. Sci. 68 (3) (2004)
Régis Barbanchon, Etienne Grandjean
Local Problems, Planar Local Problems and Linear Time. CSL (2002)
Etienne Grandjean, Thomas Schwentick
Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time. SIAM J. Comput. 32 (1) (2002)
Etienne Grandjean, Frédéric Olive
Monadic Logical Definability of Nondeterministic Linear Time. Comput. Complex. 7 (1) (1998)
Etienne Grandjean, Hans Kleine Büning
SAT-Problems and Reductions with Respect to the Number of Variables. J. Log. Comput. 7 (4) (1997)
Etienne Grandjean
Sorting, Linear Time and the Satisfiability Problem. Ann. Math. Artif. Intell. 16 (1996)
Etienne Grandjean
Linear Time Algorithms and NP-Complete Problems. SIAM J. Comput. 23 (3) (1994)
Etienne Grandjean
Invariance Properties of Rams and Linear Time. Comput. Complex. 4 (1994)
Etienne Grandjean, Frédéric Olive
Monadic Logical Definability of NP-Complete Problems. CSL (1994)
Etienne Grandjean
Linear Time Algorithms and NP-Complete Problems. CSL (1992)
Etienne Grandjean
A Nontrivial Lower Bound for an NP Problem on Automata. SIAM J. Comput. 19 (3) (1990)
Etienne Grandjean, J. M. Robson
RAM with Compact Memory: A Realistic and Robust Model of Computation. CSL (1990)
Etienne Grandjean
First-Order Spectra with One Variable. J. Comput. Syst. Sci. 40 (2) (1990)
Etienne Grandjean
A Natural NP-Complete Problem with a Nontrivial Lower Nound. SIAM J. Comput. 17 (4) (1988)
Etienne Grandjean
First-order Spectra with One Variable. Computation Theory and Logic (1987)
Etienne Grandjean
Universal Quantifiers and Time Complexity of Random Access Machines. Math. Syst. Theory 18 (2) (1985)
Etienne Grandjean
The Spectra of First-Order Sentences and Computational Complexity. SIAM J. Comput. 13 (2) (1984)
Gerard H. van der Heiden, Etienne Grandjean
Ergonomic studies in computer aided design. DAC (1984)
U. Bräuninger, Etienne Grandjean
Lighting characteristics of visual display terminals from an ergonomic point of view. CHI (1983)
Etienne Grandjean
Complexity of the First-Order Theory of Almost All Finite Structures Inf. Control. 57 (2/3) (1983)
Etienne Grandjean
Universal quantifiers and time complexity of random access machines. Logic and Machines (1983)
Etienne Grandjean
Number of universal quantifiers and computational complexity: preliminary report. SIGACT News 14 (3) (1982)