dblp.uni-trier.dewww.uni-trier.de

Etienne Grandjean Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

*2007
26EEGuillaume Bagan, Arnaud Durand, Etienne Grandjean: On Acyclic Conjunctive Queries and Constant Delay Enumeration. CSL 2007: 208-222
25EEArnaud Durand, Etienne Grandjean: First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log. 8(4): (2007)
2006
24EEArnaud Durand, Etienne Grandjean: The complexity of acyclic conjunctive queries revisited CoRR abs/cs/0605008: (2006)
23EEPhilippe Chapdelaine, Etienne Grandjean: Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes CoRR abs/cs/0606058: (2006)
2005
22EEArnaud Durand, Etienne Grandjean: First-order queries on structures of bounded degree are computable with constant delay CoRR abs/cs/0507020: (2005)
2004
21EERégis Barbanchon, Etienne Grandjean: The Minimal Logically-Defined NP-Complete Problem. STACS 2004: 338-349
20EEEtienne Grandjean, Frédéric Olive: Graph properties checkable in linear time in the number of vertices. J. Comput. Syst. Sci. 68(3): 546-597 (2004)
2002
19EERégis Barbanchon, Etienne Grandjean: Local Problems, Planar Local Problems and Linear Time. CSL 2002: 397-411
18EEEtienne Grandjean, Thomas Schwentick: Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time. SIAM J. Comput. 32(1): 196-230 (2002)
1999
17 Georg Gottlob, Etienne Grandjean, Katrin Seyr: Computer Science Logic, 12th International Workshop, CSL '98, Annual Conference of the EACSL, Brno, Czech Republic, August 24-28, 1998, Proceedings Springer 1999
1998
16 Etienne Grandjean, Frédéric Olive: Monadic Logical Definability of Nondeterministic Linear Time. Computational Complexity 7(1): 54-97 (1998)
1997
15 Etienne Grandjean, Hans Kleine Büning: SAT-Problems and Reductions with Respect to the Number of Variables. J. Log. Comput. 7(4): 457-471 (1997)
1996
14 Etienne Grandjean: Sorting, Linear Time and the Satisfiability Problem. Ann. Math. Artif. Intell. 16: 183-236 (1996)
1994
13EEEtienne Grandjean, Frédéric Olive: Monadic Logical Definability of NP-Complete Problems. CSL 1994: 190-204
12 Etienne Grandjean: Invariance Properties of Rams and Linear Time. Computational Complexity 4: 62-106 (1994)
11 Etienne Grandjean: Linear Time Algorithms and NP-Complete Problems. SIAM J. Comput. 23(3): 573-597 (1994)
1992
10EEEtienne Grandjean: Linear Time Algorithms and NP-Complete Problems. CSL 1992: 248-273
1990
9EEEtienne Grandjean, J. M. Robson: RAM with Compact Memory: A Realistic and Robust Model of Computation. CSL 1990: 195-233
8 Etienne Grandjean: First-Order Spectra with One Variable. J. Comput. Syst. Sci. 40(2): 136-153 (1990)
7 Etienne Grandjean: A Nontrivial Lower Bound for an NP Problem on Automata. SIAM J. Comput. 19(3): 438-451 (1990)
1988
6 Etienne Grandjean: A Natural NP-Complete Problem with a Nontrivial Lower Nound. SIAM J. Comput. 17(4): 786-809 (1988)
1987
5 Etienne Grandjean: First-order Spectra with One Variable. Computation Theory and Logic 1987: 166-180
1985
4 Etienne Grandjean: Universal Quantifiers and Time Complexity of Random Access Machines. Mathematical Systems Theory 18(2): 171-187 (1985)
1984
3 Etienne Grandjean: The Spectra of First-Order Sentences and Computational Complexity. SIAM J. Comput. 13(2): 356-373 (1984)
1983
2 Etienne Grandjean: Universal quantifiers and time complexity of random access machines. Logic and Machines 1983: 366-379
1 Etienne Grandjean: Complexity of the First-Order Theory of Almost All Finite Structures Information and Control 57(2/3): 180-204 (1983)

Coauthor Index

1Guillaume Bagan [26]
2Régis Barbanchon [19] [21]
3Hans Kleine Büning [15]
4Philippe Chapdelaine [23]
5Arnaud Durand [22] [24] [25] [26]
6Georg Gottlob [17]
7Frédéric Olive [13] [16] [20]
8J. M. Robson [9]
9Thomas Schwentick [18]
10Katrin Seyr [17]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)