---
_id: '2836'
abstract:
- lang: eng
text: 'We study the automatic synthesis of fair non-repudiation protocols, a class
of fair exchange protocols, used for digital contract signing. First, we show
how to specify the objectives of the participating agents and the trusted third
party as path formulas in linear temporal logic and prove that the satisfaction
of these objectives imply fairness; a property required of fair exchange protocols.
We then show that weak (co-operative) co-synthesis and classical (strictly competitive)
co-synthesis fail, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate
the success of AGS as follows: (a) any solution of AGS is attack-free; no subset
of participants can violate the objectives of the other participants; (b) the
Asokan-Shoup-Waidner certified mail protocol that has known vulnerabilities is
not a solution of AGS; (c) the Kremer-Markowitch non-repudiation protocol is a
solution of AGS; and (d) AGS presents a new and symmetric fair non-repudiation
protocol that is attack-free. To our knowledge this is the first application of
synthesis to fair non-repudiation protocols, and our results show how synthesis
can both automatically discover vulnerabilities in protocols and generate correct
protocols. The solution to AGS can be computed efficiently as the secure equilibrium
solution of three-player graph games. '
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Vishwanath
full_name: Raman, Vishwanath
last_name: Raman
citation:
ama: Chatterjee K, Raman V. Assume-guarantee synthesis for digital contract signing.
Formal Aspects of Computing. 2013;26(4):825-859. doi:10.1007/s00165-013-0283-6
apa: Chatterjee, K., & Raman, V. (2013). Assume-guarantee synthesis for digital
contract signing. Formal Aspects of Computing. Springer. https://doi.org/10.1007/s00165-013-0283-6
chicago: Chatterjee, Krishnendu, and Vishwanath Raman. “Assume-Guarantee Synthesis
for Digital Contract Signing.” Formal Aspects of Computing. Springer, 2013.
https://doi.org/10.1007/s00165-013-0283-6.
ieee: K. Chatterjee and V. Raman, “Assume-guarantee synthesis for digital contract
signing,” Formal Aspects of Computing, vol. 26, no. 4. Springer, pp. 825–859,
2013.
ista: Chatterjee K, Raman V. 2013. Assume-guarantee synthesis for digital contract
signing. Formal Aspects of Computing. 26(4), 825–859.
mla: Chatterjee, Krishnendu, and Vishwanath Raman. “Assume-Guarantee Synthesis for
Digital Contract Signing.” Formal Aspects of Computing, vol. 26, no. 4,
Springer, 2013, pp. 825–59, doi:10.1007/s00165-013-0283-6.
short: K. Chatterjee, V. Raman, Formal Aspects of Computing 26 (2013) 825–859.
date_created: 2018-12-11T11:59:51Z
date_published: 2013-07-04T00:00:00Z
date_updated: 2021-01-12T07:00:06Z
day: '04'
department:
- _id: KrCh
doi: 10.1007/s00165-013-0283-6
ec_funded: 1
external_id:
arxiv:
- '1004.2697'
intvolume: ' 26'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1004.2697
month: '07'
oa: 1
oa_version: Preprint
page: 825 - 859
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: Formal Aspects of Computing
publication_status: published
publisher: Springer
publist_id: '3963'
quality_controlled: '1'
scopus_import: 1
status: public
title: Assume-guarantee synthesis for digital contract signing
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 26
year: '2013'
...
---
_id: '2854'
abstract:
- lang: eng
text: We consider concurrent games played on graphs. At every round of a game, each
player simultaneously and independently selects a move; the moves jointly determine
the transition to a successor state. Two basic objectives are the safety objective
to stay forever in a given set of states, and its dual, the reachability objective
to reach a given set of states. First, we present a simple proof of the fact that
in concurrent reachability games, for all ε>0, memoryless ε-optimal strategies
exist. A memoryless strategy is independent of the history of plays, and an ε-optimal
strategy achieves the objective with probability within ε of the value of the
game. In contrast to previous proofs of this fact, our proof is more elementary
and more combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration)
algorithm for concurrent games with reachability objectives. Finally, we present
a strategy-improvement algorithm for turn-based stochastic games (where each player
selects moves in turns) with safety objectives. Our algorithms yield sequences
of player-1 strategies which ensure probabilities of winning that converge monotonically
(from below) to the value of the game. © 2012 Elsevier Inc.
acknowledgement: This work was partially supported in part by the NSF grants CCR-0132780,
CNS-0720884, CCR-0225610, by the Swiss National Science Foundation, ERC Start Grant
Graph Games (Project No. 279307), FWF NFN Grant S11407-N23 (RiSE), and a Microsoft
faculty fellows
article_processing_charge: No
article_type: original
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- 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, De Alfaro L, Henzinger TA. Strategy improvement for concurrent
reachability and turn based stochastic safety games. Journal of Computer and
System Sciences. 2013;79(5):640-657. doi:10.1016/j.jcss.2012.12.001
apa: Chatterjee, K., De Alfaro, L., & Henzinger, T. A. (2013). Strategy improvement
for concurrent reachability and turn based stochastic safety games. Journal
of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2012.12.001
chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Strategy
Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.”
Journal of Computer and System Sciences. Elsevier, 2013. https://doi.org/10.1016/j.jcss.2012.12.001.
ieee: K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Strategy improvement for
concurrent reachability and turn based stochastic safety games,” Journal of
Computer and System Sciences, vol. 79, no. 5. Elsevier, pp. 640–657, 2013.
ista: Chatterjee K, De Alfaro L, Henzinger TA. 2013. Strategy improvement for concurrent
reachability and turn based stochastic safety games. Journal of Computer and System
Sciences. 79(5), 640–657.
mla: Chatterjee, Krishnendu, et al. “Strategy Improvement for Concurrent Reachability
and Turn Based Stochastic Safety Games.” Journal of Computer and System Sciences,
vol. 79, no. 5, Elsevier, 2013, pp. 640–57, doi:10.1016/j.jcss.2012.12.001.
short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System
Sciences 79 (2013) 640–657.
date_created: 2018-12-11T11:59:57Z
date_published: 2013-08-01T00:00:00Z
date_updated: 2021-01-12T07:00:16Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.jcss.2012.12.001
ec_funded: 1
file:
- access_level: open_access
checksum: 6d3ee12cceb946a0abe69594b6a22409
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:48Z
date_updated: 2020-07-14T12:45:51Z
file_id: '5370'
file_name: IST-2015-388-v1+1_1-s2.0-S0022000012001778-main.pdf
file_size: 425488
relation: main_file
file_date_updated: 2020-07-14T12:45:51Z
has_accepted_license: '1'
intvolume: ' 79'
issue: '5'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 640 - 657
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Journal of Computer and System Sciences
publication_status: published
publisher: Elsevier
publist_id: '3938'
pubrep_id: '388'
quality_controlled: '1'
scopus_import: 1
status: public
title: Strategy improvement for concurrent reachability and turn based stochastic
safety 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: 79
year: '2013'
...
---
_id: '2886'
abstract:
- lang: eng
text: We focus on the realizability problem of Message Sequence Graphs (MSG), i.e.
the problem whether a given MSG specification is correctly distributable among
parallel components communicating via messages. This fundamental problem of MSG
is known to be undecidable. We introduce a well motivated restricted class of
MSG, so called controllable-choice MSG, and show that all its models are realizable
and moreover it is decidable whether a given MSG model is a member of this class.
In more detail, this class of MSG specifications admits a deadlock-free realization
by overloading existing messages with additional bounded control data. We also
show that the presented class is the largest known subclass of MSG that allows
for deadlock-free realization.
alternative_title:
- LNCS
author:
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Vojtěch
full_name: Řehák, Vojtěch
last_name: Řehák
citation:
ama: Chmelik M, Řehák V. Controllable-choice message sequence graphs. 2013;7721:118-130.
doi:10.1007/978-3-642-36046-6_12
apa: 'Chmelik, M., & Řehák, V. (2013). Controllable-choice message sequence
graphs. Presented at the MEMICS: Mathematical and Engineering Methods in Computer
Science, Znojmo, Czech Republic: Springer. https://doi.org/10.1007/978-3-642-36046-6_12'
chicago: Chmelik, Martin, and Vojtěch Řehák. “Controllable-Choice Message Sequence
Graphs.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-36046-6_12.
ieee: M. Chmelik and V. Řehák, “Controllable-choice message sequence graphs,” vol.
7721. Springer, pp. 118–130, 2013.
ista: Chmelik M, Řehák V. 2013. Controllable-choice message sequence graphs. 7721,
118–130.
mla: Chmelik, Martin, and Vojtěch Řehák. Controllable-Choice Message Sequence
Graphs. Vol. 7721, Springer, 2013, pp. 118–30, doi:10.1007/978-3-642-36046-6_12.
short: M. Chmelik, V. Řehák, 7721 (2013) 118–130.
conference:
end_date: 2012-10-28
location: Znojmo, Czech Republic
name: 'MEMICS: Mathematical and Engineering Methods in Computer Science'
start_date: 2012-10-25
date_created: 2018-12-11T12:00:09Z
date_published: 2013-01-09T00:00:00Z
date_updated: 2020-08-11T10:09:52Z
day: '09'
department:
- _id: KrCh
doi: 10.1007/978-3-642-36046-6_12
ec_funded: 1
intvolume: ' 7721'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1209.4499
month: '01'
oa: 1
oa_version: Submitted Version
page: 118 - 130
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: Springer
publist_id: '3873'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Controllable-choice message sequence graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7721
year: '2013'
...
---
_id: '3116'
abstract:
- lang: eng
text: Multithreaded programs coordinate their interaction through synchronization
primitives like mutexes and semaphores, which are managed by an OS-provided resource
manager. We propose algorithms for the automatic construction of code-aware resource
managers for multithreaded embedded applications. Such managers use knowledge
about the structure and resource usage (mutex and semaphore usage) of the threads
to guarantee deadlock freedom and progress while managing resources in an efficient
way. Our algorithms compute managers as winning strategies in certain infinite
games, and produce a compact code description of these strategies. We have implemented
the algorithms in the tool Cynthesis. Given a multithreaded program in C, the
tool produces C code implementing a code-aware resource manager. We show in experiments
that Cynthesis produces compact resource managers within a few minutes on a set
of embedded benchmarks with up to 6 threads. © 2012 Springer Science+Business
Media, LLC.
acknowledgement: This research was supported in part by the National Science Foundation
CAREER award CCR-0132780, by the ONR grant N00014-02-1-0671, by the National Science
Foundation grants CCR-0427202 and CCR-0234690, and by the ARP award TO.030.MM.D.
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Marco
full_name: Faella, Marco
last_name: Faella
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Vishwanath
full_name: Raman, Vishwanath
last_name: Raman
citation:
ama: Chatterjee K, De Alfaro L, Faella M, Majumdar R, Raman V. Code aware resource
management. Formal Methods in System Design. 2013;42(2):142-174. doi:10.1007/s10703-012-0170-4
apa: Chatterjee, K., De Alfaro, L., Faella, M., Majumdar, R., & Raman, V. (2013).
Code aware resource management. Formal Methods in System Design. Springer.
https://doi.org/10.1007/s10703-012-0170-4
chicago: Chatterjee, Krishnendu, Luca De Alfaro, Marco Faella, Ritankar Majumdar,
and Vishwanath Raman. “Code Aware Resource Management.” Formal Methods in System
Design. Springer, 2013. https://doi.org/10.1007/s10703-012-0170-4.
ieee: K. Chatterjee, L. De Alfaro, M. Faella, R. Majumdar, and V. Raman, “Code aware
resource management,” Formal Methods in System Design, vol. 42, no. 2.
Springer, pp. 142–174, 2013.
ista: Chatterjee K, De Alfaro L, Faella M, Majumdar R, Raman V. 2013. Code aware
resource management. Formal Methods in System Design. 42(2), 142–174.
mla: Chatterjee, Krishnendu, et al. “Code Aware Resource Management.” Formal
Methods in System Design, vol. 42, no. 2, Springer, 2013, pp. 142–74, doi:10.1007/s10703-012-0170-4.
short: K. Chatterjee, L. De Alfaro, M. Faella, R. Majumdar, V. Raman, Formal Methods
in System Design 42 (2013) 142–174.
date_created: 2018-12-11T12:01:29Z
date_published: 2013-04-01T00:00:00Z
date_updated: 2021-01-12T07:41:10Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/s10703-012-0170-4
intvolume: ' 42'
issue: '2'
language:
- iso: eng
month: '04'
oa_version: None
page: 142 - 174
publication: Formal Methods in System Design
publication_status: published
publisher: Springer
publist_id: '3583'
quality_controlled: '1'
scopus_import: 1
status: public
title: Code aware resource management
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 42
year: '2013'
...
---
_id: '2831'
abstract:
- lang: eng
text: 'We consider Markov decision processes (MDPs) with Büchi (liveness) objectives.
We consider the problem of computing the set of almost-sure winning states from
where the objective can be ensured with probability 1. Our contributions are as
follows: First, we present the first subquadratic symbolic algorithm to compute
the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes
O(n · √ m) symbolic steps as compared to the previous known algorithm that takes
O(n 2) symbolic steps, where n is the number of states and m is the number of
edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic
algorithm takes O(n · √ n) symbolic steps, as compared to the previous known O(n
2) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose
algorithm, with the following two properties: (a) the algorithm iteratively computes
subsets of the almost-sure winning set and its complement, as compared to all
previous algorithms that discover the almost-sure winning set upon termination;
and (b) requires O(n · √ K) symbolic steps, where K is the maximal number of edges
of strongly connected components (scc''s) of the MDP. The win-lose algorithm requires
symbolic computation of scc''s. Third, we improve the algorithm for symbolic scc
computation; the previous known algorithm takes linear symbolic steps, and our
new algorithm improves the constants associated with the linear number of steps.
In the worst case the previous known algorithm takes 5×n symbolic steps, whereas
our new algorithm takes 4×n symbolic steps.'
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Manas
full_name: Joglekar, Manas
last_name: Joglekar
- first_name: Nisarg
full_name: Shah, Nisarg
last_name: Shah
citation:
ama: Chatterjee K, Henzinger MH, Joglekar M, Shah N. Symbolic algorithms for qualitative
analysis of Markov decision processes with Büchi objectives. Formal Methods
in System Design. 2013;42(3):301-327. doi:10.1007/s10703-012-0180-2
apa: Chatterjee, K., Henzinger, M. H., Joglekar, M., & Shah, N. (2013). Symbolic
algorithms for qualitative analysis of Markov decision processes with Büchi objectives.
Formal Methods in System Design. Springer. https://doi.org/10.1007/s10703-012-0180-2
chicago: Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Nisarg
Shah. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes
with Büchi Objectives.” Formal Methods in System Design. Springer, 2013.
https://doi.org/10.1007/s10703-012-0180-2.
ieee: K. Chatterjee, M. H. Henzinger, M. Joglekar, and N. Shah, “Symbolic algorithms
for qualitative analysis of Markov decision processes with Büchi objectives,”
Formal Methods in System Design, vol. 42, no. 3. Springer, pp. 301–327,
2013.
ista: Chatterjee K, Henzinger MH, Joglekar M, Shah N. 2013. Symbolic algorithms
for qualitative analysis of Markov decision processes with Büchi objectives. Formal
Methods in System Design. 42(3), 301–327.
mla: Chatterjee, Krishnendu, et al. “Symbolic Algorithms for Qualitative Analysis
of Markov Decision Processes with Büchi Objectives.” Formal Methods in System
Design, vol. 42, no. 3, Springer, 2013, pp. 301–27, doi:10.1007/s10703-012-0180-2.
short: K. Chatterjee, M.H. Henzinger, M. Joglekar, N. Shah, Formal Methods in System
Design 42 (2013) 301–327.
date_created: 2018-12-11T11:59:49Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2023-02-23T11:23:04Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/s10703-012-0180-2
ec_funded: 1
external_id:
arxiv:
- '1104.3348'
intvolume: ' 42'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.3348
month: '06'
oa: 1
oa_version: Preprint
page: 301 - 327
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: Formal Methods in System Design
publication_status: published
publisher: Springer
publist_id: '3968'
quality_controlled: '1'
related_material:
record:
- id: '3342'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Symbolic algorithms for qualitative analysis of Markov decision processes with
Büchi objectives
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 42
year: '2013'
...
---
_id: '2279'
abstract:
- lang: eng
text: We consider two-player games played on weighted directed graphs with mean-payoff
and total-payoff objectives, two classical quantitative objectives. While for
single-dimensional games the complexity and memory bounds for both objectives
coincide, we show that in contrast to multi-dimensional mean-payoff games that
are known to be coNP-complete, multi-dimensional total-payoff games are undecidable.
We introduce conservative approximations of these objectives, where the payoff
is considered over a local finite window sliding along a play, instead of the
whole play. For single dimension, we show that (i) if the window size is polynomial,
deciding the winner takes polynomial time, and (ii) the existence of a bounded
window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff
games. For multiple dimensions, we show that (i) the problem with fixed window
size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to
decide the existence of a bounded window.
acknowledgement: 279307; ERC; Fonds National de la Reserche Luxembourg; 279499; ERC;
Fonds National de la Reserche Luxembourg
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Mickael
full_name: Randour, Mickael
last_name: Randour
- first_name: Jean
full_name: Raskin, Jean
last_name: Raskin
citation:
ama: Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff
through windows. 2013;8172:118-132. doi:10.1007/978-3-319-02444-8_10
apa: 'Chatterjee, K., Doyen, L., Randour, M., & Raskin, J. (2013). Looking at
mean-payoff and total-payoff through windows. Presented at the ATVA: Automated
Technology for Verification and Analysis, Hanoi, Vietnam: Springer. https://doi.org/10.1007/978-3-319-02444-8_10'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin.
“Looking at Mean-Payoff and Total-Payoff through Windows.” Lecture Notes in Computer
Science. Springer, 2013. https://doi.org/10.1007/978-3-319-02444-8_10.
ieee: K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff
and total-payoff through windows,” vol. 8172. Springer, pp. 118–132, 2013.
ista: Chatterjee K, Doyen L, Randour M, Raskin J. 2013. Looking at mean-payoff and
total-payoff through windows. 8172, 118–132.
mla: Chatterjee, Krishnendu, et al. Looking at Mean-Payoff and Total-Payoff through
Windows. Vol. 8172, Springer, 2013, pp. 118–32, doi:10.1007/978-3-319-02444-8_10.
short: K. Chatterjee, L. Doyen, M. Randour, J. Raskin, 8172 (2013) 118–132.
conference:
end_date: 2013-10-18
location: Hanoi, Vietnam
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2013-10-15
date_created: 2018-12-11T11:56:44Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2023-02-23T12:22:51Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-319-02444-8_10
ec_funded: 1
intvolume: ' 8172'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1302.4248
month: '01'
oa: 1
oa_version: Preprint
page: 118 - 132
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_status: published
publisher: Springer
publist_id: '4656'
quality_controlled: '1'
related_material:
record:
- id: '523'
relation: later_version
status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Looking at mean-payoff and total-payoff through windows
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8172
year: '2013'
...
---
_id: '5399'
abstract:
- lang: eng
text: In this work we present a flexible tool for tumor progression, which simulates
the evolutionary dynamics of cancer. Tumor progression implements a multi-type
branching process where the key parameters are the fitness landscape, the mutation
rate, and the average time of cell division. The fitness of a cancer cell depends
on the mutations it has accumulated. The input to our tool could be any fitness
landscape, mutation rate, and cell division time, and the tool produces the growth
dynamics and all relevant statistics.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Johannes
full_name: Reiter, Johannes
id: 4A918E98-F248-11E8-B48F-1D18A9856A87
last_name: Reiter
orcid: 0000-0002-0170-7353
- first_name: Ivana
full_name: Bozic, Ivana
last_name: Bozic
- 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: 'Reiter J, Bozic I, Chatterjee K, Nowak M. TTP: Tool for Tumor Progression.
IST Austria; 2013. doi:10.15479/AT:IST-2013-104-v1-1'
apa: 'Reiter, J., Bozic, I., Chatterjee, K., & Nowak, M. (2013). TTP: Tool
for Tumor Progression. IST Austria. https://doi.org/10.15479/AT:IST-2013-104-v1-1'
chicago: 'Reiter, Johannes, Ivana Bozic, Krishnendu Chatterjee, and Martin Nowak.
TTP: Tool for Tumor Progression. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-104-v1-1.'
ieee: 'J. Reiter, I. Bozic, K. Chatterjee, and M. Nowak, TTP: Tool for Tumor
Progression. IST Austria, 2013.'
ista: 'Reiter J, Bozic I, Chatterjee K, Nowak M. 2013. TTP: Tool for Tumor Progression,
IST Austria, 17p.'
mla: 'Reiter, Johannes, et al. TTP: Tool for Tumor Progression. IST Austria,
2013, doi:10.15479/AT:IST-2013-104-v1-1.'
short: 'J. Reiter, I. Bozic, K. Chatterjee, M. Nowak, TTP: Tool for Tumor Progression,
IST Austria, 2013.'
date_created: 2018-12-12T11:39:07Z
date_published: 2013-01-11T00:00:00Z
date_updated: 2023-02-23T10:23:57Z
day: '11'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-104-v1-1
file:
- access_level: open_access
checksum: 2cc8c6e157eca1271128db80bb3dec80
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:20Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5542'
file_name: IST-2013-104-v1+1_tumortool.pdf
file_size: 1471954
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '17'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '104'
related_material:
record:
- id: '2000'
relation: later_version
status: public
status: public
title: 'TTP: Tool for Tumor Progression'
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2295'
abstract:
- lang: eng
text: We consider partially observable Markov decision processes (POMDPs) with ω-regular
conditions specified as parity objectives. The qualitative analysis problem given
a POMDP 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, we establish decidability (with optimal EXPTIME-complete
complexity) of the qualitative analysis problems for POMDPs with all parity objectives
under finite-memory strategies. We also establish asymptotically optimal (exponential)
memory bounds.
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: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Mathieu
full_name: Tracol, Mathieu
id: 3F54FA38-F248-11E8-B48F-1D18A9856A87
last_name: Tracol
citation:
ama: Chatterjee K, Chmelik M, Tracol M. What is decidable about partially observable
Markov decision processes with omega-regular objectives. 2013;23:165-180. doi:10.4230/LIPIcs.CSL.2013.165
apa: 'Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable about
partially observable Markov decision processes with omega-regular objectives.
Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2013.165'
chicago: Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. “What Is Decidable
about Partially Observable Markov Decision Processes with Omega-Regular Objectives.”
Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.165.
ieee: K. Chatterjee, M. Chmelik, and M. Tracol, “What is decidable about partially
observable Markov decision processes with omega-regular objectives,” vol. 23.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 165–180, 2013.
ista: Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially
observable Markov decision processes with omega-regular objectives. 23, 165–180.
mla: Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable
Markov Decision Processes with Omega-Regular Objectives. Vol. 23, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 165–80, doi:10.4230/LIPIcs.CSL.2013.165.
short: K. Chatterjee, M. Chmelik, M. Tracol, 23 (2013) 165–180.
conference:
end_date: 2013-09-05
location: Torino, Italy
name: 'CSL: Computer Science Logic'
start_date: 2013-09-02
date_created: 2018-12-11T11:56:50Z
date_published: 2013-08-27T00:00:00Z
date_updated: 2023-02-23T12:24:38Z
day: '27'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CSL.2013.165
ec_funded: 1
file:
- access_level: open_access
checksum: ba2828322955574d9283bea0e17a37a6
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:42Z
date_updated: 2020-07-14T12:45:37Z
file_id: '4766'
file_name: IST-2017-756-v1+1_2.pdf
file_size: 345171
relation: main_file
file_date_updated: 2020-07-14T12:45:37Z
has_accepted_license: '1'
intvolume: ' 23'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 165 - 180
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: '4633'
pubrep_id: '756'
quality_controlled: '1'
related_material:
record:
- id: '1477'
relation: later_version
status: public
- id: '5400'
relation: earlier_version
status: public
scopus_import: 1
series_title: Leibniz International Proceedings in Informatics
status: public
title: What is decidable about partially observable Markov decision processes with
omega-regular objectives
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: '5403'
abstract:
- lang: eng
text: 'We consider concurrent games played by two-players on a finite state graph,
where in every round the players simultaneously choose a move, and the current
state along with the joint moves determine the successor state. We study the most
fundamental objective for concurrent games, namely, mean-payoff or limit-average
objective, where a reward is associated to every transition, and the goal of player
1 is to maximize the long-run average of the rewards, and the objective of player
2 is strictly the opposite (i.e., the games are zero-sum). The path constraint
for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward,
or arbitrarily close to it; or quantitative, i.e., a given threshold between the
minimal and maximal reward. We consider the computation of the almost-sure (resp.
positive) winning sets, where player 1 can ensure that the path constraint is
satisfied with probability 1 (resp. positive probability). Almost-sure winning
with qualitative constraint exactly corresponds to the question whether there
exists a strategy to ensure that the payoff is the maximal reward of the game.
Our main results for qualitative path constraints are as follows: (1) we establish
qualitative determinacy results that show for every state either player 1 has
a strategy to ensure almost-sure (resp. positive) winning against all player-2
strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive)
winning against all player-1 strategies; (2) we present optimal strategy complexity
results that precisely characterize the classes of strategies required for almost-sure
and positive winning for both players; and (3) we present quadratic time algorithms
to compute the almost-sure and the positive winning sets, matching the best known
bound of the algorithms for much simpler problems (such as reachability objectives).
For quantitative constraints we show that a polynomial time solution for the almost-sure
or the positive winning set would imply a solution to a long-standing open problem
(of solving the value problem of mean-payoff games) that is not known to be in
polynomial time.'
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
citation:
ama: Chatterjee K, Ibsen-Jensen R. Qualitative Analysis of Concurrent Mean-Payoff
Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-126-v1-1
apa: Chatterjee, K., & Ibsen-Jensen, R. (2013). Qualitative analysis of concurrent
mean-payoff games. IST Austria. https://doi.org/10.15479/AT:IST-2013-126-v1-1
chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. Qualitative Analysis
of Concurrent Mean-Payoff Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-126-v1-1.
ieee: K. Chatterjee and R. Ibsen-Jensen, Qualitative analysis of concurrent mean-payoff
games. IST Austria, 2013.
ista: Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff
games, IST Austria, 33p.
mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. Qualitative Analysis of
Concurrent Mean-Payoff Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-126-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, Qualitative Analysis of Concurrent Mean-Payoff
Games, IST Austria, 2013.
date_created: 2018-12-12T11:39:08Z
date_published: 2013-07-03T00:00:00Z
date_updated: 2023-02-23T12:22:53Z
day: '03'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-126-v1-1
file:
- access_level: open_access
checksum: 063868c665beec37bf28160e2a695746
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:49Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5510'
file_name: IST-2013-126-v1+1_soda_full.pdf
file_size: 434523
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: '33'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '126'
related_material:
record:
- id: '524'
relation: later_version
status: public
status: public
title: Qualitative analysis of concurrent mean-payoff games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5400'
abstract:
- lang: eng
text: We consider partially observable Markov decision processes (POMDPs) with ω-regular
conditions specified as parity objectives. The class of ω-regular languages extends
regular languages to infinite strings and provides a robust specification language
to express all properties used in verification, and parity objectives are canonical
forms to express ω-regular conditions. The qualitative analysis problem given
a POMDP and a parity objective asks whether there is a strategy to ensure that
the objective is satis- fied with probability 1 (resp. positive probability).
While the qualitative analysis problems are known to be undecidable even for very
special cases of parity objectives, we establish decidability (with optimal complexity)
of the qualitative analysis problems for POMDPs with all parity objectives under
finite- memory strategies. We establish asymptotically optimal (exponential) memory
bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory
strategies for POMDPs with parity objectives.
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: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Mathieu
full_name: Tracol, Mathieu
id: 3F54FA38-F248-11E8-B48F-1D18A9856A87
last_name: Tracol
citation:
ama: Chatterjee K, Chmelik M, Tracol M. What Is Decidable about Partially Observable
Markov Decision Processes with ω-Regular Objectives. IST Austria; 2013. doi:10.15479/AT:IST-2013-109-v1-1
apa: Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable
about partially observable Markov decision processes with ω-regular objectives.
IST Austria. https://doi.org/10.15479/AT:IST-2013-109-v1-1
chicago: Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. What Is
Decidable about Partially Observable Markov Decision Processes with ω-Regular
Objectives. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-109-v1-1.
ieee: K. Chatterjee, M. Chmelik, and M. Tracol, What is decidable about partially
observable Markov decision processes with ω-regular objectives. IST Austria,
2013.
ista: Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially
observable Markov decision processes with ω-regular objectives, IST Austria, 41p.
mla: Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable
Markov Decision Processes with ω-Regular Objectives. IST Austria, 2013, doi:10.15479/AT:IST-2013-109-v1-1.
short: K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable
Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013.
date_created: 2018-12-12T11:39:07Z
date_published: 2013-02-20T00:00:00Z
date_updated: 2023-02-23T10:36:45Z
day: '20'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-109-v1-1
file:
- access_level: open_access
checksum: cbba40210788a1b22c6cf06433b5ed6f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:06Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5467'
file_name: IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf
file_size: 483407
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '41'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '109'
related_material:
record:
- id: '1477'
relation: later_version
status: public
- id: '2295'
relation: later_version
status: public
status: public
title: What is decidable about partially observable Markov decision processes with
ω-regular objectives
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...