Publications of Etienne Grandjean

by type, in reverse chronological order

(with some abstracts and some pdf files)

by type, in reverse chronological order

(with some abstracts and some pdf files)

International journals

[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. [ pdf ]

Abstract: We design algorithms of ”optimal” data complexity for several natural problems about first-order queries on structures of bounded degree. For that purpose, we first introduce a framework to deal with logical or combinatorial problems R ⊂ I × O whose instances x ∈ I may admit of several solutions R(x) = {y ∈ O : (x,y) ∈ R}. One associates to such a problem several specific tasks:

- compute a random (for the uniform probability distribution) solution y ∈ R(x);

- enumerate without repetition each solution yj in some specific linear order y0 < y1 < ··· < yn−1 where R(x) = {y0,...,yn−1};

- compute the solution yj of rank j in the linear order <.

Algorithms of ”minimal” data complexity are presented for the following problems: given any first-order formula φ(v) and any structure S of bounded degree:

(1) compute a random element of φ(S) = {a : (S, a) |= φ(v)};

(2) compute the jth element of φ(S) for some linear order of φ(S);

(3) enumerate the elements of φ(S) in lexicographical order.

More precisely, we prove that, for any fixed formula φ, the above problem (1) (resp. (2), (3)) can be computed within average constant time (resp. within constant time, with constant delay) after a linear (O(|S|)) precomputation. Our essential tool for deriving those complexity results is a normalization procedure of first-order formulas on bijective structures.

[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. [ pdf ]

Abstract: The interest of this paper is twofold:

- It introduces a minimal complexity class for enumeration problems, denoted CONSTANT-DELAY(lin); it establishes that this class which is a natural extension of the complexity class DLIN for enumeration problems is similarly a robust complexity class;

- It exhibits a query problem (presented below) whose enumeration problem belongs to CONSTANT-DELAY(lin).

A relational structure is d-degree-bounded, for some integer d, if each element of its domain belongs to at most d tuples of its relations. In this paper that extends a result of [Seese96], we revisit the complexity of the evaluation problem of (not necessarily boolean) first-order (FO) queries over d-degree-bounded structures.

Query evaluation is considered here as a dynamical process.

We prove that any FO query on some d-degree-bounded structure belongs to the complexity class CONSTANT-DELAY(lin), i.e., can be computed by an algorithm that has two separate parts:

- it has a precomputation step of time linear in the size of the structure, and then,

- it outputs all the solutions (i.e., the tuples that satisfy the formula) one by one, with a constant delay between two successive solutions and in constant space (the “constant” depends on the degree d and the size of the formula ϕ).

(In other words, this query problem belongs to CONSTANT-DELAY(lin) when the formula ϕ and the degree d are fixed.)

This implies that any FO query on a d-degree-bounded structure can be evaluated in total time f(|ϕ|, d). (|S| +|ϕ(S)|) and space f(|ϕ|, d). |S|, where S is the structure, ϕ is the formula, ϕ(S) is the result of the query and f is some fixed function. This generalizes a result of Seese [Seese96] who proved that any FO sentence can be evaluated on a d-degree-bounded structure in linear time f(|ϕ|, d). |S|.

[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. [ pdf ]

Abstract: This paper originates from the observation that many classical NP graph problems, including some NP-complete problems, are actually of very low nondeterministic time complexity.

In order to formalize this observation, we define the complexity class vertexNLIN, which collects the graph problems computable on a nondeterministic RAM in time O(n), where n is the number of vertices of the input graph G = (V, E), rather than its usual size |V| + |E| .

It appears that this class is robust (it is defined by a natural restrictive computational device; it is logically characterized by several simple fragments of existential second-order logic; it is closed under various combinatorial operators, including some restrictions of transitive closure) and meaningful (it contains many natural NP problems: connectivity, hamiltonicity, nonplanarity, etc.).

Furthermore, the very restrictive definition of vertexNLIN seems to have beneficial effects on our ability to answer difficult questions about complexity lower bounds or separation between determinism and nondeterminism.

For instance, we prove that vertexNLIN strictly contains its deterministic counterpart, vertexDLIN, and even that the class vertexNLIN is not closed under complement. Also, we prove that several famous graph problems (e.g., planarity, colourability) do not belong to vertexNLIN, although they are computable in deterministic time O(|V| + |E|), i.e., are in DLIN.

[J12] E. Grandjean & T. Schwentick, « Machine-independent characterizations and complete problems for deterministic linear time », SIAM J. Comput. 32 (2002), pp. 196-230.

Abstract: This article presents two algebraic characterizations and two related complete problems for the complexity class DLIN that was introduced in [E. Grandjean, Ann. Math. Artif. Intell., 16 (1996), pp. 183-236]. DLIN is essentially the class of all functions that can be computed in linear time on a Random Access Machine which uses only numbers of linear value during its computations. The algebraic characterizations are in terms of recursion schemes that define unary functions. One of these schemes defines several functions simultaneously, while the other one defines only one function. From the algebraic characterizations, we derive two complete problems for DLIN under new, very strict, and machine-independent affine reductions.

[J11] E. Grandjean & F. Olive, « Monadic logical definability of nondeterministic linear time», Computational Complexity 7 (1998), pp. 54-97.

[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.

Abstract: We consider polynomial time bounded reductions, in particular between k – SAT, SAT and SAT*, in order to obtain the minimal number of variables. As an example we prove that SAT and Unique SAT have, for deterministic algorithms, the same upper bound of the form O( Π c n) for some c > 1, where n is the number of variables of Π. We show that k – Unique SAT is not harder than k – SAT, but not easier than k(r) – SAT (formulas in k – CNF with at most r positive or negative clauses). Finally we present a proof that for each problem in NTlME(n) there is a polynomial reduction to SAT such that the number of variables in f(Π) is only O(n) improving Schnorr–Cook's reduction with O(n log n) variables.

[J9] E. Grandjean, « Sorting, linear time and the satisfiability problem », Annals Math. & Artif. Intell. 16 (1996), pp. 183-236.

Abstract: After a series of papers [C3, J7, C4, J8] that study the RAM model and its robustness and try to formalize the intuitive notion of linear time in successive improvements, this paper introduces the complexity class DLIN that is, I am convinced, the right formulation of linear-time complexity.

For binary word problems (that means: when the inputs of problems are given in the form of binary words), DLIN is the class of problems that are computable within O(n/log n) uniform time on a RAM which can read its input (a binary word of length n) in blocks (of length Θ(log n)) and only uses numbers O(n / log n).

We prove that the sorting problem belongs to DLIN and formulate the Linear Time Thesis: “Each problem computable by a linear time bounded algorithm (in an intuitive sense) belongs to DLIN.”

Moreover, we show that the nondeterministic counterpart of DLIN, the class NLIN, contains all the 21 NP-complete problems proved in the seminal paper [Karp72] and argue that most of the many NP-complete problems quoted by the reference book [GareyJohnson79] are also in NLIN. Finally, we prove that one of them, problem RISA (quoted AL7 in [GareyJohnson79]) is NLIN-complete under reductions computable in linear time on Turing machines. This establishes the equivalence

DLIN ≠ NLIN iff RISA ∉ DLIN

which can be compared to the well-known equivalence P ≠ NP iff SAT ∉ P.

We also study the subclass DTIMESORT(n) of DLIN, that is defined as the class of problems computable within linear time on a Turing machine using in addition a fixed number of sortings, and we show how the reductions of this class, so-called sort-lin reductions, are useful to classify the NP problems: typically, we show that many NP-complete problems are reducible to SAT by sort-lin reductions or are equivalent to SAT by those reductions.

[J8] E. Grandjean, « Linear time algorithms and NP-complete problems », SIAM J. Comput. 23 (1994), pp. 573-597, revised and augmented version of [C4].

Abstract: This paper defines and studies a computational model (a random access machine with powerful input/output instructions), and shows that the classes DLINEAR and NLINEAR of problems computable in deterministic (respectively, nondeterministic) linear time in this model of computation are robust and powerful. In particular, DLINEAR includes most of the concrete problems commonly regarded as computable in linear time (such as graph problems, topological sorting, strong connectivity, etc.). Most combinatorial NP-complete problems are in NLINEAR. The interest of NLINEAR class is enhanced by the fact that some natural NP-complete problems, for example, "reduction of incompletely specified automata" (RISA), are NLINEAR-complete (consequently, NLINEAR ≠DLINEAR if and only if RISA∉DLINEAR). This notion strengthens NP-completeness, as this paper argues that propositional satisfiability is not NLINEAR complete.

[J7] E. Grandjean, « Invariance properties of RAMs and linear time », Computational Complexity 4 (1994), pp. 62-106.

[J6] E. Grandjean, « A nontrivial lower bound for an NP problem on automata », SIAM J. Comput. 19 (1990), pp. 438-451.

Abstract: An NP-complete problem L is NLIN-complete if it satisfies the following conditions (1-2):

1) L is in NLIN, that means L is recognizable on a nondeterministic RAM in linear time;

2) every problem in NLIN is reducible to L in linear time on a deterministic Turing machine.

Let RISA (Reduction of Incompletely Specified Automata) be the following NP-complete problem (quoted AL7 in the reference book by Garey & Johnson [GareyJohnson79]):

Instance: a positive integer K and an incompletely specified finite state automaton A = (Q, Σ, δ, q0, F), where δ is a partial transition function from QxΣ into Q, and Q, Σ, q0, F are defined as usual.

Question: Can δ be extended to a total transition function from QxΣ into Q in such a way that the resulting completely specified finite state automaton has an equivalent “reduced automaton” with K or fewer states?

It is proved that problem RISA is NLIN-complete. As a consequence of the following inclusion and separation results DTIME(n) ⊂ NTIME(n) ⊆ NLIN, it implies that RISA ∉ DTIME(n).

So, RISA is the first problem among the many NP-complete problems quoted by the reference book [GareyJohnson79] for which a nontrivial time lower bound has been proved.

Two remarks on this paper: (1) The NLIN complexity class that I have introduced in my paper [J9] published in 1996 (see below) was not yet defined when this paper was published (in 1990). Nevertheless, in this abstract, for sake of simplicity, I have chosen to reformulate the results of 1990, i.e., the hardness and time lower bound proved for RISA by deducing them from the NLIN-completeness of this problem proved in my papers [J8, J9].

(2) At this date (2011), RISA is still (to my knowledge) the only problem quoted in [GareyJohnson79] for which a nontrivial time lower bound has been proved.

[J5] E. Grandjean, « First-order spectra with one variable », J. Comput. Syst. Sci. 40 (1990), pp. 136-153, revised and augmented version of [C2].

Abstract: Define a (1 forall, unary)-sentence to be a prenex first-order sentence of unary type (i.e., a type which only contains unary relation and function symbols and constant symbols) with only one (universal) quantifier. A successor structure is a structure left angle bracketB, Sright-pointing angle bracket such that S is a function which is a permutation of the basis B with only one cycle. We exhibit a (for all1, unary)-sentence φ of type {S, U1, …, Up} such that if B is finite then left angle bracketB, Sright-pointing angle bracket is a successor structure if left angle bracketB, Sright-pointing angle bracket satisfies there existsU1, …, there existsUpphi. It implies that union operator NRAM(cn)=SPECTRA(for all1, unary), cgreater-or-equal, slanted1 where NRAM(cn) denotes the class of sets of positive integers accepted by a nondeterministic random access machine in time cn (where n is the input integer) and SPECTRA(for all1, unary) is the class of finite spectra of (for all1, unary)-sentences. Another consequence is that some graph properties (hamiltonicity, connectedness) can be characterised by sentences with unary function symbols and constant symbols and only one variable. This contrasts with the result (by Fagin and de Rougemont) that these two graph properties are not definable by monadic generalized spectra (without function symbols) even in the presence of an underlying successor relation.

[J4] E. Grandjean, « A natural NP-complete problem with a nontrivial lower bound », SIAM J. Comput. 17 (1988), pp. 786-809.

[J3] E. Grandjean, « Universal quantifiers and time complexity of Random Access Machine », Math. System Theory 18 (1985), pp. 171-187, revised and augmented version of [C1].

Abstract: Let Sp(d forall) denote the class of spectra of prenex first-order sentences (with equality) with d universal quantifiers. Let NRAM(T(n)) denote the class of sets (of positive integers) accepted by Nondeterministic Random Access Machines, NRAM, (with successor as the only arithmetical operation) in time O(T(n)) where n is the input integer. We prove Sp(d forall) = NRAM(n d) for d ≥ 2. Moreover, each spectrum of Sp(d forall) is the spectrum of a d-universal-quantifier sentence with relation and function symbols of arity d only. Similar results hold for generalized spectra and alternating spectra.

[J2] E. Grandjean, « The spectra of first-order sentences and computational complexity », SIAM J. Comput. 13 (1984), pp. 356-373.

[J1] E. Grandjean, « Complexity of the first-order theory of almost all finite structures », Information and Control 57 (1983), pp. 180-204.

Abstract: A first-order sentence of some fixed relational signature S is true almost everywhere if the proportion of its models among the structures of type S and cardinality m tends to 1 when m tends to infinity. We show that Th(S), the set of sentences of signature S that are true almost everywhere, is PSPACE-complete.

Further, we obtain various upper and lower bounds of the complexity of this theory.

- For example, if the arity of S is d ≥ 2 and if PrenexTh(S) denotes the set of sentences of Th(S) in prenex form, then PrenexTh(S) ∈ DSPACE((n / log n)d)

and PrenexTh(S) ∉ NTIME(o(n / log n)d).

- For the theory of almost all graphs, i.e., Th({E}) where E is a binary relation symbol, we have PrenexTh({E}) ∉ NSPACE(o(n / log n)).

These results (upper or lower bounds for time, space or mixed time-space complexity) are optimal modulo open problems in complexity theory such as NTIME(T) =? DSPACE(T) and NSPACE(S) =? DSPACE(Square(S)).

International conferences

[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. [ pdf ]

Abstract: We study the enumeration complexity of the natural extension of acyclic conjunctive queries with disequalities ≠. In this language, a number of NP-complete problems can be expressed. We first improve a previous result of Papadimitriou and Yannakakis by proving that such queries can be computed in time c.|M|.|φ(M)| where M is the structure, φ(M) is the result set of the query and c is a simple exponential in the size of the formula φ. A consequence of our method is that, in the general case, tuples of such queries can be enumerated with a linear delay between two tuples.

We then introduce a large subclass of acyclic formulas with unequalities called CCQ(≠) and prove that the tuples of a CCQ(≠) query can be enumerated with a linear time precomputation and a constant delay between consecutive solutions. Moreover, under the hypothesis that the multiplication of two n × n boolean matrices cannot be done in time O(square(n)), this leads to the following dichotomy for acyclic queries: either such a query is in CCQ(≠) or it cannot be enumerated with linear precomputation and constant delay. Furthermore we prove that testing whether an acyclic formula is in CCQ(≠) can be performed in polynomial time.

Finally, the notion of free-connex treewidth of a structure is defined. We show that for each query of free-connex treewidth bounded by some constant k, enumeration of results can be done with O(|M|{k+1}) precomputation steps and constant delay.

[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. [ pdf ]

Abstract: We present an NP complete defined by an existential monadic second order formula over functional structures that

1) is minimal under several syntactic criteria, and

2) is unique for such restrictions, up to renamings and symmetries.

Our reductions and proofs are surprisingly very elementary and simple in comparison with some recent similar results classifying existential second-order formulas over relational structures according to their ability either to express NP complete problems only PTIME ones.

[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.

[ pdf ]

Abstract: This paper aims at being a step in the precise classification of the many NP-complete problems which belong to NLIN (nondeterministic linear time complexity on random-access machines), but are seemingly not NLIN-complete. We define the complexity class LIN-LOCAL - the class of problems linearly reducible to problems defined by Boolean local constraints - as well as its planar restriction LIN-PLAN-LOCAL. We show that both "local" classes are rather computationally robust and that SAT and PLAN-SAT are complete in classes LIN-LOCAL and LIN-PLAN-LOCAL, respectively. We prove that some unexpected problems that involve some seemingly global constraints are complete for those classes. E.g., VERTEX-COVER and many similar problems involving cardinality constraints are LIN-LOCAL-complete. Our most striking result is that PLAN-HAMILTON - the planar version of the Hamiltonian problem - is LIN-PLAN-LOCAL and even is LIN-PLAN-LOCAL-complete. Further, since our linear-time reductions also turn out to be parsimonious, they yield new DP-completeness results for UNIQUE-PLAN-HAMILTON and UNIQUE-PLAN-VERTEX-COVER.

[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.

Abstract: It is well known that monadic second-order logic with linear order captures exactly regular languages. On the other hand, if addition is allowed, then J.F.Lynch has proved that existential monadic secondorder logic captures at least all the languages in NTIME(n), and then expresses some NP-complete languages (e.g. knapsack problem).

It seems that most combinatorial NP-complete problems (e.g. traveling salesman, colorability of a graph) do not belong to NTIME(n). But it has been proved that they do belong to NLIN (the similar class for RAM's). In the present paper, we prove that existential monadic second-order logic with addition captures the class NLIN, so enlarging considerably the set of natural problems expressible in this logic. Moreover, we also prove that this logic still captures NLIN even if first-order part of the second-order formulas is required to be forall*exist*, so improving the recent similar result of J.F.Lynch about NTIME(n).

[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.

[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.

Abstract: An operation op of arity k on the set of natural integers N is linear time Turing computable (for short, LTTC) if it is computable in linear time on a Turing machine (for usual binary or dyadic notation of integers). Let + and Conc respectively denote usual addition of integers and concatenation (of their dyadic notations). A RAM which uses only arithmetical operations of a set I is called an I - RAM. An LTTC-RAM is a RAM which only uses LTTC operations.

In the present paper, we use the logarithmic criterion for time measure of RAMs. A RAM works with polynomially (resp. strongly polynomially) compact memory if it only uses addresses (resp. addresses and register contents) less than p(t) where p(t) is a polynomial in the time t of the computation.

Theorem 1. A deterministic LTTC-RAM R with polynomially compact memory is simulated in linear time by a deterministic {+}-RAM (resp. {Conc}-RAM) R' with strongly polynomially compact memory.

Theorem 2. A nondeterministic LTTC-RAM R can be simulated in linear time by a nondeterministic {+}-RAM (resp. {Conc}-RAM) R' with strongly poynomially compact memory.

Note that Theorem 2 holds for both weak nondeterministic RAMs and strong nondeterministic RAMs, i.e. in case the RAMs have only nondeterministic goto instructions or in case they have an instruction to guess an integer.

If moreover the RAMs R of Theorem 1–2 are sane (i.e. R does not use noninitialised registers) then the simulating RAMs R' are sane, too.

We also study and discuss more restrictive notions of compact memory (linearly compact memory).

[C2] E. Grandjean, « First-order spectra with one variable », CSL’86 (Computer Science Logic 1986), Lect. Notes Comput. Sci. 270 (1987), pp. 166-180.

[C1] E. Grandjean, « Universal quantifiers and time complexity of Random Access Machines», Logic & Machines 1983, Lect. Notes Comput. Sci. 171 (1984), pp. 366-379.

Notes in a national journal (in French)

[N2] E. Grandjean, “Sur les classes de relations définies par la méthode de Trahtenbrot”, C.R. Acad. Sci. t. 283 Série A (1976), pp. 127-129.

[N1] E. Grandjean, “Une notion de récursivité relative qui correspond à la récursivité au sens de Trahtenbrot”, C.R. Acad. Sci. t. 282 Série A (1976), pp. 251-253.

In preparation

[P1] E. Grandjean, F. Olive & G. Richard, « Linear time complexity on cellular automata », 30 pages.

Editor (special issue of an international journal, proceedings of an international conference)

[E1] E. Grandjean, Theoretical Computer Science, special issue 101(1) (1992).

[E2] G. Gottlob, E. Grandjean & Katrin Seyr, CSL’98 (Computer Science Logic 1998), Lect. Notes Comput. Sci. 1584 (1999).