---
_id: '5405'
abstract:
- lang: eng
text: "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\r\nin time O(d ·
n^{2d}·MeanGame) to compute the set of almost-sure winning states from which the
objective\r\ncan be ensured with probability 1, where n is the number of states
of the game, d the number of priorities\r\nof the parity objective, and MeanGame
is the complexity to compute the set of almost-sure winning states\r\nin 2-1/2-player
mean-payoff games. Our results are useful in the synthesis of stochastic reactive
systems\r\nwith both functional requirement (given as a qualitative objective)
and performance requirement (given\r\nas a quantitative objective)."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Hugo
full_name: Gimbert, Hugo
last_name: Gimbert
- first_name: Youssouf
full_name: Oualhadj, Youssouf
last_name: Oualhadj
citation:
ama: Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. Perfect-Information Stochastic
Mean-Payoff Parity Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-128-v1-1
apa: Chatterjee, K., Doyen, L., Gimbert, H., & Oualhadj, Y. (2013). Perfect-information
stochastic mean-payoff parity games. IST Austria. https://doi.org/10.15479/AT:IST-2013-128-v1-1
chicago: Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj.
Perfect-Information Stochastic Mean-Payoff Parity Games. IST Austria, 2013.
https://doi.org/10.15479/AT:IST-2013-128-v1-1.
ieee: K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, Perfect-information
stochastic mean-payoff parity games. IST Austria, 2013.
ista: Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2013. Perfect-information stochastic
mean-payoff parity games, IST Austria, 22p.
mla: Chatterjee, Krishnendu, et al. Perfect-Information Stochastic Mean-Payoff
Parity Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-128-v1-1.
short: K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, Perfect-Information Stochastic
Mean-Payoff Parity Games, IST Austria, 2013.
date_created: 2018-12-12T11:39:09Z
date_published: 2013-07-08T00:00:00Z
date_updated: 2023-02-23T10:33:08Z
day: '08'
ddc:
- '000'
- '005'
- '510'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-128-v1-1
file:
- access_level: open_access
checksum: ede787a10e74e4f7db302fab8f12f3ca
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:54Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5516'
file_name: IST-2013-128-v1+1_full_stoch_mpp.pdf
file_size: 387467
relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '22'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '128'
related_material:
record:
- id: '2212'
relation: later_version
status: public
status: public
title: Perfect-information stochastic mean-payoff parity games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5406'
abstract:
- lang: eng
text: '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.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed Synthesis
for LTL Fragments. IST Austria; 2013. doi:10.15479/AT:IST-2013-130-v1-1
apa: Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013).
Distributed synthesis for LTL Fragments. IST Austria. https://doi.org/10.15479/AT:IST-2013-130-v1-1
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis.
Distributed Synthesis for LTL Fragments. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-130-v1-1.
ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, Distributed
synthesis for LTL Fragments. IST Austria, 2013.
ista: Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis
for LTL Fragments, IST Austria, 11p.
mla: Chatterjee, Krishnendu, et al. Distributed Synthesis for LTL Fragments.
IST Austria, 2013, doi:10.15479/AT:IST-2013-130-v1-1.
short: K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, Distributed Synthesis
for LTL Fragments, IST Austria, 2013.
date_created: 2018-12-12T11:39:09Z
date_published: 2013-07-08T00:00:00Z
date_updated: 2023-02-21T17:01:26Z
day: '08'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2013-130-v1-1
file:
- access_level: open_access
checksum: 855513ebaf6f72228800c5fdb522f93c
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:18Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5540'
file_name: IST-2013-130-v1+1_Distributed_Synthesis.pdf
file_size: 467895
relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '11'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '130'
related_material:
record:
- id: '1376'
relation: later_version
status: public
status: public
title: Distributed synthesis for LTL Fragments
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5408'
abstract:
- lang: eng
text: "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 \r\nEXPTIME-complete;
and also establish optimal (exponential) memory bounds for finite-memory strategies
required for qualitative analysis. "
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Sumit
full_name: Nain, Sumit
last_name: Nain
- first_name: Moshe
full_name: Vardi, Moshe
last_name: Vardi
citation:
ama: Chatterjee K, Doyen L, Nain S, Vardi M. The Complexity of Partial-Observation
Stochastic Parity Games with Finite-Memory Strategies. IST Austria; 2013.
doi:10.15479/AT:IST-2013-141-v1-1
apa: Chatterjee, K., Doyen, L., Nain, S., & Vardi, M. (2013). The complexity
of partial-observation stochastic parity games with finite-memory strategies.
IST Austria. https://doi.org/10.15479/AT:IST-2013-141-v1-1
chicago: Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. The
Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies.
IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-141-v1-1.
ieee: K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, The complexity of partial-observation
stochastic parity games with finite-memory strategies. IST Austria, 2013.
ista: Chatterjee K, Doyen L, Nain S, Vardi M. 2013. The complexity of partial-observation
stochastic parity games with finite-memory strategies, IST Austria, 17p.
mla: Chatterjee, Krishnendu, et al. The Complexity of Partial-Observation Stochastic
Parity Games with Finite-Memory Strategies. IST Austria, 2013, doi:10.15479/AT:IST-2013-141-v1-1.
short: K. Chatterjee, L. Doyen, S. Nain, M. Vardi, The Complexity of Partial-Observation
Stochastic Parity Games with Finite-Memory Strategies, IST Austria, 2013.
date_created: 2018-12-12T11:39:10Z
date_published: 2013-09-12T00:00:00Z
date_updated: 2023-02-23T10:33:11Z
day: '12'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-141-v1-1
file:
- access_level: open_access
checksum: 226bc791124f8d3138379778ce834e86
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:16Z
date_updated: 2020-07-14T12:46:46Z
file_id: '5477'
file_name: IST-2013-141-v1+1_main-tech-rpt.pdf
file_size: 300481
relation: main_file
file_date_updated: 2020-07-14T12:46:46Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '17'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '141'
related_material:
record:
- id: '2213'
relation: later_version
status: public
status: public
title: The complexity of partial-observation stochastic parity games with finite-memory
strategies
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5409'
abstract:
- lang: eng
text: "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. \r\nIn 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."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Rupak
full_name: Majumdar, Rupak
last_name: Majumdar
citation:
ama: Chatterjee K, Ibsen-Jensen R, Majumdar R. Edit Distance for Timed Automata.
IST Austria; 2013. doi:10.15479/AT:IST-2013-144-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Majumdar, R. (2013). Edit distance
for timed automata. IST Austria. https://doi.org/10.15479/AT:IST-2013-144-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Rupak Majumdar. Edit
Distance for Timed Automata. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-144-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, Edit distance for timed
automata. IST Austria, 2013.
ista: Chatterjee K, Ibsen-Jensen R, Majumdar R. 2013. Edit distance for timed automata,
IST Austria, 12p.
mla: Chatterjee, Krishnendu, et al. Edit Distance for Timed Automata. IST
Austria, 2013, doi:10.15479/AT:IST-2013-144-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, Edit Distance for Timed Automata,
IST Austria, 2013.
date_created: 2018-12-12T11:39:10Z
date_published: 2013-10-30T00:00:00Z
date_updated: 2023-02-23T10:33:18Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-144-v1-1
file:
- access_level: open_access
checksum: 0f7633081ba8299c543322f0ad08571f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:08Z
date_updated: 2020-07-14T12:46:46Z
file_id: '5469'
file_name: IST-2013-144-v1+1_main.pdf
file_size: 336377
relation: main_file
file_date_updated: 2020-07-14T12:46:46Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: '12'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '144'
related_material:
record:
- id: '2216'
relation: later_version
status: public
status: public
title: Edit distance for timed automata
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5410'
abstract:
- lang: eng
text: "Board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only
in development of mathematical and logical skills, but also in emotional and social
development. In this paper, we address the problem of generating targeted starting
positions for such games. This can facilitate new approaches for bringing novice
players to mastery, and also leads to discovery of interesting game variants.
\r\nOur approach generates starting states of varying hardness levels for player
1 in a two-player board game, given rules of the board game, the desired number
of steps required for player 1 to win, and the expertise levels of the two players.
Our approach leverages symbolic methods and iterative simulation to efficiently
search the extremely large state space. We present experimental results that include
discovery of states of varying hardness levels for several simple grid-based board
games. Also, the presence of such states for standard game variants like Tic-Tac-Toe
on board size 4x4 opens up new games to be played that have not been played for
ages since the default start state is heavily biased. "
alternative_title:
- IST Austria Technical Report
author:
- first_name: Umair
full_name: Ahmed, Umair
last_name: Ahmed
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Sumit
full_name: Gulwani, Sumit
last_name: Gulwani
citation:
ama: Ahmed U, Chatterjee K, Gulwani S. Automatic Generation of Alternative Starting
Positions for Traditional Board Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-146-v1-1
apa: Ahmed, U., Chatterjee, K., & Gulwani, S. (2013). Automatic generation
of alternative starting positions for traditional board games. IST Austria.
https://doi.org/10.15479/AT:IST-2013-146-v1-1
chicago: Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. Automatic Generation
of Alternative Starting Positions for Traditional Board Games. IST Austria,
2013. https://doi.org/10.15479/AT:IST-2013-146-v1-1.
ieee: U. Ahmed, K. Chatterjee, and S. Gulwani, Automatic generation of alternative
starting positions for traditional board games. IST Austria, 2013.
ista: Ahmed U, Chatterjee K, Gulwani S. 2013. Automatic generation of alternative
starting positions for traditional board games, IST Austria, 13p.
mla: Ahmed, Umair, et al. Automatic Generation of Alternative Starting Positions
for Traditional Board Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-146-v1-1.
short: U. Ahmed, K. Chatterjee, S. Gulwani, Automatic Generation of Alternative
Starting Positions for Traditional Board Games, IST Austria, 2013.
date_created: 2018-12-12T11:39:10Z
date_published: 2013-12-03T00:00:00Z
date_updated: 2023-02-23T10:00:50Z
day: '03'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-146-v1-1
file:
- access_level: open_access
checksum: 409f3aaaf1184e4057b89cbb449dac80
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:06Z
date_updated: 2020-07-14T12:46:46Z
file_id: '5528'
file_name: IST-2013-146-v1+1_main.pdf
file_size: 818189
relation: main_file
file_date_updated: 2020-07-14T12:46:46Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '13'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '146'
related_material:
record:
- id: '1481'
relation: later_version
status: public
status: public
title: Automatic generation of alternative starting positions for traditional board
games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '1374'
abstract:
- lang: eng
text: 'We study two-player zero-sum games over infinite-state graphs equipped with
ωB and finitary conditions. Our first contribution is about the strategy complexity,
i.e the memory required for winning strategies: we prove that over general infinite-state
graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory
suffices for finitary parity games. We then study pushdown games with boundedness
conditions, with two contributions. First we prove a collapse result for pushdown
games with ωB-conditions, implying the decidability of solving these games. Second
we consider pushdown games with finitary parity along with stack boundedness conditions,
and show that solving these games is EXPTIME-complete.'
alternative_title:
- LIPIcs
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Nathanaël
full_name: Fijalkow, Nathanaël
last_name: Fijalkow
citation:
ama: 'Chatterjee K, Fijalkow N. Infinite-state games with finitary conditions. In:
22nd EACSL Annual Conference on Computer Science Logic. Vol 23. Leibniz
International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2013:181-196. doi:10.4230/LIPIcs.CSL.2013.181'
apa: 'Chatterjee, K., & Fijalkow, N. (2013). Infinite-state games with finitary
conditions. In 22nd EACSL Annual Conference on Computer Science Logic (Vol.
23, pp. 181–196). Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CSL.2013.181'
chicago: Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Infinite-State Games with
Finitary Conditions.” In 22nd EACSL Annual Conference on Computer Science Logic,
23:181–96. Leibniz International Proceedings in Informatics. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.181.
ieee: K. Chatterjee and N. Fijalkow, “Infinite-state games with finitary conditions,”
in 22nd EACSL Annual Conference on Computer Science Logic, Torino, Italy,
2013, vol. 23, pp. 181–196.
ista: 'Chatterjee K, Fijalkow N. 2013. Infinite-state games with finitary conditions.
22nd EACSL Annual Conference on Computer Science Logic. CSL: Computer Science
LogicLeibniz International Proceedings in Informatics, LIPIcs, vol. 23, 181–196.'
mla: Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Infinite-State Games with
Finitary Conditions.” 22nd EACSL Annual Conference on Computer Science Logic,
vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–96,
doi:10.4230/LIPIcs.CSL.2013.181.
short: K. Chatterjee, N. Fijalkow, in:, 22nd EACSL Annual Conference on Computer
Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–196.
conference:
end_date: 2013-09-05
location: Torino, Italy
name: 'CSL: Computer Science Logic'
start_date: 203-09-02
date_created: 2018-12-11T11:51:39Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2021-01-12T06:50:14Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CSL.2013.181
ec_funded: 1
file:
- access_level: open_access
checksum: b7091a3866db573c0db5ec486952255e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:38Z
date_updated: 2020-07-14T12:44:47Z
file_id: '5023'
file_name: IST-2016-624-v1+1_ChKr_Infinite-state_games_2013_17.pdf
file_size: 547296
relation: main_file
file_date_updated: 2020-07-14T12:44:47Z
has_accepted_license: '1'
intvolume: ' 23'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 181 - 196
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 22nd EACSL Annual Conference on Computer Science Logic
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '5837'
pubrep_id: '624'
quality_controlled: '1'
scopus_import: 1
series_title: Leibniz International Proceedings in Informatics
status: public
title: Infinite-state games with finitary conditions
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2013'
...
---
_id: '1376'
abstract:
- lang: eng
text: 'We consider the distributed synthesis problem for temporal 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 LTL and 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.'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed synthesis
for LTL fragments. In: 13th International Conference on Formal Methods in Computer-Aided
Design. IEEE; 2013:18-25. doi:10.1109/FMCAD.2013.6679386'
apa: 'Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013).
Distributed synthesis for LTL fragments. In 13th International Conference on
Formal Methods in Computer-Aided Design (pp. 18–25). Portland, OR, United
States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679386'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis.
“Distributed Synthesis for LTL Fragments.” In 13th International Conference
on Formal Methods in Computer-Aided Design, 18–25. IEEE, 2013. https://doi.org/10.1109/FMCAD.2013.6679386.
ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, “Distributed
synthesis for LTL fragments,” in 13th International Conference on Formal Methods
in Computer-Aided Design, Portland, OR, United States, 2013, pp. 18–25.
ista: 'Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis
for LTL fragments. 13th International Conference on Formal Methods in Computer-Aided
Design. FMCAD: Formal Methods in Computer-Aided Design, 18–25.'
mla: Chatterjee, Krishnendu, et al. “Distributed Synthesis for LTL Fragments.” 13th
International Conference on Formal Methods in Computer-Aided Design, IEEE,
2013, pp. 18–25, doi:10.1109/FMCAD.2013.6679386.
short: K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International
Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25.
conference:
end_date: 2013-10-23
location: Portland, OR, United States
name: 'FMCAD: Formal Methods in Computer-Aided Design'
start_date: 2013-10-20
date_created: 2018-12-11T11:51:40Z
date_published: 2013-12-11T00:00:00Z
date_updated: 2023-02-23T12:24:53Z
day: '11'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1109/FMCAD.2013.6679386
ec_funded: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 18 - 25
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 13th International Conference on Formal Methods in Computer-Aided Design
publication_status: published
publisher: IEEE
publist_id: '5835'
quality_controlled: '1'
related_material:
record:
- id: '5406'
relation: earlier_version
status: public
status: public
title: Distributed synthesis for LTL fragments
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '9749'
abstract:
- lang: eng
text: Cooperative behavior, where one individual incurs a cost to help another,
is a wide spread phenomenon. Here we study direct reciprocity in the context of
the alternating Prisoner's Dilemma. We consider all strategies that can be implemented
by one and two-state automata. We calculate the payoff matrix of all pairwise
encounters in the presence of noise. We explore deterministic selection dynamics
with and without mutation. Using different error rates and payoff values, we observe
convergence to a small number of distinct equilibria. Two of them are uncooperative
strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium
is mixed and represents a cooperative alliance of several strategies, dominated
by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent
has cooperated; it defects once when the opponent has defected, but subsequently
Forgiver attempts to re-establish cooperation even if the opponent has defected
again. Forgiver is not an evolutionarily stable strategy, but the alliance, which
it rules, is asymptotically stable. For a wide range of parameter values the most
commonly observed outcome is convergence to the mixed equilibrium, dominated by
Forgiver. Our results show that although forgiving might incur a short-term loss
it can lead to a long-term gain. Forgiveness facilitates stable cooperation in
the presence of exploitation and noise.
article_processing_charge: No
author:
- first_name: Benjamin
full_name: Zagorsky, Benjamin
last_name: Zagorsky
- first_name: Johannes
full_name: Reiter, Johannes
id: 4A918E98-F248-11E8-B48F-1D18A9856A87
last_name: Reiter
orcid: 0000-0002-0170-7353
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Zagorsky B, Reiter J, Chatterjee K, Nowak M. Forgiver triumphs in alternating
prisoner’s dilemma . 2013. doi:10.1371/journal.pone.0080814.s001
apa: Zagorsky, B., Reiter, J., Chatterjee, K., & Nowak, M. (2013). Forgiver
triumphs in alternating prisoner’s dilemma . Public Library of Science. https://doi.org/10.1371/journal.pone.0080814.s001
chicago: Zagorsky, Benjamin, Johannes Reiter, Krishnendu Chatterjee, and Martin
Nowak. “Forgiver Triumphs in Alternating Prisoner’s Dilemma .” Public Library
of Science, 2013. https://doi.org/10.1371/journal.pone.0080814.s001.
ieee: B. Zagorsky, J. Reiter, K. Chatterjee, and M. Nowak, “Forgiver triumphs in
alternating prisoner’s dilemma .” Public Library of Science, 2013.
ista: Zagorsky B, Reiter J, Chatterjee K, Nowak M. 2013. Forgiver triumphs in alternating
prisoner’s dilemma , Public Library of Science, 10.1371/journal.pone.0080814.s001.
mla: Zagorsky, Benjamin, et al. Forgiver Triumphs in Alternating Prisoner’s Dilemma
. Public Library of Science, 2013, doi:10.1371/journal.pone.0080814.s001.
short: B. Zagorsky, J. Reiter, K. Chatterjee, M. Nowak, (2013).
date_created: 2021-07-28T15:45:07Z
date_published: 2013-12-12T00:00:00Z
date_updated: 2023-02-23T10:34:39Z
day: '12'
department:
- _id: KrCh
doi: 10.1371/journal.pone.0080814.s001
month: '12'
oa_version: Published Version
publisher: Public Library of Science
related_material:
record:
- id: '2247'
relation: used_in_publication
status: public
status: public
title: 'Forgiver triumphs in alternating prisoner''s dilemma '
type: research_data_reference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
year: '2013'
...
---
_id: '2715'
abstract:
- lang: eng
text: 'We consider Markov decision processes (MDPs) with specifications given as
Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure
winning vertices from where the objective can be ensured with probability 1. We
study for the first time the average case complexity of the classical algorithm
for computing the set of almost-sure winning vertices for MDPs with Büchi objectives.
Our contributions are as follows: First, we show that for MDPs with constant out-degree
the expected number of iterations is at most logarithmic and the average case
running time is linear (as compared to the worst case linear number of iterations
and quadratic time complexity). Second, for the average case analysis over all
MDPs we show that the expected number of iterations is constant and the average
case running time is linear (again as compared to the worst case linear number
of iterations and quadratic time complexity). Finally we also show that given
that all MDPs are equally likely, the probability that the classical algorithm
requires more than constant number of iterations is exponentially small.'
alternative_title:
- LIPIcs
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Manas
full_name: Joglekar, Manas
last_name: Joglekar
- first_name: Nisarg
full_name: Shah, Nisarg
last_name: Shah
citation:
ama: 'Chatterjee K, Joglekar M, Shah N. Average case analysis of the classical algorithm
for Markov decision processes with Büchi objectives. In: Vol 18. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2012:461-473. doi:10.4230/LIPIcs.FSTTCS.2012.461'
apa: 'Chatterjee, K., Joglekar, M., & Shah, N. (2012). Average case analysis
of the classical algorithm for Markov decision processes with Büchi objectives
(Vol. 18, pp. 461–473). Presented at the FSTTCS: Foundations of Software Technology
and Theoretical Computer Science, Hyderabad, India: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461'
chicago: Chatterjee, Krishnendu, Manas Joglekar, and Nisarg Shah. “Average Case
Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives,”
18:461–73. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461.
ieee: 'K. Chatterjee, M. Joglekar, and N. Shah, “Average case analysis of the classical
algorithm for Markov decision processes with Büchi objectives,” presented at the
FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad,
India, 2012, vol. 18, pp. 461–473.'
ista: 'Chatterjee K, Joglekar M, Shah N. 2012. Average case analysis of the classical
algorithm for Markov decision processes with Büchi objectives. FSTTCS: Foundations
of Software Technology and Theoretical Computer Science, LIPIcs, vol. 18, 461–473.'
mla: Chatterjee, Krishnendu, et al. Average Case Analysis of the Classical Algorithm
for Markov Decision Processes with Büchi Objectives. Vol. 18, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2012, pp. 461–73, doi:10.4230/LIPIcs.FSTTCS.2012.461.
short: K. Chatterjee, M. Joglekar, N. Shah, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2012, pp. 461–473.
conference:
end_date: 2012-12-17
location: Hyderabad, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2012-12-15
date_created: 2018-12-11T11:59:13Z
date_published: 2012-12-10T00:00:00Z
date_updated: 2023-02-23T10:06:04Z
day: '10'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2012.461
ec_funded: 1
file:
- access_level: open_access
checksum: d4d644ed1a885dbfc4fa1ef4c5724dab
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:53Z
date_updated: 2020-07-14T12:45:45Z
file_id: '5040'
file_name: IST-2016-525-v1+1_42_1_.pdf
file_size: 519040
relation: main_file
file_date_updated: 2020-07-14T12:45:45Z
has_accepted_license: '1'
intvolume: ' 18'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 461 - 473
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '4180'
pubrep_id: '525'
quality_controlled: '1'
related_material:
record:
- id: '1598'
relation: later_version
status: public
scopus_import: 1
status: public
title: Average case analysis of the classical algorithm for Markov decision processes
with Büchi objectives
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 18
year: '2012'
...
---
_id: '2848'
abstract:
- lang: eng
text: We study evolutionary game theory in a setting where individuals learn from
each other. We extend the traditional approach by assuming that a population contains
individuals with different learning abilities. In particular, we explore the situation
where individuals have different search spaces, when attempting to learn the strategies
of others. The search space of an individual specifies the set of strategies learnable
by that individual. The search space is genetically given and does not change
under social evolutionary dynamics. We introduce a general framework and study
a specific example in the context of direct reciprocity. For this example, we
obtain the counter intuitive result that cooperation can only evolve for intermediate
benefit-to-cost ratios, while small and large benefit-to-cost ratios favor defection.
Our paper is a step toward making a connection between computational learning
theory and evolutionary game dynamics.
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Chatterjee K, Zufferey D, Nowak M. Evolutionary game dynamics in populations
with different learners. Journal of Theoretical Biology. 2012;301:161-173.
doi:10.1016/j.jtbi.2012.02.021
apa: Chatterjee, K., Zufferey, D., & Nowak, M. (2012). Evolutionary game dynamics
in populations with different learners. Journal of Theoretical Biology.
Elsevier. https://doi.org/10.1016/j.jtbi.2012.02.021
chicago: Chatterjee, Krishnendu, Damien Zufferey, and Martin Nowak. “Evolutionary
Game Dynamics in Populations with Different Learners.” Journal of Theoretical
Biology. Elsevier, 2012. https://doi.org/10.1016/j.jtbi.2012.02.021.
ieee: K. Chatterjee, D. Zufferey, and M. Nowak, “Evolutionary game dynamics in populations
with different learners,” Journal of Theoretical Biology, vol. 301. Elsevier,
pp. 161–173, 2012.
ista: Chatterjee K, Zufferey D, Nowak M. 2012. Evolutionary game dynamics in populations
with different learners. Journal of Theoretical Biology. 301, 161–173.
mla: Chatterjee, Krishnendu, et al. “Evolutionary Game Dynamics in Populations with
Different Learners.” Journal of Theoretical Biology, vol. 301, Elsevier,
2012, pp. 161–73, doi:10.1016/j.jtbi.2012.02.021.
short: K. Chatterjee, D. Zufferey, M. Nowak, Journal of Theoretical Biology 301
(2012) 161–173.
date_created: 2018-12-11T11:59:55Z
date_published: 2012-05-21T00:00:00Z
date_updated: 2021-01-12T07:00:12Z
day: '21'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.jtbi.2012.02.021
ec_funded: 1
external_id:
pmid:
- '22394652'
intvolume: ' 301'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3322297/
month: '05'
oa: 1
oa_version: Submitted Version
page: 161 - 173
pmid: 1
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Journal of Theoretical Biology
publication_status: published
publisher: Elsevier
publist_id: '3946'
quality_controlled: '1'
scopus_import: 1
status: public
title: Evolutionary game dynamics in populations with different learners
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 301
year: '2012'
...
---
_id: '2916'
abstract:
- lang: eng
text: The classical (boolean) notion of refinement for behavioral interfaces of
system components is the alternating refinement preorder. In this paper, we define
a quantitative measure for interfaces, called interface simulation distance. It
makes the alternating refinement preorder quantitative by, intu- itively, tolerating
errors (while counting them) in the alternating simulation game. We show that
the interface simulation distance satisfies the triangle inequality, that the
distance between two interfaces does not increase under parallel composition with
a third interface, and that the distance between two interfaces can be bounded
from above and below by distances between abstractions of the two interfaces.
We illustrate the framework, and the properties of the distances under composition
of interfaces, with two case studies.
arxiv: 1
author:
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Arjun
full_name: Radhakrishna, Arjun
id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
last_name: Radhakrishna
citation:
ama: 'Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. Interface Simulation Distances.
In: Electronic Proceedings in Theoretical Computer Science. Vol 96. EPTCS;
2012:29-42. doi:10.4204/EPTCS.96.3'
apa: 'Cerny, P., Chmelik, M., Henzinger, T. A., & Radhakrishna, A. (2012). Interface
Simulation Distances. In Electronic Proceedings in Theoretical Computer Science
(Vol. 96, pp. 29–42). Napoli, Italy: EPTCS. https://doi.org/10.4204/EPTCS.96.3'
chicago: Cerny, Pavol, Martin Chmelik, Thomas A Henzinger, and Arjun Radhakrishna.
“Interface Simulation Distances.” In Electronic Proceedings in Theoretical
Computer Science, 96:29–42. EPTCS, 2012. https://doi.org/10.4204/EPTCS.96.3.
ieee: P. Cerny, M. Chmelik, T. A. Henzinger, and A. Radhakrishna, “Interface Simulation
Distances,” in Electronic Proceedings in Theoretical Computer Science,
Napoli, Italy, 2012, vol. 96, pp. 29–42.
ista: 'Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. 2012. Interface Simulation
Distances. Electronic Proceedings in Theoretical Computer Science. GandALF: Games,
Automata, Logic, and Formal Verification vol. 96, 29–42.'
mla: Cerny, Pavol, et al. “Interface Simulation Distances.” Electronic Proceedings
in Theoretical Computer Science, vol. 96, EPTCS, 2012, pp. 29–42, doi:10.4204/EPTCS.96.3.
short: P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, in:, Electronic Proceedings
in Theoretical Computer Science, EPTCS, 2012, pp. 29–42.
conference:
end_date: 2012-09-08
location: Napoli, Italy
name: 'GandALF: Games, Automata, Logic, and Formal Verification'
start_date: 2012-09-06
date_created: 2018-12-11T12:00:19Z
date_published: 2012-10-07T00:00:00Z
date_updated: 2023-02-23T10:12:05Z
day: '07'
department:
- _id: ToHe
- _id: KrCh
doi: 10.4204/EPTCS.96.3
ec_funded: 1
external_id:
arxiv:
- '1210.2450'
intvolume: ' 96'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1210.2450
month: '10'
oa: 1
oa_version: Submitted Version
page: 29 - 42
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Electronic Proceedings in Theoretical Computer Science
publication_status: published
publisher: EPTCS
publist_id: '3827'
quality_controlled: '1'
related_material:
record:
- id: '1733'
relation: later_version
status: public
scopus_import: 1
status: public
title: Interface Simulation Distances
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 96
year: '2012'
...
---
_id: '2936'
abstract:
- lang: eng
text: The notion of delays arises naturally in many computational models, such as,
in the design of circuits, control systems, and dataflow languages. In this work,
we introduce automata with delay blocks (ADBs), extending finite state automata
with variable time delay blocks, for deferring individual transition output symbols,
in a discrete-time setting. We show that the ADB languages strictly subsume the
regular languages, and are incomparable in expressive power to the context-free
languages. We show that ADBs are closed under union, concatenation and Kleene
star, and under intersection with regular languages, but not closed under complementation
and intersection with other ADB languages. We show that the emptiness and the
membership problems are decidable in polynomial time for ADBs, whereas the universality
problem is undecidable. Finally we consider the linear-time model checking problem,
i.e., whether the language of an ADB is contained in a regular language, and show
that the model checking problem is PSPACE-complete. Copyright 2012 ACM.
acknowledgement: 'This work has been financially supported in part by the European
Commission FP7-ICT Cognitive Systems, Interaction, and Robotics under the contract
# 270180 (NOPTILUS); by Fundacao para Ciencia e Tecnologia under project PTDC/EEA-CRO/104901/2008
(Modeling and control of Networked vehicle systems in persistent autonomous operations);
by Austrian Science Fund (FWF) Grant No P 23499-N23 on Modern Graph Algorithmic
Techniques in Formal Verification; FWF NFN Grant No S11407-N23 (RiSE); ERC Start
grant (279307: Graph Games); Microsoft faculty fellows award; ERC Advanced grant
QUAREM; and FWF Grant No S11403-N23 (RiSE).'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Vinayak
full_name: Prabhu, Vinayak
last_name: Prabhu
citation:
ama: 'Chatterjee K, Henzinger TA, Prabhu V. Finite automata with time delay blocks.
In: Roceedings of the Tenth ACM International Conference on Embedded Software.
ACM; 2012:43-52. doi:10.1145/2380356.2380370'
apa: 'Chatterjee, K., Henzinger, T. A., & Prabhu, V. (2012). Finite automata
with time delay blocks. In roceedings of the tenth ACM international conference
on Embedded software (pp. 43–52). Tampere, Finland: ACM. https://doi.org/10.1145/2380356.2380370'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Finite
Automata with Time Delay Blocks.” In Roceedings of the Tenth ACM International
Conference on Embedded Software, 43–52. ACM, 2012. https://doi.org/10.1145/2380356.2380370.
ieee: K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Finite automata with time
delay blocks,” in roceedings of the tenth ACM international conference on Embedded
software, Tampere, Finland, 2012, pp. 43–52.
ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2012. Finite automata with time delay
blocks. roceedings of the tenth ACM international conference on Embedded software.
EMSOFT: Embedded Software , 43–52.'
mla: Chatterjee, Krishnendu, et al. “Finite Automata with Time Delay Blocks.” Roceedings
of the Tenth ACM International Conference on Embedded Software, ACM, 2012,
pp. 43–52, doi:10.1145/2380356.2380370.
short: K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, Roceedings of the Tenth ACM
International Conference on Embedded Software, ACM, 2012, pp. 43–52.
conference:
end_date: 2012-10-12
location: Tampere, Finland
name: 'EMSOFT: Embedded Software '
start_date: 2012-10-07
date_created: 2018-12-11T12:00:26Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2021-01-12T07:39:53Z
day: '01'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1145/2380356.2380370
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1207.7019
month: '10'
oa: 1
oa_version: Preprint
page: 43 - 52
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication: roceedings of the tenth ACM international conference on Embedded software
publication_status: published
publisher: ACM
publist_id: '3799'
quality_controlled: '1'
scopus_import: 1
status: public
title: Finite automata with time delay blocks
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '2947'
abstract:
- lang: eng
text: We introduce games with probabilistic uncertainty, a model for controller
synthesis in which the controller observes the state through imprecise sensors
that provide correct information about the current state with a fixed probability.
That is, in each step, the sensors return an observed state, and given the observed
state, there is a probability distribution (due to the estimation error) over
the actual current state. The controller must base its decision on the observed
state (rather than the actual current state, which it does not know). On the other
hand, we assume that the environment can perfectly observe the current state.
We show that controller synthesis for qualitative ω-regular objectives in our
model can be reduced in polynomial time to standard partial-observation stochastic
games, and vice-versa. As a consequence we establish the precise decidability
frontier for the new class of games, and establish optimal complexity results
for all the decidable problems.
acknowledgement: 'The research was supported by Austrian Science Fund (FWF) Grant
No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF
NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft
faculty fellows award.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
citation:
ama: 'Chatterjee K, Chmelik M, Majumdar R. Equivalence of games with probabilistic
uncertainty and partial observation games. In: Vol 7561. Springer; 2012:385-399.
doi:10.1007/978-3-642-33386-6_30'
apa: 'Chatterjee, K., Chmelik, M., & Majumdar, R. (2012). Equivalence of games
with probabilistic uncertainty and partial observation games (Vol. 7561, pp. 385–399).
Presented at the ATVA: Automated Technology for Verification and Analysis, Thiruvananthapuram,
India: Springer. https://doi.org/10.1007/978-3-642-33386-6_30'
chicago: Chatterjee, Krishnendu, Martin Chmelik, and Ritankar Majumdar. “Equivalence
of Games with Probabilistic Uncertainty and Partial Observation Games,” 7561:385–99.
Springer, 2012. https://doi.org/10.1007/978-3-642-33386-6_30.
ieee: 'K. Chatterjee, M. Chmelik, and R. Majumdar, “Equivalence of games with probabilistic
uncertainty and partial observation games,” presented at the ATVA: Automated
Technology for Verification and Analysis, Thiruvananthapuram, India, 2012, vol.
7561, pp. 385–399.'
ista: 'Chatterjee K, Chmelik M, Majumdar R. 2012. Equivalence of games with probabilistic
uncertainty and partial observation games. ATVA: Automated Technology for Verification
and Analysis, LNCS, vol. 7561, 385–399.'
mla: Chatterjee, Krishnendu, et al. Equivalence of Games with Probabilistic Uncertainty
and Partial Observation Games. Vol. 7561, Springer, 2012, pp. 385–99, doi:10.1007/978-3-642-33386-6_30.
short: K. Chatterjee, M. Chmelik, R. Majumdar, in:, Springer, 2012, pp. 385–399.
conference:
end_date: 2012-10-06
location: Thiruvananthapuram, India
name: ' ATVA: Automated Technology for Verification and Analysis'
start_date: 2012-10-03
date_created: 2018-12-11T12:00:29Z
date_published: 2012-06-01T00:00:00Z
date_updated: 2021-01-12T07:39:58Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-33386-6_30
ec_funded: 1
intvolume: ' 7561'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1202.4140
month: '06'
oa: 1
oa_version: Preprint
page: 385 - 399
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Springer
publist_id: '3785'
quality_controlled: '1'
scopus_import: 1
status: public
title: Equivalence of games with probabilistic uncertainty and partial observation
games
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7561
year: '2012'
...
---
_id: '2955'
abstract:
- lang: eng
text: 'We consider two-player stochastic games played on finite graphs with reachability
objectives where the first player tries to ensure a target state to be visited
almost-surely (i.e., with probability 1), or positively (i.e., with positive probability),
no matter the strategy of the second player. We classify such games according
to the information and the power of randomization available to the players. On
the basis of information, the game can be one-sided with either (a) player 1,
or (b) player 2 having partial observation (and the other player has perfect observation),
or two-sided with (c) both players having partial observation. On the basis of
randomization, the players (a) may not be allowed to use randomization (pure strategies),
or (b) may choose a probability distribution over actions but the actual random
choice is external and not visible to the player (actions invisible), or (c) may
use full randomization. Our main results for pure strategies are as follows. (1)
For one-sided games with player 1 having partial observation we show that (in
contrast to full randomized strategies) belief-based (subset-construction based)
strategies are not sufficient, and we present an exponential upper bound on memory
both for almostsure and positive winning strategies; we show that the problem
of deciding the existence of almost-sure and positive winning strategies for player
1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation
we show that non-elementary memory is both necessary and sufficient for both almost-sure
and positive winning strategies. (3) We show that for the general (two-sided)
case finite-memory strategies are sufficient for both positive and almost-sure
winning, and at least non-elementary memory is required. We establish the equivalence
of the almost-sure winning problems for pure strategies and for randomized strategies
with actions invisible. Our equivalence result exhibits serious flaws in previous
results of the literature: we show a non-elementary memory lower bound for almost-sure
winning whereas an exponential upper bound was previously claimed.'
acknowledgement: 'This work was partially supported by FWF Grant No P 23499-N23, FWF
NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft
faculty fellows award.'
article_number: '6280436'
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when
belief fails. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on
Logic in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.28'
apa: 'Chatterjee, K., & Doyen, L. (2012). Partial-observation stochastic games:
How to win when belief fails. In Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science. Dubrovnik, Croatia: IEEE. https://doi.org/10.1109/LICS.2012.28'
chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic
Games: How to Win When Belief Fails.” In Proceedings of the 2012 27th Annual
ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.28.'
ieee: 'K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to
win when belief fails,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science, Dubrovnik, Croatia, 2012.'
ista: 'Chatterjee K, Doyen L. 2012. Partial-observation stochastic games: How to
win when belief fails. Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science. LICS: Logic in Computer Science, 6280436.'
mla: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic
Games: How to Win When Belief Fails.” Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, 6280436, IEEE, 2012, doi:10.1109/LICS.2012.28.'
short: K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, IEEE, 2012.
conference:
end_date: 2012-06-28
location: Dubrovnik, Croatia
name: 'LICS: Logic in Computer Science'
start_date: 2012-06-25
date_created: 2018-12-11T12:00:32Z
date_published: 2012-08-23T00:00:00Z
date_updated: 2023-02-23T12:23:43Z
day: '23'
department:
- _id: KrCh
doi: 10.1109/LICS.2012.28
ec_funded: 1
external_id:
arxiv:
- '1107.2141'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2141
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_status: published
publisher: IEEE
publist_id: '3771'
quality_controlled: '1'
related_material:
record:
- id: '2211'
relation: later_version
status: public
- id: '5381'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: 'Partial-observation stochastic games: How to win when belief fails'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '2956'
abstract:
- lang: eng
text: 'Two-player games on graphs are central in many problems in formal verification
and program analysis such as synthesis and verification of open systems. In this
work we consider solving recursive game graphs (or pushdown game graphs) that
can model the control flow of sequential programs with recursion. While pushdown
games have been studied before with qualitative objectives, such as reachability
and parity objectives, in this work we study for the first time such games with
the most well-studied quantitative objective, namely, mean payoff objectives.
In pushdown games two types of strategies are relevant: (1) global strategies,
that depend on the entire global history; and (2) modular strategies, that have
only local memory and thus do not depend on the context of invocation, but only
on the history of the current invocation of the module. Our main results are as
follows: (1) One-player pushdown games with mean-payoff objectives under global
strategies are decidable in polynomial time. (2) Two-player pushdown games with
mean-payoff objectives under global strategies are undecidable. (3) One-player
pushdown games with mean-payoff objectives under modular strategies are NP-hard.
(4) Two-player pushdown games with mean-payoff objectives under modular strategies
can be solved in NP (i.e., both one-player and two-player pushdown games with
mean-payoff objectives under modular strategies are NP-complete). We also establish
the optimal strategy complexity showing that global strategies for mean-payoff
objectives require infinite memory even in one-player pushdown games; and memoryless
modular strategies are sufficient in two-player pushdown games. Finally we also
show that all the problems have the same computational complexity if the stack
boundedness condition is added, where along with the mean-payoff objective the
player must also ensure that the stack height is bounded.'
acknowledgement: "The research was supported by Austrian Science Fund (FWF) Grant
No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph
Games), Microsoft faculty fellows award, the Israeli Centers of Research Excellence
(ICORE) program, (Center No. 4/11), the RICH Model Toolkit (ICT COST Action IC0901),
and was carried out in partial fulfillment of the requirements for the Ph.D. degree
of the second author.\r\nA Technical Report of this paper is available via internal
link."
article_number: '6280438'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Yaron
full_name: Velner, Yaron
last_name: Velner
citation:
ama: 'Chatterjee K, Velner Y. Mean payoff pushdown games. In: Proceedings of
the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE;
2012. doi:10.1109/LICS.2012.30'
apa: 'Chatterjee, K., & Velner, Y. (2012). Mean payoff pushdown games. In Proceedings
of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. Dubrovnik,
Croatia : IEEE. https://doi.org/10.1109/LICS.2012.30'
chicago: Chatterjee, Krishnendu, and Yaron Velner. “Mean Payoff Pushdown Games.”
In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.30.
ieee: K. Chatterjee and Y. Velner, “Mean payoff pushdown games,” in Proceedings
of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, Dubrovnik,
Croatia , 2012.
ista: 'Chatterjee K, Velner Y. 2012. Mean payoff pushdown games. Proceedings of
the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic
in Computer Science, 6280438.'
mla: Chatterjee, Krishnendu, and Yaron Velner. “Mean Payoff Pushdown Games.” Proceedings
of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, 6280438,
IEEE, 2012, doi:10.1109/LICS.2012.30.
short: K. Chatterjee, Y. Velner, in:, Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, IEEE, 2012.
conference:
end_date: 2012-06-28
location: 'Dubrovnik, Croatia '
name: 'LICS: Logic in Computer Science'
start_date: 2012-06-25
date_created: 2018-12-11T12:00:32Z
date_published: 2012-08-23T00:00:00Z
date_updated: 2023-02-23T12:23:30Z
day: '23'
department:
- _id: KrCh
doi: 10.1109/LICS.2012.30
ec_funded: 1
language:
- iso: eng
month: '08'
oa_version: None
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_status: published
publisher: IEEE
publist_id: '3770'
quality_controlled: '1'
related_material:
record:
- id: '5377'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Mean payoff pushdown games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '2957'
abstract:
- lang: eng
text: 'We consider probabilistic automata on infinite words with acceptance defined
by parity conditions. We consider three qualitative decision problems: (i) the
positive decision problem asks whether there is a word that is accepted with positive
probability; (ii) the almost decision problem asks whether there is a word that
is accepted with probability 1; and (iii) the limit decision problem asks whether
words are accepted with probability arbitrarily close to 1. We unify and generalize
several decidability results for probabilistic automata over infinite words, and
identify a robust (closed under union and intersection) subclass of probabilistic
automata for which all the qualitative decision problems are decidable for parity
conditions. We also show that if the input words are restricted to lasso shape
(regular) words, then the positive and almost problems are decidable for all probabilistic
automata with parity conditions. For most decidable problems we show an optimal
PSPACE-complete complexity bound.'
article_number: '6280437'
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Mathieu
full_name: Tracol, Mathieu
id: 3F54FA38-F248-11E8-B48F-1D18A9856A87
last_name: Tracol
citation:
ama: 'Chatterjee K, Tracol M. Decidable problems for probabilistic automata on infinite
words. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic
in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.29'
apa: 'Chatterjee, K., & Tracol, M. (2012). Decidable problems for probabilistic
automata on infinite words. In Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science. Dubrovnik, Croatia : IEEE. https://doi.org/10.1109/LICS.2012.29'
chicago: Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic
Automata on Infinite Words.” In Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.29.
ieee: K. Chatterjee and M. Tracol, “Decidable problems for probabilistic automata
on infinite words,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science, Dubrovnik, Croatia , 2012.
ista: 'Chatterjee K, Tracol M. 2012. Decidable problems for probabilistic automata
on infinite words. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic
in Computer Science. LICS: Logic in Computer Science, 6280437.'
mla: Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic
Automata on Infinite Words.” Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science, 6280437, IEEE, 2012, doi:10.1109/LICS.2012.29.
short: K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, IEEE, 2012.
conference:
end_date: 2012-06-28
location: 'Dubrovnik, Croatia '
name: 'LICS: Logic in Computer Science'
start_date: 2012-06-25
date_created: 2018-12-11T12:00:33Z
date_published: 2012-08-23T00:00:00Z
date_updated: 2023-02-23T12:23:51Z
day: '23'
department:
- _id: KrCh
doi: 10.1109/LICS.2012.29
ec_funded: 1
external_id:
arxiv:
- '1107.2091'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1107.2091
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_status: published
publisher: IEEE
publist_id: '3769'
quality_controlled: '1'
related_material:
record:
- id: '5384'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Decidable problems for probabilistic automata on infinite words
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '2972'
abstract:
- lang: eng
text: 'Energy parity games are infinite two-player turn-based games played on weighted
graphs. The objective of the game combines a (qualitative) parity condition with
the (quantitative) requirement that the sum of the weights (i.e., the level of
energy in the game) must remain positive. Beside their own interest in the design
and synthesis of resource-constrained omega-regular specifications, energy parity
games provide one of the simplest model of games with combined qualitative and
quantitative objectives. Our main results are as follows: (a) exponential memory
is sufficient and may be necessary for winning strategies in energy parity games;
(b) the problem of deciding the winner in energy parity games can be solved in
NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to
energy games. We also show that the problem of deciding the winner in energy parity
games is logspace-equivalent to the problem of deciding the winner in mean-payoff
parity games, which can thus be solved in NP ∩ coNP. As a consequence we also
obtain a conceptually simple algorithm to solve mean-payoff parity games.'
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: Chatterjee K, Doyen L. Energy parity games. Theoretical Computer Science.
2012;458:49-60. doi:10.1016/j.tcs.2012.07.038
apa: Chatterjee, K., & Doyen, L. (2012). Energy parity games. Theoretical
Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2012.07.038
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games.” Theoretical
Computer Science. Elsevier, 2012. https://doi.org/10.1016/j.tcs.2012.07.038.
ieee: K. Chatterjee and L. Doyen, “Energy parity games,” Theoretical Computer
Science, vol. 458. Elsevier, pp. 49–60, 2012.
ista: Chatterjee K, Doyen L. 2012. Energy parity games. Theoretical Computer Science.
458, 49–60.
mla: Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games.” Theoretical
Computer Science, vol. 458, Elsevier, 2012, pp. 49–60, doi:10.1016/j.tcs.2012.07.038.
short: K. Chatterjee, L. Doyen, Theoretical Computer Science 458 (2012) 49–60.
date_created: 2018-12-11T12:00:37Z
date_published: 2012-11-02T00:00:00Z
date_updated: 2023-02-23T11:45:29Z
day: '02'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.1016/j.tcs.2012.07.038
ec_funded: 1
external_id:
arxiv:
- '1001.5183'
file:
- access_level: open_access
checksum: 719e4a5af5a01ad3f2f7f7f05b3c2b09
content_type: application/pdf
creator: kschuh
date_created: 2019-02-06T11:56:22Z
date_updated: 2020-07-14T12:45:57Z
file_id: '5935'
file_name: 2012_Elsevier_Chatterjee.pdf
file_size: 351271
relation: main_file
file_date_updated: 2020-07-14T12:45:57Z
has_accepted_license: '1'
intvolume: ' 458'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 49 - 60
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '3736'
pubrep_id: '935'
quality_controlled: '1'
related_material:
record:
- id: '3851'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Energy parity games
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 458
year: '2012'
...
---
_id: '3128'
abstract:
- lang: eng
text: 'We consider two-player zero-sum stochastic games on graphs with ω-regular
winning conditions specified as parity objectives. These games have applications
in the design and control of reactive systems. We survey the complexity results
for the problem of deciding the winner in such games, and in classes of interest
obtained as special cases, based on the information and the power of randomization
available to the players, on the class of objectives and on the winning mode.
On the basis of information, these games can be classified as follows: (a) partial-observation
(both players have partial view of the game); (b) one-sided partial-observation
(one player has partial-observation and the other player has complete-observation);
and (c) complete-observation (both players have complete view of the game). The
one-sided partial-observation games have two important subclasses: the one-player
games, known as partial-observation Markov decision processes (POMDPs), and the
blind one-player games, known as probabilistic automata. On the basis of randomization,
(a) the players may not be allowed to use randomization (pure strategies), or
(b) they may choose a probability distribution over actions but the actual random
choice is external and not visible to the player (actions invisible), or (c) they
may use full randomization. Finally, various classes of games are obtained by
restricting the parity objective to a reachability, safety, Büchi, or coBüchi
condition. We also consider several winning modes, such as sure-winning (i.e.,
all outcomes of a strategy have to satisfy the winning condition), almost-sure
winning (i.e., winning with probability 1), limit-sure winning (i.e., winning
with probability arbitrarily close to 1), and value-threshold winning (i.e., winning
with probability at least ν, where ν is a given rational). '
acknowledgement: 'The research was supported by Austrian Science Fund (FWF) Grant
No. P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, FWF
NFN Grant No. S11407-N23(RiSE), ERC Start grant (279307: Graph Games), Microsoft
faculty fellows award, ERC Advanced grant QUAREM, and FWF Grant No. S11403-N23 (RiSE).'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Chatterjee K, Doyen L, Henzinger TA. A survey of partial-observation stochastic
parity games. Formal Methods in System Design. 2012;43(2):268-284. doi:10.1007/s10703-012-0164-2
apa: Chatterjee, K., Doyen, L., & Henzinger, T. A. (2012). A survey of partial-observation
stochastic parity games. Formal Methods in System Design. Springer. https://doi.org/10.1007/s10703-012-0164-2
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “A Survey
of Partial-Observation Stochastic Parity Games.” Formal Methods in System Design.
Springer, 2012. https://doi.org/10.1007/s10703-012-0164-2.
ieee: K. Chatterjee, L. Doyen, and T. A. Henzinger, “A survey of partial-observation
stochastic parity games,” Formal Methods in System Design, vol. 43, no.
2. Springer, pp. 268–284, 2012.
ista: Chatterjee K, Doyen L, Henzinger TA. 2012. A survey of partial-observation
stochastic parity games. Formal Methods in System Design. 43(2), 268–284.
mla: Chatterjee, Krishnendu, et al. “A Survey of Partial-Observation Stochastic
Parity Games.” Formal Methods in System Design, vol. 43, no. 2, Springer,
2012, pp. 268–84, doi:10.1007/s10703-012-0164-2.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, Formal Methods in System Design
43 (2012) 268–284.
date_created: 2018-12-11T12:01:33Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2021-01-12T07:41:15Z
day: '01'
ddc:
- '005'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/s10703-012-0164-2
ec_funded: 1
file:
- access_level: open_access
checksum: dd3d590f383bb2ac6cfda1489ac1c42a
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:27Z
date_updated: 2020-07-14T12:46:00Z
file_id: '4882'
file_name: IST-2014-303-v1+1_Survey_Partial-Observation_Stochastic_Parity_Games.pdf
file_size: 163983
relation: main_file
file_date_updated: 2020-07-14T12:46:00Z
has_accepted_license: '1'
intvolume: ' 43'
issue: '2'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 268 - 284
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Formal Methods in System Design
publication_status: published
publisher: Springer
publist_id: '3570'
pubrep_id: '303'
quality_controlled: '1'
scopus_import: 1
status: public
title: A survey of partial-observation stochastic parity games
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 43
year: '2012'
...
---
_id: '3135'
abstract:
- lang: eng
text: 'We introduce consumption games, a model for discrete interactive system with
multiple resources that are consumed or reloaded independently. More precisely,
a consumption game is a finite-state graph where each transition is labeled by
a vector of resource updates, where every update is a non-positive number or ω.
The ω updates model the reloading of a given resource. Each vertex belongs either
to player □ or player ◇, where the aim of player □ is to play so that the resources
are never exhausted. We consider several natural algorithmic problems about consumption
games, and show that although these problems are computationally hard in general,
they are solvable in polynomial time for every fixed number of resource types
(i.e., the dimension of the update vectors) and bounded resource updates. '
acknowledgement: 'Tomas Brazdil, Antonin Kucera, and Petr Novotny are supported by
the Czech Science Foundation, grant No. P202/10/1469. Krishnendu Chatterjee is supported
by the FWF (Austrian Science Fund) NFN Grant No S11407-N23 (RiSE) and ERC Start
grant (279307: Graph Games).'
alternative_title:
- LNCS
author:
- first_name: Brázdil
full_name: Brázdil, Brázdil
last_name: Brázdil
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Antonín
full_name: Kučera, Antonín
last_name: Kučera
- first_name: Petr
full_name: Novotny, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotny
citation:
ama: 'Brázdil B, Chatterjee K, Kučera A, Novotný P. Efficient controller synthesis
for consumption games with multiple resource types. In: Vol 7358. Springer; 2012:23-38.
doi:10.1007/978-3-642-31424-7_8'
apa: 'Brázdil, B., Chatterjee, K., Kučera, A., & Novotný, P. (2012). Efficient
controller synthesis for consumption games with multiple resource types (Vol.
7358, pp. 23–38). Presented at the CAV: Computer Aided Verification, Berkeley,
CA, USA: Springer. https://doi.org/10.1007/978-3-642-31424-7_8'
chicago: Brázdil, Brázdil, Krishnendu Chatterjee, Antonín Kučera, and Petr Novotný.
“Efficient Controller Synthesis for Consumption Games with Multiple Resource Types,”
7358:23–38. Springer, 2012. https://doi.org/10.1007/978-3-642-31424-7_8.
ieee: 'B. Brázdil, K. Chatterjee, A. Kučera, and P. Novotný, “Efficient controller
synthesis for consumption games with multiple resource types,” presented at the
CAV: Computer Aided Verification, Berkeley, CA, USA, 2012, vol. 7358, pp. 23–38.'
ista: 'Brázdil B, Chatterjee K, Kučera A, Novotný P. 2012. Efficient controller
synthesis for consumption games with multiple resource types. CAV: Computer Aided
Verification, LNCS, vol. 7358, 23–38.'
mla: Brázdil, Brázdil, et al. Efficient Controller Synthesis for Consumption
Games with Multiple Resource Types. Vol. 7358, Springer, 2012, pp. 23–38,
doi:10.1007/978-3-642-31424-7_8.
short: B. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, in:, Springer, 2012, pp.
23–38.
conference:
end_date: 2012-07-13
location: Berkeley, CA, USA
name: 'CAV: Computer Aided Verification'
start_date: 2012-07-07
date_created: 2018-12-11T12:01:35Z
date_published: 2012-07-01T00:00:00Z
date_updated: 2021-01-12T07:41:18Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-31424-7_8
ec_funded: 1
intvolume: ' 7358'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1202.0796
month: '07'
oa: 1
oa_version: Preprint
page: 23 - 38
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '3562'
quality_controlled: '1'
scopus_import: 1
status: public
title: Efficient controller synthesis for consumption games with multiple resource
types
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7358
year: '2012'
...
---
_id: '3157'
abstract:
- lang: eng
text: Colorectal tumours that are wild type for KRAS are often sensitive to EGFR
blockade, but almost always develop resistance within several months of initiating
therapy. The mechanisms underlying this acquired resistance to anti-EGFR antibodies
are largely unknown. This situation is in marked contrast to that of small-molecule
targeted agents, such as inhibitors of ABL, EGFR, BRAF and MEK, in which mutations
in the genes encoding the protein targets render the tumours resistant to the
effects of the drugs. The simplest hypothesis to account for the development of
resistance to EGFR blockade is that rare cells with KRAS mutations pre-exist at
low levels in tumours with ostensibly wild-type KRAS genes. Although this hypothesis
would seem readily testable, there is no evidence in pre-clinical models to support
it, nor is there data from patients. To test this hypothesis, we determined whether
mutant KRAS DNA could be detected in the circulation of 28 patients receiving
monotherapy with panitumumab, a therapeutic anti-EGFR antibody. We found that
9 out of 24 (38%) patients whose tumours were initially KRAS wild type developed
detectable mutations in KRAS in their sera, three of which developed multiple
different KRAS mutations. The appearance of these mutations was very consistent,
generally occurring between 5 and 6months following treatment. Mathematical modelling
indicated that the mutations were present in expanded subclones before the initiation
of panitumumab treatment. These results suggest that the emergence of KRAS mutations
is a mediator of acquired resistance to EGFR blockade and that these mutations
can be detected in a non-invasive manner. They explain why solid tumours develop
resistance to targeted therapies in a highly reproducible fashion.
author:
- first_name: Luis
full_name: Diaz Jr, Luis
last_name: Diaz Jr
- first_name: Richard
full_name: Williams, Richard
last_name: Williams
- first_name: Jian
full_name: Wu, Jian
last_name: Wu
- first_name: Isaac
full_name: Kinde, Isaac
last_name: Kinde
- first_name: Joel
full_name: Hecht, Joel
last_name: Hecht
- first_name: Jordan
full_name: Berlin, Jordan
last_name: Berlin
- first_name: Benjamin
full_name: Allen, Benjamin
last_name: Allen
- first_name: Ivana
full_name: Božić, Ivana
last_name: Božić
- first_name: Johannes
full_name: Reiter, Johannes
id: 4A918E98-F248-11E8-B48F-1D18A9856A87
last_name: Reiter
orcid: 0000-0002-0170-7353
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
- first_name: Kenneth
full_name: Kinzler, Kenneth
last_name: Kinzler
- first_name: Kelly
full_name: Oliner, Kelly
last_name: Oliner
- first_name: Bert
full_name: Vogelstein, Bert
last_name: Vogelstein
citation:
ama: Diaz Jr L, Williams R, Wu J, et al. The molecular evolution of acquired resistance
to targeted EGFR blockade in colorectal cancers. Nature. 2012;486(7404):537-540.
doi:10.1038/nature11219
apa: Diaz Jr, L., Williams, R., Wu, J., Kinde, I., Hecht, J., Berlin, J., … Vogelstein,
B. (2012). The molecular evolution of acquired resistance to targeted EGFR blockade
in colorectal cancers. Nature. Nature Publishing Group. https://doi.org/10.1038/nature11219
chicago: Diaz Jr, Luis, Richard Williams, Jian Wu, Isaac Kinde, Joel Hecht, Jordan
Berlin, Benjamin Allen, et al. “The Molecular Evolution of Acquired Resistance
to Targeted EGFR Blockade in Colorectal Cancers.” Nature. Nature Publishing
Group, 2012. https://doi.org/10.1038/nature11219.
ieee: L. Diaz Jr et al., “The molecular evolution of acquired resistance
to targeted EGFR blockade in colorectal cancers,” Nature, vol. 486, no.
7404. Nature Publishing Group, pp. 537–540, 2012.
ista: Diaz Jr L, Williams R, Wu J, Kinde I, Hecht J, Berlin J, Allen B, Božić I,
Reiter J, Nowak M, Kinzler K, Oliner K, Vogelstein B. 2012. The molecular evolution
of acquired resistance to targeted EGFR blockade in colorectal cancers. Nature.
486(7404), 537–540.
mla: Diaz Jr, Luis, et al. “The Molecular Evolution of Acquired Resistance to Targeted
EGFR Blockade in Colorectal Cancers.” Nature, vol. 486, no. 7404, Nature
Publishing Group, 2012, pp. 537–40, doi:10.1038/nature11219.
short: L. Diaz Jr, R. Williams, J. Wu, I. Kinde, J. Hecht, J. Berlin, B. Allen,
I. Božić, J. Reiter, M. Nowak, K. Kinzler, K. Oliner, B. Vogelstein, Nature 486
(2012) 537–540.
date_created: 2018-12-11T12:01:43Z
date_published: 2012-06-28T00:00:00Z
date_updated: 2023-09-07T11:40:43Z
day: '28'
department:
- _id: KrCh
doi: 10.1038/nature11219
ec_funded: 1
external_id:
pmid:
- '22722843'
intvolume: ' 486'
issue: '7404'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3436069/
month: '06'
oa: 1
oa_version: Submitted Version
page: 537 - 540
pmid: 1
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: Nature
publication_status: published
publisher: Nature Publishing Group
publist_id: '3537'
quality_controlled: '1'
related_material:
record:
- id: '1400'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: The molecular evolution of acquired resistance to targeted EGFR blockade in
colorectal cancers
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 486
year: '2012'
...