Nathalie Bertrand

Nathalie Bertrand

Auto-generated profile, based on publicly available information

Nathalie Bertrand

Univ Rennes, Inria, CNRS, IRISA

Research Focus & Metrics

Academic Career Length

24Years (2003-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 October 2004 in European Journal of Combinatorics
Verified
Journal Article
Closed access
NBNathalie Bertrand
Nathalie Bertrand
ICIrène Charon
Irène Charon
OHOlivier Hudry
Olivier Hudry
ALAntoine Lobstein
Antoine Lobstein

9 December 2014 in Logical Methods in Computer Science
Verified
Journal Article
Open access
PDF file
NBNathalie Bertrand
Nathalie Bertrand
PBPatricia Bouyer
Patricia Bouyer
TBThomas Brihaye
Thomas Brihaye
QMQuentin Menet
Quentin Menet
CBChristel Baier
Christel Baier
MJMarcin Jurdzinski
Marcin Jurdzinski
A stochastic timed automaton is a purely stochastic process defined on a timed automaton, in which both delays and discrete choices are made randomly. We study the almost-sure model-checking problem for this model, that is, given a stochastic timed automaton A and a property $\Phi$, we want to decide whether A satisfies $\Phi$ with probability 1. In this paper, we identify several classes of automata and of properties for which this can be decided. The proof relies on the construction of a finite abstraction, called the thick graph, that we interpret as a finite Markov chain, and for which we can decide the almost-sure model-checking problem. Correctness of the abstraction holds when automata are almost-surely fair, which we show, is the case for two large classes of systems, single- clock automata and so-called weak-reactive automata. Techniques employed in this article gather tools from real-time verification and probabilistic verification, as well as topological games played on timed automata.

1 January 2009
Verified
Book Chapter
Closed access
PDF file
CBChristel Baier
Christel Baier
NBNathalie Bertrand
Nathalie Bertrand
PBPatricia Bouyer
Patricia Bouyer
TBThomas Brihaye
Thomas Brihaye

1 November 2005 in Information and Computation
Verified
Journal Article
Closed access
PAP.A. Abdulla
P.A. Abdulla
NBN. Bertrand
N. Bertrand
ARA. Rabinovich
A. Rabinovich
PSPh. Schnoebelen
Ph. Schnoebelen

1 February 2012 in Journal of the ACM
Verified
Journal Article
Open access
PDF file
CBChristel Baier
Christel Baier
MGMarcus Grösser
Marcus Grösser
NBNathalie Bertrand
Nathalie Bertrand
Probabilistic ω-automata are variants of nondeterministic automata over infinite words where all choices are resolved by probabilistic distributions. Acceptance of a run for an infinite input word can be defined using traditional acceptance criteria for ω-automata, such as Büchi, Rabin or Streett conditions. The accepted language of a probabilistic ω-automata is then defined by imposing a constraint on the probability measure of the accepting runs. In this paper, we study a series of fundamental properties of probabilistic ω-automata with three different language-semantics: (1) the probable semantics that requires positive acceptance probability, (2) the almost-sure semantics that requires acceptance with probability 1, and (3) the threshold semantics that relies on an additional parameter λ ∈ ]0,1[ that specifies a lower probability bound for the acceptance probability. We provide a comparison of probabilistic ω-automata under these three semantics and nondeterministic ω-automata concerning expressiveness and efficiency. Furthermore, we address closure properties under the Boolean operators union, intersection and complementation and algorithmic aspects, such as checking emptiness or language containment.

1 April 2008
Verified
Book Chapter
Closed access
PDF file
CBChristel Baier
Christel Baier
NBNathalie Bertrand
Nathalie Bertrand
MGMarcus Größer
Marcus Größer