Etienne Grandjean

40 papers A* 4A 1B 7Journal 25Unranked 3

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