---
_id: '524'
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 each 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 of 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 that 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 turn-based deterministic mean-payoff
games) that is not known to be solvable in polynomial time.'
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. *Information and Computation*. 2015;242(6):2-24. doi:10.1016/j.ic.2015.03.009
apa: Chatterjee, K., & Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent
mean payoff games. *Information and Computation*. Elsevier. https://doi.org/10.1016/j.ic.2015.03.009
chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis
of Concurrent Mean Payoff Games.” *Information and Computation*. Elsevier,
2015. https://doi.org/10.1016/j.ic.2015.03.009.
ieee: K. Chatterjee and R. Ibsen-Jensen, “Qualitative analysis of concurrent mean
payoff games,” *Information and Computation*, vol. 242, no. 6. Elsevier,
pp. 2–24, 2015.
ista: Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean
payoff games. Information and Computation. 242(6), 2–24.
mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent
Mean Payoff Games.” *Information and Computation*, vol. 242, no. 6, Elsevier,
2015, pp. 2–24, doi:10.1016/j.ic.2015.03.009.
short: K. Chatterjee, R. Ibsen-Jensen, Information and Computation 242 (2015) 2–24.
date_created: 2018-12-11T11:46:57Z
date_published: 2015-10-11T00:00:00Z
date_updated: 2021-01-12T08:01:49Z
day: '11'
department:
- _id: KrCh
doi: 10.1016/j.ic.2015.03.009
external_id:
arxiv:
- '1409.5306'
intvolume: ' 242'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1409.5306
month: '10'
oa: 1
oa_version: Preprint
page: 2 - 24
publication: Information and Computation
publication_status: published
publisher: Elsevier
publist_id: '7295'
quality_controlled: '1'
related_material:
record:
- id: '5403'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Qualitative analysis of concurrent mean payoff games
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 242
year: '2015'
...
---
_id: '532'
abstract:
- lang: eng
text: Ethylene is a gaseous phytohormone that plays vital roles in plant growth
and development. Previous studies uncovered EIN2 as an essential signal transducer
linking ethylene perception on ER to transcriptional regulation in the nucleus
through a “cleave and shuttle” model. In this study, we report another mechanism
of EIN2-mediated ethylene signaling, whereby EIN2 imposes the translational repression
of EBF1 and EBF2 mRNA. We find that the EBF1/2 3′ UTRs mediate EIN2-directed translational
repression and identify multiple poly-uridylates (PolyU) motifs as functional
cis elements of 3′ UTRs. Furthermore, we demonstrate that ethylene induces EIN2
to associate with 3′ UTRs and target EBF1/2 mRNA to cytoplasmic processing-body
(P-body) through interacting with multiple P-body factors, including EIN5 and
PABs. Our study illustrates translational regulation as a key step in ethylene
signaling and presents mRNA 3′ UTR functioning as a “signal transducer” to sense
and relay cellular signaling in plants.
author:
- first_name: Wenyang
full_name: Li, Wenyang
last_name: Li
- first_name: Mengdi
full_name: Ma, Mengdi
last_name: Ma
- first_name: Ying
full_name: Feng, Ying
last_name: Feng
- first_name: Hongjiang
full_name: Li, Hongjiang
id: 33CA54A6-F248-11E8-B48F-1D18A9856A87
last_name: Li
orcid: 0000-0001-5039-9660
- first_name: Yichuan
full_name: Wang, Yichuan
last_name: Wang
- first_name: Yutong
full_name: Ma, Yutong
last_name: Ma
- first_name: Mingzhe
full_name: Li, Mingzhe
last_name: Li
- first_name: Fengying
full_name: An, Fengying
last_name: An
- first_name: Hongwei
full_name: Guo, Hongwei
last_name: Guo
citation:
ama: Li W, Ma M, Feng Y, et al. EIN2-directed translational regulation of ethylene
signaling in arabidopsis. *Cell*. 2015;163(3):670-683. doi:10.1016/j.cell.2015.09.037
apa: Li, W., Ma, M., Feng, Y., Li, H., Wang, Y., Ma, Y., … Guo, H. (2015). EIN2-directed
translational regulation of ethylene signaling in arabidopsis. *Cell*. Cell
Press. https://doi.org/10.1016/j.cell.2015.09.037
chicago: Li, Wenyang, Mengdi Ma, Ying Feng, Hongjiang Li, Yichuan Wang, Yutong Ma,
Mingzhe Li, Fengying An, and Hongwei Guo. “EIN2-Directed Translational Regulation
of Ethylene Signaling in Arabidopsis.” *Cell*. Cell Press, 2015. https://doi.org/10.1016/j.cell.2015.09.037.
ieee: W. Li *et al.*, “EIN2-directed translational regulation of ethylene signaling
in arabidopsis,” *Cell*, vol. 163, no. 3. Cell Press, pp. 670–683, 2015.
ista: Li W, Ma M, Feng Y, Li H, Wang Y, Ma Y, Li M, An F, Guo H. 2015. EIN2-directed
translational regulation of ethylene signaling in arabidopsis. Cell. 163(3), 670–683.
mla: Li, Wenyang, et al. “EIN2-Directed Translational Regulation of Ethylene Signaling
in Arabidopsis.” *Cell*, vol. 163, no. 3, Cell Press, 2015, pp. 670–83, doi:10.1016/j.cell.2015.09.037.
short: W. Li, M. Ma, Y. Feng, H. Li, Y. Wang, Y. Ma, M. Li, F. An, H. Guo, Cell
163 (2015) 670–683.
date_created: 2018-12-11T11:47:00Z
date_published: 2015-10-22T00:00:00Z
date_updated: 2021-01-12T08:01:27Z
day: '22'
department:
- _id: JiFr
doi: 10.1016/j.cell.2015.09.037
intvolume: ' 163'
issue: '3'
language:
- iso: eng
month: '10'
oa_version: None
page: 670 - 683
publication: Cell
publication_status: published
publisher: Cell Press
publist_id: '7285'
quality_controlled: '1'
scopus_import: 1
status: public
title: EIN2-directed translational regulation of ethylene signaling in arabidopsis
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 163
year: '2015'
...
---
_id: '5429'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) with multiple limit-average
(or mean-payoff) objectives. \r\nThere have been two different views: (i) the
expectation semantics, where the goal is to optimize the expected mean-payoff
objective, and (ii) the satisfaction semantics, where the goal is to maximize
the probability of runs such that the mean-payoff value stays above a given vector.
\ \r\nWe consider the problem where the goal is to optimize the expectation under
the constraint that the satisfaction semantics is ensured, and thus consider a
generalization that unifies the existing semantics.\r\nOur problem captures the
notion of optimization with respect to strategies that are risk-averse (i.e.,
ensures certain probabilistic guarantee).\r\nOur main results are algorithms for
the decision problem which are always polynomial in the size of the MDP. We also
show that an approximation of the Pareto-curve can be computed in time polynomial
in the size of the MDP, and the approximation factor, but exponential in the number
of dimensions.\r\nFinally, we present a complete characterization of the strategy
complexity (in terms of memory bounds and randomization) required to solve our
problem."
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: Zuzana
full_name: Komarkova, Zuzana
last_name: Komarkova
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: Chatterjee K, Komarkova Z, Kretinsky J. *Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes*. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v1-1
apa: Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). *Unifying two
views on multiple mean-payoff objectives in Markov decision processes*. IST
Austria. https://doi.org/10.15479/AT:IST-2015-318-v1-1
chicago: Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. *Unifying
Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes*.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v1-1.
ieee: K. Chatterjee, Z. Komarkova, and J. Kretinsky, *Unifying two views on multiple
mean-payoff objectives in Markov decision processes*. IST Austria, 2015.
ista: Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple
mean-payoff objectives in Markov decision processes, IST Austria, 41p.
mla: Chatterjee, Krishnendu, et al. *Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes*. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v1-1.
short: K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple
Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.
date_created: 2018-12-12T11:39:17Z
date_published: 2015-01-12T00:00:00Z
date_updated: 2021-01-12T08:02:15Z
day: '12'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-318-v1-1
file:
- access_level: open_access
checksum: e4869a584567c506349abda9c8ec7db3
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:11Z
date_updated: 2020-07-14T12:46:52Z
file_id: '5533'
file_name: IST-2015-318-v1+1_main.pdf
file_size: 689863
relation: main_file
file_date_updated: 2020-07-14T12:46:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '41'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '318'
related_material:
record:
- id: '466'
relation: later_version
status: public
- id: '1657'
relation: later_version
status: public
- id: '5435'
relation: later_version
status: public
status: public
title: Unifying two views on multiple mean-payoff objectives in Markov decision processes
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5430'
abstract:
- lang: eng
text: We consider the core algorithmic problems related to verification of systems
with respect to three classical quantitative properties, namely, the mean- payoff
property, the ratio property, and the minimum initial credit for energy property.
The algorithmic problem given a graph and a quantitative property asks to compute
the optimal value (the infimum value over all traces) from every node of the graph.
We consider graphs with constant treewidth, and it is well-known that the control-flow
graphs of most programs have constant treewidth. Let n denote the number of nodes
of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) )
and W the largest absolute value of the weights. Our main theoretical results
are as follows. First, for constant treewidth graphs we present an algorithm that
approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time
O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms
that require quadratic time. Second, for the ratio property we present an algorithm
that for constant treewidth graphs works in time O ( n · log( | a · b · n | ))
= O ( n · log( n · W )) , when the output is a b , as compared to the previously
best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the
minimum initial credit problem we show that (i) for general graphs the problem
can be solved in O ( n 2 · m ) time and the associated decision problem can be
solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n
· W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth
graphs we present an algorithm that requires O ( n · log n ) time, improving the
previous known O ( n 4 · log( n · W )) bound. We have implemented some of our
algorithms and show that they present a significant speedup on standard benchmarks.
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: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. *Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs*. IST Austria; 2015. doi:10.15479/AT:IST-2015-319-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). *Faster
algorithms for quantitative verification in constant treewidth graphs*. IST
Austria. https://doi.org/10.15479/AT:IST-2015-319-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
*Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs*.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-319-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, *Faster algorithms
for quantitative verification in constant treewidth graphs*. IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for
quantitative verification in constant treewidth graphs, IST Austria, 31p.
mla: Chatterjee, Krishnendu, et al. *Faster Algorithms for Quantitative Verification
in Constant Treewidth Graphs*. IST Austria, 2015, doi:10.15479/AT:IST-2015-319-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs, IST Austria, 2015.
date_created: 2018-12-12T11:39:17Z
date_published: 2015-02-10T00:00:00Z
date_updated: 2021-01-12T08:02:17Z
day: '10'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-319-v1-1
file:
- access_level: open_access
checksum: 62c6ea01e342553dcafb88a070fb1ad5
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:21Z
date_updated: 2020-07-14T12:46:52Z
file_id: '5482'
file_name: IST-2015-319-v1+1_long.pdf
file_size: 1089651
relation: main_file
file_date_updated: 2020-07-14T12:46:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '31'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '319'
related_material:
record:
- id: '1607'
relation: later_version
status: public
- id: '5437'
relation: later_version
status: public
status: public
title: Faster algorithms for quantitative verification in constant treewidth graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5431'
abstract:
- lang: eng
text: "We consider finite-state concurrent stochastic games, played by k>=2 players
for an infinite number of rounds, where in every round, each player simultaneously
and independently of the other players chooses an action, whereafter the successor
state is determined by a probability distribution given by the current state and
the chosen actions. We consider reachability objectives that given a target set
of states require that some state in the target set is visited, and the dual safety
objectives that given a target set require that only states in the target set
are visited. We are interested in the complexity of stationary strategies measured
by their patience, which is defined as the inverse of the smallest non-zero probability
employed.\r\n\r\n Our main results are as follows: We show that in two-player
zero-sum concurrent stochastic games (with reachability objective for one player
and the complementary safety objective for the other player): (i) the optimal
bound on the patience of optimal and epsilon-optimal strategies, for both players
is doubly exponential; and (ii) even in games with a single non-absorbing state
exponential (in the number of actions) patience is necessary. In general we study
the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that
if there is at least one player with reachability objective, then doubly-exponential
patience is needed in general for epsilon-Nash equilibrium strategies, whereas
in contrast if all players have safety objectives, then the optimal bound on patience
for epsilon-Nash equilibrium strategies is only exponential."
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: Kristoffer
full_name: Hansen, Kristoffer
last_name: Hansen
citation:
ama: Chatterjee K, Ibsen-Jensen R, Hansen K. *The Patience of Concurrent Stochastic
Games with Safety and Reachability Objectives*. IST Austria; 2015. doi:10.15479/AT:IST-2015-322-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Hansen, K. (2015). *The patience
of concurrent stochastic games with safety and reachability objectives*. IST
Austria. https://doi.org/10.15479/AT:IST-2015-322-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Kristoffer Hansen. *The
Patience of Concurrent Stochastic Games with Safety and Reachability Objectives*.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-322-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and K. Hansen, *The patience of concurrent
stochastic games with safety and reachability objectives*. IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic
games with safety and reachability objectives, IST Austria, 25p.
mla: Chatterjee, Krishnendu, et al. *The Patience of Concurrent Stochastic Games
with Safety and Reachability Objectives*. IST Austria, 2015, doi:10.15479/AT:IST-2015-322-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic
Games with Safety and Reachability Objectives, IST Austria, 2015.
date_created: 2018-12-12T11:39:17Z
date_published: 2015-02-19T00:00:00Z
date_updated: 2021-01-12T08:02:13Z
day: '19'
ddc:
- '005'
- '519'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-322-v1-1
file:
- access_level: open_access
checksum: bfb858262c30445b8e472c40069178a2
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:31Z
date_updated: 2020-07-14T12:46:53Z
file_id: '5491'
file_name: IST-2015-322-v1+1_safetygames.pdf
file_size: 661015
relation: main_file
file_date_updated: 2020-07-14T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '25'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '322'
status: public
title: The patience of concurrent stochastic games with safety and reachability objectives
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5432'
abstract:
- lang: eng
text: "Evolution occurs in populations of reproducing individuals. The structure
of the population affects the outcome of the evolutionary process. Evolutionary
graph theory is a powerful approach to study this phenomenon. There are two graphs.
The interaction graph specifies who interacts with whom in the context of evolution.The
replacement graph specifies who competes with whom for reproduction. \r\nThe vertices
of the two graphs are the same, and each vertex corresponds to an individual of
the population. A key quantity is the fixation probability of a new mutant. It
is defined as the probability that a newly introduced mutant (on a single vertex)
generates a lineage of offspring which eventually takes over the entire population
of resident individuals. The basic computational questions are as follows: (i)
the qualitative question asks whether the fixation probability is positive; and
(ii) the quantitative approximation question asks for an approximation of the
fixation probability. \r\nOur main results are:\r\n(1) We show that the qualitative
question is NP-complete and the quantitative approximation question is #P-hard
in the special case when the interaction and the replacement graphs coincide and
even with the restriction that the resident individuals do not reproduce (which
corresponds to an invading population taking over an empty structure).\r\n(2)
We show that in general the qualitative question is PSPACE-complete and the quantitative
approximation question is PSPACE-hard and can be solved in exponential time.\r\n"
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: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Chatterjee K, Ibsen-Jensen R, Nowak M. *The Complexity of Evolutionary Games
on Graphs*. IST Austria; 2015. doi:10.15479/AT:IST-2015-323-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2015). *The complexity
of evolutionary games on graphs*. IST Austria. https://doi.org/10.15479/AT:IST-2015-323-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. *The Complexity
of Evolutionary Games on Graphs*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-323-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, *The complexity of evolutionary
games on graphs*. IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary
games on graphs, IST Austria, 29p.
mla: Chatterjee, Krishnendu, et al. *The Complexity of Evolutionary Games on Graphs*.
IST Austria, 2015, doi:10.15479/AT:IST-2015-323-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary
Games on Graphs, IST Austria, 2015.
date_created: 2018-12-12T11:39:18Z
date_published: 2015-02-19T00:00:00Z
date_updated: 2021-01-12T08:02:20Z
day: '19'
ddc:
- '005'
- '576'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-323-v1-1
file:
- access_level: open_access
checksum: 546c1b291d545e7b24aaaf4199dac671
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:57Z
date_updated: 2020-07-14T12:46:53Z
file_id: '5519'
file_name: IST-2015-323-v1+1_main.pdf
file_size: 576347
relation: main_file
file_date_updated: 2020-07-14T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '29'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '323'
related_material:
record:
- id: '5421'
relation: earlier_version
status: public
- id: '5440'
relation: later_version
status: public
status: public
title: The complexity of evolutionary games on graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5434'
abstract:
- lang: eng
text: DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate
in an uncertain environment independently to achieve a joint objective. DEC-POMDPs
have been studied with finite-horizon and infinite-horizon discounted-sum objectives,
and there exist solvers both for exact and approximate solutions. In this work
we consider Goal-DEC-POMDPs, where given a set of target states, the objective
is to ensure that the target set is reached with minimal cost. We consider the
indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum,
where absorbing goal states have zero-cost) problem. We present a new method to
solve the problem that extends methods for finite-horizon DEC- POMDPs and the
RTDP-Bel approach for POMDPs. We present experimental results on several examples,
and show our approach presents promising results.
alternative_title:
- IST Austria Technical Report
author:
- first_name: '1'
full_name: Anonymous, 1
last_name: Anonymous
- first_name: '2'
full_name: Anonymous, 2
last_name: Anonymous
citation:
ama: Anonymous 1, Anonymous 2. *Optimal Cost Indefinite-Horizon Reachability in
Goal DEC-POMDPs*. IST Austria; 2015.
apa: Anonymous, 1, & Anonymous, 2. (2015). *Optimal cost indefinite-horizon
reachability in goal DEC-POMDPs*. IST Austria.
chicago: Anonymous, 1, and 2 Anonymous. *Optimal Cost Indefinite-Horizon Reachability
in Goal DEC-POMDPs*. IST Austria, 2015.
ieee: 1 Anonymous and 2 Anonymous, *Optimal cost indefinite-horizon reachability
in goal DEC-POMDPs*. IST Austria, 2015.
ista: Anonymous 1, Anonymous 2. 2015. Optimal cost indefinite-horizon reachability
in goal DEC-POMDPs, IST Austria, 16p.
mla: Anonymous, 1, and 2 Anonymous. *Optimal Cost Indefinite-Horizon Reachability
in Goal DEC-POMDPs*. IST Austria, 2015.
short: 1 Anonymous, 2 Anonymous, Optimal Cost Indefinite-Horizon Reachability in
Goal DEC-POMDPs, IST Austria, 2015.
date_created: 2018-12-12T11:39:18Z
date_published: 2015-02-19T00:00:00Z
date_updated: 2020-07-14T23:04:59Z
day: '19'
ddc:
- '000'
file:
- access_level: open_access
checksum: 8542fd0b10aed7811cd41077b8ccb632
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:14Z
date_updated: 2020-07-14T12:46:53Z
file_id: '5475'
file_name: IST-2015-326-v1+1_main.pdf
file_size: 378162
relation: main_file
- access_level: closed
checksum: 84c31c537bdaf7a91909f18d25d640ab
content_type: text/plain
creator: dernst
date_created: 2019-04-16T13:00:33Z
date_updated: 2020-07-14T12:46:53Z
file_id: '6317'
file_name: IST-2015-326-v1+2_authors.txt
file_size: 64
relation: main_file
file_date_updated: 2020-07-14T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '16'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '326'
status: public
title: Optimal cost indefinite-horizon reachability in goal DEC-POMDPs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5435'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) with multiple limit-average
(or mean-payoff) objectives. \r\nThere have been two different views: (i) the
expectation semantics, where the goal is to optimize the expected mean-payoff
objective, and (ii) the satisfaction semantics, where the goal is to maximize
the probability of runs such that the mean-payoff value stays above a given vector.
\ \r\nWe consider the problem where the goal is to optimize the expectation under
the constraint that the satisfaction semantics is ensured, and thus consider a
generalization that unifies the existing semantics. Our problem captures the notion
of optimization with respect to strategies that are risk-averse (i.e., ensures
certain probabilistic guarantee).\r\nOur main results are algorithms for the decision
problem which are always polynomial in the size of the MDP.\r\nWe also show that
an approximation of the Pareto-curve can be computed in time polynomial in the
size of the MDP, and the approximation factor, but exponential in the number of
dimensions. Finally, we present a complete characterization of the strategy complexity
(in terms of memory bounds and randomization) required to solve our problem."
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: Zuzana
full_name: Komarkova, Zuzana
last_name: Komarkova
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
citation:
ama: Chatterjee K, Komarkova Z, Kretinsky J. *Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes*. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v2-1
apa: Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). *Unifying two
views on multiple mean-payoff objectives in Markov decision processes*. IST
Austria. https://doi.org/10.15479/AT:IST-2015-318-v2-1
chicago: Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. *Unifying
Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes*.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v2-1.
ieee: K. Chatterjee, Z. Komarkova, and J. Kretinsky, *Unifying two views on multiple
mean-payoff objectives in Markov decision processes*. IST Austria, 2015.
ista: Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple
mean-payoff objectives in Markov decision processes, IST Austria, 51p.
mla: Chatterjee, Krishnendu, et al. *Unifying Two Views on Multiple Mean-Payoff
Objectives in Markov Decision Processes*. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v2-1.
short: K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple
Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-02-23T00:00:00Z
date_updated: 2021-01-12T08:02:15Z
day: '23'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-318-v2-1
file:
- access_level: open_access
checksum: 75284adec80baabdfe71ff9ebbc27445
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:03Z
date_updated: 2020-07-14T12:46:53Z
file_id: '5525'
file_name: IST-2015-318-v2+1_main.pdf
file_size: 717630
relation: main_file
file_date_updated: 2020-07-14T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '51'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '327'
related_material:
record:
- id: '5429'
relation: earlier_version
status: public
- id: '466'
relation: later_version
status: public
- id: '1657'
relation: later_version
status: public
status: public
title: Unifying two views on multiple mean-payoff objectives in Markov decision processes
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5436'
abstract:
- lang: eng
text: "Recently there has been a significant effort to handle quantitative properties
in formal verification and synthesis. While weighted automata over finite and
infinite words provide a natural and flexible framework to express quantitative
properties, perhaps surprisingly, some basic system properties such as average
response time cannot be expressed using weighted automata, nor in any other know
decidable formalism. In this work, we introduce nested weighted automata as a
natural extension of weighted automata which makes it possible to express important
quantitative properties such as average response time.\r\nIn nested weighted automata,
a master automaton spins off and collects results from weighted slave automata,
each of which computes a quantity along a finite portion of an infinite word.
Nested weighted automata can be viewed as the quantitative analogue of monitor
automata, which are used in run-time verification. We establish an almost complete
decidability picture for the basic decision problems about nested weighted automata,
and illustrate their applicability in several domains. In particular, nested weighted
automata can be used to decide average response time properties."
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
citation:
ama: Chatterjee K, Henzinger TA, Otop J. *Nested Weighted Automata*. IST Austria;
2015. doi:10.15479/AT:IST-2015-170-v2-2
apa: Chatterjee, K., Henzinger, T. A., & Otop, J. (2015). *Nested weighted
automata*. IST Austria. https://doi.org/10.15479/AT:IST-2015-170-v2-2
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. *Nested Weighted
Automata*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-170-v2-2.
ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, *Nested weighted automata*.
IST Austria, 2015.
ista: Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria,
29p.
mla: Chatterjee, Krishnendu, et al. *Nested Weighted Automata*. IST Austria,
2015, doi:10.15479/AT:IST-2015-170-v2-2.
short: K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria,
2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-04-24T00:00:00Z
date_updated: 2021-01-12T08:02:16Z
day: '24'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2015-170-v2-2
file:
- access_level: open_access
checksum: 3c402f47d3669c28d04d1af405a08e3f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:19Z
date_updated: 2020-07-14T12:46:54Z
file_id: '5541'
file_name: IST-2015-170-v2+2_report.pdf
file_size: 569991
relation: main_file
file_date_updated: 2020-07-14T12:46:54Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '29'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '331'
related_material:
record:
- id: '5415'
relation: earlier_version
status: public
- id: '467'
relation: later_version
status: public
- id: '1656'
relation: later_version
status: public
status: public
title: Nested weighted automata
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '5437'
abstract:
- lang: eng
text: "We consider the core algorithmic problems related to verification of systems
with respect to three classical quantitative properties, namely, the mean-payoff
property, the ratio property, and the minimum initial credit for energy property.
\r\nThe algorithmic problem given a graph and a quantitative property asks to
compute the optimal value (the infimum value over all traces) from every node
of the graph. We consider graphs with constant treewidth, and it is well-known
that the control-flow graphs of most programs have constant treewidth. Let $n$
denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth
graphs $m=O(n)$) and $W$ the largest absolute value of the weights.\r\nOur main
theoretical results are as follows.\r\nFirst, for constant treewidth graphs we
present an algorithm that approximates the mean-payoff value within a multiplicative
factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ and linear space,
as compared to the classical algorithms that require quadratic time. Second, for
the ratio property we present an algorithm that for constant treewidth graphs
works in time $O(n \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when
the output is $\\frac{a}{b}$, as compared to the previously best known algorithm
with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial
credit problem we show that (i)~for general graphs the problem can be solved in
$O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot
m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$
and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs
we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the
previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented
some of our algorithms and show that they present a significant speedup on standard
benchmarks. "
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: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. *Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs*. IST Austria; 2015. doi:10.15479/AT:IST-2015-330-v2-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). *Faster
algorithms for quantitative verification in constant treewidth graphs*. IST
Austria. https://doi.org/10.15479/AT:IST-2015-330-v2-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
*Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs*.
IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-330-v2-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, *Faster algorithms
for quantitative verification in constant treewidth graphs*. IST Austria, 2015.
ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for
quantitative verification in constant treewidth graphs, IST Austria, 27p.
mla: Chatterjee, Krishnendu, et al. *Faster Algorithms for Quantitative Verification
in Constant Treewidth Graphs*. IST Austria, 2015, doi:10.15479/AT:IST-2015-330-v2-1.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative
Verification in Constant Treewidth Graphs, IST Austria, 2015.
date_created: 2018-12-12T11:39:19Z
date_published: 2015-04-27T00:00:00Z
date_updated: 2021-01-12T08:02:17Z
day: '27'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-330-v2-1
file:
- access_level: open_access
checksum: f5917c20f84018b362d385c000a2e123
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:12Z
date_updated: 2020-07-14T12:46:54Z
file_id: '5473'
file_name: IST-2015-330-v2+1_main.pdf
file_size: 1072137
relation: main_file
file_date_updated: 2020-07-14T12:46:54Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '27'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '333'
related_material:
record:
- id: '5430'
relation: earlier_version
status: public
- id: '1607'
relation: later_version
status: public
status: public
title: Faster algorithms for quantitative verification in constant treewidth graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...