Etienne Grandjean

According to our database, Etienne Grandjean authored at least 33 papers between 1982 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of four.

2024

Inductive definitions in logic versus programs of real-time cellular automata.

Etienne Grandjean, Théo Grente, Véronique Terrier

Theor. Comput. Sci., 2024

2022

Which arithmetic operations can be performed in constant time in the RAM model with addition?

Etienne Grandjean, Louis Jachiet

CoRR, 2022

2021

Conjunctive Grammars, Cellular Automata and Logic.

Théo Grente, Etienne Grandjean

Proceedings of the 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, 2021

2019

Descriptive complexity for minimal time of cellular automata.

Etienne Grandjean, Théo Grente

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

2017

Definability by Horn Formulas and Linear Time on Cellular Automata.

Nicolas Bacquey, Etienne Grandjean, Frédéric Olive

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

A logical approach to locality in pictures languages.

Etienne Grandjean, Frédéric Olive

J. Comput. Syst. Sci., 2016

2012

Descriptive complexity for pictures languages (extended abstract)

Etienne Grandjean, Frédéric Olive, Gaétan Richard

CoRR, 2012

Descriptive complexity for pictures languages.

Etienne Grandjean, Frédéric Olive

Proceedings of the Computer Science Logic (CSL'12), 2012

2008

Computing the jth solution of a first-order query.

Guillaume Bagan, Arnaud Durand, Etienne Grandjean, Frédéric Olive

RAIRO Theor. Informatics Appl., 2008

2007

First-order queries on structures of bounded degree are computable with constant delay.

Arnaud Durand, Etienne Grandjean

ACM Trans. Comput. Log., 2007

On Acyclic Conjunctive Queries and Constant Delay Enumeration.

Guillaume Bagan, Arnaud Durand, Etienne Grandjean

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006

Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes

Philippe Chapdelaine, Etienne Grandjean

CoRR, 2006

The complexity of acyclic conjunctive queries revisited

Arnaud Durand, Etienne Grandjean

CoRR, 2006

2004

Graph properties checkable in linear time in the number of vertices.

Etienne Grandjean, Frédéric Olive

J. Comput. Syst. Sci., 2004

The Minimal Logically-Defined NP-Complete Problem.

Régis Barbanchon, Etienne Grandjean

Proceedings of the STACS 2004, 2004

2002

Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time.

Etienne Grandjean, Thomas Schwentick

SIAM J. Comput., 2002

Local Problems, Planar Local Problems and Linear Time.

Régis Barbanchon, Etienne Grandjean

Proceedings of the Computer Science Logic, 16th International Workshop, 2002

1998

Monadic Logical Definability of Nondeterministic Linear Time.

Etienne Grandjean, Frédéric Olive

Comput. Complex., 1998

1997

SAT-Problems and Reductions with Respect to the Number of Variables.

Etienne Grandjean, Hans Kleine Büning

J. Log. Comput., 1997

1996

Sorting, Linear Time and the Satisfiability Problem.

Etienne Grandjean

Ann. Math. Artif. Intell., 1996

1994

Linear Time Algorithms and NP-Complete Problems.

Etienne Grandjean

SIAM J. Comput., 1994

Invariance Properties of Rams and Linear Time.

Etienne Grandjean

Comput. Complex., 1994

Monadic Logical Definability of NP-Complete Problems.

Etienne Grandjean, Frédéric Olive

Proceedings of the Computer Science Logic, 8th International Workshop, 1994

1990

A Nontrivial Lower Bound for an NP Problem on Automata.

Etienne Grandjean

SIAM J. Comput., 1990

First-Order Spectra with One Variable.

Etienne Grandjean

J. Comput. Syst. Sci., 1990

RAM with Compact Memory: A Realistic and Robust Model of Computation.

Etienne Grandjean, J. M. Robson

Proceedings of the Computer Science Logic, 4th Workshop, 1990

1988

A Natural NP-Complete Problem with a Nontrivial Lower Nound.

Etienne Grandjean

SIAM J. Comput., 1988

1985

Universal Quantifiers and Time Complexity of Random Access Machines.

Etienne Grandjean

Math. Syst. Theory, 1985

1984

The Spectra of First-Order Sentences and Computational Complexity.

Etienne Grandjean

SIAM J. Comput., 1984

Ergonomic studies in computer aided design.

Gerard H. van der Heiden, Etienne Grandjean

Proceedings of the 21st Design Automation Conference, 1984

1983

Complexity of the First-Order Theory of Almost All Finite Structures

Etienne Grandjean

Inf. Control., 1983

Lighting characteristics of visual display terminals from an ergonomic point of view.

U. Bräuninger, Etienne Grandjean

Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 1983

1982

Number of universal quantifiers and computational complexity: preliminary report.

Etienne Grandjean

SIGACT News, 1982