Etienne Grandjean

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

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Inductive definitions in logic versus programs of real-time cellular automata.
Theor. Comput. Sci., 2024

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

2021
Conjunctive Grammars, Cellular Automata and Logic.
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.
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.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
A logical approach to locality in pictures languages.
J. Comput. Syst. Sci., 2016

2012
Descriptive complexity for pictures languages (extended abstract)
CoRR, 2012

Descriptive complexity for pictures languages.
Proceedings of the Computer Science Logic (CSL'12), 2012

2008
Computing the jth solution of a first-order query.
RAIRO Theor. Informatics Appl., 2008

2007
First-order queries on structures of bounded degree are computable with constant delay.
ACM Trans. Comput. Log., 2007

On Acyclic Conjunctive Queries and Constant Delay Enumeration.
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
CoRR, 2006

The complexity of acyclic conjunctive queries revisited
CoRR, 2006

2004
Graph properties checkable in linear time in the number of vertices.
J. Comput. Syst. Sci., 2004

The Minimal Logically-Defined NP-Complete Problem.
Proceedings of the STACS 2004, 2004

2002
Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time.
SIAM J. Comput., 2002

Local Problems, Planar Local Problems and Linear Time.
Proceedings of the Computer Science Logic, 16th International Workshop, 2002

1998
Monadic Logical Definability of Nondeterministic Linear Time.
Comput. Complex., 1998

1997
SAT-Problems and Reductions with Respect to the Number of Variables.
J. Log. Comput., 1997

1996
Sorting, Linear Time and the Satisfiability Problem.
Ann. Math. Artif. Intell., 1996

1994
Linear Time Algorithms and NP-Complete Problems.
SIAM J. Comput., 1994

Invariance Properties of Rams and Linear Time.
Comput. Complex., 1994

Monadic Logical Definability of NP-Complete Problems.
Proceedings of the Computer Science Logic, 8th International Workshop, 1994

1990
A Nontrivial Lower Bound for an NP Problem on Automata.
SIAM J. Comput., 1990

First-Order Spectra with One Variable.
J. Comput. Syst. Sci., 1990

RAM with Compact Memory: A Realistic and Robust Model of Computation.
Proceedings of the Computer Science Logic, 4th Workshop, 1990

1988
A Natural NP-Complete Problem with a Nontrivial Lower Nound.
SIAM J. Comput., 1988

1985
Universal Quantifiers and Time Complexity of Random Access Machines.
Math. Syst. Theory, 1985

1984
The Spectra of First-Order Sentences and Computational Complexity.
SIAM J. Comput., 1984

Ergonomic studies in computer aided design.
Proceedings of the 21st Design Automation Conference, 1984

1983
Complexity of the First-Order Theory of Almost All Finite Structures
Inf. Control., 1983

Lighting characteristics of visual display terminals from an ergonomic point of view.
Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 1983

1982
Number of universal quantifiers and computational complexity: preliminary report.
SIGACT News, 1982


  Loading...