4 citations · 6 across the 3 of their papers we have counts for
6 papers
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…