75 citations
- Université Paris CitéFR48 papers
- Centre National de la Recherche ScientifiqueFR25 papers
- Institut national de recherche en sciences et technologies du numériqueFR8 papers
- Laboratoire Bordelais de Recherche en InformatiqueFR8 papers
- Délégation Paris 7FR7 papers
- Sorbonne UniversitéFR4 papers
- École Normale Supérieure de LyonFR3 papers
- Laboratoire d'Informatique de l'École PolytechniqueFR3 papers
- Orange (France)FR3 papers
- CEA Paris-SaclayFR2 papers
- Commissariat à l'Énergie Atomique et aux Énergies AlternativesFR2 papers
- Computer Algorithms for MedicineAT2 papers
10 papers · 1 filter
Parameterized Verification of Safety Properties in Ad Hoc Network Protocols
Giorgio Delzanno, Arnaud Sangnier, Gianluigi Zavattaro
We summarize the main results proved in recent work on the parameterized verification of safety properties for ad hoc network protocols. We consider a model in which the communicat…
Pushing undecidability of the isolation problem for probabilistic automata
Nathanaël Fijalkow, Hugo Gimbert, Youssouf Oualhadj
This short note aims at proving that the isolation problem is undecidable for probabilistic automata with only one probabilistic transition. This problem is known to be undecidable…
Redundancy of minimal weight expansions in Pisot bases
Peter J. Grabner, Wolfgang Steiner
Motivated by multiplication algorithms based on redundant number representations, we study representations of an integer as a sum , where the digits are…
Optimal bounds for quantum bit commitment
André Chailloux, Iordanis Kerenidis
Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes in the information theoretic setting where…
The complexity of approximate Nash equilibrium in congestion games with negative delays
Frederic Magniez, Michel de Rougemont, Miklos Santha +1
We extend the study of the complexity of finding an $\eps$-approximate Nash equilibrium in congestion games from the case of positive delay functions to delays of arbitrary sign. W…
Splicing systems and the Chomsky hierarchy
Jean Berstel, Luc Boasson, Isabelle Fagnot
In this paper, we prove decidability properties and new results on the position of the family of languages generated by (circular) splicing systems within the Chomsky hierarchy. Th…