1 citations · 5 across the 8 of their papers we have counts for
10 papers
Giant Components in Random Temporal Graphs
Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi +4
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős-Rényi…
Regular Model Checking Upside-Down: An Invariant-Based Approach
Javier Esparza, Michael Raskin, Christoph Welzel-Mohr
Regular model checking is a technique for the verification of infinite-state systems whose configurations can be represented as finite words over a suitable alphabet. The form we a…
Sharp Thresholds in Random Simple Temporal Graphs
Arnaud Casteigts, Michael Raskin, Malte Renken +1
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is c…
A unified algorithm for colouring graphs of bounded clique-width
Bruno Courcelle, Irène Durand, Michael Raskin
Clique-width is one of the graph complexity measures leading to polynomial special-case algorithms for generally NP-complete problems, e.g. graph colourability. The best two curren…
Efficient Restrictions of Immediate Observation Petri Nets
Michael Raskin, Chana Weil-Kennedy
In a previous paper we introduced immediate observation Petri nets, a subclass of Petri nets with application domains in distributed protocols (population protocols) and theoretica…
Minimization of visibly pushdown automata is NP-complete
Olivier Gauwin, Anca Muscholl, Michael Raskin
We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-v…
Working with first-order proofs and provers
Michael Raskin, Christoph Welzel
Verifying software correctness has always been an important and complicated task. Recently, formal proofs of critical properties of algorithms and even implementations are becoming…
A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
Michael Raskin
Unambiguous non-deterministic finite automata have intermediate expressive power and succinctness between deterministic and non-deterministic automata. It has been conjectured that…
Paradoxical examples of social networks games with product choice
M. Raskin, N. Nikitenkov
Paradox of choice occurs when permitting new strategies to some players yields lower payoffs for all players in the new equilibrium via a sequence of individually rational actions.…
Approximating the minimum cycle mean
Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger +1
We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean wei…