8 citations · 24 across the 19 of their papers we have counts for
22 papers
Graphs with Bounded Push-Pop Walk Orderings
Antoine Amarilli, Claire David, Nadime Francis +3
Consider a directed graph G and the (generally infinite) set Walks(G) of the walks in that graph. We are interested in ordering Walks(G) as w1, w2,... in a way that ensures that ea…
Expressive Power of Property Graph Constraint Languages
Stefania Dumbrava, Nadime Francis, Victor Marsault +1
We present the first principled and systematic study of the expressive power of property graph constraint languages, focused on the recent PG-Keys language, set to inform the upcom…
Designing and Comparing RPQ Semantics
Victor Marsault, Antoine Meyer
Modern property graph database query languages such as Cypher, PGQL, GSQL, and the standard GQL draw inspiration from the formalism of regular path queries (RPQs). In order to outp…
Gray Codes With Constant Delay and Constant Auxiliary Space
Antoine Amarilli, Claire David, Nadime Francis +3
We give the first two algorithms to enumerate all binary words of (like Gray codes) while ensuring that the delay and the auxiliary space is independent from ,…
Rel: A Programming Language for Relational Data
Molham Aref, Paolo Guagliardo, George Kastrinis +12
From the moment of their inception, languages for relational data have been described as sublanguages embedded in a host programming language. Rel is a new relational language whos…
Matching walks that are minimal with respect to edge inclusion
Victor Marsault
In this paper we show that enumerating the set MM(G,R), defined below, cannot be done with polynomial-delay in its input G and R, unless P=NP. R is a regular expression over an alp…
Distinct Shortest Walk Enumeration for RPQs
Claire David, Nadime Francis, Victor Marsault
We consider the Distinct Shortest Walks problem. Given two vertices and of a graph database and a regular path query, enumerate all walks of minimal length fr…
Enumerating regular languages in radix order : Revisiting the Ackerman-Shallit algorithm
Nadime Francis, Victor Marsault
We consider the problem of enumerating a regular language in radix order, or more precisely, the equivalent problem of enumerating all words in of a given length in lexicog…
Run-Based Semantics for RPQs
Claire David, Victor Marsault, Nadime Francis
The formalism of RPQs (regular path queries) is an important building block of most query languages for graph databases. RPQs are generally evaluated under homomorphism semantics;…
GPC: A Pattern Calculus for Property Graphs
Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo +7
The development of practical query languages for graph databases runs well ahead of the underlying theory. The ISO committee in charge of database query languages is currently deve…
Graph Pattern Matching in GQL and SQL/PGQ
Alin Deutsch, Nadime Francis, Alastair Green +15
As graph databases become widespread, JTC1 -- the committee in joint charge of information technology standards for the International Organization for Standardization (ISO), and In…
Taking-and-merging games as rewrite games
Eric Duchêne, Victor Marsault, Aline Parreau +1
This work is a contribution to the study of rewrite games. Positions are finite words, and the possible moves are defined by a finite number of local rewriting rules. We introduce…
Formal Semantics of the Language Cypher
Nadime Francis, Alastair Green, Paolo Guagliardo +8
Cypher is a query language for property graphs. It was originally designed and implemented as part of the Neo4j graph database, and it is currently used in a growing number of comm…
On p/q-recognisable sets
Victor Marsault
Let p/q be a rational number. Numeration in base p/q is defined by a function that evaluates each finite word over A_p={0,1,...,p-1} to some rational number. We let N_p/q denote th…
An efficient algorithm to decide periodicity of -recognisable sets using LSDF convention
Victor Marsault
Let be an integer strictly greater than . Each set of nonnegative integers is represented in base by a language over . The set is said to be -…
On subtrees of the representation tree in rational base numeration systems
Shigeki Akiyama, Victor Marsault, Jacques Sakarovitch
Every rational number p/q defines a rational base numeration system in which every integer has a unique finite representation, up to leading zeroes. This work is a contribution to…
An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention
Bernard Boigelot, Isabelle Mainz, Victor Marsault +1
Given an integer base , a set of integers is represented in base by a language over . The set is said to be -recognisable if its representation is a re…
Breadth-first serialisation of trees and rational languages
Victor Marsault, Jacques Sakarovitch
We present here the notion of breadth-first signature and its relationship with numeration system theory. It is the serialisation into an infinite word of an ordered infinite tree…
Rhythmic generation of infinite trees and languages
Victor Marsault, Jacques Sakarovitch
This work builds on the notion of breadth-first signature of infinite trees and (prefix-closed) languages introduced by the authors in a previous work. We focus here on periodic si…
Auto-similarity in rational base number systems
Shigeki Akiyama, Victor Marsault, Jacques Sakarovitch
This work is a contribution to the study of set of the representations of integers in a rational base number system. This prefix-closed subset of the free monoid is naturally repre…
Ultimate periodicity of b-recognisable sets : a quasilinear procedure
Victor Marsault, Jacques Sakarovitch
It is decidable if a set of numbers, whose representation in a base b is a regular language, is ultimately periodic. This was established by Honkala in 1986. We give here a structu…
On sets of numbers rationally represented in a rational base number system
Victor Marsault, Jacques Sakarovitch
In this work, it is proved that a set of numbers closed under addition and whose representations in a rational base numeration system is a rational language is not a finitely gener…