Zobrazeno 1 - 10
of 51
pro vyhledávání: '"Marsault, Victor"'
Autor:
Marsault, Victor
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 alphabet $\Sigma$, G is directed graph labeled over $\Sigma$, and MM(G,R)
Externí odkaz:
http://arxiv.org/abs/2408.14048
We consider the Distinct Shortest Walks problem. Given two vertices $s$ and $t$ of a graph database $\mathcal{D}$ and a regular path query, enumerate all walks of minimal length from $s$ to $t$ that carry a label that conforms to the query. Usual the
Externí odkaz:
http://arxiv.org/abs/2312.05505
Autor:
Francis, Nadime, Marsault, Victor
We consider the problem of enumerating a regular language $L$ in radix order, or more precisely, the equivalent problem of enumerating all words in $L$ of a given length in lexicographic order. Ackerman and Shallit gave in 2009 the principles of an e
Externí odkaz:
http://arxiv.org/abs/2310.13309
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; in particular only the endpoints of the matched walks are returned. Pr
Externí odkaz:
http://arxiv.org/abs/2211.13313
Autor:
Angles, Renzo, Bonifati, Angela, Dumbrava, Stefania, Fletcher, George, Green, Alastair, Hidders, Jan, Li, Bei, Libkin, Leonid, Marsault, Victor, Martens, Wim, Murlak, Filip, Plantikow, Stefan, Savković, Ognjen, Schmidt, Michael, Sequeda, Juan, Staworko, Sławek, Tomaszuk, Dominik, Voigt, Hannes, Vrgoč, Domagoj, Wu, Mingxi, Živković, Dušan
Publikováno v:
Proc. ACM Manag. Data (2023)
Property graphs have reached a high level of maturity, witnessed by multiple robust graph database systems as well as the ongoing ISO standardization effort aiming at creating a new standard Graph Query Language (GQL). Yet, despite documented demand,
Externí odkaz:
http://arxiv.org/abs/2211.10962
Autor:
Francis, Nadime, Gheerbrant, Amélie, Guagliardo, Paolo, Libkin, Leonid, Marsault, Victor, Martens, Wim, Murlak, Filip, Peterfreund, Liat, Rogova, Alexandra, Vrgoč, Domagoj
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 developing a new standard called Graph Query Language (GQL) as well as an
Externí odkaz:
http://arxiv.org/abs/2210.16580
Autor:
Deutsch, Alin, Francis, Nadime, Green, Alastair, Hare, Keith, Li, Bei, Libkin, Leonid, Lindaaker, Tobias, Marsault, Victor, Martens, Wim, Michels, Jan, Murlak, Filip, Plantikow, Stefan, Selmer, Petra, Voigt, Hannes, van Rest, Oskar, Vrgoč, Domagoj, Wu, Mingxi, Zemke, Fred
As graph databases become widespread, JTC1 -- the committee in joint charge of information technology standards for the International Organization for Standardization (ISO), and International Electrotechnical Commission (IEC) -- has approved a projec
Externí odkaz:
http://arxiv.org/abs/2112.06217
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 22 no. 4 (September 23, 2020) dmtcs:5200
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 and investigate taking-and-merging games, that is, where each rule is
Externí odkaz:
http://arxiv.org/abs/1902.07011
Autor:
Francis, Nadime, Green, Alastair, Guagliardo, Paolo, Libkin, Leonid, Lindaaker, Tobias, Marsault, Victor, Plantikow, Stefan, Rydberg, Mats, Schuster, Martin, Selmer, Petra, Taylor, Andrés
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 commercial systems, industrial applications and research projects. In this
Externí odkaz:
http://arxiv.org/abs/1802.09984
Autor:
Marsault, Victor
Publikováno v:
Logical Methods in Computer Science, Volume 17, Issue 3 (July 28, 2021) lmcs:6834
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 the image of this evaluation function. In particular, N_p/q contains all
Externí odkaz:
http://arxiv.org/abs/1801.08707