22 citations · 38 across the 7 of their papers we have counts for
11 papers
Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
Étienne Grandjean, Louis Jachiet
In this paper, we study the class of operations , of any fixed arity , satisfying the following property: for each…
Dynamic Membership for Regular Tree Languages
Antoine Amarilli, Corentin Barloy, Louis Jachiet +1
We study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet and a regular tree language over (expressed, e.g., as a…
Low-Latency Sliding Window Algorithms for Formal Languages
Moses Ganardi, Louis Jachiet, Markus Lohrey +1
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…
Which arithmetic operations can be performed in constant time in the RAM model with addition?
Étienne Grandjean, Louis Jachiet
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. Howev…
Tailored vertex ordering for faster triangle listing in large graphs
Fabrice Lécuyer, Louis Jachiet, Clémence Magnien +1
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 hig…
Efficient Enumeration Algorithms for Annotated Grammars
Antoine Amarilli, Louis Jachiet, Martín Muñoz +1
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…
Dynamic Membership for Regular Languages
Antoine Amarilli, Louis Jachiet, Charles Paperman
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 str…
Ranked enumeration of MSO logic on words
Pierre Bourhis, Alejandro Grez, Louis Jachiet +1
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 preproc…
Balancing expressiveness and inexpressiveness in view design
Michael Benedikt, Pierre Bourhis, Louis Jachiet +1
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 publi…
Reasoning about disclosure in data integration in the presence of source constraints
Michael Benedikt, Pierre Bourhis, Louis Jachiet +1
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 co…
A Circuit-Based Approach to Efficient Enumeration
Antoine Amarilli, Pierre Bourhis, Louis Jachiet +1
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 cla…