5 citations · 5 across the 6 of their papers we have counts for
4 papers · 1 filter
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…
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…
First-order queries on structures of bounded degree are computable with constant delay
Arnaud Durand, Etienne Grandjean
A bounded degree structure is either a relational structure all of whose relations are of bounded degree or a functional structure involving bijective functions only. In this paper…