5 citations · 5 across the 6 of their papers we have counts for
7 papers
Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
Étienne Grandjean, Louis Jachiet
In this paper, we study the class of operations , of any fixed arity , satisfying the following property: for each…
Which arithmetic operations can be performed in constant time in the RAM model with addition?
Étienne Grandjean, Louis Jachiet
In the literature of algorithms, the specific computation model is often not explicit as it is assumed that the model of computation is the RAM (Random Access Machine) model. Howev…
Descriptive complexity for minimal time of cellular automata
Étienne Grandjean, Théo Grente
Descriptive complexity may be useful to design programs in a natural declarative way. This is important for parallel computation models such as cellular automata, because designing…
Descriptive complexity for pictures languages (extended abstract)
Etienne Grandjean, Frédéric Olive, Gaétan richard
This paper deals with descriptive complexity of picture languages of any dimension by syntactical fragments of existential second-order logic. - We uniformly generalize to any dime…
Lower bounds and complete problems in nondeterministic linear time and sublinear space complexity classes
Philippe Chapdelaine, Etienne Grandjean
Proving lower bounds remains the most difficult of tasks in computational complexity theory. In this paper, we show that whereas most natural NP-complete problems belong to NLIN (l…
The complexity of acyclic conjunctive queries revisited
Arnaud Durand, Etienne Grandjean
In this paper, we consider first-order logic over unary functions and study the complexity of the evaluation problem for conjunctive queries described by such kind of formulas. A n…