TY - GEN
AB - The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running
in time O(d · n^{2d}·MeanGame) to compute the set of almost-sure winning states from which the objective
can be ensured with probability 1, where n is the number of states of the game, d the number of priorities
of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states
in 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems
with both functional requirement (given as a qualitative objective) and performance requirement (given
as a quantitative objective).
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Gimbert, Hugo
AU - Oualhadj, Youssouf
ID - 5405
SN - 2664-1690
TI - Perfect-information stochastic mean-payoff parity games
ER -
TY - GEN
AB - We consider the distributed synthesis problem fortemporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTLand our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3)Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
AU - Pavlogiannis, Andreas
ID - 5406
SN - 2664-1690
TI - Distributed synthesis for LTL Fragments
ER -
TY - GEN
AB - This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the mandatory features, which need to be fulfilled to provide an institutional repository as a platform and also a service to the scientists at the institute. It also includes optional features, which would be of strong benefit for the scientists and would increase the usage of the repository, and hence the visibility of research at IST Austria.
AU - Porsche, Jana
ID - 5407
TI - Technical requirements and features
ER -
TY - GEN
AB - We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are
EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Nain, Sumit
AU - Vardi, Moshe
ID - 5408
SN - 2664-1690
TI - The complexity of partial-observation stochastic parity games with finite-memory strategies
ER -
TY - GEN
AB - The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition.
In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in timestamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than delta away from the parameter, for delta>0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and we show analogous decidability results for rectangular automata.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Majumdar, Rupak
ID - 5409
SN - 2664-1690
TI - Edit distance for timed automata
ER -