Author name cluster

Laurent Doyen 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

MFCS Conference 2011 Conference Paper

Energy and Mean-Payoff Parity Markov Decision Processes

Krishnendu Chatterjee
Laurent Doyen 0001

Abstract We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω -regular specifications, while the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition requires that the resource level never drops below 0, and the mean-payoff condition requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i. e. , winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean-payoff parity MDPs, the problem is solvable in polynomial time.

Details

MFCS Conference 2011 Conference Paper

Infinite Synchronizing Words for Probabilistic Automata

Laurent Doyen 0001
Thierry Massart
Mahsa Shirmohammadi

Abstract Probabilistic automata are finite-state automata where the transitions are chosen according to fixed probability distributions. We consider a semantics where on an input word the automaton produces a sequence of probability distributions over states. An infinite word is accepted if the produced sequence is synchronizing, i. e. the sequence of the highest probability in the distributions tends to 1. We show that this semantics generalizes the classical notion of synchronizing words for deterministic automata. We consider the emptiness problem, which asks whether some word is accepted by a given probabilistic automaton, and the universality problem, which asks whether all words are accepted. We provide reductions to establish the PSPACE-completeness of the two problems.

Details

CSL Conference 2010 Conference Paper

Energy and Mean-Payoff Games with Imperfect Information

Aldric Degorre
Laurent Doyen 0001
Raffaella Gentilini
Jean-François Raskin
Szymon Torunczyk

Abstract We consider two-player games with imperfect information and quantitative objective. The game is played on a weighted graph with a state space partitioned into classes of indistinguishable states, giving players partial knowledge of the state. In an energy game, the weights represent resource consumption and the objective of the game is to maintain the sum of weights always nonnegative. In a mean-payoff game, the objective is to optimize the limit-average usage of the resource. We show that the problem of determining if an energy game with imperfect information with fixed initial credit has a winning strategy is decidable, while the question of the existence of some initial credit such that the game has a winning strategy is undecidable. This undecidability result carries over to mean-payoff games with imperfect information. On the positive side, using a simple restriction on the game graph (namely, that the weights are visible), we show that these problems become EXPTIME-complete.

Details

MFCS Conference 2010 Conference Paper

Qualitative Analysis of Partially-Observable Markov Decision Processes

Krishnendu Chatterjee
Laurent Doyen 0001
Thomas A. Henzinger

Abstract We study observation-based strategies for partially-observable Markov decision processes ( POMDP s) with parity objectives. An observation-based strategy relies on partial information about the history of a play, namely, on the past sequence of observations. We consider qualitative analysis problems: given a POMDP with a parity objective, decide whether there exists an observation-based strategy to achieve the objective with probability 1 (almost-sure winning), or with positive probability (positive winning). Our main results are twofold. First, we present a complete picture of the computational complexity of the qualitative analysis problem for POMDP s with parity objectives and its subclasses: safety, reachability, Büchi, and coBüchi objectives. We establish several upper and lower bounds that were not known in the literature. Second, we give optimal bounds (matching upper and lower bounds) for the memory required by pure and randomized observation-based strategies for each class of objectives.

Details

MFCS Conference 2010 Conference Paper

Randomness for Free

Krishnendu Chatterjee
Laurent Doyen 0001
Hugo Gimbert
Thomas A. Henzinger

Abstract We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (players interact simultaneously); and (b) turn-based (players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. We present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function (probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games.

Details

CSL Conference 2008 Conference Paper

Quantitative Languages

Krishnendu Chatterjee
Laurent Doyen 0001
Thomas A. Henzinger

Abstract Quantitative generalizations of classical languages, which assign to each word a real number instead of a boolean value, have applications in modeling resource-constrained computation. We use weighted automata (finite automata with transition weights) to define several natural classes of quantitative languages over finite and infinite words; in particular, the real value of an infinite run is computed as the maximum, limsup, liminf, limit average, or discounted sum of the transition weights. We define the classical decision problems of automata theory (emptiness, universality, language inclusion, and language equivalence) in the quantitative setting and study their computational complexity. As the decidability of language inclusion remains open for some classes of weighted automata, we introduce a notion of quantitative simulation that is decidable and implies language inclusion. We also give a complete characterization of the expressive power of the various classes of weighted automata. In particular, we show that most classes of weighted automata cannot be determinized.

Details

CSL Conference 2006 Conference Paper

Algorithms for Omega-Regular Games with Imperfect Information,

Krishnendu Chatterjee
Laurent Doyen 0001
Thomas A. Henzinger
Jean-François Raskin

Abstract We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Büchi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.

Details