4 citations · 8 across the 8 of their papers we have counts for
10 papers
Revisiting the Sparse Matrix Compression Problem
Vincent Jugé, Dominik Köppl, Vincent Limouzy +4
The sparse matrix compression problem asks for a one-dimensional representation of a binary matrix, formed by an integer array of row indices and a shift function f…
Timed Systems through the Lens of Logic
S. Akshay, Paul Gastin, Vincent Juge +1
In this paper, we analyze timed systems with data structures, using a rich interplay of logic and properties of graphs. We start by describing behaviors of timed systems using grap…
Asymptotic combinatorics of Artin-Tits monoids and of some other monoids
Samy Abbes, Sébastien Gouëzel, Vincent Jugé +1
We introduce methods to study the combinatorics of the normal form of large random elements in Artin-Tits monoids. These methods also apply in an axiomatic framework that encompass…
Adaptive Shivers Sort: An Alternative Sorting Algorithm
Vincent Jugé
We present one stable mergesort algorithm, called \Adaptive Shivers Sort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. We also prove…
On the Worst-Case Complexity of TimSort
Nicolas Auger, Vincent Jugé, Cyril Nicaud +1
TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two…
Unbounded product-form Petri nets
Patricia Bouyer, Serge Haddad, Vincent Jugé
Computing steady-state distributions in infinite-state stochastic systems is in general a very dificult task. Product-form Petri nets are those Petri nets for which the steady-stat…
Courcelle's Theorem Made Dynamic
Patricia Bouyer-Decitre, Vincent Jugé, Nicolas Markey
Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of model checking a fixed monadic second-o…
Dynamic Complexity of Parity Games with Bounded Tree-Width
Patricia Bouyer, Vincent Jugé, Nicolas Markey
Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of two-player parity games over graphs of…
Dynamic Complexity of the Dyck Reachability
Patricia Bouyer, Vincent Jugé
Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of Dyck reachability problems in directed…
The Relaxation Normal Form of Braids is Regular
Vincent Jugé
Braids can be represented geometrically as laminations of punctured disks. The geometric complexity of a braid is the minimal complexity of a lamination that represents it, and tig…