18 citations · 31 across the 5 of their papers we have counts for
5 papers
Complexity of conjunctive regular path query homomorphisms
Laurent Beaudou, Florent Foucaud, Florent R. Madelaine +2
A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose edges are labeled with regular expressions…
Linear functional classes over cellular automata
Anaël Grandjean, Gaétan Richard, Véronique Terrier
Cellular automata are a discrete dynamical system which models massively parallel computation. Much attention is devoted to computations with small time complexity for which the pa…
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…
Revisiting the Rice Theorem of Cellular Automata
Pierre Guillon, Gaétan Richard
A cellular automaton is a parallel synchronous computing model, which consists in a juxtaposition of finite automata whose state evolves according to that of their neighbors. It in…
A Particular Universal Cellular Automaton
Nicolas Ollinger, Gaétan Richard
Signals are a classical tool used in cellular automata constructions that proved to be useful for language recognition or firing-squad synchronisation. Particles and collisions for…