Nicolas Markey

Résumé

In formal verification, runtime monitoring consists of observing the execution of a system in order to decide as quickly as possible whether or not it satisfies a given property. We consider monitoring in a distributed setting, for properties given as reachability timed automata. In such a setting, the system is made of several components, each equipped with its own local clock and monitor. The monitors observe events occurring on their associated component, and receive timestamped events from other monitors through FIFO channels. Since clocks are local, they cannot be perfectly synchronized, resulting in imprecise timestamps. Consequently, they must be seen as intervals, leading monitors to consider possible reorderings of events. In this context, each monitor aims to provide, as early as possible, a verdict on the property it is monitoring, based on its potentially incomplete and imprecise knowledge of the current execution. In this paper, we propose an on-line monitoring algorithm for timed properties, robust to time imprecision and partial information from distant components. We first identify the date at which a monitor can safely compute a verdict based on received events. We then propose a monitoring algorithm that updates this date when new information arrives, maintains the current set of states in which the property can reside, and updates its verdict accordingly.

@inproceedings{rv2024-HJMR,
  author =              {Henry, L{\'e}o and J{\'e}ron, Thierry and Markey,
                         Nicolas and Roussanaly, Victor},
  title =               {Distributed Monitoring of Timed Properties},
  editor =              {{\'A}brah{\'a}m, Erikz and Abbas, Houssam},
  booktitle =           {{P}roceedings of the 24th {I}nternational {W}orkshop
                         on {R}untime {V}erification ({RV}'24)},
  acronym =             {{RV}'24},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {15191},
  pages =               {243-261},
  year =                {2024},
  month =               oct,
  doi =                 {10.1007/978-3-031-74234-7_16},
  abstract =            {In formal verification, runtime monitoring consists
                         of observing the execution of a system in order to
                         decide as quickly as possible whether or not it
                         satisfies a given property. We consider monitoring
                         in a distributed setting, for properties given as
                         reachability timed automata. In~such a setting,
                         the~system is made of several components, each
                         equipped with its own local clock and monitor.
                         The~monitors observe events occurring on their
                         associated component, and receive timestamped events
                         from other monitors through FIFO channels. Since
                         clocks are local, they cannot be perfectly
                         synchronized, resulting in imprecise timestamps.
                         Consequently, they must be seen as intervals,
                         leading monitors to consider possible reorderings of
                         events. In this context, each monitor aims to
                         provide, as early as possible, a verdict on the
                         property it is monitoring, based on its potentially
                         incomplete and imprecise knowledge of the current
                         execution. In~this~paper, we~propose an on-line
                         monitoring algorithm for timed properties, robust to
                         time imprecision and partial information from
                         distant components. We~first identify the date at
                         which a monitor can safely compute a verdict based
                         on received events. We~then propose a monitoring
                         algorithm that updates this date when new
                         information arrives, maintains the current set of
                         states in which the property can reside, and updates
                         its verdict accordingly.},
}

Résumé

We consider atomic congestion games on series-parallel networks, and study the structure of the sets of Nash equilibria and social local optima on a given network when the number of players varies. We establish that these sets are definable in Presburger arithmetic and that they admit semilinear representations whose all period vectors have a common direction. As an application, we prove that the prices of anarchy and stability converge to 1 as the number of players goes to infinity, and show how to exploit these semilinear representations to compute these ratios precisely for a given network and number of players.

@inproceedings{fsttcs2022-BMSS,
  author =              {Bertrand, Nathalie and Markey, Nicolas and
                         Sadhukhan, Suman and Sankur, Ocan},
  title =               {Semilinear Representations for Series-Parallel
                         Atomic Congestion Games},
  editor =              {Dawar, Anuj and Guruswami, Venkatesan},
  booktitle =           {{P}roceedings of the 42nd {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'22)},
  acronym =             {{FSTTCS}'22},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {250},
  pages =               {32:1-32:20},
  year =                {2022},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2022.32},
  abstract =            {We~consider atomic congestion games on
                         series-parallel networks, and study the structure of
                         the sets of Nash equilibria and social local optima
                         on a given network when the number of players
                         varies. We establish that these sets are definable
                         in Presburger arithmetic and that they admit
                         semilinear representations whose all period vectors
                         have a common direction. As~an~application, we~prove
                         that the prices of anarchy and stability converge
                         to~1 as the number of players goes to infinity, and
                         show how to exploit these semilinear representations
                         to compute these ratios precisely for a given
                         network and number of players.},
}

Résumé

We consider the parameterized verification problem for distributed algorithms where the goal is to develop techniques to prove the correctness of a given algorithm regardless of the number of participating processes. Motivated by an asynchronous binary consensus algorithm of [J. Aspnes; Fast deterministic consensus in a noisy environment; J. Algorithms, 2002], we consider round-based distributed algorithms communicating with shared memory. A particular challenge in these systems is that 1) the number of processes is unbounded, and, more importantly, 2) there is a fresh set of registers at each round. A verification algorithm thus needs to manage both sources of infinity. In this setting, we prove that the safety verification problem, which consists in deciding whether all possible executions avoid a given error state, is PSPACE-complete. For negative instances of the safety verification problem, we also provide exponential lower and upper bounds on the minimal number of processes needed for an error execution and on the minimal round on which the error state can be covered.

@inproceedings{icalp2022-BMSW,
  author =              {Bertrand, Nathalie and Markey, Nicolas and Sankur,
                         Ocan and Waldburger, Nicolas},
  title =               {Parameterized safety verification of round-based
                         shared-memory systems},
  editor =              {Woodruff, David and Boja{\'n}czyk, Miko{\l}aj},
  booktitle =           {{P}roceedings of the 49th {I}nternational
                         {C}olloquium on {A}utomata, {L}anguages and
                         {P}rogramming ({ICALP}'22)},
  acronym =             {{ICALP}'22},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  pages =               {113:1-113:20},
  year =                {2022},
  month =               jul,
  doi =                 {10.4230/LIPIcs.ICALP.2022.113},
  abstract =            {We consider the parameterized verification problem
                         for distributed algorithms where the goal is to
                         develop techniques to prove the correctness of a
                         given algorithm regardless of the number of
                         participating processes. Motivated by an
                         asynchronous binary consensus algorithm~of
                         [J.~Aspnes; Fast deterministic consensus in a noisy
                         environment; J.~Algorithms,~2002], we~consider
                         round-based distributed algorithms communicating
                         with shared memory. A~particular challenge in these
                         systems is that 1)~the~number of processes is
                         unbounded, and, more importantly, 2)~there is a
                         fresh set of registers at each round. A~verification
                         algorithm thus needs to manage both sources of
                         infinity. In~this setting, we~prove that the safety
                         verification problem, which consists in deciding
                         whether all possible executions avoid a given error
                         state, is PSPACE-complete. For~negative instances of
                         the safety verification problem, we~also provide
                         exponential lower and upper bounds on the minimal
                         number of processes needed for an error execution
                         and on the minimal round on which the error state
                         can be covered.},
}

Résumé

A chronicle is a temporal model introduced by Dousson et al. for situation recognition. In short, a chronicle consists of a set of events and a set of real-valued temporal constraints on the delays between pairs of events. This work investigates the relationship between chronicles and classical temporal model formalisms, namely TPTL and MTL. More specifically, we answer the following question: is it possible to find an equivalent formula in such formalisms for any chronicle? This question arises from the observation that a single chronicle captures complex temporal behaviours that do not order the events in time.

In this article, we introduce the subclass of linear chronicles, which defines a temporal order of occurrence of the event to be recognized in a temporal sequence. Our first result is that any chronicle can be expressed as a disjunction of linear chronicles. Our second result is that any linear chronicle has an equivalent TPTL formula. Using existing expressiveness results between TPTL and MTL, we show that some chronicles have no equivalent in MTL. This confirms that the model of chronicle has interesting properties for situation recognition.

@inproceedings{time2022-GM,
  author =              {Guyet, {\relax Th}omas and Markey, Nicolas},
  title =               {Logical forms of chronicles},
  editor =              {Artikis, Alexander and Posenato, Roberto and
                         Tonetta, Stefano},
  booktitle =           {{P}roceedings of the 29th {I}nternational
                         {S}ymposium on {T}emporal {R}epresentation and
                         {R}easoning ({TIME}'22)},
  acronym =             {{TIME}'22},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  pages =               {7:1-7:15},
  year =                {2022},
  month =               nov,
  doi =                 {10.4230/LIPIcs.TIME.2022.7},
  abstract =            {A~chronicle is a temporal model introduced by
                         Dousson~\textit{et~al.} for situation recognition.
                         In~short, a chronicle consists of a set of events
                         and a set of real-valued temporal constraints on the
                         delays between pairs of events. This~work
                         investigates the relationship between chronicles and
                         classical temporal model formalisms, namely
                         \textsf{TPTL} and~\textsf{MTL}. More~specifically,
                         we~answer the following question: is~it possible to
                         find an equivalent formula in such formalisms for
                         any chronicle? This~question arises from the
                         observation that a single chronicle captures complex
                         temporal behaviours that do not order the events in
                         time.\par In~this article, we~introduce the subclass
                         of linear chronicles, which defines a temporal order
                         of occurrence of the event to be recognized in a
                         temporal sequence. Our~first result is that any
                         chronicle can be expressed as a disjunction of
                         linear chronicles. Our~second result is that any
                         linear chronicle has an equivalent \textsf{TPTL}
                         formula. Using existing expressiveness results
                         between \textsf{TPTL} and~\textsf{MTL}, we~show that
                         some chronicles have no equivalent in~\textsf{MTL}.
                         This confirms that the model of chronicle has
                         interesting properties for situation recognition.},
}

Résumé

Network congestion games are a convenient model for reasoning about routing problems in a network: agents have to move from a source to a target vertex while avoiding congestion, measured as a cost depending on the number of players using the same link. Network congestion games have been extensively studied over the last 40 years, while their extension with timing constraints were considered more recently.

Most of the results on network congestion games consider blind strategies: they are static, and do not adapt to the strategies selected by the other players. We extend the recent results of [Bertrand et al., Dynamic network congestion games. FSTTCS'20] to timed network congestion games, in which the availability of the edges depend on (discrete) time. We prove that computing Nash equilibria satisfying some constraint on the total cost (and in particular, computing the best and worst Nash equilibria), and computing the social optimum, can be achieved in exponential space. The social optimum can be computed in polynomial space if all players have the same source and target.

@inproceedings{formats2022-GMS,
  author =              {Goeminne, Aline and Markey, Nicolas and Sankur,
                         Ocan},
  title =               {Non-Blind Strategies in Timed Network Congestion
                         Games},
  editor =              {Bogomolov, Sergiy and Parker, David},
  booktitle =           {{P}roceedings of the 20th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'22)},
  acronym =             {{FORMATS}'22},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {13465},
  pages =               {183-199},
  year =                {2022},
  month =               sep,
  doi =                 {10.1007/978-3-031-15839-1_11},
  abstract =            {Network congestion games are a convenient model for
                         reasoning about routing problems in a network:
                         agents have to move from a source to a target vertex
                         while avoiding congestion, measured as a cost
                         depending on the number of players using the same
                         link. Network congestion games have been extensively
                         studied over the last 40 years, while their
                         extension with timing constraints were considered
                         more recently. \par Most of the results on network
                         congestion games consider blind strategies: they are
                         static, and do not adapt to the strategies selected
                         by the other players. We extend the recent results
                         of [Bertrand~\textit{et~al.}, Dynamic network
                         congestion games. FSTTCS'20] to timed network
                         congestion games, in which the availability of the
                         edges depend on (discrete) time. We prove that
                         computing Nash equilibria satisfying some constraint
                         on the total cost (and in particular, computing the
                         best and worst Nash equilibria), and computing the
                         social optimum, can be achieved in exponential
                         space. The social optimum can be computed in
                         polynomial space if all players have the same source
                         and target.},
}

Résumé

We consider the problem of repairing inconsistent real-time requirements with respect to two consistency notions: non-vacuity, which means that each requirement can be realized without violating other ones, and rt-consistency, which means that inevitable violations are detected immediately. We provide an iterative algorithm, based on solving SMT queries, to replace designated parameters of real-time requirements with new Boolean expressions and time constraints, so that the resulting set of requirements becomes consistent.

@inproceedings{atva2022-NSJMM,
  author =              {Noguchi, Reiya and Sankur, Ocan and J{\'e}ron,
                         Thierry and Markey, Nicolas and Mentr{\'e}, David},
  title =               {Repairing Real-Time Requirements},
  editor =              {Bouajjani, Ahmed and Hol{\'\i}k, Luk{\'a}{\v s} and
                         Wu, Zhilin},
  booktitle =           {{P}roceedings of the 20th {I}nternational
                         {S}ymposium on {A}utomated {T}echnology for
                         {V}erification and {A}nalysis ({ATVA}'22)},
  acronym =             {{ATVA}'22},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {13505},
  pages =               {371-387},
  year =                {2022},
  month =               oct,
  doi =                 {10.1007/978-3-031-19992-9_24},
  abstract =            {We~consider the problem of repairing inconsistent
                         real-time requirements with respect to two
                         consistency notions: non-vacuity, which means that
                         each requirement can be realized without violating
                         other ones, and rt-consistency, which means that
                         inevitable violations are detected immediately.
                         We~provide an iterative algorithm, based on solving
                         SMT queries, to replace designated parameters of
                         real-time requirements with new Boolean expressions
                         and time constraints, so that the resulting set of
                         requirements becomes consistent.},
}

Résumé

Congestion games are a classical type of games studied in game theory, in which n players choose a resource, and their individual cost increases with the number of other players choosing the same resource. In network congestion games (NCGs), the resources correspond to simple paths in a graph, e.g. representing routing options from a source to a target. In this paper, we introduce a variant of NCGs, referred to as dynamic NCGs: in this setting, players take transitions synchronously, they select their next transitions dynamically, and they are charged a cost that depends on the number of players simultaneously using the same transition.

We study, from a complexity perspective, standard concepts of game theory in dynamic NCGs: social optima, Nash equilibria, and subgame perfect equilibria. Our contributions are the following: the existence of a strategy profile with social cost bounded by a constant is in PSPACE and NP-hard. (Pure) Nash equilibria always exist in dynamic NCGs; the existence of a Nash equilibrium with bounded cost can be decided in EXPSPACE, and computing a witnessing strategy profile can be done in doubly-exponential time. The existence of a subgame perfect equilibrium with bounded cost can be decided in 2EXPSPACE, and a witnessing strategy profile can be computed in triply-exponential time.

@inproceedings{fsttcs2020-BMSS,
  author =              {Bertrand, Nathalie and Markey, Nicolas and
                         Sadhukhan, Suman and Sankur, Ocan},
  title =               {Dynamic network congestion games},
  editor =              {Saxena, Nitin and Simon, Sunil},
  booktitle =           {{P}roceedings of the 40th {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'20)},
  acronym =             {{FSTTCS}'20},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {182},
  pages =               {40:1-40:16},
  year =                {2020},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2020.40},
  abstract =            {Congestion games are a classical type of games
                         studied in game theory, in which n players choose a
                         resource, and their individual cost increases with
                         the number of other players choosing the same
                         resource. In network congestion games~(NCGs), the
                         resources correspond to simple paths in a graph,
                         e.g.~representing routing options from a source to a
                         target. In this paper, we introduce a variant
                         of~NCGs, referred to as dynamic~NCGs: in~this
                         setting, players take transitions synchronously,
                         they select their next transitions dynamically, and
                         they are charged a cost that depends on the number
                         of players simultaneously using the same transition.
                         \par We~study, from a complexity perspective,
                         standard concepts of game theory in dynamic NCGs:
                         social optima, Nash equilibria, and subgame perfect
                         equilibria. Our contributions are the following: the
                         existence of a strategy profile with social cost
                         bounded by a constant is in PSPACE and NP-hard.
                         (Pure)~Nash equilibria always exist in dynamic~NCGs;
                         the existence of a Nash equilibrium with bounded
                         cost can be decided in EXPSPACE, and computing a
                         witnessing strategy profile can be done in
                         doubly-exponential time. The~existence of a subgame
                         perfect equilibrium with bounded cost can be decided
                         in 2EXPSPACE, and a witnessing strategy profile can
                         be computed in triply-exponential~time.},
}

Résumé

Timed automata are a convenient mathematical model for modelling and reasoning about real-time systems. While they provide a powerful way of representing timing aspects of such systems, timed automata assume arbitrary precision and zero-delay actions; in particular, a state might be declared reachable in a timed automaton, but impossible to reach in the physical system it models.

In this paper, we consider permissive strategies as a way to overcome this problem: such strategies propose intervals of delays instead of single delays, and aim at reaching a target state whichever delay actually takes place. We develop an algorithm for computing the optimal permissiveness (and an associated maximally-permissive strategy) in acyclic timed automata and games.

@inproceedings{formats2020-CJMM,
  author =              {Clement, Emily and J{\'e}ron, Thierry and Markey,
                         Nicolas and Mentr{\'e}, David},
  title =               {Computing maximally-permissive strategies in acyclic
                         timed automata},
  editor =              {Bertrand, Nathalie and Jansen, Nils},
  booktitle =           {{P}roceedings of the 18th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'20)},
  acronym =             {{FORMATS}'20},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {12288},
  pages =               {111-126},
  year =                {2020},
  month =               sep,
  doi =                 {10.1007/978-3-030-57628-8_7},
  abstract =            {Timed automata are a convenient mathematical model
                         for modelling and reasoning about real-time systems.
                         While they provide a powerful way of representing
                         timing aspects of such systems, timed automata
                         assume arbitrary precision and zero-delay actions;
                         in~particular, a~state might be declared reachable
                         in a timed automaton, but impossible to reach in the
                         physical system it models. \par In this paper, we
                         consider permissive strategies as a way to overcome
                         this problem: such strategies propose intervals of
                         delays instead of single delays, and aim at reaching
                         a target state whichever delay actually takes place.
                         We develop an algorithm for computing the optimal
                         permissiveness (and~an associated
                         maximally-permissive strategy) in acyclic timed
                         automata and games.},
}

Résumé

Active learning of timed languages is concerned with the inference of timed automata by observing some of the timed words in their languages. The learner can query for the membership of words in the language, or propose a candidate model and ask if it is equivalent to the target. The major difficulty of this framework is the inference of clock resets, which are central to the dynamics of timed automata but not directly observable.

Interesting first steps have already been made by restricting to the subclass of event-recording automata, where clock resets are tied to observations. In order to advance towards learning of general timed automata, we generalize this method to a new class, called reset-free event-recording automata, where some transitions may reset no clocks.

Central to our contribution is the notion of invalidity, and the algorithm and data structures to deal with it, allowing on-the-fly detection and pruning of reset hypotheses that contradict observations. This notion is a key to any efficient active-learning procedure for generic timed automata.

@inproceedings{formats2020-HJM,
  author =              {Henry, L{\'e}o and J{\'e}ron, Thierry and Markey,
                         Nicolas},
  title =               {Active learning of timed automata with unobservable
                         resets},
  editor =              {Bertrand, Nathalie and Jansen, Nils},
  booktitle =           {{P}roceedings of the 18th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'20)},
  acronym =             {{FORMATS}'20},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {12288},
  pages =               {144-160},
  year =                {2020},
  month =               sep,
  doi =                 {10.1007/978-3-030-57628-8_9},
  abstract =            {Active learning of timed languages is concerned with
                         the inference of timed automata by observing some of
                         the timed words in their languages. The learner can
                         query for the membership of words in the language,
                         or propose a candidate model and ask if it is
                         equivalent to the target. The major difficulty of
                         this framework is the inference of clock resets,
                         which are central to the dynamics of timed automata
                         but not directly observable. \par Interesting first
                         steps have already been made by restricting to the
                         subclass of event-recording automata, where clock
                         resets are tied to observations. In order to advance
                         towards learning of general timed automata, we
                         generalize this method to a new class, called
                         reset-free event-recording automata, where some
                         transitions may reset no clocks. \par Central to our
                         contribution is the notion of invalidity, and the
                         algorithm and data structures to deal with it,
                         allowing on-the-fly detection and pruning of reset
                         hypotheses that contradict observations. This notion
                         is a key to any efficient active-learning procedure
                         for generic timed automata.},
}

Résumé

Requirements engineering is a key phase in the development process. Ensuring that requirements are consistent is essential so that they do not conflict and admit implementations. We consider the formal verification of rt-consistency, which imposes that the inevitability of definitive errors of a requirement should be anticipated, and that of partial consistency, which was recently introduced as a more effective check. We generalize and formalize both notions for discrete-time timed automata, develop three incremental algorithms, and present experimental results.

@inproceedings{formats2020-JMMNS,
  author =              {J{\'e}ron, Thierry and Markey, Nicolas and
                         Mentr{\'e}, David and Noguchi, Reiya and Sankur,
                         Ocan},
  title =               {Incremental methods for checking real-time
                         consistency},
  editor =              {Bertrand, Nathalie and Jansen, Nils},
  booktitle =           {{P}roceedings of the 18th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'20)},
  acronym =             {{FORMATS}'20},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {12288},
  pages =               {249-264},
  year =                {2020},
  month =               sep,
  doi =                 {10.1007/978-3-030-57628-8_15},
  abstract =            {Requirements engineering is a key phase in the
                         development process. Ensuring that requirements are
                         consistent is essential so that they do not conflict
                         and admit implementations. We~consider the formal
                         verification of rt-consistency, which imposes that
                         the inevitability of definitive errors of a
                         requirement should be anticipated, and that of
                         partial consistency, which was recently introduced
                         as a more effective check. We~generalize and
                         formalize both notions for discrete-time timed
                         automata, develop three incremental algorithms, and
                         present experimental results.},
}

Résumé

We introduce and study SL[F]—a quantitative extension of SL (Strategy Logic), one of the most natural and expressive logics describing strategic behaviours. The satisfaction value of an SL[F] formula is a real value in [0,1], reflecting "how much" or "how well" the strategic on-going objectives of the underlying agents are satisfied. We demonstrate the applications of SL[F] in quantitative reasoning about multi-agent systems, by showing how it can express concepts of stability in multi-agent systems, and how it generalises some fuzzy temporal logics. We also provide a model-checking algorithm for our logic, based on a quantitative extension of Quantified CTL.

@inproceedings{ijcai2019-BKMMMP,
  author =              {Bouyer, Patricia and Kupferman, Orna and Markey,
                         Nicolas and Maubert, Bastien and Murano, Aniello and
                         Perelli, Giuseppe},
  title =               {Reasoning about Quality and Fuzziness of Strategic
                         Behaviours},
  editor =              {Kraus, Sarit},
  booktitle =           {{P}roceedings of the 28th {I}nternational {J}oint
                         {C}onference on {A}rtificial {I}ntelligence
                         ({IJCAI}'19)},
  acronym =             {{IJCAI}'19},
  publisher =           {IJCAI organization},
  pages =               {1588-1594},
  year =                {2019},
  month =               aug,
  doi =                 {10.24963/ijcai.2019/220},
  abstract =            {We~introduce and study
                         {\(\textsf{SL}[\mathcal{F}]\)}---a~quantitative
                         extension of {\(\textsf{SL}\)} (Strategy Logic),
                         one~of the most natural and expressive logics
                         describing strategic behaviours. The satisfaction
                         value of an {\(\textsf{SL}[\mathcal{F}]\)} formula
                         is a real value in~{\([0,1]\)}, reflecting {"}how
                         much{"} or {"}how well{"} the strategic on-going
                         objectives of the underlying agents are satisfied.
                         We~demonstrate the applications of
                         {\(\textsf{SL}[\mathcal{F}]\)} in quantitative
                         reasoning about multi-agent systems, by showing how
                         it can express concepts of stability in multi-agent
                         systems, and how it generalises some fuzzy temporal
                         logics. We~also provide a model-checking algorithm
                         for our logic, based on a quantitative extension of
                         Quantified~\textsf{CTL}.},
}

Résumé

We study games with reachability objectives under energy constraints. We first prove that under strict energy constraints (either only lower-bound constraint or interval constraint), those games are LOGSPACE-equivalent to energy games with the same energy constraints but without reachability objective (i.e., for infinite runs). We then consider two kinds of relaxations of the upper-bound constraints (while keeping the lower-bound constraint strict): in the first one, called weak upper bound, the upper bound is absorbing, in the sense that it allows receiving more energy when the upper bound is already reached, but the extra energy will not be stored; in the second one, we allow for temporary violations of the upper bound, imposing limits on the number or on the amount of violations.

We prove that when considering weak upper bound, reachability objectives require memory, but can still be solved in polynomial-time for one-player arenas; we prove that they are in coNP in the two-player setting. Allowing for bounded violations makes the problem PSPACE-complete for one-player arenas and EXPTIME-complete for two players.

@inproceedings{gandalf2019-HMR,
  author =              {H{\'e}lou{\"e}t, Lo{\"\i}c and Markey, Nicolas and
                         Raha, Ritam},
  title =               {Reachability games with relaxed energy constraints},
  editor =              {Leroux, J{\'e}r{\^o}me and Raskin, Jean-Fran{\c
                         c}ois},
  booktitle =           {{P}roceedings of the 10th {I}nternational
                         {S}ymposium on {G}ames, {A}utomata, {L}ogics and
                         {F}ormal {V}erification ({GandALF}'19)},
  acronym =             {{GandALF}'19},
  series =              {Electronic Proceedings in Theoretical Computer
                         Science},
  volume =              {305},
  pages =               {17-33},
  year =                {2019},
  month =               sep,
  doi =                 {10.4204/EPTCS.305.2},
  abstract =            {We study games with reachability objectives under
                         energy constraints. We first prove that under strict
                         energy constraints (either only lower-bound
                         constraint or interval constraint), those games are
                         \textsf{LOGSPACE}-equivalent to energy games with
                         the same energy constraints but without reachability
                         objective (i.e., for infinite runs). We then
                         consider two kinds of relaxations of the upper-bound
                         constraints (while keeping the lower-bound
                         constraint strict): in the first one, called
                         \emph{weak upper bound}, the upper bound is
                         \emph{absorbing}, in the sense that it allows
                         receiving more energy when the upper bound is
                         already reached, but the extra energy will not be
                         stored; in~the second~one, we~allow for
                         \emph{temporary violations} of the upper bound,
                         imposing limits on the number or on the amount of
                         violations.\par We prove that when considering weak
                         upper bound, reachability objectives require memory,
                         but can still be solved in polynomial-time for
                         one-player arenas; we prove that they are in
                         \textsf{coNP} in the two-player setting. Allowing
                         for bounded violations makes the problem
                         \textsf{PSPACE}-complete for one-player arenas and
                         \textsf{EXPTIME}-complete for two players.},
}

Résumé

We present abstraction-refinement algorithms for model checking safety properties of timed automata. The abstraction domain we consider abstracts away zones by restricting the set of clock constraints that can be used to define them, while the refinement procedure computes the set of constraints that must be taken into consideration in the abstraction so as to exclude a given spurious counterexample. We implement this idea in two ways: an enumerative algorithm where a lazy abstraction approach is adopted, meaning that possibly different abstract domains are assigned to each exploration node; and a symbolic algorithm where the abstract transition system is encoded with Boolean formulas.

@inproceedings{cav2019-RSM,
  author =              {Roussanaly, Victor and Sankur, Ocan and Markey,
                         Nicolas},
  title =               {Abstraction Refinement Algorithms for Timed
                         Automata},
  editor =              {Dillig, I{\c s}il and Ta{\c s}iran, Serdar},
  booktitle =           {{P}roceedings of the 31st {I}nternational
                         {C}onference on {C}omputer {A}ided {V}erification
                         ({CAV}'19)},
  acronym =             {{CAV}'19},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {11561},
  pages =               {22-40},
  year =                {2019},
  month =               jul,
  doi =                 {10.1007/978-3-030-25540-4_2},
  abstract =            {We~present abstraction-refinement algorithms for
                         model checking safety properties of timed automata.
                         The~abstraction domain we consider abstracts away
                         zones by restricting the set of clock constraints
                         that can be used to define them, while the
                         refinement procedure computes the set of constraints
                         that must be taken into consideration in the
                         abstraction so as to exclude a given spurious
                         counterexample. We~implement this idea in two~ways:
                         an~enumerative algorithm where a lazy abstraction
                         approach is adopted, meaning that possibly different
                         abstract domains are assigned to each exploration
                         node; and a symbolic algorithm where the abstract
                         transition system is encoded with Boolean formulas.},
}

Résumé

In this paper, we propose a novel framework for the synthesis of robust and optimal energy-aware controllers. The framework is based on energy timed automata, allowing for easy expression of timing-constraints and variable energy-rates. We prove decidability of the energy-constrained infinite-run problem in settings with both certainty and uncertainty of the energy-rates. We also consider the optimization problem of identifying the minimal upper bound that will permit existence of energy-constrained infinite runs. Our algorithms are based on quantifier elimination for linear real arithmetic. Using Mathematica and Mjollnir, we illustrate our framework through a real industrial example of a hydraulic oil pump. Compared with previous approaches our method is completely automated and provides improved results.

@inproceedings{fm2018-BBFLMR,
  author =              {Bacci, Giovanni and Bouyer, Patricia and Fahrenberg,
                         Uli and Larsen, Kim Guldstrand and Markey, Nicolas
                         and Reynier, Pierre-Alain},
  title =               {Optimal and Robust Controller Synthesis Using Energy
                         Timed Automata with Uncertainty},
  editor =              {Havelund, Klaus and Peleska, Jan and Roscoe, Bill W.
                         and de Vink, Erik},
  booktitle =           {{P}roceedings of the 22nd {I}nternational
                         {S}ymposium on {F}ormal {M}ethods ({FM}'18)},
  acronym =             {{FM}'18},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {10951},
  pages =               {203-221},
  year =                {2018},
  month =               jul,
  doi =                 {10.1007/978-3-319-95582-7_12},
  abstract =            {In this paper, we propose a novel framework for the
                         synthesis of robust and optimal energy-aware
                         controllers. The framework is based on energy timed
                         automata, allowing for easy expression of
                         timing-constraints and variable energy-rates. We
                         prove decidability of the energy-constrained
                         infinite-run problem in settings with both certainty
                         and uncertainty of the energy-rates. We also
                         consider the optimization problem of identifying the
                         minimal upper bound that will permit existence of
                         energy-constrained infinite runs. Our algorithms are
                         based on quantifier elimination for linear real
                         arithmetic. Using Mathematica and Mjollnir, we
                         illustrate our framework through a real industrial
                         example of a hydraulic oil pump. Compared with
                         previous approaches our method is completely
                         automated and provides improved results.},
}

Résumé

Reconfigurable broadcast networks provide a convenient formalism for modelling and reasoning about networks of mobile agents broadcasting messages to other agents following some (evolving) communication topology. The parameterized verification of such models aims at checking whether a given property holds irrespective of the initial configuration (number of agents, initial states and initial communication topology). We focus here on the synchronization property, asking whether all agents converge to a set of target states after some execution. This problem is known to be decidable in polynomial time when no constraints are imposed on the evolution of the communication topology (while it is undecidable for static broadcast networks).

In this paper we investigate how various constraints on reconfigurations affect the decidability and complexity of the synchronization problem. In particular, we show that when bounding the number of reconfigured links between two communications steps by a constant, synchronization becomes undecidable; on the other hand, synchronization remains decidable in PTIME when the bound grows with the number of agents.

@inproceedings{tacas2018-2-BBM,
  author =              {Balasubramanian, A. R. and Bertrand, Nathalie and
                         Markey, Nicolas},
  title =               {Parameterized verification of synchronization in
                         constrained reconfigurable broadcast networks},
  editor =              {Beyer, Dirk and Huisman, Marieke},
  booktitle =           {{P}roceedings of the 24th {I}nternational
                         {C}onference on {T}ools and {A}lgorithms for
                         {C}onstruction and {A}nalysis of {S}ystems
                         ({TACAS}'18)~-- {P}art~{II}},
  acronym =             {{TACAS}'18 (Part~{II})},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {10806},
  pages =               {38-54},
  year =                {2018},
  month =               apr,
  doi =                 {10.1007/978-3-319-89963-3_3},
  abstract =            {Reconfigurable broadcast networks provide a
                         convenient formalism for modelling and reasoning
                         about networks of mobile agents broadcasting
                         messages to other agents following some (evolving)
                         communication topology. The parameterized
                         verification of such models aims at checking whether
                         a given property holds irrespective of the initial
                         configuration (number of agents, initial states and
                         initial communication topology). We~focus here on
                         the \emph{synchronization property}, asking whether
                         all agents converge to a set of target states after
                         some execution. This~problem is known to be
                         decidable in polynomial time when no constraints are
                         imposed on the evolution of the communication
                         topology (while~it~is undecidable for static
                         broadcast networks).\par In this paper we
                         investigate how various constraints on
                         reconfigurations affect the decidability and
                         complexity of the synchronization problem.
                         In~particular, we show that when bounding the number
                         of reconfigured links between two communications
                         steps by a constant, synchronization becomes
                         undecidable; on~the other hand, synchronization
                         remains decidable in PTIME when the bound grows with
                         the number of agents.},
}

Résumé

In this paper, we are interested in the synthesis of schedulers in double-weighted Markov decision processes, which satisfy both a percentile constraint over a weighted reachability condition, and a quantitative constraint on the expected value of a random variable defined using a weighted reachability condition. This problem is inspired by the modelization of an electric-vehicle charging problem. We study the cartography of the problem, when one parameter varies, and show how a partial cartography can be obtained via two sequences of opimization problems. We discuss completeness and feasability of the method.

@inproceedings{gandalf2018-BGMR,
  author =              {Bouyer, Patricia and Gonz{\'a}lez, Mauricio and
                         Markey, Nicolas and Randour, Mickael},
  title =               {Multi-weighted Markov Decision Processes with
                         Reachability Objectives},
  editor =              {Orlandini, Andrea and Zimmermann, Martin},
  booktitle =           {{P}roceedings of the 9th {I}nternational {S}ymposium
                         on {G}ames, {A}utomata, {L}ogics and {F}ormal
                         {V}erification ({GandALF}'18)},
  acronym =             {{GandALF}'18},
  series =              {Electronic Proceedings in Theoretical Computer
                         Science},
  volume =              {277},
  pages =               {250-264},
  year =                {2018},
  month =               sep,
  doi =                 {10.4204/EPTCS.277.18},
  abstract =            {In~this paper, we~are interested in the synthesis of
                         schedulers in double-weighted Markov decision
                         processes, which satisfy both a percentile
                         constraint over a weighted reachability condition,
                         and a quantitative constraint on the expected value
                         of a random variable defined using a weighted
                         reachability condition. This~problem is inspired by
                         the modelization of an electric-vehicle charging
                         problem. We study the cartography of the problem,
                         when one parameter varies, and show how a partial
                         cartography can be obtained via two sequences of
                         opimization problems. We~discuss completeness and
                         feasability of the method.},
}

Résumé

We consider the problems of efficiently diagnosing and predicting what did (or will) happen in a partially-observable one-clock timed automaton. We introduce timed sets as a formalism to keep track of the evolution of the reachable configurations over time, and use our previous work on automata over timed domains to build a candidate diagnoser for our timed automaton. We report on our implementation of this approach compared to the approach of [Tripakis, Fault diagnosis for timed autmata, 2002].

@inproceedings{rv2018-BJM,
  author =              {Bouyer, Patricia and Jaziri, Samy and Markey,
                         Nicolas},
  title =               {Efficient timed diagnosis using automata with timed
                         domains},
  editor =              {Colombo, Christian and Leucker, Martin},
  booktitle =           {{P}roceedings of the 18th {I}nternational {W}orkshop
                         on {R}untime {V}erification ({RV}'18)},
  acronym =             {{RV}'18},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {11237},
  pages =               {205-221},
  year =                {2018},
  month =               nov,
  doi =                 {10.1007/978-3-030-03769-7_12},
  abstract =            {We consider the problems of efficiently diagnosing
                         and predicting what did (or~will) happen in a
                         partially-observable one-clock timed automaton.
                         We~introduce timed sets as a formalism to keep track
                         of the evolution of the reachable configurations
                         over time, and use our previous work on automata
                         over timed domains to build a candidate diagnoser
                         for our timed automaton. We~report on our
                         implementation of this approach compared to the
                         approach of [Tripakis, Fault diagnosis for timed
                         autmata,~2002].},
}

Résumé

Strategy Logic (SL) is a very expressive temporal logic for specifying and verifying properties of multi-agent systems: in SL, one can quantify over strategies, assign them to agents, and express LTL properties of the resulting plays. Such a powerful framework has two drawbacks: first, model checking SL has non-elementary complexity; second, the exact semantics of SL is rather intricate, and may not correspond to what is expected. In this paper, we focus on strategy dependences in SL, by tracking how existentially-quantified strategies in a formula may (or may not) depend on other strategies selected in the formula, revisiting the approach of [Mogavero et al., Reasoning about strategies: On the model-checking problem, 2014]. We explain why elementary dependences, as defined by Mogavero et al., do not exactly capture the intended concept of behavioral strategies. We address this discrepancy by introducing timeline dependences, and exhibit a large fragment of SL for which model checking can be performed in 2EXPTIME under this new semantics.

@inproceedings{stacs2018-GBM,
  author =              {Gardy, Patrick and Bouyer, Patricia and Markey,
                         Nicolas},
  title =               {Dependences in Strategy Logic},
  editor =              {Niedermeier, Rolf and Vall{\'e}e, Brigitte},
  booktitle =           {{P}roceedings of the 35th {S}ymposium on
                         {T}heoretical {A}spects of {C}omputer {S}cience
                         ({STACS}'18)},
  acronym =             {{STACS}'18},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {96},
  pages =               {34:1-34:14},
  year =                {2018},
  month =               feb,
  doi =                 {10.4230/LIPIcs.STACS.2018.34},
  abstract =            {Strategy Logic~(\textsf{SL}) is a very expressive
                         temporal logic for specifying and verifying
                         properties of multi-agent systems: in~\textsf{SL},
                         one can quantify over strategies, assign them to
                         agents, and express \textsf{LTL} properties of the
                         resulting plays. Such a powerful framework has two
                         drawbacks: first, model checking \textsf{SL} has
                         non-elementary complexity; second, the exact
                         semantics of \textsf{SL} is rather intricate, and
                         may not correspond to what is expected. In~this
                         paper, we~focus on \emph{strategy dependences}
                         in~\textsf{SL}, by tracking how
                         existentially-quantified strategies in a formula may
                         (or~may~not) depend on other strategies selected in
                         the formula, revisiting the approach of~[Mogavero
                         \emph{et~al.}, Reasoning about strategies: On~the
                         model-checking problem,~2014]. We~explain why
                         \emph{elementary} dependences, as defined by
                         Mogavero~\emph{et~al.}, do not exactly capture the
                         intended concept of behavioral strategies.
                         We~address this discrepancy by introducing
                         \emph{timeline} dependences, and exhibit a large
                         fragment of \textsf{SL} for which model checking can
                         be performed in \textsf{2EXPTIME} under this new
                         semantics.},
}

Résumé

Partial observability and controllability are two well-known issues in test-case synthesis for interactive systems. We address the problem of partial control in the synthesis of test cases from timed-automata specifications. Building on the tioco timed testing framework, we extend a previous game interpretation of the test-synthesis problem from the untimed to the timed setting. This extension requires a deep reworking of the models, game interpretation and test-synthesis algorithms. We exhibit strategies of a game that tries to minimize both control losses and distance to the satisfaction of a test purpose, and prove they are winning under some fairness assumptions. This entails that when turning those strategies into test cases, we get properties such as soundness and exhaustiveness of the test synthesis method.

@inproceedings{spin2018-HJM,
  author =              {Henry, L{\'e}o and J{\'e}ron, Thierry and Markey,
                         Nicolas},
  title =               {Control strategies for off-line testing of timed
                         systems},
  editor =              {Gallardo, Mar{\'\i}a-del-Mar and Merino, Pedro},
  booktitle =           {{P}roceedings of the 25th {I}nternational
                         {S}ymposium on {M}odel-{C}herking {S}oftware
                         ({SPIN}'18)},
  acronym =             {{SPIN}'18},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {10869},
  pages =               {171-189},
  year =                {2018},
  month =               jun,
  doi =                 {10.1007/978-3-319-94111-0_10},
  abstract =            {Partial observability and controllability are two
                         well-known issues in test-case synthesis for
                         interactive systems. We~address the problem of
                         partial control in the synthesis of test cases from
                         timed-automata specifications. Building on the tioco
                         timed testing framework, we~extend a previous game
                         interpretation of the test-synthesis problem from
                         the untimed to the timed setting. This extension
                         requires a deep reworking of the models, game
                         interpretation and test-synthesis algorithms.
                         We~exhibit strategies of a game that tries to
                         minimize both control losses and distance to the
                         satisfaction of a test purpose, and prove they are
                         winning under some fairness assumptions. This
                         entails that when turning those strategies into test
                         cases, we get properties such as soundness and
                         exhaustiveness of the test synthesis method.},
}

Résumé

We consider average-energy games, where the goal is to minimize the long-run average of the accumulated energy. Decidability of average-energy games with a lower-bound constraint on the energy level (but no upper bound) is an open problem; in particular, there is no known upper bound on the memory that is required for winning strategies.

By reducing average-energy games with lower-bounded energy to infinite-state mean-payoff games and analyzing the frequency of low-energy configurations, we show an almost tight doubly-exponential upper bound on the necessary memory, and that the winner of average-energy games with lower-bounded energy can be determined in doubly-exponential time. We also prove EXPSPACE-hardness of this problem.

Finally, we consider multi-dimensional extensions of all types of average-energy games: without bounds, with only a lower bound, and with both a lower and an upper bound on the energy. We show that the fully-bounded version is the only case to remain decidable in multiple dimensions.

@inproceedings{fossacs2017-BHMRZ,
  author =              {Bouyer, Patricia and Hofman, Piotr and Markey,
                         Nicolas and Randour, Mickael and Zimmermann, Martin},
  title =               {Bounding Average-energy Games},
  editor =              {Esparza, Javier and Murawski, Andrzej},
  booktitle =           {{P}roceedings of the 20th {I}nternational
                         {C}onference on {F}oundations of {S}oftware
                         {S}cience and {C}omputation {S}tructure
                         ({FoSSaCS}'17)},
  acronym =             {{FoSSaCS}'17},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {10203},
  pages =               {179-195},
  year =                {2017},
  month =               apr,
  doi =                 {10.1007/978-3-662-54458-7_11},
  abstract =            {We~consider average-energy games, where the goal is
                         to minimize the long-run average of the accumulated
                         energy. Decidability of average-energy games with a
                         lower-bound constraint on the energy level (but~no
                         upper bound) is an open problem; in~particular,
                         there is no known upper bound on the memory that is
                         required for winning strategies.\par By~reducing
                         average-energy games with lower-bounded energy to
                         infinite-state mean-payoff games and analyzing the
                         frequency of low-energy configurations, we~show an
                         almost tight doubly-exponential upper bound on the
                         necessary memory, and that the winner of
                         average-energy games with lower-bounded energy can
                         be determined in doubly-exponential time. We~also
                         prove EXPSPACE-hardness of this problem.\par
                         Finally, we~consider multi-dimensional extensions of
                         all types of average-energy games: without bounds,
                         with only a lower bound, and with both a lower and
                         an upper bound on the energy. We show that the
                         fully-bounded version is the only case to remain
                         decidable in multiple dimensions.},
}

Résumé

We introduce a new formalism called automata over a timed domain which provides an adequate framework for the determinization of timed systems. In this formalism, determinization w.r.t. timed language is always possible at the cost of changing the timed domain. We give a condition for determinizability of automata over a timed domain without changing the timed domain, which allows us to recover several known determinizable classes of timed systems, such as strongly-non-zeno timed automata, integer-reset timed automata, perturbed timed automata, etc. Moreover in the case of timed automata this condition encompasses most determinizability conditions from the literature.

@inproceedings{formats2017-BJM,
  author =              {Bouyer, Patricia and Jaziri, Samy and Markey,
                         Nicolas},
  title =               {On the determinization of timed systems},
  editor =              {Abate, Alessandro and Geeraerts, Gilles},
  booktitle =           {{P}roceedings of the 15th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'17)},
  acronym =             {{FORMATS}'17},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {10419},
  pages =               {25-41},
  year =                {2017},
  month =               sep,
  doi =                 {10.1007/978-3-319-65765-3_2},
  abstract =            {We introduce a new formalism called \emph{automata
                         over a timed domain} which provides an adequate
                         framework for the determinization of timed systems.
                         In~this formalism, determinization w.r.t. timed
                         language is always possible at the cost of changing
                         the timed domain. We~give a condition for
                         determinizability of automata over a timed domain
                         without changing the timed domain, which allows us
                         to recover several known determinizable classes of
                         timed systems, such as strongly-non-zeno timed
                         automata, integer-reset timed automata, perturbed
                         timed automata, etc. Moreover in the case of timed
                         automata this condition encompasses most
                         determinizability conditions from the literature.},
}

Résumé

Weighted timed automata have been defined in the early 2000's for modelling resource-consumption or -allocation problems in real-time systems. Optimal reachability is decidable in weighted timed automata, and a symbolic forward algorithm has been developed to solve that problem. This algorithm uses so-called priced zones, an extension of standard zones with cost functions. In order to ensure termination, the algorithm requires clocks to be bounded. For unpriced timed automata, much work has been done to develop sound abstractions adapted to the forward exploration of timed automata, ensuring termination of the model-checking algorithm without bounding the clocks. In this paper, we take advantage of recent developments on abstractions for timed automata, and propose an algorithm allowing for symbolic analysis of all weighted timed automata, without requiring bounded clocks.

@inproceedings{cav2016-BCM,
  author =              {Bouyer, Patricia and Colange, Maximilien and Markey,
                         Nicolas},
  title =               {Symbolic Optimal Reachability in Weighted Timed
                         Automata},
  editor =              {Chaudhuri, Swarat and Farzan, Azadeh},
  booktitle =           {{P}roceedings of the 28th {I}nternational
                         {C}onference on {C}omputer {A}ided {V}erification
                         ({CAV}'16)},
  acronym =             {{CAV}'16},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {9779},
  pages =               {513-530},
  year =                {2016},
  month =               jul,
  doi =                 {10.1007/978-3-319-41528-4_28},
  url =                 {http://arxiv.org/abs/1602.00481},
  abstract =            {Weighted timed automata have been defined in the
                         early 2000's for modelling resource-consumption or
                         -allocation problems in real-time systems. Optimal
                         reachability is decidable in weighted timed
                         automata, and a symbolic forward algorithm has been
                         developed to solve that problem. This algorithm uses
                         so-called priced zones, an extension of standard
                         zones with cost functions. In order to ensure
                         termination, the algorithm requires clocks to be
                         bounded. For unpriced timed automata, much work has
                         been done to develop sound abstractions adapted to
                         the forward exploration of timed automata, ensuring
                         termination of the model-checking algorithm without
                         bounding the clocks. In this paper, we take
                         advantage of recent developments on abstractions for
                         timed automata, and propose an algorithm allowing
                         for symbolic analysis of all weighted timed
                         automata, without requiring bounded clocks.},
}

Résumé

We study the almost-sure reachability problem in a distributed system obtained as the asynchronous composition of N copies (called processes) of the same automaton (called protocol), that can communicate via a shared register with finite domain. The automaton has two types of transitions: write-transitions update the value of the register, while read-transitions move to a new state depending on the content of the register. Non-determinism is resolved by a stochastic scheduler. Given a protocol, we focus on almost-sure reachability of a target state by one of the processes. The answer to this problem naturally depends on the number N of processes. However, we prove that our setting has a cut-off property : the answer to the almost-sure reachability problem is constant when N is large enough; we then develop an EXPSPACE algorithm deciding whether this constant answer is positive or negative.

@inproceedings{icalp2016-BMRSS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Randour,
                         Mickael and Sangnier, Arnaud and Stan, Daniel},
  title =               {Reachability in Networks of Register Protocols under
                         Stochastic Schedulers},
  editor =              {Chatzigiannakis, Ioannis and Mitzenmacher, Michael
                         and Rabani, Yuval and Sangiorgi, Davide},
  booktitle =           {{P}roceedings of the 43rd {I}nternational
                         {C}olloquium on {A}utomata, {L}anguages and
                         {P}rogramming ({ICALP}'16)~-- Part~{II}},
  acronym =             {{ICALP}'16},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {55},
  pages =               {106:1-106:14},
  year =                {2016},
  month =               jul,
  doi =                 {10.4230/LIPIcs.ICALP.2016.106},
  abstract =            {We study the almost-sure reachability problem in a
                         distributed system obtained as the asynchronous
                         composition of~\(N\) copies (called
                         \emph{processes}) of the same automaton (called
                         \emph{protocol}), that can communicate via a shared
                         register with finite domain. The automaton has two
                         types of transitions: write-transitions update the
                         value of the register, while read-transitions move
                         to a new state depending on the content of the
                         register. Non-determinism is resolved by a
                         stochastic scheduler. Given a protocol, we focus on
                         almost-sure reachability of a target state by one of
                         the processes. The answer to this problem naturally
                         depends on the number~\(N\) of processes. However,
                         we prove that our setting has a cut-off property :
                         the answer to the almost-sure reachability problem
                         is constant when \(N\) is large enough; we~then
                         develop an EXPSPACE algorithm deciding whether this
                         constant answer is positive or negative.},
}

Résumé

We study the existence of mixed-strategy equilibria in concurrent games played on graphs. While existence is guaranteed with safety objectives for each player, Nash equilibria need not exist when players are given arbitrary terminal-reward objectives, and their existence is undecidable with qualitative reachability objectives (and only three players). However, these results rely on the fact that the players can enforce infinite plays while trying to improve their payoffs. In this paper, we introduce a relaxed notion of equilibria, where deviations are imprecise. We prove that contrary to Nash equilibria, such (stationary) equilibria always exist, and we develop a PSPACE algorithm to compute one.

@inproceedings{gandalf2016-BMS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Stan,
                         Daniel},
  title =               {Stochastic Equilibria under Imprecise Deviations in
                         Terminal-Reward Concurrent Games},
  editor =              {Cantone, Domenico and Delzanno, Giorgio},
  booktitle =           {{P}roceedings of the 7th {I}nternational {S}ymposium
                         on {G}ames, {A}utomata, {L}ogics and {F}ormal
                         {V}erification ({GandALF}'16)},
  acronym =             {{GandALF}'16},
  series =              {Electronic Proceedings in Theoretical Computer
                         Science},
  volume =              {226},
  pages =               {61-75},
  year =                {2016},
  month =               sep,
  doi =                 {10.4204/EPTCS.226.5},
  abstract =            {We study the existence of mixed-strategy equilibria
                         in concurrent games played on graphs. While
                         existence is guaranteed with safety objectives for
                         each player, Nash equilibria need not exist when
                         players are given arbitrary terminal-reward
                         objectives, and their existence is undecidable with
                         qualitative reachability objectives (and~only three
                         players). However, these results rely on the fact
                         that the players can enforce infinite plays while
                         trying to improve their payoffs. In this paper, we
                         introduce a relaxed notion of equilibria, where
                         deviations are imprecise. We prove that contrary to
                         Nash equilibria, such (stationary) equilibria always
                         exist, and we develop a PSPACE algorithm to compute
                         one.},
}

Résumé

QCTL extends the temporal logic CTL with quantification over atomic propositions. While the algorithmic questions for QCTL and its fragments with limited quantification depth are well-understood (e.g. satisfiability of QCTLk, with at most k nested blocks of quantifiers, is k+1-EXPTIME-complete), very few results are known about the expressiveness of this logic. We address such expressiveness questions in this paper. We first consider the distinguishing power of these logics (i.e., their ability to separate models), their relationship with behavioural equivalences, and their ability to capture the behaviours of finite Kripke structures with so-called characteristic formulas. We then consider their expressive power (i.e., their ability to express a property), showing that in terms of expressiveness the hierarchy QCTLk collapses at level 2 (in other terms, any QCTL formula can be expressed using at most two nested blocks of quantifiers).

@inproceedings{concur2016-DLM,
  author =              {David, Am{\'e}lie and Laroussinie, Fran{\c c}ois and
                         Markey, Nicolas},
  title =               {On~the expressiveness of~{QCTL}},
  editor =              {Desharnais, Jules and Jagadeesan, Radha},
  booktitle =           {{P}roceedings of the 27th {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'16)},
  acronym =             {{CONCUR}'16},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {59},
  pages =               {28:1-28:15},
  year =                {2016},
  month =               aug,
  doi =                 {10.4230/LIPIcs.CONCUR.2016.28},
  abstract =            {QCTL extends the temporal logic CTL with
                         quantification over atomic propositions. While the
                         algorithmic questions for QCTL and its fragments
                         with limited quantification depth are
                         well-understood (e.g. satisfiability of
                         QCTL\textsuperscript{\(k\)}, with at most \(k\)
                         nested blocks of quantifiers, is
                         \(k+1\)-EXPTIME-complete), very few results are
                         known about the expressiveness of this logic.
                         We~address such expressiveness questions in this
                         paper. We first consider the \emph{distinguishing
                         power} of these logics (i.e.,~their ability to
                         separate models), their relationship with
                         behavioural equivalences, and their ability to
                         capture the behaviours of finite Kripke structures
                         with so-called characteristic formulas. We then
                         consider their \emph{expressive power} (i.e.,~their
                         ability to express a property), showing that in
                         terms of expressiveness the hierarchy
                         QCTL\textsuperscript{\(k\)} collapses at level~2
                         (in~other terms, any~QCTL formula can be expressed
                         using at most two nested blocks of quantifiers).},
}

Résumé

Switched systems are a convenient formalism for modeling physical processes interacting with a digital controller. Unfortunately, the formalism does not capture the distributed nature encountered e.g. in cyber-physical systems, which are organized as networks of elements interacting with each other and with local controllers. Most current methods for control synthesis can only produce a centralized controller, which is assumed to have complete knowledge of all the component states and can interact with all of them. In this paper, we consider a controller synthesis method based on state space decomposition, and propose a game-based approach in order to extend it within a distributed framework.

@inproceedings{syncop2015-FKM,
  author =              {Fribourg, Laurent and K{\"u}hne, Ulrich and Markey,
                         Nicolas},
  title =               {Game-based Synthesis of Distributed Controllers for
                         Sampled Switched Systems},
  editor =              {Andr{\'e}, {\'E}tienne and Frehse, Goran},
  booktitle =           {{P}roceedings of the 2nd {I}nternational {W}orkshop
                         on {S}ynthesis of {C}omplex {P}arameters
                         ({S}yn{C}o{P}'15)},
  acronym =             {{S}yn{C}o{P}'15},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {OpenAccess Series in Informatics},
  volume =              {44},
  pages =               {47-61},
  year =                {2016},
  month =               apr,
  doi =                 {10.4230/OASIcs.SynCoP.2015.48},
  abstract =            {Switched systems are a convenient formalism for
                         modeling physical processes interacting with a
                         digital controller. Unfortunately, the formalism
                         does not capture the distributed nature encountered
                         e.g. in cyber-physical systems, which are organized
                         as networks of elements interacting with each other
                         and with local controllers. Most current methods for
                         control synthesis can only produce a centralized
                         controller, which is assumed to have complete
                         knowledge of all the component states and can
                         interact with all of them. In~this paper,
                         we~consider a controller synthesis method based on
                         state space decomposition, and propose a game-based
                         approach in order to extend it within a distributed
                         framework.},
}

Résumé

We present a correct-by-design method of state-dependent control synthesis for linear discrete-time switching systems. Given an objective region R of the state space, the method builds a capture set S and a control which steers any element of S into R. The method works by iterated backward reachability from R. More precisely, S is given as a parametric extension of R, and the maximum value of the parameter is solved by linear programming. The method can also be used to synthesize a stability control which maintains indefinitely within R all the states starting at R. We explain how the synthesis method can be performed in a distributed manner. The method has been implemented and successfully applied to the synthesis of a distributed control of a concrete floor heating system with 11 rooms and 211 = 2048 switching modes.

@inproceedings{rp2016-LFMDC,
  author =              {Le{~}Co{\"e}nt, Adrien and Fribourg, Laurent and
                         Markey, Nicolas and De{~}Vuyst, Florian and Chamoin,
                         Ludovic},
  title =               {Distributed Synthesis of State-Dependent Switching
                         Control},
  editor =              {Larsen, Kim Guldstrand and Srba, Ji{\v r}{\'\i}},
  booktitle =           {{P}roceedings of the 10th {W}orkshop on
                         {R}eachability {P}roblems in {C}omputational
                         {M}odels ({RP}'16)},
  acronym =             {{RP}'16},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {9899},
  pages =               {119-133},
  year =                {2016},
  month =               sep,
  doi =                 {10.1007/978-3-319-45994-3_9},
  abstract =            {We present a correct-by-design method of
                         state-dependent control synthesis for linear
                         discrete-time switching systems. Given an objective
                         region~\(R\) of the state space, the method builds a
                         capture set~\(S\) and a control which steers any
                         element of~\(S\) into~\(R\). The method works by
                         iterated backward reachability from~\(R\). More
                         precisely, \(S\)~is given as a parametric extension
                         of~\(R\), and the maximum value of the parameter is
                         solved by linear programming. The method can also be
                         used to synthesize a stability control which
                         maintains indefinitely within~\(R\) all the states
                         starting at~\(R\). We~explain how the synthesis
                         method can be performed in a distributed manner. The
                         method has been implemented and successfully applied
                         to the synthesis of a distributed control of a
                         concrete floor heating system with 11 rooms and
                         \(2^{11} = 2048\) switching modes.},
}

Résumé

Parametric timed automata (PTA) are a powerful formalism to model and reason about concurrent systems with some unknown timing delays. In this paper, we address the (untimed) language- and trace-preservation problems: given a reference parameter valuation, does there exist another parameter valuation with the same untimed language (or trace)? We show that these problems are undecidable both for general PTA, and even for the restricted class of L/U-PTA. On the other hand, we exhibit decidable subclasses: 1-clock PTA, and 1-parameter deterministic L-PTA and U-PTA.

@inproceedings{formats2015-AM,
  author =              {Andr{\'e}, {\'E}tienne and Markey, Nicolas},
  title =               {Language Preservation Problems in Parametric Timed
                         Automata},
  editor =              {Sankaranarayanan, Sriram and Vicario, Enrico},
  booktitle =           {{P}roceedings of the 13th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'15)},
  acronym =             {{FORMATS}'15},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {9268},
  pages =               {27-43},
  year =                {2015},
  month =               sep,
  doi =                 {10.1007/978-3-319-22975-1_3},
  abstract =            {Parametric timed automata (PTA) are a powerful
                         formalism to model and reason about concurrent
                         systems with some unknown timing delays. In this
                         paper, we address the (untimed) language- and
                         trace-preservation problems: given a reference
                         parameter valuation, does there exist another
                         parameter valuation with the same untimed language
                         (or trace)? We show that these problems are
                         undecidable both for general PTA, and even for the
                         restricted class of L/U-PTA. On the other hand, we
                         exhibit decidable subclasses: 1-clock PTA, and
                         1-parameter deterministic L-PTA and U-PTA.},
}

Résumé

Timed automata are a convenient framework for modelling and reasoning about real-time systems. While these models are now very well-understood, they do not offer a convenient way of taking timing imprecisions into account. Several solutions (e.g. parametric guard enlargement) have recently been proposed over the last ten years to take such imprecisions into account. In this paper, we propose a new approach for handling robust reachability, based on permissive strategies. While classical strategies propose to play an action at an exact point in time, permissive strategies return an interval of possible dates when to play the selected action. With such a permissive strategy, we associate a penalty, which is the inverse of the length of the proposed interval, and accumulates along the run. We show that in that setting, optimal strategies can be computed in polynomial time for one-clock timed automata.

@inproceedings{avocs2015-BFM,
  author =              {Bouyer, Patricia and Fang, Erwin and Markey,
                         Nicolas},
  title =               {Permissive strategies in timed automata and games},
  editor =              {Grov, Gudmund and Ireland, Andrew},
  booktitle =           {{P}roceedings of the 15th {I}nternational {W}orkshop
                         on {A}utomated {V}erification of {C}ritical
                         {S}ystems ({AVOCS}'15)},
  acronym =             {{AVOCS}'15},
  publisher =           {European Association of Software Science and
                         Technology},
  series =              {Electronic Communications of the EASST},
  volume =              {72},
  year =                {2015},
  month =               sep,
  doi =                 {10.14279/tuj.eceasst.72.1015},
  abstract =            {Timed automata are a convenient framework for
                         modelling and reasoning about real-time systems.
                         While these models are now very well-understood,
                         they do not offer a convenient way of taking timing
                         imprecisions into account. Several solutions (e.g.
                         parametric guard enlargement) have recently been
                         proposed over the last ten years to take such
                         imprecisions into account. In this paper, we propose
                         a new approach for handling robust reachability,
                         based on permissive strategies. While classical
                         strategies propose to play an action at an exact
                         point in time, permissive strategies return an
                         interval of possible dates when to play the selected
                         action. With such a permissive strategy, we
                         associate a penalty, which is the inverse of the
                         length of the proposed interval, and accumulates
                         along the run. We show that in that setting, optimal
                         strategies can be computed in polynomial time for
                         one-clock timed automata.},
}

Résumé

Strategy Logic is a powerful specification language for expressing non-zero-sum properties of multi-player games. SL conveniently extends the logic ATL with explicit quantification and assignment of strategies. In this paper, we consider games over one-counter automata, and a quantitative extension 1cSL of SL with assertions over the value of the counter. We prove two results: we first show that, if decidable, model checking the so-called Boolean-goal fragment of 1cSL has non-elementary complexity; we actually prove the result for the Boolean-goal fragment of SL over finite-state games, which was an open question in (Mogavero et al. Reasoning about strategies: On the model-checking problem. 2014). As a first step towards proving decidability, we then show that the Boolean-goal fragment of 1cSL over one-counter games enjoys a nice periodicity property.

@inproceedings{fsttcs2015-BGM,
  author =              {Bouyer, Patricia and Gardy, Patrick and Markey,
                         Nicolas},
  title =               {Weighted strategy logic with boolean goals over
                         one-counter games},
  editor =              {Harsha, Prahladh and Ramalingam, G.},
  booktitle =           {{P}roceedings of the 35th {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'15)},
  acronym =             {{FSTTCS}'15},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {45},
  pages =               {69-83},
  year =                {2015},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2015.69},
  abstract =            {Strategy Logic is a powerful specification language
                         for expressing non-zero-sum properties of
                         multi-player games. SL conveniently extends the
                         logic ATL with explicit quantification and
                         assignment of strategies. In this paper, we consider
                         games over one-counter automata, and a quantitative
                         extension 1cSL of SL with assertions over the value
                         of the counter. We prove two results: we first show
                         that, if decidable, model checking the so-called
                         Boolean-goal fragment of 1cSL has non-elementary
                         complexity; we actually prove the result for the
                         Boolean-goal fragment of SL over finite-state games,
                         which was an open question in (Mogavero
                         \emph{et~al.} Reasoning about strategies: On the
                         model-checking problem. 2014). As a first step
                         towards proving decidability, we then show that the
                         Boolean-goal fragment of 1cSL over one-counter games
                         enjoys a nice periodicity property.},
}

Résumé

A weighted timed game is a timed game with extra quantitative information representing e.g. energy consumption. Optimizing the cost for reaching a target is a natural question, which has been investigated for ten years. Existence of optimal strategies is known to be undecidable in general, and only very restricted classes of games have been described for which optimal cost and almost-optimal strategies can be computed.

In this paper, we show that the value problem is undecidable in general weighted timed games. The undecidability proof relies on that for the existence of optimal strategies and on a diagonalization construction recently designed in the context of quantitative temporal logics. We then provide an algorithm to compute arbitrary approximations of the value in a game, and almost-optimal strategies. The algorithm applies in a large subclass of weighted timed games, and is the first approximation scheme which is designed in the current context.

@inproceedings{concur2015-BJM,
  author =              {Bouyer, Patricia and Jaziri, Samy and Markey,
                         Nicolas},
  title =               {On~the Value Problem in Weighted Timed Games},
  editor =              {Aceto, Luca and de Frutos{-}Escrig, David},
  booktitle =           {{P}roceedings of the 26th {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'15)},
  acronym =             {{CONCUR}'15},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {42},
  pages =               {311-324},
  year =                {2015},
  month =               sep,
  doi =                 {10.4230/LIPIcs.CONCUR.2015.311},
  abstract =            {A~weighted timed game is a timed game with extra
                         quantitative information representing e.g. energy
                         consumption. Optimizing the cost for reaching a
                         target is a natural question, which has been
                         investigated for ten years. Existence of optimal
                         strategies is known to be undecidable in general,
                         and only very restricted classes of games have been
                         described for which optimal cost and almost-optimal
                         strategies can be computed.\par In this paper, we
                         show that the value problem is undecidable in
                         general weighted timed games. The undecidability
                         proof relies on that for the existence of optimal
                         strategies and on a diagonalization construction
                         recently designed in the context of quantitative
                         temporal logics. We then provide an algorithm to
                         compute arbitrary approximations of the value in a
                         game, and almost-optimal strategies. The algorithm
                         applies in a large subclass of weighted timed games,
                         and is the first approximation scheme which is
                         designed in the current context.},
}

Résumé

The development of formal methods for control design is an important challenge with potential applications in a wide range of safety-critical cyber-physical systems. Focusing on switched dynamical systems, we propose a new abstraction, based on time-varying regions of invariance (the control funnels), that models behaviors of systems as timed automata. The main advantage of this method is that it allows automated verification of formal specifications and reactive controller synthesis without discretizing the evolution of the state of the system. Efficient constructions are possible in the case of linear dynamics. We demonstrate the potential of our approach with two examples.

@inproceedings{formats2015-BMPS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Perrin,
                         Nicolas and Schlehuber{-}Caissier, Philipp},
  title =               {Timed automata abstraction of switched dynamical
                         systems using control funnels},
  editor =              {Sankaranarayanan, Sriram and Vicario, Enrico},
  booktitle =           {{P}roceedings of the 13th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'15)},
  acronym =             {{FORMATS}'15},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {9268},
  pages =               {60-75},
  year =                {2015},
  month =               sep,
  doi =                 {10.1007/978-3-319-22975-1_5},
  abstract =            {The~development of formal methods for control design
                         is an important challenge with potential
                         applications in a wide range of safety-critical
                         cyber-physical systems. Focusing on switched
                         dynamical systems, we~propose a new abstraction,
                         based on time-varying regions of invariance
                         (the~\emph{control funnels}), that models behaviors
                         of systems as timed automata. The main advantage of
                         this method is that it allows automated verification
                         of formal specifications and reactive controller
                         synthesis without discretizing the evolution of the
                         state of the system. Efficient constructions are
                         possible in the case of linear dynamics.
                         We~demonstrate the potential of our approach with
                         two examples.},
}

Résumé

Two-player quantitative zero-sum games provide a natural framework to synthesize controllers with performance guarantees for reactive systems within an uncontrollable environment. Classical settings include mean-payoff games, where the objective is to optimize the long-run average gain per action, and energy games, where the system has to avoid running out of energy.

We study average-energy games, where the goal is to optimize the long-run average of the accumulated energy. We show that this objective arises naturally in several applications, and that it yields interesting connections with previous concepts in the literature. We prove that deciding the winner in such games is in NP∩coNP and at least as hard as solving mean-payoff games, and we establish that memoryless strategies suffice to win. We also consider the case where the system has to minimize the average-energy while maintaining the accumulated energy within predefined bounds at all times: this corresponds to operating with a finite-capacity storage for energy. We give results for one-player and two-player games, and establish complexity bounds and memory requirements.

@inproceedings{gandalf2015-BMRLL,
  author =              {Bouyer, Patricia and Markey, Nicolas and Randour,
                         Mickael and Larsen, Kim Guldstrand and Laursen,
                         Simon},
  title =               {Average-energy games},
  editor =              {Esparza, Javier and Tronci, Enrico},
  booktitle =           {{P}roceedings of the 6th {I}nternational {S}ymposium
                         on {G}ames, {A}utomata, {L}ogics and {F}ormal
                         {V}erification ({GandALF}'15)},
  acronym =             {{GandALF}'15},
  series =              {Electronic Proceedings in Theoretical Computer
                         Science},
  volume =              {193},
  pages =               {1-15},
  year =                {2015},
  month =               sep,
  doi =                 {10.4204/EPTCS.193.1},
  abstract =            {Two-player quantitative zero-sum games provide a
                         natural framework to synthesize controllers with
                         performance guarantees for reactive systems within
                         an uncontrollable environment. Classical settings
                         include mean-payoff games, where the objective is to
                         optimize the long-run average gain per action, and
                         energy games, where the system has to avoid running
                         out of energy.\par We study \emph{average-energy}
                         games, where the goal is to optimize the long-run
                         average of the accumulated energy. We show that this
                         objective arises naturally in several applications,
                         and that it yields interesting connections with
                         previous concepts in the literature. We prove that
                         deciding the winner in such games is in
                         \textsf{NP}{{\(\cap\)}}\textsf{coNP} and at least as
                         hard as solving mean-payoff games, and we establish
                         that memoryless strategies suffice to win. We also
                         consider the case where the system has to minimize
                         the average-energy while maintaining the accumulated
                         energy within predefined bounds at all times: this
                         corresponds to operating with a finite-capacity
                         storage for energy. We give results for one-player
                         and two-player games, and establish complexity
                         bounds and memory requirements.},
}

Résumé

Alternating-time temporal logic with strategy contexts (ATLsc) is a powerful formalism for expressing properties of multi-agent systems: it extends CTL with strategy quantifiers, offering a convenient way of expressing both collaboration and antagonism between several agents. Incomplete observation of the state space is a desirable feature in such a framework, but it quickly leads to undecidable verification problems. In this paper, we prove that uniform incomplete observation (where all players have the same observation) preserves decidability of the model checking problem, even for very expressive logics such as ATLsc.

@inproceedings{gandalf2015-LMS,
  author =              {Laroussinie, Fran{\c c}ois and Markey, Nicolas and
                         Sangnier, Arnaud},
  title =               {{{\(\textsf{ATL}_{\textsf{sc}}\)}} with partial
                         observation},
  editor =              {Esparza, Javier and Tronci, Enrico},
  booktitle =           {{P}roceedings of the 6th {I}nternational {S}ymposium
                         on {G}ames, {A}utomata, {L}ogics and {F}ormal
                         {V}erification ({GandALF}'15)},
  acronym =             {{GandALF}'15},
  series =              {Electronic Proceedings in Theoretical Computer
                         Science},
  volume =              {193},
  pages =               {43-57},
  year =                {2015},
  month =               sep,
  doi =                 {10.4204/EPTCS.193.4},
  abstract =            {Alternating-time temporal logic with strategy
                         contexts ({{\(\textsf{ATL}_{\textsf{sc}}\)}}) is a
                         powerful formalism for expressing properties of
                         multi-agent systems: it~extends \textsf{CTL} with
                         \emph{strategy quantifiers}, offering a convenient
                         way of expressing both collaboration and antagonism
                         between several agents. Incomplete observation of
                         the state space is a desirable feature in such a
                         framework, but it quickly leads to undecidable
                         verification problems. In this paper, we prove that
                         \emph{uniform} incomplete observation (where all
                         players have the same observation) preserves
                         decidability of the model checking problem, even for
                         very expressive logics such as
                         {{\(\textsf{ATL}_{\textsf{sc}}\)}}.},
}

Résumé

Extending formal verification techniques to handle quantitative aspects, both for the models and for the properties to be checked, has become a central research topic over the last twenty years. Following several recent works, we study model checking for (one-dimensional) weighted Kripke structures with positive and negative weights, and temporal logics constraining the total and/or average weight. We prove decidability when only accumulated weight is constrained, while allowing average-weight constraints alone already is undecidable.

@inproceedings{atva2014-BGM,
  author =              {Bouyer, Patricia and Gardy, Patrick and Markey,
                         Nicolas},
  title =               {Quantitative verification of weighted {K}ripke
                         structures},
  editor =              {Cassez, Franck and Raskin, Jean-Fran{\c c}ois},
  booktitle =           {{P}roceedings of the 12th {I}nternational
                         {S}ymposium on {A}utomated {T}echnology for
                         {V}erification and {A}nalysis ({ATVA}'14)},
  acronym =             {{ATVA}'14},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {8837},
  pages =               {64-80},
  year =                {2014},
  month =               nov,
  doi =                 {10.1007/978-3-319-11936-6_6},
  abstract =            {Extending formal verification techniques to handle
                         quantitative aspects, both for the models and for
                         the properties to be checked, has become a central
                         research topic over the last twenty years. Following
                         several recent works, we study model checking for
                         (one-dimensional) weighted Kripke structures with
                         positive and negative weights, and temporal logics
                         constraining the total and/or average weight. We
                         prove decidability when only accumulated weight is
                         constrained, while allowing average-weight
                         constraints alone already is undecidable.},
}

Résumé

For the accurate analysis of computerized systems, powerful quantitative formalisms have been designed, together with efficient verification algorithms. However, verification has mostly remained boolean—either a property is true, or it is false. We believe that this is too crude in a context where quantitative information and constraints are crucial: correctness should be quantified!

In a recent line of works, several authors have proposed quantitative semantics for temporal logics, using e.g. discounting modalities (which give less importance to distant events). In the present paper, we define and study a quantitative semantics of LTL with averaging modalities, either on the long run or within an until modality. This, in a way, relaxes the classical Boolean semantics of LTL, and provides a measure of certain properties of a model. We prove that computing and even approximating the value of a formula in this logic is undecidable.

@inproceedings{concur2014-BMM,
  author =              {Bouyer, Patricia and Markey, Nicolas and
                         Matteplackel, Raj~Mohan},
  title =               {Averaging in~{LTL}},
  editor =              {Baldan, Paolo and Gorla, Daniele},
  booktitle =           {{P}roceedings of the 25th {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'14)},
  acronym =             {{CONCUR}'14},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {8704},
  pages =               {266-280},
  year =                {2014},
  month =               sep,
  doi =                 {10.1007/978-3-662-44584-6_19},
  abstract =            {For the accurate analysis of computerized systems,
                         powerful quantitative formalisms have been designed,
                         together with efficient verification algorithms.
                         However, verification has mostly remained
                         boolean---either a property is~true, or it~is false.
                         We~believe that this is too crude in a context where
                         quantitative information and constraints are
                         crucial: correctness should be quantified!\par In a
                         recent line of works, several authors have proposed
                         quantitative semantics for temporal logics, using
                         e.g. \emph{discounting} modalities (which give less
                         importance to distant events). In~the present paper,
                         we define and study a quantitative semantics of~LTL
                         with \emph{averaging} modalities, either on the long
                         run or within an until modality. This, in a way,
                         relaxes the classical Boolean semantics of~LTL, and
                         provides a measure of certain properties of a model.
                         We~prove that computing and even approximating the
                         value of a formula in this logic is undecidable.},
}

Résumé

We study mixed-strategy Nash equilibria in multiplayer deterministic concurrent games played on graphs, with terminal-reward payoffs (that is, absorbing states with a value for each player). We show undecidability of the existence of a constrained Nash equilibrium (the constraint requiring that one player should have maximal payoff), with only three players and 0/1-rewards (i.e., reachability objectives). This has to be compared with the undecidability result by Ummels and Wojtczak for turn-based games which requires 14 players and general rewards. Our proof has various interesting consequences: (i) the undecidability of the existence of a Nash equilibrium with a constraint on the social welfare; (ii) the undecidability of the existence of an (unconstrained) Nash equilibrium in concurrent games with terminal-reward payoffs.

@inproceedings{fsttcs2014-BMS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Stan,
                         Daniel},
  title =               {Mixed {N}ash Equilibria in Concurrent Games},
  editor =              {Raman, Venkatesh and Suresh, S. P.},
  booktitle =           {{P}roceedings of the 34th {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'14)},
  acronym =             {{FSTTCS}'14},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {29},
  pages =               {351-363},
  year =                {2014},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2014.351},
  abstract =            {We study mixed-strategy Nash equilibria in
                         multiplayer deterministic concurrent games played on
                         graphs, with terminal-reward payoffs (that is,
                         absorbing states with a value for each player). We
                         show undecidability of the existence of a
                         constrained Nash equilibrium (the constraint
                         requiring that one player should have maximal
                         payoff), with only three players and 0/1-rewards
                         (i.e., reachability objectives). This has to be
                         compared with the undecidability result by Ummels
                         and Wojtczak for turn-based games which requires 14
                         players and general rewards. Our proof has various
                         interesting consequences: (i)~the~undecidability of
                         the existence of a Nash equilibrium with a
                         constraint on the social welfare;
                         (ii)~the~undecidability of the existence of an
                         (unconstrained) Nash equilibrium in concurrent games
                         with terminal-reward payoffs.},
}

Résumé

We investigate a model for representing large multiplayer games, which satisfy strong symmetry properties. This model is made of multiple copies of an arena; each player plays in his own arena, and can partially observe what the other players do. Therefore, this game has partial information and symmetry constraints, which make the computation of Nash equilibria difficult. We show several undecidability results, and for bounded-memory strategies, we precisely characterize the complexity of computing pure Nash equilibria (for qualitative objectives) in this game model.

@inproceedings{sr2014-BMV,
  author =              {Bouyer, Patricia and Markey, Nicolas and Vester,
                         Steen},
  title =               {Nash Equilibria in Symmetric Games with Partial
                         Observation},
  booktitle =           {{P}roceedings of the 2nd {I}nternational {W}orkshop
                         on {S}trategic {R}easoning ({SR}'14)},
  acronym =             {{SR}'14},
  series =              {Electronic Proceedings in Theoretical Computer
                         Science},
  volume =              {146},
  pages =               {49-55},
  year =                {2014},
  month =               mar,
  doi =                 {10.4204/EPTCS.146.7},
  abstract =            {We investigate a model for representing large
                         multiplayer games, which satisfy strong symmetry
                         properties. This model is made of multiple copies of
                         an arena; each player plays in his own arena, and
                         can partially observe what the other players do.
                         Therefore, this game has partial information and
                         symmetry constraints, which make the computation of
                         Nash equilibria difficult. We show several
                         undecidability results, and for bounded-memory
                         strategies, we precisely characterize the complexity
                         of computing pure Nash equilibria (for qualitative
                         objectives) in this game model.},
}

Résumé

The problem of synchronizing automata is concerned with the existence of a word that sends all states ofM the automaton to one and the same state. This problem has classically been studied for complete deterministic finite automata, with the existence problem being NLOGSPACE-complete.

In this paper we consider synchronizing-word problems for weighted and timed automata. We consider the synchronization problem in several variants and combinations of these, including deterministic and non-deterministic timed and weighted automata, synchronization to unique location with possibly different clock valuations or accumulated weights, as well as synchronization with a safety condition forbidding the automaton to visit states outside a safety-set during synchronization (e.g. energy constraints). For deterministic weighted automata, the synchronization problem is proven PSPACE-complete under energy constraints, and in 3-EXPSPACE under general safety constraints. For timed automata the synchronization problems are shown to be PSPACE-complete in the deterministic case, and undecidable in the non-deterministic case.

@inproceedings{fsttcs2014-DJLMS,
  author =              {Doyen, Laurent and Juhl, Line and Larsen, Kim
                         Guldstrand and Markey, Nicolas and Shirmohammadi,
                         Mahsa},
  title =               {Synchronizing words for weighted and timed automata},
  editor =              {Raman, Venkatesh and Suresh, S. P.},
  booktitle =           {{P}roceedings of the 34th {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'14)},
  acronym =             {{FSTTCS}'14},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {29},
  pages =               {121-132},
  year =                {2014},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2014.121},
  abstract =            {The problem of synchronizing automata is concerned
                         with the existence of a word that sends all states
                         ofM the automaton to one and the same state. This
                         problem has classically been studied for complete
                         deterministic finite automata, with the existence
                         problem being NLOGSPACE-complete.\par In this paper
                         we consider synchronizing-word problems for weighted
                         and timed automata. We consider the synchronization
                         problem in several variants and combinations of
                         these, including deterministic and non-deterministic
                         timed and weighted automata, synchronization to
                         unique location with possibly different clock
                         valuations or accumulated weights, as well as
                         synchronization with a safety condition forbidding
                         the automaton to visit states outside a safety-set
                         during synchronization (e.g. energy constraints).
                         For deterministic weighted automata, the
                         synchronization problem is proven PSPACE-complete
                         under energy constraints, and in 3-EXPSPACE under
                         general safety constraints. For timed automata the
                         synchronization problems are shown to be
                         PSPACE-complete in the deterministic case, and
                         undecidable in the non-deterministic case.},
}

Résumé

Symmetry reductions have been applied extensively for the verification of finite-state concurrent systems and hardware designs using model-checking of temporal logics such as LTL, CTL and CTL*, as well as real-time and probabilistic-system model-checking. In this paper we extend the technique to handle infinite-state games on graphs with finite branching where the objectives of the players can be very general. As particular applications, it is shown that the technique can be applied to reduce the state space in parity games as well as when doing model-checking of the temporal logic ATL*.

@inproceedings{atva2014-MV,
  author =              {Markey, Nicolas and Vester, Steen},
  title =               {Symmetry Reduction in Infinite Games with Finite
                         Branching},
  editor =              {Cassez, Franck and Raskin, Jean-Fran{\c c}ois},
  booktitle =           {{P}roceedings of the 12th {I}nternational
                         {S}ymposium on {A}utomated {T}echnology for
                         {V}erification and {A}nalysis ({ATVA}'14)},
  acronym =             {{ATVA}'14},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {8837},
  pages =               {281-296},
  year =                {2014},
  month =               nov,
  doi =                 {10.1007/978-3-319-11936-6_21},
  abstract =            {Symmetry reductions have been applied extensively
                         for the verification of finite-state concurrent
                         systems and hardware designs using model-checking of
                         temporal logics such as LTL, CTL and
                         CTL\textsuperscript{*}, as well as real-time and
                         probabilistic-system model-checking. In this paper
                         we extend the technique to handle infinite-state
                         games on graphs with finite branching where the
                         objectives of the players can be very general. As
                         particular applications, it is shown that the
                         technique can be applied to reduce the state space
                         in parity games as well as when doing model-checking
                         of the temporal logic ATL\textsuperscript{*}.},
}

Résumé

Formal methods (e.g. Timed Automata or Linear Hybrid Automata) can be used to analyse a real-time system by performing a reachability analysis on the model. The advantage of using formal methods is that they are more expressive than classical analytic models used in schedulability analysis. For example, it is possible to express state-dependent behaviour, arbitrary activation patterns, etc.

In this paper we use the formalism of Linear Hybrid Automata to encode a hierarchical scheduling system. In particular, we model a dynamic server algorithm and the tasks contained within, abstracting away the rest of the system, thus enabling component-based scheduling analysis. We prove the correctness of the model and the decidability of the reachability analysis for the case of periodic tasks. Then, we compare the results of our model against classical schedulability analysis techniques, showing that our analysis performs better than analytic methods in terms of resource utilisation. We further present two case studies: a component with state-dependent tasks, and a simplified model of a real avionics system. Finally, through extensive tests with various configurations, we demonstrate that this approach is usable for medium size components.

@inproceedings{rtcsa2014-SLSFM,
  author =              {Sun, Youcheng and Lipari, Giuseppe and Soulat,
                         Romain and Fribourg, Laurent and Markey, Nicolas},
  title =               {Component-Based Analysis of Hierarchical Scheduling
                         using Linear Hybrid Automata},
  booktitle =           {{P}roceedings of the 20th {I}nternational
                         {C}onference on {R}eal-{T}ime {C}omputing {S}ystems
                         and {A}pplications ({RTCSA}'14)},
  acronym =             {{RTCSA}'14},
  publisher =           {IEEE Comp. Soc. Press},
  year =                {2014},
  month =               aug,
  doi =                 {10.1109/RTCSA.2014.6910502},
  abstract =            {Formal methods (e.g. Timed Automata or Linear Hybrid
                         Automata) can be used to analyse a real-time system
                         by performing a reachability analysis on the model.
                         The advantage of using formal methods is that they
                         are more expressive than classical analytic models
                         used in schedulability analysis. For example, it is
                         possible to express state-dependent behaviour,
                         arbitrary activation patterns,~etc.\par In this
                         paper we use the formalism of Linear Hybrid Automata
                         to encode a hierarchical scheduling system. In
                         particular, we model a dynamic server algorithm and
                         the tasks contained within, abstracting away the
                         rest of the system, thus enabling component-based
                         scheduling analysis. We prove the correctness of the
                         model and the decidability of the reachability
                         analysis for the case of periodic tasks. Then, we
                         compare the results of our model against classical
                         schedulability analysis techniques, showing that our
                         analysis performs better than analytic methods in
                         terms of resource utilisation. We further present
                         two case studies: a~component with state-dependent
                         tasks, and a simplified model of a real avionics
                         system. Finally, through extensive tests with
                         various configurations, we demonstrate that this
                         approach is usable for medium size components.},
}

Résumé

Weighted timed automata extend timed automata with cost variables that can be used to model the evolution of various quantities. Although cost-optimal reachability is decidable (in polynomial space) on this model, it becomes undecidable on weighted timed games. This paper studies cost-optimal reachability problems on weighted timed automata and games under robust semantics. More precisely, we consider two perturbation game semantics that introduce imprecisions in the standard semantics, and bring robustness properties w.r.t. timing imprecisions to controllers. We give a polynomial-space algorithm for weighted timed automata, and prove the undecidability of cost-optimal reachability on weighted timed games, showing that the problem is robustly undecidable.

@inproceedings{formats2013-BMS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Sankur,
                         Ocan},
  title =               {Robust Weighted Timed Automata and Games},
  editor =              {Braberman, V{\'\i}ctor and Fribourg, Laurent},
  booktitle =           {{P}roceedings of the 11th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'13)},
  acronym =             {{FORMATS}'13},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {8053},
  pages =               {31-46},
  year =                {2013},
  month =               aug,
  doi =                 {10.1007/978-3-642-40229-6_3},
  abstract =            {Weighted timed automata extend timed automata with
                         cost variables that can be used to model the
                         evolution of various quantities. Although
                         cost-optimal reachability is decidable (in
                         polynomial space) on this model, it becomes
                         undecidable on weighted timed games. This paper
                         studies cost-optimal reachability problems on
                         weighted timed automata and games under robust
                         semantics. More precisely, we consider two
                         perturbation game semantics that introduce
                         imprecisions in the standard semantics, and bring
                         robustness properties w.r.t. timing imprecisions to
                         controllers. We give a polynomial-space algorithm
                         for weighted timed automata, and prove the
                         undecidability of cost-optimal reachability on
                         weighted timed games, showing that the problem is
                         robustly undecidable.},
}

Résumé

Various extensions of the temporal logic ATL have recently been introduced to express rich properties of multi-agent systems. Among these, ATLsc extends ATL with strategy contexts, while Strategy Logic has first-order quantification over strategies. There is a price to pay for the rich expressiveness of these logics: model-checking is non-elementary, and satisfiability is undecidable.

We prove in this paper that satisfiability is decidable in several special cases. The most important one is when restricting to turn-based games. We prove that decidability also holds for concurrent games if the number of moves available to the agents is bounded. Finally, we prove that restricting strategy quantification to memoryless strategies brings back undecidability.

@inproceedings{gandalf2013-LM,
  author =              {Laroussinie, Fran{\c c}ois and Markey, Nicolas},
  title =               {Satisfiability of {ATL} with strategy contexts},
  editor =              {Puppis, Gabriele and Villa, Tiziano},
  booktitle =           {{P}roceedings of the 4th {I}nternational {S}ymposium
                         on {G}ames, {A}utomata, {L}ogics and {F}ormal
                         {V}erification ({GandALF}'13)},
  acronym =             {{GandALF}'13},
  series =              {Electronic Proceedings in Theoretical Computer
                         Science},
  volume =              {119},
  pages =               {208-223},
  year =                {2013},
  month =               aug,
  doi =                 {10.4204/EPTCS.119.18},
  abstract =            {Various extensions of the temporal logic ATL have
                         recently been introduced to express rich properties
                         of multi-agent systems. Among these, ATLsc extends
                         ATL with \emph{strategy contexts}, while Strategy
                         Logic has \emph{first-order quantification} over
                         strategies. There is a price to pay for the rich
                         expressiveness of these logics: model-checking is
                         non-elementary, and satisfiability is
                         undecidable.\par We prove in this paper that
                         satisfiability is decidable in several special
                         cases. The most important one is when restricting to
                         \emph{turn-based} games. We~prove that decidability
                         also holds for concurrent games if the number of
                         moves available to the agents is bounded. Finally,
                         we~prove that restricting strategy quantification to
                         memoryless strategies brings back undecidability.},
}

Résumé

We consider the fundamental problem of Büchi acceptance in timed automata in a robust setting. The problem is formalised in terms of controller synthesis: timed automata are equipped with a parametrised game-based semantics that models the possible perturbations of the decisions taken by the controller. We characterise timed automata that are robustly controllable for some parameter, with a simple graph theoretic condition, by showing the equivalence with the existence of an aperiodic lasso that satisfies the winning condition (aperiodicity was defined and used earlier in different contexts to characterise convergence phenomena in timed automata). We then show decidability and PSPACE-completeness of our problem.

@inproceedings{concur2013-SBMR,
  author =              {Sankur, Ocan and Bouyer, Patricia and Markey,
                         Nicolas and Reynier, Pierre-Alain},
  title =               {Robust Controller Synthesis in Timed Automata},
  editor =              {D{'}Argenio, Pedro R. and Melgratt, Hern{\'a}n C.},
  booktitle =           {{P}roceedings of the 24th {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'13)},
  acronym =             {{CONCUR}'13},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {8052},
  pages =               {546-560},
  year =                {2013},
  month =               aug,
  doi =                 {10.1007/978-3-642-40184-8_38},
  abstract =            {We consider the fundamental problem of B{\"u}chi
                         acceptance in timed automata in a robust setting.
                         The problem is formalised in terms of controller
                         synthesis: timed automata are equipped with a
                         parametrised game-based semantics that models the
                         possible perturbations of the decisions taken by the
                         controller. We characterise timed automata that are
                         robustly controllable for some parameter, with a
                         simple graph theoretic condition, by showing the
                         equivalence with the existence of an aperiodic lasso
                         that satisfies the winning condition (aperiodicity
                         was defined and used earlier in different contexts
                         to characterise convergence phenomena in timed
                         automata). We then show decidability and
                         PSPACE-completeness of our problem.},
}

Résumé

We consider concurrent games played on graphs, in which each player has several qualitative (e.g. reachability or Büchi) objectives, and a preorder on these objectives (for instance the counting order, where the aim is to maximise the number of objectives that are fulfilled).

We study two fundamental problems in that setting: (1) the value problem, which aims at deciding the existence of a strategy that ensures a given payoff; (2) the Nash equilibrium problem, where we want to decide the existence of a Nash equilibrium (possibly with a condition on the payoffs). We characterise the exact complexities of these problems for several relevant preorders, and several kinds of objectives.

@inproceedings{fossacs2012-BBMU,
  author =              {Bouyer, Patricia and Brenguier, Romain and Markey,
                         Nicolas and Ummels, Michael},
  title =               {Concurrent games with ordered objectives},
  editor =              {Birkedal, Lars},
  booktitle =           {{P}roceedings of the 15th {I}nternational
                         {C}onference on {F}oundations of {S}oftware
                         {S}cience and {C}omputation {S}tructure
                         ({FoSSaCS}'12)},
  acronym =             {{FoSSaCS}'12},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {7213},
  pages =               {301-315},
  year =                {2012},
  month =               mar,
  doi =                 {10.1007/978-3-642-28729-9_20},
  abstract =            {We consider concurrent games played on graphs, in
                         which each player has several qualitative (e.g.
                         reachability or B{\"u}chi) objectives, and a
                         preorder on these objectives (for instance the
                         counting order, where the aim is to maximise the
                         number of objectives that are fulfilled).\par We
                         study two fundamental problems in that setting:
                         (1)~the \emph{value problem}, which aims at deciding
                         the existence of a strategy that ensures a given
                         payoff; (2)~the \emph{Nash equilibrium problem},
                         where we want to decide the existence of a Nash
                         equilibrium (possibly with a condition on the
                         payoffs). We characterise the exact complexities of
                         these problems for several relevant preorders, and
                         several kinds of objectives.},
}

Résumé

We investigate a number of problems related to infinite runs of weighted timed automata, subject to lower-bound constraints on the accumulated weight. Closing an open problem from [Bouyer et al., "Infinite runs in weighted timed automata with energy constraints", FORMATS'08], we show that the existence of an infinite lower-bound-constrained run is—for us somewhat unexpectedly—undecidable for weighted timed automata with four or more clocks.

This undecidability result assumes a fixed and know initial credit. We show that the related problem of existence of an initial credit for which there ex- ist a feasible run is decidable in PSPACE. We also investigate the variant of these problems where only bounded-duration runs are considered, showing that this restriction makes our original problem decidable in NEXPTIME. Finally, we prove that the universal versions of all those problems (i.e, checking that all the considered runs satisfy the lower-bound constraint) are decidable in PSPACE.

@inproceedings{qest2012-BLM,
  author =              {Bouyer, Patricia and Larsen, Kim Guldstrand and
                         Markey, Nicolas},
  title =               {Lower-Bound Constrained Runs in Weighted Timed
                         Automata},
  booktitle =           {{P}roceedings of the 9th {I}nternational
                         {C}onference on {Q}uantitative {E}valuation of
                         {S}ystems ({QEST}'12)},
  acronym =             {{QEST}'12},
  publisher =           {IEEE Comp. Soc. Press},
  pages =               {128-137},
  year =                {2012},
  month =               sep,
  doi =                 {10.1109/QEST.2012.28},
  abstract =            {We investigate a number of problems related to
                         infinite runs of weighted timed automata, subject to
                         lower-bound constraints on the accumulated weight.
                         Closing an open problem from [Bouyer
                         \textit{et~al.}, {"}Infinite runs in weighted timed
                         automata with energy constraints{"}, FORMATS'08], we
                         show that the existence of an infinite
                         lower-bound-constrained run is---for us somewhat
                         unexpectedly---undecidable for weighted timed
                         automata with four or more clocks.\par This
                         undecidability result assumes a fixed and know
                         initial credit. We show that the related problem of
                         existence of an initial credit for which there ex-
                         ist a feasible run is decidable in PSPACE. We also
                         investigate the variant of these problems where only
                         bounded-duration runs are considered, showing that
                         this restriction makes our original problem
                         decidable in NEXPTIME. Finally, we prove that the
                         universal versions of all those problems (i.e,
                         checking that all the considered runs satisfy the
                         lower-bound constraint) are decidable in PSPACE.},
}

Résumé

Reachability checking is one of the most basic problems in verification. By solving this problem, one synthesizes a strategy that dictates the actions to be performed for ensuring that the target location is reached. In this work, we are interested in synthesizing "robust" strategies for ensuring reachability of a location in a timed automaton; with "robust", we mean that it must still ensure reachability even when the delays are perturbed by the environment. We model this perturbed semantics as a game between the controller and its environment, and solve the parameterized robust reachability problem: we show that the existence of an upper bound on the perturbations under which there is a strategy reaching a target location is EXPTIME-complete.

@inproceedings{icalp2012-BMS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Sankur,
                         Ocan},
  title =               {Robust reachability in timed automata: a~game-based
                         approach},
  editor =              {Czumaj, Artur and Mehlhorn, Kurt and Pitts, Andrew
                         and Wattenhofer, Roger},
  booktitle =           {{P}roceedings of the 39th {I}nternational
                         {C}olloquium on {A}utomata, {L}anguages and
                         {P}rogramming ({ICALP}'12)~-- Part~{II}},
  acronym =             {{ICALP}'12},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {7392},
  pages =               {128-140},
  year =                {2012},
  month =               jul,
  doi =                 {10.1007/978-3-642-31585-5_15},
  abstract =            {Reachability checking is one of the most basic
                         problems in verification. By solving this problem,
                         one synthesizes a strategy that dictates the actions
                         to be performed for ensuring that the target
                         location is reached. In this work, we are interested
                         in synthesizing {"}robust{"} strategies for ensuring
                         reachability of a location in a timed automaton;
                         with {"}robust{"}, we mean that it must still ensure
                         reachability even when the delays are perturbed by
                         the environment. We model this perturbed semantics
                         as a game between the controller and its
                         environment, and solve the parameterized robust
                         reachability problem: we show that the existence of
                         an upper bound on the perturbations under which
                         there is a strategy reaching a target location is
                         EXPTIME-complete.},
}

Résumé

While it was defined long ago, the extension of CTL with quantification over atomic propositions has never been studied extensively. Considering two different semantics (depending whether propositional quantification refers to the Kripke structure or to its unwinding tree), we study its expressiveness (showing in particular that QCTL coincides with Monadic Second-Order Logic for both semantics) and characterize the complexity of its model-checking problem, depending on the number of nested propositional quantifiers (showing that the structure semantics populates the polynomial hierarchy while the tree semantics populates the exponential hierarchy). We also show how these results apply to model checking ATL-like temporal logics for games.

@inproceedings{concur2012-DLM,
  author =              {Da{~}Costa, Arnaud and Laroussinie, Fran{\c c}ois
                         and Markey, Nicolas},
  title =               {Quantified~{CTL}: Expressiveness and Model Checking},
  editor =              {Koutny, Maciej and Ulidowski, Irek},
  booktitle =           {{P}roceedings of the 23rd {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'12)},
  acronym =             {{CONCUR}'12},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {7454},
  pages =               {177-192},
  year =                {2012},
  month =               sep,
  doi =                 {10.1007/978-3-642-32940-1_14},
  abstract =            {While it was defined long ago, the extension of CTL
                         with quantification over atomic propositions has
                         never been studied extensively. Considering two
                         different semantics (depending whether propositional
                         quantification refers to the Kripke structure or to
                         its unwinding tree), we study its expressiveness
                         (showing in particular that QCTL coincides with
                         Monadic Second-Order Logic for both semantics) and
                         characterize the complexity of its model-checking
                         problem, depending on the number of nested
                         propositional quantifiers (showing that the
                         structure semantics populates the polynomial
                         hierarchy while the tree semantics populates the
                         exponential hierarchy). We also show how these
                         results apply to model checking ATL-like temporal
                         logics for games.},
}

Résumé

We study the problem of the existence (and computation) of Nash equilibria in multi-player concurrent games with Büchi-definable objectives. First, when the objectives are Büchi conditions on the game, we prove that the existence problem can be solved in polynomial time. In a second part, we extend our technique to objectives defined by deterministic Büchi automata, and prove that the problem then becomes EXPTIME-complete. We prove PSPACE-completeness for the case where the Büchi automata are 1-weak.

@inproceedings{fsttcs2011-BBMU,
  author =              {Bouyer, Patricia and Brenguier, Romain and Markey,
                         Nicolas and Ummels, Michael},
  title =               {{N}ash Equilibria in Concurrent Games with
                         {B}{\"u}chi Objectives},
  editor =              {Chakraborty, Supratik and Kumar, Amit},
  booktitle =           {{P}roceedings of the 31st {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'11)},
  acronym =             {{FSTTCS}'11},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {13},
  pages =               {375-386},
  year =                {2011},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2011.375},
  abstract =            {We study the problem of the existence (and
                         computation) of Nash equilibria in multi-player
                         concurrent games with B{\"u}chi-definable
                         objectives. First, when the objectives are B{\"u}chi
                         conditions on the game, we prove that the existence
                         problem can be solved in polynomial time. In a
                         second part, we extend our technique to objectives
                         defined by deterministic B{\"u}chi automata, and
                         prove that the problem then becomes
                         EXPTIME-complete. We prove PSPACE-completeness for
                         the case where the B{\"u}chi automata are 1-weak.},
}

Résumé

Timed automata follow a mathematical semantics, which assumes perfect precision and synchrony of clocks. Since this hypothesis does not hold in digital systems, properties proven formally on a timed automaton may be lost at implementation. In order to ensure implementability, several approaches have been considered, corresponding to different hypotheses on the implementation platform. We address two of these: a timed automaton is samplable if its semantics is preserved under a discretization of time; it is robust if its semantics is preserved when all timing constraints are relaxed by some small positive parameter. We propose a construction which makes timed automata implementable in the above sense: From any timed automaton A, we build a timed automaton A' that exhibits the same behaviour as A, and moreover is both robust and samplable by construction.

@inproceedings{concur2011-BLMST,
  author =              {Bouyer, Patricia and Larsen, Kim Guldstrand and
                         Markey, Nicolas and Sankur, Ocan and Thrane, Claus},
  title =               {Timed automata can always be made implementable},
  editor =              {Katoen, Joost-Pieter and K{\"o}nig, Barbara},
  booktitle =           {{P}roceedings of the 22nd {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'11)},
  acronym =             {{CONCUR}'11},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {6901},
  pages =               {76-91},
  year =                {2011},
  month =               sep,
  doi =                 {10.1007/978-3-642-23217-6_6},
  abstract =            {Timed automata follow a mathematical semantics,
                         which assumes perfect precision and synchrony of
                         clocks. Since this hypothesis does not hold in
                         digital systems, properties proven formally on a
                         timed automaton may be lost at implementation. In
                         order to ensure implementability, several approaches
                         have been considered, corresponding to different
                         hypotheses on the implementation platform. We
                         address two of these: a~timed automaton is samplable
                         if its semantics is preserved under a discretization
                         of time; it is robust if its semantics is preserved
                         when all timing constraints are relaxed by some
                         small positive parameter. We propose a construction
                         which makes timed automata implementable in the
                         above sense: From any timed
                         automaton~\(\mathcal{A}\), we build a timed
                         automaton~\(\mathcal{A}'\) that exhibits the same
                         behaviour as~\(\mathcal{A}\), and moreover is both
                         robust and samplable by construction.},
}

Résumé

We study nondeterministic strategies in parity games with the aim of computing a most permissive winning strategy. Following earlier work, we measure permissiveness in terms of the average number/weight of transitions blocked by a strategy. Using a translation into mean-payoff parity games, we prove that deciding (the permissiveness of) a most permissive winning strategy is in NP∩coNP. Along the way, we provide a new study of mean-payoff parity games. In particular, we give a new algorithm for solving these games, which beats all previously known algorithms for this problem.

@inproceedings{atva2011-BMOU,
  author =              {Bouyer, Patricia and Markey, Nicolas and Olschewski,
                         J{\"o}rg and Ummels, Michael},
  title =               {Measuring Permissiveness in Parity Games:
                         Mean-Payoff Parity Games Revisited},
  editor =              {Bultan, Tevfik and Hsiung, Pao-Ann},
  booktitle =           {{P}roceedings of the 9th {I}nternational {S}ymposium
                         on {A}utomated {T}echnology for {V}erification and
                         {A}nalysis ({ATVA}'11)},
  acronym =             {{ATVA}'11},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {6996},
  pages =               {135-149},
  year =                {2011},
  month =               oct,
  doi =                 {10.1007/978-3-642-24372-1_11},
  abstract =            {We study nondeterministic strategies in parity games
                         with the aim of computing a most permissive winning
                         strategy. Following earlier work, we measure
                         permissiveness in terms of the average
                         number{\slash}weight of transitions blocked by a
                         strategy. Using a translation into mean-payoff
                         parity games, we prove that deciding (the
                         permissiveness~of) a~most permissive winning
                         strategy is in \(\textsf{NP}\cap\textsf{coNP}\).
                         Along the way, we~provide a new study of mean-payoff
                         parity games. In particular, we give a new algorithm
                         for solving these games, which beats all previously
                         known algorithms for this problem.},
}

Résumé

Timed automata are governed by a mathematical semantics which assumes perfectly continuous and precise clocks. This requirement is not satised by digital hardware on which the models are implemented. In fact, it was shown that the presence of imprecisions, however small they may be, may yield extra behaviours. Therefore correctness proven on the formal model does not imply correctness of the real system.

The problem of robust model-checking was then dened to circumvent this inconsistency. It consists in computing a bound on the imprecision under which the system will be correct.

In this work, we show that robust model-checking against ω-regular properties for timed automata can be reduced to standard model-checking of timed automata, by computing an adequate bound on the imprecision. This yields a new algorithm for robust model-checking of ω-regular properties, which is both optimal and valid for general timed automata.

@inproceedings{formats2011-BMS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Sankur,
                         Ocan},
  title =               {Robust Model-Checking of Timed Automata via Pumping
                         in Channel Machines},
  editor =              {Fahrenberg, Uli and Tripakis, Stavros},
  booktitle =           {{P}roceedings of the 9th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'11)},
  acronym =             {{FORMATS}'11},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {6919},
  pages =               {97-112},
  year =                {2011},
  month =               sep,
  doi =                 {10.1007/978-3-642-24310-3_8},
  abstract =            {Timed automata are governed by a mathematical
                         semantics which assumes perfectly continuous and
                         precise clocks. This requirement is not satised by
                         digital hardware on which the models are
                         implemented. In~fact, it~was shown that the presence
                         of imprecisions, however small they may be, may
                         yield extra behaviours. Therefore correctness proven
                         on the formal model does not imply correctness of
                         the real system.\par The problem of robust
                         model-checking was then dened to circumvent this
                         inconsistency. It consists in computing a bound on
                         the imprecision under which the system will be
                         correct.\par In this work, we show that robust
                         model-checking against \(\omega\)-regular properties
                         for timed automata can be reduced to standard
                         model-checking of timed automata, by computing an
                         adequate bound on the imprecision. This yields a new
                         algorithm for robust model-checking of
                         \(\omega\)-regular properties, which is both optimal
                         and valid for general timed automata.},
}

Résumé

We define and study a new approach to the implementability of timed automata, where the semantics is perturbed by imprecisions and finite frequency of the hardware. In order to circumvent these effects, we introduce parametric shrinking of clock constraints, which corresponds to tightening the guards. We propose symbolic procedures to decide the existence of (and then compute) parameters under which the shrunk version of a given timed automaton is non-blocking and can time-abstract simulate the exact semantics. We then define an implementation semantics for timed automata with a digital clock and positive reaction times, and show that for shrinkable timed automata both properties are preserved in implementation.

@inproceedings{fsttcs2011-SBM,
  author =              {Sankur, Ocan and Bouyer, Patricia and Markey,
                         Nicolas},
  title =               {Shrinking Timed Automata},
  editor =              {Chakraborty, Supratik and Kumar, Amit},
  booktitle =           {{P}roceedings of the 31st {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'11)},
  acronym =             {{FSTTCS}'11},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {13},
  pages =               {90-102},
  year =                {2011},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2011.90},
  abstract =            {We define and study a new approach to the
                         implementability of timed automata, where the
                         semantics is perturbed by imprecisions and finite
                         frequency of the hardware. In order to circumvent
                         these effects, we introduce \emph{parametric
                         shrinking} of clock constraints, which corresponds
                         to tightening the guards. We propose symbolic
                         procedures to decide the existence of (and then
                         compute) parameters under which the shrunk version
                         of a given timed automaton is non-blocking and can
                         time-abstract simulate the exact semantics. We then
                         define an implementation semantics for timed
                         automata with a digital clock and positive reaction
                         times, and show that for shrinkable timed automata
                         both properties are preserved in implementation.},
}

Résumé

We propose a procedure for computing Nash equilibria in multi-player timed games with reachability objectives. Our procedure is based on the construction of a finite concurrent game, and on a generic characterization of Nash equilibria in (possibly infinite) concurrent games. Along the way, we use our characterization to compute Nash equilibria in finite concurrent games.

@inproceedings{concur2010-BBM,
  author =              {Bouyer, Patricia and Brenguier, Romain and Markey,
                         Nicolas},
  title =               {{N}ash Equilibria for Reachability Objectives in
                         Multi-player Timed Games},
  editor =              {Gastin, Paul and Laroussinie, Fran{\c c}ois},
  booktitle =           {{P}roceedings of the 21st {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'10)},
  acronym =             {{CONCUR}'10},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {6269},
  pages =               {192-206},
  year =                {2010},
  month =               sep,
  doi =                 {10.1007/978-3-642-15375-4_14},
  abstract =            {We propose a procedure for computing Nash equilibria
                         in multi-player timed games with reachability
                         objectives. Our procedure is based on the
                         construction of a finite concurrent game, and on a
                         generic characterization of Nash equilibria in
                         (possibly infinite) concurrent games. Along the way,
                         we~use our characterization to compute Nash
                         equilibria in finite concurrent games.},
}

Résumé

We study two-player timed games where the objectives of the two players are not opposite. We focus on the standard notion of Nash equilibrium and propose a series of transformations that builds two finite turn-based games out of a timed game, with a precise correspondence between Nash equilibria in the original and in final games. This provides us with an algorithm to compute Nash equilibria in two-player timed games for large classes of properties.

@inproceedings{formats2010-BBM,
  author =              {Bouyer, Patricia and Brenguier, Romain and Markey,
                         Nicolas},
  title =               {Computing Equilibria in Two-Player Timed Games
                         {\textit{via}}~Turn-Based Finite Games},
  editor =              {Chatterjee, Krishnendu and Henzinger, Thomas A.},
  booktitle =           {{P}roceedings of the 8th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'10)},
  acronym =             {{FORMATS}'10},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {6246},
  pages =               {62-76},
  year =                {2010},
  month =               sep,
  doi =                 {10.1007/978-3-642-15297-9_7},
  abstract =            {We study two-player timed games where the objectives
                         of the two players are not opposite. We focus on the
                         standard notion of Nash equilibrium and propose a
                         series of transformations that builds two finite
                         turn-based games out of a timed game, with a precise
                         correspondence between Nash equilibria in the
                         original and in final games. This provides us with
                         an algorithm to compute Nash equilibria in
                         two-player timed games for large classes of
                         properties.},
}

Résumé

In this paper, we study one-clock priced timed automata in which prices can grow linearly (dp/dt=k) or exponentially (dp/dt=kp), with discontinuous updates on edges. We propose EXPTIME algorithms to decide the existence of controllers that ensure existence of infinite runs or reachability of some goal location with non-negative observer value all along the run. These algorithms consist in computing the optimal delays that should be elapsed in each location along a run, so that the final observer value is maximized (and never goes below zero).

@inproceedings{hscc2010-BFLM,
  author =              {Bouyer, Patricia and Fahrenberg, Uli and Larsen, Kim
                         Guldstrand and Markey, Nicolas},
  title =               {Timed Automata with Observers under Energy
                         Constraints},
  editor =              {Johansson, Karl Henrik and Yi, Wang},
  booktitle =           {{P}roceedings of the 13th {I}nternational {W}orkshop
                         on {H}ybrid {S}ystems: {C}omputation and {C}ontrol
                         ({HSCC}'10)},
  acronym =             {{HSCC}'10},
  publisher =           {ACM Press},
  pages =               {61-70},
  year =                {2010},
  month =               apr,
  doi =                 {10.1145/1755952.1755963},
  abstract =            {In this paper, we study one-clock priced timed
                         automata in which prices can grow linearly
                         (\(\frac{dp}{dt}=k\)) or exponentially
                         (\(\frac{dp}{dt}=kp\)), with discontinuous updates
                         on edges. We propose EXPTIME algorithms to decide
                         the existence of controllers that ensure existence
                         of infinite runs or reachability of some goal
                         location with non-negative observer value all along
                         the run. These algorithms consist in computing the
                         optimal delays that should be elapsed in each
                         location along a run, so that the final observer
                         value is maximized (and never goes below zero).},
}

Résumé

We study the alternating-time temporal logics ATL and ATL* extended with strategy contexts: these make agents commit to their strategies during the evaluation of formulas, contrary to plain ATL and ATL* where strategy quantifiers reset previously selected strategies.

We illustrate the important expressive power of strategy contexts by proving that they make the extended logics, namely ATLsc and ATLsc*, equally expressive: any formula in ATLsc* can be translated into an equivalent, linear-size ATLsc formula. Despite the high expressiveness of these logics, we prove that they remain decidable by designing a tree-automata-based algorithm for model-checking ATLsc on the full class of n-player concurrent game structures.

@inproceedings{fsttcs2010-DLM,
  author =              {Da{~}Costa, Arnaud and Laroussinie, Fran{\c c}ois
                         and Markey, Nicolas},
  title =               {{ATL} with strategy contexts: Expressiveness and
                         Model Checking},
  editor =              {Lodaya, Kamal and Mahajan, Meena},
  booktitle =           {{P}roceedings of the 30th {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'10)},
  acronym =             {{FSTTCS}'10},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {8},
  pages =               {120-132},
  year =                {2010},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2010.120},
  abstract =            {We study the alternating-time temporal logics
                         \(\textsf{ATL}\) and~\(\textsf{ATL}^{*}\) extended
                         with strategy contexts: these make agents commit to
                         their strategies during the evaluation of formulas,
                         contrary to plain \(\textsf{ATL}\)
                         and~\(\textsf{ATL}^{*}\) where strategy quantifiers
                         reset previously selected strategies.\par We
                         illustrate the important expressive power of
                         strategy contexts by proving that they make the
                         extended logics, namely
                         \(\textsf{ATL}_{\textsf{sc}}\)
                         and~\(\textsf{ATL}_{\textsf{sc}}^{*}\), equally
                         expressive: any~formula
                         in~\(\textsf{ATL}_{\textsf{sc}}^{*}\) can be
                         translated into an equivalent, linear-size
                         \(\textsf{ATL}_{\textsf{sc}}\) formula. Despite the
                         high expressiveness of these logics, we prove that
                         they remain decidable by designing a
                         tree-automata-based algorithm for model-checking
                         \(\textsf{ATL}_{\textsf{sc}}\) on the full class of
                         \(n\)-player concurrent game structures.},
}

Résumé

A fundamental problem in numerical computation and computational geometry is to determine the sign of arithmetic expressions in radicals. Here we consider the simpler problem of deciding whether ∑i=1m Ci . AiXi is zero for given rational numbers Ai, Ci, Xi. It has been known for almost twenty years that this can be decided in polynomial time. In this paper we improve this result by showing membership in uniform TC0. This requires several significant departures from Blömer's polynomial-time algorithm as the latter crucially relies on primitives, such as gcd computation and binary search, that are not known to be in TC0.

@inproceedings{fsttcs2010-HBMOW,
  author =              {Hunter, Paul and Bouyer, Patricia and Markey,
                         Nicolas and Ouaknine, Jo{\"e}l and Worrell, James},
  title =               {Computing Rational Radical Sums in Uniform
                         {TC\textsuperscript{0}}},
  editor =              {Lodaya, Kamal and Mahajan, Meena},
  booktitle =           {{P}roceedings of the 30th {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'10)},
  acronym =             {{FSTTCS}'10},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {8},
  pages =               {308-316},
  year =                {2010},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2010.308},
  abstract =            {A~fundamental problem in numerical computation and
                         computational geometry is to determine the sign of
                         arithmetic expressions in radicals. Here we consider
                         the simpler problem of deciding whether
                         \(\sum_{i=1}^m C_i \cdot A_i^{X_i}\) is zero for
                         given rational numbers~\(A_i\), \(C_i\),~\(X_i\).
                         It~has been known for almost twenty years that this
                         can be decided in polynomial time. In this paper we
                         improve this result by showing membership in uniform
                         \(\textsf{TC}^0\). This requires several significant
                         departures from Bl{\"o}mer's polynomial-time
                         algorithm as the latter crucially relies on
                         primitives, such as gcd computation and binary
                         search, that are not known to be
                         in~\(\textsf{TC}^0\).},
}

Résumé

We extend the alternating-time temporal logics ATL and ATL* with strategy contexts and memory constraints: the first extension make strategy quantifiers to not "forget" the strategies being executed by the other players. The second extension allows strategy quantifiers to restrict to memoryless or bounded-memory strategies.

We first consider expressiveness issues. We show that our logics can express important properties such as equilibria, and we formally compare them with other similar formalisms (ATL, ATL*, Game Logic, Strategy Logic, ...). We then address the problem of model-checking for our logics, providing a PSPACE algoritm for the sublogics involving only memoryless strategies and an EXPSPACE algorithm for the bounded-memory case.

@inproceedings{lfcs2009-BDLM,
  author =              {Brihaye, {\relax Th}omas and Da{~}Costa, Arnaud and
                         Laroussinie, Fran{\c c}ois and Markey, Nicolas},
  title =               {{ATL} with Strategy Contexts and Bounded Memory},
  editor =              {Artemov, Sergei N. and Nerode, Anil},
  booktitle =           {{P}roceedings of the {I}nternational {S}ymposium
                         {L}ogical {F}oundations of {C}omputer {S}cience
                         ({LFCS}'09)},
  acronym =             {{LFCS}'09},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {5407},
  pages =               {92-106},
  year =                {2009},
  month =               jan,
  doi =                 {10.1007/978-3-540-92687-0_7},
  abstract =            {We extend the alternating-time temporal logics ATL
                         and ATL\textsuperscript{*} with \emph{strategy
                         contexts} and \emph{memory constraints}: the first
                         extension make strategy quantifiers to not
                         {"}forget{"} the strategies being executed by the
                         other players. The second extension allows strategy
                         quantifiers to restrict to memoryless or
                         bounded-memory strategies.\par We first consider
                         expressiveness issues. We show that our logics can
                         express important properties such as equilibria, and
                         we formally compare them with other similar
                         formalisms (ATL, ATL\textsuperscript{*}, Game Logic,
                         Strategy Logic,~...). We~then address the problem of
                         model-checking for our logics, providing a PSPACE
                         algoritm for the sublogics involving only memoryless
                         strategies and an EXPSPACE algorithm for the
                         bounded-memory case.},
}

Résumé

In this paper, we extend the classical notion of strategies in turn-based finite games by allowing several moves to be selected. We define and study a quantitative measure for permissivity of such strategies by assigning penalties when blocking transitions. We prove that for reachability objectives, most permissive strategies exist, can be chosen memoryless, and can be computed in polynomial time, while it is in NP∩coNP for discounted and mean penalties.

@inproceedings{concur2009-BDMR,
  author =              {Bouyer, Patricia and Duflot, Marie and Markey,
                         Nicolas and Renault, Gabriel},
  title =               {Measuring Permissivity in Finite Games},
  editor =              {Bravetti, Mario and Zavattaro, Gianluigi},
  booktitle =           {{P}roceedings of the 20th {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'09)},
  acronym =             {{CONCUR}'09},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {5710},
  pages =               {196-210},
  year =                {2009},
  month =               sep,
  doi =                 {10.1007/978-3-642-04081-8_14},
  abstract =            {In this paper, we extend the classical notion of
                         strategies in turn-based finite games by allowing
                         several moves to be selected. We~define and study a
                         quantitative measure for permissivity of such
                         strategies by assigning penalties when blocking
                         transitions. We~prove that for reachability
                         objectives, most permissive strategies exist, can be
                         chosen memoryless, and can be computed in polynomial
                         time, while it is in
                         \(\textsf{NP}\cap\textsf{coNP}\) for discounted and
                         mean penalties.},
}

Résumé

In [Baier et al., Probabilistic and Topological Semantics for Timed Automata, FSTTCS'07] a probabilistic semantics for timed automata has been defined in order to rule out unlikely (sequences of) events. The qualitative model-checking problem for LTL properties has been investigated, where the aim is to check whether a given LTL property holds with probability 1 in a timed automaton, and solved for the class of single-clock timed automata.

In this paper, we consider the quantitative model-checking problem for ω-regular properties: we aim at computing the exact probability that a given timed automaton satisfies an ω-regular property. We develop a framework in which we can compute a closed-form expression for this probability; we furthermore give an approximation algorithm, and finally prove that we can decide the threshold problem in that framework.

@inproceedings{qest2008-BBBM,
  author =              {Bertrand, Nathalie and Bouyer, Patricia and Brihaye,
                         {\relax Th}omas and Markey, Nicolas},
  title =               {Quantitative Model-Checking of One-Clock Timed
                         Automata under Probabilistic Semantics},
  booktitle =           {{P}roceedings of the 5th {I}nternational
                         {C}onference on {Q}uantitative {E}valuation of
                         {S}ystems ({QEST}'08)},
  acronym =             {{QEST}'08},
  publisher =           {IEEE Comp. Soc. Press},
  pages =               {55-64},
  year =                {2008},
  month =               sep,
  doi =                 {10.1109/QEST.2008.19},
  abstract =            {In [Baier \emph{et~al.}, \textit{Probabilistic and
                         Topological Semantics for Timed Automata},
                         FSTTCS'07] a probabilistic semantics for timed
                         automata has been defined in order to rule out
                         unlikely (sequences of) events. The qualitative
                         model-checking problem for LTL properties has been
                         investigated, where the aim is to check whether a
                         given LTL property holds with probability~\(1\) in a
                         timed automaton, and solved for the class of
                         single-clock timed automata.\par In this paper, we
                         consider the quantitative model-checking problem for
                         \(\omega\)-regular properties: we aim at computing
                         the exact probability that a given timed automaton
                         satisfies an \(\omega\)-regular property. We develop
                         a framework in which we can compute a closed-form
                         expression for this probability; we furthermore give
                         an approximation algorithm, and finally prove that
                         we can decide the threshold problem in that
                         framework.},
}

Résumé

We study the problems of existence and construction of infinite schedules for finite weighted automata and one-clock weighted timed automata, subject to boundary constraints on the accumulated weight. More specifically, we consider automata equipped with positive and negative weights on transitions and locations, corresponding to the production and consumption of some resource (e.g. energy). We ask the question whether there exists an infinite path for which the accumulated weight for any finite prefix satisfies certain constraints (e.g. remains between 0 and some given upper-bound). We also consider a game version of the above, where certain transitions may be uncontrollable.

@inproceedings{formats2008-BFLMS,
  author =              {Bouyer, Patricia and Fahrenberg, Uli and Larsen, Kim
                         Guldstrand and Markey, Nicolas and Srba, Ji{\v
                         r}{\'\i}},
  title =               {Infinite Runs in Weighted Timed Automata with Energy
                         Constraints},
  editor =              {Cassez, Franck and Jard, Claude},
  booktitle =           {{P}roceedings of the 6th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'08)},
  acronym =             {{FORMATS}'08},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {5215},
  pages =               {33-47},
  year =                {2008},
  month =               sep,
  doi =                 {10.1007/978-3-540-85778-5_4},
  abstract =            {We~study the problems of existence and construction
                         of infinite schedules for finite weighted automata
                         and one-clock weighted timed automata, subject to
                         boundary constraints on the accumulated weight. More
                         specifically, we~consider automata equipped with
                         positive and negative weights on transitions and
                         locations, corresponding to the production and
                         consumption of some resource (\emph{e.g.}~energy).
                         We~ask the question whether there exists an infinite
                         path for which the accumulated weight for any finite
                         prefix satisfies certain constraints
                         (\emph{e.g.}~remains between~\(0\) and some given
                         upper-bound). We~also consider a game version of the
                         above, where certain transitions may be
                         uncontrollable.},
}

Résumé

We focus on the problem of finding (the size of) a minimal winning coalition in a multi-player game. More precisely, we prove that deciding whether there is a winning coalition of size at most k is NP-complete, while deciding whether k is the optimal size is DP-complete. We also study different variants of our original problem: the function problem, where the aim is to effectively compute the coalition; more succinct encoding of the game; and richer families of winning objectives.

@inproceedings{time2008-BGMR,
  author =              {Brihaye, {\relax Th}omas and Ghannem, Mohamed and
                         Markey, Nicolas and Rieg, Lionel},
  title =               {Good friends are hard to find!},
  booktitle =           {{P}roceedings of the 15th {I}nternational
                         {S}ymposium on {T}emporal {R}epresentation and
                         {R}easoning ({TIME}'08)},
  acronym =             {{TIME}'08},
  publisher =           {IEEE Comp. Soc. Press},
  pages =               {32-40},
  year =                {2008},
  month =               jun,
  doi =                 {10.1109/TIME.2008.10},
  abstract =            {We focus on the problem of finding (the~size of)
                         a~minimal winning coalition in a multi-player game.
                         More precisely, we~prove that deciding whether there
                         is a winning coalition of size at most~\(k\) is
                         NP-complete, while deciding whether \(k\) is the
                         optimal size is DP-complete. We~also study different
                         variants of our original problem: the function
                         problem, where the aim is to effectively compute the
                         coalition; more succinct encoding of the game; and
                         richer families of winning objectives.},
}

Résumé

A channel machine consists of a finite controller together with several fifo channels; the controller can read messages from the head of a channel and write messages to the tail of a channel. In this paper, we focus on channel machines with insertion errors, i.e., machines in whose channels messages can spontaneously appear. Such devices have been previously introduced in the study of Metric Temporal Logic. We consider the termination problem: are all the computations of a given insertion channel machine finite? We show that this problem has non-elementary, yet primitive recursive complexity.

@inproceedings{stacs2008-BMOSW,
  author =              {Bouyer, Patricia and Markey, Nicolas and Ouaknine,
                         Jo{\"e}l and Schnoebelen, {\relax Ph}ilippe and
                         Worrell, James},
  title =               {On Termination for Faulty Channel Machines},
  editor =              {Albers, Susanne and Weil, Pascal},
  booktitle =           {{P}roceedings of the 25th {S}ymposium on
                         {T}heoretical {A}spects of {C}omputer {S}cience
                         ({STACS}'08)},
  acronym =             {{STACS}'08},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {1},
  pages =               {121-132},
  year =                {2008},
  month =               feb,
  doi =                 {10.4230/LIPIcs.STACS.2008.1339},
  abstract =            {A channel machine consists of a finite controller
                         together with several fifo channels; the controller
                         can read messages from the head of a channel and
                         write messages to the tail of a channel. In this
                         paper, we focus on channel machines with
                         \emph{insertion errors}, \textit{i.e.}, machines in
                         whose channels messages can spontaneously appear.
                         Such devices have been previously introduced in the
                         study of Metric Temporal Logic. We~consider the
                         termination problem: are all the computations of a
                         given insertion channel machine finite? We~show that
                         this problem has non-elementary, yet primitive
                         recursive complexity.},
}

Résumé

Metric Interval Temporal Logic (MITL) is a popular formalism for expressing real-time specifications. This logic achieves decidability by restricting the precision of timing constraints, in particular, by banning so-called punctual specifications. In this paper we introduce a significantly more expressive logic that can express a wide variety of punctual specifications, but whose model-checking problem has the same complexity as that of MITL. We conclude that for model checking the most commonly occurring specifications, such as invariance and bounded response, punctuality can be accommodated at no cost.

@inproceedings{icalp2008-BMOW,
  author =              {Bouyer, Patricia and Markey, Nicolas and Ouaknine,
                         Jo{\"e}l and Worrell, James},
  title =               {On Expressiveness and Complexity in Real-time Model
                         Checking},
  editor =              {Aceto, Luca and Damg{\aa}rd, Ivan and Goldberg,
                         Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and
                         Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor},
  booktitle =           {{P}roceedings of the 35th {I}nternational
                         {C}olloquium on {A}utomata, {L}anguages and
                         {P}rogramming ({ICALP}'08)~-- Part~{II}},
  acronym =             {{ICALP}'08},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {5126},
  pages =               {124-135},
  year =                {2008},
  month =               jul,
  doi =                 {10.1007/978-3-540-70583-3_11},
  abstract =            {Metric Interval Temporal Logic (MITL) is a popular
                         formalism for expressing real-time specifications.
                         This logic achieves decidability by restricting the
                         precision of timing constraints, in particular, by
                         banning so-called \emph{punctual} specifications.
                         In~this paper we~introduce a significantly more
                         expressive logic that can express a wide variety of
                         punctual specifications, but whose model-checking
                         problem has the same complexity as that of~MITL.
                         We~conclude that for model checking the most
                         commonly occurring specifications, such as
                         invariance and bounded response, punctuality can be
                         accommodated at no cost.},
}

Résumé

Whereas formal verification of timed systems has become a very active field of research, the idealised mathematical semantics of timed automata cannot be faithfully implemented. Several works have thus focused on a modified semantics of timed automata which ensures implementability, and robust model-checking algorithms for safety, and later LTL properties have been designed. Recently, a new approach has been proposed, which reduces (standard) model-checking of timed automata to other verification problems on channel machines. Thanks to a new encoding of the modified semantics as a network of timed systems, we propose an original combination of both approaches, and prove that robust model-checking for coFlat-MTL, a large fragment of MTL, is EXPSPACE-Complete.

@inproceedings{fossacs2008-BMR,
  author =              {Bouyer, Patricia and Markey, Nicolas and Reynier,
                         Pierre-Alain},
  title =               {Robust Analysis of Timed Automata via Channel
                         Machines},
  editor =              {Amadio, Roberto},
  booktitle =           {{P}roceedings of the 11th {I}nternational
                         {C}onference on {F}oundations of {S}oftware
                         {S}cience and {C}omputation {S}tructure
                         ({FoSSaCS}'08)},
  acronym =             {{FoSSaCS}'08},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {4962},
  pages =               {157-171},
  year =                {2008},
  month =               mar,
  doi =                 {10.1007/978-3-540-78499-9_12},
  abstract =            {Whereas formal verification of timed systems has
                         become a very active field of research, the
                         idealised mathematical semantics of timed automata
                         cannot be faithfully implemented. Several works have
                         thus focused on a modified semantics of timed
                         automata which ensures implementability, and robust
                         model-checking algorithms for safety, and later LTL
                         properties have been designed. Recently, a~new
                         approach has been proposed, which reduces (standard)
                         model-checking of timed automata to other
                         verification problems on channel machines. Thanks to
                         a new encoding of the modified semantics as a
                         network of timed systems, we propose an original
                         combination of both approaches, and prove that
                         robust model-checking for coFlat-MTL, a large
                         fragment of~MTL, is EXPSPACE-Complete.},
}

Résumé

We consider the model of priced (a.k.a. weighted) timed automata, an extension of timed automata with cost information on both locations and transitions. We prove that model-checking this class of models against the logic WCTL, CTL with cost-constrained modalities, is PSPACE-complete under the "single-clock" assumption. In contrast, it has been recently proved that the model-checking problem is undecidable for this model as soon as the system has three clocks. We also prove that the model-checking of WCTL becomes undecidable, even under this "single-clock" assumption.

@inproceedings{fossacs2007-BLM,
  author =              {Bouyer, Patricia and Larsen, Kim Guldstrand and
                         Markey, Nicolas},
  title =               {Model Checking One-clock Priced Timed Automata},
  editor =              {Seidl, Helmut},
  booktitle =           {{P}roceedings of the 10th {I}nternational
                         {C}onference on {F}oundations of {S}oftware
                         {S}cience and {C}omputation {S}tructure
                         ({FoSSaCS}'07)},
  acronym =             {{FoSSaCS}'07},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {4423},
  pages =               {108-122},
  year =                {2007},
  month =               mar,
  doi =                 {10.1007/978-3-540-71389-0_9},
  abstract =            {We consider the model of priced (a.k.a.~weighted)
                         timed automata, an extension of timed automata with
                         cost information on both locations and transitions.
                         We prove that model-checking this class of models
                         against the logic~WCTL, CTL~with cost-constrained
                         modalities, is PSPACE-complete under the
                         {"}single-clock{"} assumption. In~contrast, it~has
                         been recently proved that the model-checking problem
                         is undecidable for this model as soon as the system
                         has three clocks. We also prove that the
                         model-checking of~WCTL becomes undecidable, even
                         under this {"}single-clock{"} assumption.},
}

Résumé

We propose a new model for timed games, based on concurrent game structures (CGSs). Compared to the classical timed game automata of Asarin et al., our timed CGSs are "more concurrent", in the sense that they always allow all the agents to act on the system, independently of the delay they want to elapse before their action. Timed CGSs weaken the "element of surprise" of timed game automata reported by de Alfaro et al.

We prove that our model has nice properties, in particular that model-checking timed CGSs against timed ATL is decidable via region abstraction, and in particular that strategies are "region-stable" if winning objectives are. We also propose a new extension of TATL, containing ATL*, which we call TALTL. We prove that model-checking this logic remains decidable on timed CGSs. Last, we explain how our algorithms can be adapted in order to rule out Zeno (co-)strategies, based on the ideas of Henzinger et al.

@inproceedings{concur2007-BLMO,
  author =              {Brihaye, {\relax Th}omas and Laroussinie, Fran{\c
                         c}ois and Markey, Nicolas and Oreiby, Ghassan},
  title =               {Timed Concurrent Game Structures},
  editor =              {Caires, Lu{\'\i}s and Vasconcelos, Vasco T.},
  booktitle =           {{P}roceedings of the 18th {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'07)},
  acronym =             {{CONCUR}'07},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {4703},
  pages =               {445-459},
  year =                {2007},
  month =               sep,
  doi =                 {10.1007/978-3-540-74407-8_30},
  abstract =            {We propose a new model for timed games, based on
                         concurrent game structures~(CGSs). Compared to the
                         classical \emph{timed game automata} of~Asarin
                         \emph{et~al.}, our timed~CGSs are {"}more
                         concurrent{"}, in the sense that they always allow
                         all the agents to act on the system, independently
                         of the delay they want to elapse before their
                         action. Timed CGSs weaken the {"}element of
                         surprise{"} of timed game automata reported by
                         de~Alfaro \emph{et~al.}\par We prove that our model
                         has nice properties, in particular that
                         model-checking timed CGSs against timed
                         \(\textsf{ATL}\) is decidable \emph{via} region
                         abstraction, and in particular that strategies are
                         {"}region-stable{"} if winning objectives are. We
                         also propose a new extension of \(\textsf{TATL}\),
                         containing~\(\textsf{ATL}^{*}\), which we
                         call~\(\textsf{TALTL}\). We~prove that
                         model-checking this logic remains decidable on timed
                         CGSs. Last, we explain how our algorithms can be
                         adapted in order to rule out Zeno (co-)strategies,
                         based on the ideas of Henzinger \emph{et~al.}},
}

Résumé

We study the model-checking problem for WMTL, a cost-extension of the linear-time timed temporal logic MTL, that is interpreted over weighted timed automata. We draw a complete picture of the decidability for that problem: it is decidable only for the class of one-clock weighted timed automata with a restricted stopwatch cost, and any slight extension of this model leads to undecidability. We finally give some consequences on the undecidability of linear hybrid automata.

@inproceedings{formats2007-BM,
  author =              {Bouyer, Patricia and Markey, Nicolas},
  title =               {Costs are Expensive!},
  editor =              {Raskin, Jean-Fran{\c c}ois and Thiagarajan, P. S.},
  booktitle =           {{P}roceedings of the 5th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'07)},
  acronym =             {{FORMATS}'07},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {4763},
  pages =               {53-68},
  year =                {2007},
  month =               oct,
  doi =                 {10.1007/978-3-540-75454-1_6},
  abstract =            {We study the model-checking problem for WMTL,
                         a~cost-extension of the linear-time timed temporal
                         logic MTL, that is interpreted over weighted timed
                         automata. We~draw a complete picture of the
                         decidability for that problem: it~is decidable only
                         for the class of one-clock weighted timed automata
                         with a restricted stopwatch cost, and any slight
                         extension of this model leads to undecidability.
                         We~finally give some consequences on the
                         undecidability of linear hybrid automata.},
}