Zobrazeno 1 - 10
of 32
pro vyhledávání: '"Jachiet, Louis"'
Low-latency sliding window algorithms for regular and context-free languages are studied, where latency refers to the worst-case time spent for a single window update or query. For every regular language $L$ it is shown that there exists a constant-l
Externí odkaz:
http://arxiv.org/abs/2209.14835
Autor:
Grandjean, Étienne, Jachiet, Louis
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. However, the RAM model itself is ill-founded in the literature, with dispar
Externí odkaz:
http://arxiv.org/abs/2206.13851
Listing triangles is a fundamental graph problem with many applications, and large graphs require fast algorithms. Vertex ordering allows the orientation of edges from lower to higher vertex indices, and state-of-the-art triangle listing algorithms u
Externí odkaz:
http://arxiv.org/abs/2203.04774
We introduce annotated grammars, an extension of context-free grammars which allows annotations on terminals. Our model extends the standard notion of regular spanners, and is more expressive than the extraction grammars recently introduced by Peterf
Externí odkaz:
http://arxiv.org/abs/2201.00549
We study the dynamic membership problem for regular languages: fix a language L, read a word w, build in time O(|w|) a data structure indicating if w is in L, and maintain this structure efficiently under letter substitutions on w. We consider this p
Externí odkaz:
http://arxiv.org/abs/2102.07728
In the last years, enumeration algorithms with bounded delay have attracted a lot of attention for several data management tasks. Given a query and the data, the task is to preprocess the data and then enumerate all the answers to the query one by on
Externí odkaz:
http://arxiv.org/abs/2010.08042
We study the design of data publishing mechanisms that allow a collection of autonomous distributed datasources to collaborate to support queries. A common mechanism for data publishing is via views: functions that expose derived data to users, usual
Externí odkaz:
http://arxiv.org/abs/2006.00875
Autor:
Jachiet, Louis
Ma thèse porte sur la compilation des langages de requêtes orientés web des données. Plus particulièrement, ma thèse s'intéresse à l'analyse, l'optimisation et l'évaluation distribuée d'un tel langage : SPARQL. Ma contribution principale es
Externí odkaz:
http://www.theses.fr/2018GREAM038/document
Publikováno v:
28th International Joint Conference on Artificial Intelligence (IJCAI-19), Aug 2019, Macau, China
Data integration systems allow users to access data sitting in multiple sources by means of queries over a global schema, related to the sources via mappings. Data sources often contain sensitive information, and thus an analysis is needed to verify
Externí odkaz:
http://arxiv.org/abs/1906.00624
We study the problem of enumerating the satisfying valuations of a circuit while bounding the delay, i.e., the time needed to compute each successive valuation. We focus on the class of structured d-DNNF circuits originally introduced in knowledge co
Externí odkaz:
http://arxiv.org/abs/1702.05589