Main results of Etienne Grandjean
(References of my papers are listed below with numbers of the
form [Ji] or [Ci]; additional references by other authors
are also listed below after.)
Complexity of the theory of first-order sentences true almost everywhere
- [J1] proves the PSPACE-completeness of the theory Th(S)
of first-order sentences, of signature S, true almost everywhere,
for each fixed relational signature S.
- Further, [J1] proves several (time or space or mixed time-space)
upper and lower bounds for the complexity of this theory : most are
optimal modulo open problems in complexity theory such as NTIME(T) =? DSPACE(T) or NSPACE(S) =? DSPACE(S2).
Logical characterizations of nondeterministic precise polynomial or linear time
In a series of improvements [J2, J3, J5, J11, J13], I finally prove
that, for each integer d≥1 and each (relational or functional)
signature S, a set of S-structures belongs to NTIMERAM(nd)
iff this set is definable in existential (functional) second-order
logic with only d distinct first-order variables (here, n is the
cardinality of the domain of the input structure).
Important things about this result:
- This equivalence is very robust: there
are many (natural) equivalent computational (resp. logical) variants of
the concerned complexity (resp. definability) classes; it holds
whatever the arity of the signature S is, independently of degree d;
there is no need of any built-in relation (e.g., no linear order) in
- This equivalence requires two related conditions:
function symbols are needed among the existentially quantified symbols
of the formulas; RAMs are required instead of Turing machines: this
explains the sequel of my research;
- NLIN is defined in [J8, J9] as the class of sets of unary functional S-structures in NTIMERAM(n).
Note: As a (delicate)
corollary, [J11] proves that any language (set of words) in NLIN can be
defined in existential (relational) monadic logic with built-in
addition, on the domain of indices of the input word (this is an
improvement of a result by Jim Lynch: he has proved the same definability result for the class
NTIME(n) of Turing machines (instead of RAMs); note that when restricted to built-in linear order instead of
addition, this logic only characterizes regular languages [Büchi,
RAMs, DLIN, NLIN and NP-complete problems
Class DLIN and RAMs: The
deterministic counterpart of NLIN is defined similarly in [J9]: DLIN is
the class of sets of unary functional structures in DTIMERAM(n), where
n denotes the cardinality of the domain of the input structure.
Robustness of the RAM model: Papers
[C3, J7] are exclusively dedicated to establish the robustness of time
complexity on RAMs w.r.t. many variants: set of allowed instructions,
use of memory, etc.
"Linear Time Thesis": In [J8,
J9], I argue that DLIN is the set of problems computed by linear-time
(in an intuitive sense) algorithms. As an important argument, [J9]
proves that the sorting problem is in DLIN and hence the class DLIN is
essentially insensitive to the presentation of inputs and outputs.
NLIN is also meaningful: I also
establish in [J8, J9] that all the 21 problems established by R. Karp
(and more generally, most combinatorial NP-complete problems) are in
NLIN-complete problems and lower bounds: Papers
[J4, J6] exhibit two NLIN-complete problems under reductions in
DTIME(n) (linear time of Turing machines); one of them (RISA: Reduction
of Incompletely Specified Automata) is the reference problem AL7 of the
reference book [GareyJohnson1979]; as a consequence, they are not in
More classifications of NP problems modulo linear reductions:
- In [J8, J9], I establish that there are many natural NP-complete
problems are equivalent each other under linear reductions (in DLIN,
or, better, very often in DTIME(n), with or without a fixed number of
sortings, the class so-called DTIMESORT(n)).
- The SAT linear class and existential monadic second-order logic:
[C6, C7] prove that the class of problems DLIN-reducible to SAT equals
the class of problems DLIN-reducible to problems definable in
existential monadic (relational) second-order logic with only one
first-order variable; this robust subclass of NLIN is called
MonadicNLIN; moreover, [C7] proves the following striking result: there
is a minimal formula in that logic (existential monadic second-order
logic with only one first-order variable) that defines a
MonadicNLIN-complete problem, hence an NP-complete problem. This
formula is minimal for defining an NP-complete problem under each of 6
syntactic criteria. Moreover, this minimal formula is proved to be
unique, up to renaming and symmetries.
Algebraic robustness of DLIN:
[J12] establishes a simple algebraic characterization of DLIN
(comparable to the one proved by Yuri Gurevich for LogSpace). From this
characterization, we derive two rather natural DLIN-complete problems
Note: Further, both problems are DLIN-complete under affine reductions.
[J12] introduces this (very strict, static) notion of affine reduction,
that is defined by a system of affine equations, and shows that many
natural reductions, including those involved in NLIN-completeness, are
Two classes of graph problems computable in linear in the number of vertices:
[J13] introduces two classes of graph problems (presented by adjacency
matrices) denoted VertexNLIN and VertexDLIN in the respective
nondeterministic and deterministic cases. VertexNLIN is shown to be
computationally and logically robust and meaningful: it contains many
natural graph problems. Moreover, [J13] proves (by a simple counting
method) several structural (nonclosure, separation) properties
involving classes DLIN, VertexNLIN and VertexDLIN.
Extension of linear time to enumeration problems
I have introduced a complexity class for enumeration,
called LIN-DELAY(lin), : it is the class of enumeration problems
computable in two successive phases: a preprocessing phase that runs in
linear time in the input size ; an enumeration phase that enumerates
the solutions of the problem (one by one, without repetition) with
delay (between two successive solutions) and space linear in the size
of each expected solution.
I have shown that LIN-DELAY(lin) is a minimal robust complexity class for
enumeration problems; we (I and my collaborators) have proved that
LIN-DELAY(lin) contains the enumeration extensions of the three classical
following model-checking problems :
- MSO queries on classes of bounded tree-width structures : Bagan
2006 [Bagan06]; this is an extension of a classical theorem of
Courcelle [Courcelle90, Courcelle92]; see also [Courcelle09] for a
variant of this result;
- FO queries on classes of bounded-degree structures [J14, J15] : this is an extension of a theorem of Seese [Seese96];
- a well identified class of acyclic conjunctive queries called
connex-acyclic conjunctive queries: see [C8]; this is an extension of
the class of acyclic joins [Yannakakis81].
Descriptive complexity of linear time of cellular automata (CA)
Answering a question of J. Mazoyer, I have recently obtained a
robust logical characterization of linear time of nondeterministic CAs
(paper in preparation), very similar to the one obtained for
nondeterministic RAMs : a decision problem (of d-dimensional pictures) is
recognized in linear time by a d-dimensional nondeterministic CA iff it
is definable in existential relational second-order logic (with a
built-in successor function) with only d+1 first-order variables.
[J1] E. Grandjean, « Complexity of the first-order theory of
almost all finite structures », Information and Control 57 (1983), pp.
[J2] E. Grandjean, « The spectra of first-order sentences and
computational complexity », SIAM J. Comput. 13 (1984), pp. 356-373.
[J3] E. Grandjean, « Universal quantifiers and time complexity of
Random Access Machines », Math. System Theory 18 (1985), pp. 171-187,
revised and augmented version of [C1].
[J4] E. Grandjean, « A natural NP-complete problem with a
nontrivial lower bound », SIAM J. Comput. 17 (1988), pp. 786-809.
[J5] E. Grandjean, « First-order spectra with one variable », J.
Comput. Syst. Sci. 40 (1990), pp. 136-153, revised and augmented
version of [C2].
[J6] E. Grandjean, « A nontrivial lower bound for an NP problem on automata », SIAM J. Comput. 19 (1990), pp. 438-451.
[J7] E. Grandjean, « Invariance properties of RAMs and linear time », Computational Complexity 4 (1994), pp. 62-106.
[J8] E. Grandjean, « Linear time algorithms and NP-complete
problems », SIAM J. Comput. 23 (1994), pp. 573-597, revised and
augmented version of [C4].
[J9] E. Grandjean, « Sorting, linear time and the satisfiability
problem », Annals Math. & Artif. Intell. 16 (1996), pp. 183-236.
[J10] E. Grandjean & H. Kleine Büning, « SAT-problems and
reductions with respect to the number of variables », J. Logic &
Computation 7 (1997), pp. 457-471.
[J11] E. Grandjean & F. Olive, « Monadic logical definability
of nondeterministic linear time », Computational Complexity 7 (1998),
[J12] E. Grandjean & T. Schwentick, « Machine-independent
characterizations and complete problems for deterministic linear time », SIAM J. Comput. 32 (2002), pp. 196-230.
[J13] E. Grandjean & F. Olive, « Graph properties checkable
in linear time in the number of vertices », J. Comput. Syst. Sci. 68
(2004), pp. 546-597.
[J14] A. Durand & E. Grandjean, « First-order queries on
structures of bounded degree are computable with constant delay », ACM
Transactions on Computational Logic (TOCL) 8(4) (2007), 18 pages.
[J15] G. Bagan, A. Durand, E. Grandjean & F. Olive, «
Computing the jth solution of a first-order query », RAIRO Theoretical
Informatics & Applications 42 (2008), pp. 147-164.
Proceedings of international conferences
[C1] E. Grandjean, « Universal quantifiers and time complexity of
Random Access Machines», Logic & Machines 1983, Lect. Notes Comput.
Sci. 171 (1984), pp. 366-379.
[C2] E. Grandjean, « First-order spectra with one variable »,
CSL'86 (Computer Science Logic 1986), Lect. Notes Comput. Sci. 270
(1987), pp. 166-180.
[C3] E. Grandjean & J.-M. Robson, "RAM with compact memory: a
realistic and robust model of computation"�, CSL'90 (Computer Science
Logic 1990), Lect. Notes Comput. Sci. 533 (1991), pp. 195-233.
[C4] E. Grandjean, « Linear time algorithms and NP-complete
problems », CSL'92 (Computer Science Logic 1992), Lect. Notes Comput.
Sci. 702 (1993), pp. 248-273.
[C5] E. Grandjean & F. Olive, "Monadic logical definability
of NP-complete problems"�, CSL'94 (Computer Science Logic 1994), Lect.
Notes Comput. Sci. 933 (1995), pp. 190-204.
[C6] R. Barbanchon & E. Grandjean, "Local problems, planar
local problems and linear time", CSL'02 (Computer Science Logic 2002),
Lect. Notes Comput. Sci. 2471 (2002), pp. 397-411.
[C7] R. Barbanchon & E. Grandjean, "The minimal
logically-defined NP-complete problem", STACS'04 (Symposium on
Theoretical Aspects of Computer Sciences 2004), Lect. Notes Comput.
Sci. 2996 (2004), pp. 338-349.
[C8] G. Bagan, A. Durand & E. Grandjean, "On acyclic
conjunctive queries and constant delay enumeration"�, CSL'07 (Computer
Science Logic 2007), Lect. Notes Comput. Sci. 4646 (2007), pp. 208-222.
[AhoHopcroftUllman74] A. Aho, J. Hopcroft & J. Ullman,
"The design and analysis of computer algorithms"�, Addison-Wesley
[Bagan06] G. Bagan, "MSO queries on tree decomposable structures
are computable with linear delay"�, CSL'06 (Computer Science Logic
2006), Lect. Notes Comput. Sci. 4207 (2006), pp. 167-181.
[BorelloRichardTerrier11] A. Borello, G. Richard & V.
Terrier, "A speed-up of oblivious multi-head finite automata by
cellular automata"�, STACS'11 (Symposium on Theoretical Aspects of
Computer Sciences 2011) (2011), 11 pages.
[CookReckhow73] S. Cook & R. Reckhow, "Time-bounded random
access machines"�, J. Comput. System Sci. 7 (1973), pp. 354-375.
[Courcelle90] B. Courcelle, "The monadic second-order logic of
graphs. I. Recognizable sets of finite graphs"�, Inf. & Comput.
85(1) (1990), pp. 12-75.
[Courcelle92] B. Courcelle, "The monadic second-order logic of
graphs. III: Tree-decomposition, minor and complexity issues"�, ITA 26
(1992), pp. 257-286.
[Courcelle09] B. Courcelle, "Linear delay enumeration and monadic
second-order logic"�, Discrete Appl. Math. 157(12) (2009), pp. 2675-2700.
[EbbinghausFlum99] H.-D. Ebbinghaus & J. Flum, "Finite model theory"�, Springer-Verlag, 2nd ed. (1999).
[Fagin74] R. Fagin, "Generalized first-order spectra and
polynomial time recognizable sets"�, in "Complexity of Computations"�, R.
Karp ed., American Math. Soc., SIAM AMS Proc. VII (1974), pp. 43-73.
[Feder94] R. Feder, "Network flow and 2-satisfiability"�, Algorithmica 11 (1994), pp. 291-319.
[GareyJohnson79] M. Garey & D. Johnson, "Computers and
intractability: A guide to the theory of NP-completeness"� (1979),
[GrÃ¤del90] E. Grädel, "On the notion of linear time computability"�, Internat. Found. Comput. Sci. 1 (1990), pp. 295-307.
[Gurevich00] Y. Gurevich, "Sequential abstract state machines
capture sequential algorithms", ACM Trans. Comput. Logic (TOCL) 1
(2000), pp. 77-111.
[GurevichShelah89] Y. Gurevich & S. Shelah, "Nearly linear time"�, Lect. Notes Comput. Sci. 363 (1989), pp. 108-118.
[Immerman99] N. Immerman, "Descriptive complexity", Springer-Verlag (1999).
[Karp72] R. Karp, "Reducibility among combinatorial problems",
IBM Symp. 1972, in "Complexity of computer computations"�, R.E. Miller
& J.W. Thatcher (ed.), Plenum Press (1972), pp. 85-103.
[PaulPippengerSzemerediTrotter83] W. Paul, N. Pippenger, E.
Szemeredi & W. Trotter, "On determinism versus non-determinism and
related problems"�, 24th Symp. Found. of Comput. Sci. (1983), pp.
[Seese96] D. Seese, "Linear computable problems and first-order
descriptions"�, Math. Structures in Computer Science 6(6) (1996), pp.
[Smith71] A. R. Smith III, "Simple computation-universal cellular spaces"�, JACM 18(3) (1971), pp. 339-353.
[Yannakakis81] M. Yannakakis, "Algorithms for acyclic database schemes"�, VLDB'81 (1981), pp. 82-94.