---
_id: '8089'
abstract:
- lang: eng
text: "We consider the classical problem of invariant generation for programs with
polynomial assignments and focus on synthesizing invariants that are a conjunction
of strict polynomial inequalities. We present a sound and semi-complete method
based on positivstellensaetze, i.e. theorems in semi-algebraic geometry that characterize
positive polynomials over a semi-algebraic set.\r\n\r\nOn the theoretical side,
the worst-case complexity of our approach is subexponential, whereas the worst-case
complexity of the previous complete method (Kapur, ACA 2004) is doubly-exponential.
Even when restricted to linear invariants, the best previous complexity for complete
invariant generation is exponential (Colon et al, CAV 2003). On the practical
side, we reduce the invariant generation problem to quadratic programming (QCLP),
which is a classical optimization problem with many industrial solvers. We demonstrate
the applicability of our approach by providing experimental results on several
academic benchmarks. To the best of our knowledge, the only previous invariant
generation method that provides completeness guarantees for invariants consisting
of polynomial inequalities is (Kapur, ACA 2004), which relies on quantifier elimination
and cannot even handle toy programs such as our running example."
article_processing_charge: No
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: Hongfei
full_name: Fu, Hongfei
id: 3AAD03D6-F248-11E8-B48F-1D18A9856A87
last_name: Fu
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Ehsan Kafshdar
full_name: Goharshady, Ehsan Kafshdar
last_name: Goharshady
citation:
ama: 'Chatterjee K, Fu H, Goharshady AK, Goharshady EK. Polynomial invariant generation
for non-deterministic recursive programs. In: Proceedings of the 41st ACM SIGPLAN
Conference on Programming Language Design and Implementation. Association
for Computing Machinery; 2020:672-687. doi:10.1145/3385412.3385969'
apa: 'Chatterjee, K., Fu, H., Goharshady, A. K., & Goharshady, E. K. (2020).
Polynomial invariant generation for non-deterministic recursive programs. In Proceedings
of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
(pp. 672–687). London, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3385412.3385969'
chicago: Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Ehsan
Kafshdar Goharshady. “Polynomial Invariant Generation for Non-Deterministic Recursive
Programs.” In Proceedings of the 41st ACM SIGPLAN Conference on Programming
Language Design and Implementation, 672–87. Association for Computing Machinery,
2020. https://doi.org/10.1145/3385412.3385969.
ieee: K. Chatterjee, H. Fu, A. K. Goharshady, and E. K. Goharshady, “Polynomial
invariant generation for non-deterministic recursive programs,” in Proceedings
of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation,
London, United Kingdom, 2020, pp. 672–687.
ista: 'Chatterjee K, Fu H, Goharshady AK, Goharshady EK. 2020. Polynomial invariant
generation for non-deterministic recursive programs. Proceedings of the 41st ACM
SIGPLAN Conference on Programming Language Design and Implementation. PLDI: Programming
Language Design and Implementation, 672–687.'
mla: Chatterjee, Krishnendu, et al. “Polynomial Invariant Generation for Non-Deterministic
Recursive Programs.” Proceedings of the 41st ACM SIGPLAN Conference on Programming
Language Design and Implementation, Association for Computing Machinery, 2020,
pp. 672–87, doi:10.1145/3385412.3385969.
short: K. Chatterjee, H. Fu, A.K. Goharshady, E.K. Goharshady, in:, Proceedings
of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation,
Association for Computing Machinery, 2020, pp. 672–687.
conference:
end_date: 2020-06-20
location: London, United Kingdom
name: 'PLDI: Programming Language Design and Implementation'
start_date: 2020-06-15
date_created: 2020-07-05T22:00:45Z
date_published: 2020-06-11T00:00:00Z
date_updated: 2025-06-02T08:53:42Z
day: '11'
department:
- _id: KrCh
doi: 10.1145/3385412.3385969
external_id:
arxiv:
- '1902.04373'
isi:
- '000614622300045'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1902.04373
month: '06'
oa: 1
oa_version: Preprint
page: 672-687
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
publication: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language
Design and Implementation
publication_identifier:
isbn:
- '9781450376136'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Polynomial invariant generation for non-deterministic recursive programs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '8193'
abstract:
- lang: eng
text: 'Multiple-environment Markov decision processes (MEMDPs) are MDPs equipped
with not one, but multiple probabilistic transition functions, which represent
the various possible unknown environments. While the previous research on MEMDPs
focused on theoretical properties for long-run average payoff, we study them with
discounted-sum payoff and focus on their practical advantages and applications.
MEMDPs can be viewed as a special case of Partially observable and Mixed observability
MDPs: the state of the system is perfectly observable, but not the environment.
We show that the specific structure of MEMDPs allows for more efficient algorithmic
analysis, in particular for faster belief updates. We demonstrate the applicability
of MEMDPs in several domains. In particular, we formalize the sequential decision-making
approach to contextual recommendation systems as MEMDPs and substantially improve
over the previous MDP approach.'
acknowledgement: Krishnendu Chatterjee is supported by the Austrian ScienceFund (FWF)
NFN Grant No. S11407-N23 (RiSE/SHiNE),and COST Action GAMENET. Petr Novotn ́y is
supported bythe Czech Science Foundation grant No. GJ19-15134Y.
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: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Deep
full_name: Karkhanis, Deep
last_name: Karkhanis
- first_name: Petr
full_name: Novotný, Petr
id: 3CC3B868-F248-11E8-B48F-1D18A9856A87
last_name: Novotný
- first_name: Amélie
full_name: Royer, Amélie
id: 3811D890-F248-11E8-B48F-1D18A9856A87
last_name: Royer
orcid: 0000-0002-8407-0705
citation:
ama: 'Chatterjee K, Chmelik M, Karkhanis D, Novotný P, Royer A. Multiple-environment
Markov decision processes: Efficient analysis and applications. In: Proceedings
of the 30th International Conference on Automated Planning and Scheduling.
Vol 30. Association for the Advancement of Artificial Intelligence; 2020:48-56.'
apa: 'Chatterjee, K., Chmelik, M., Karkhanis, D., Novotný, P., & Royer, A. (2020).
Multiple-environment Markov decision processes: Efficient analysis and applications.
In Proceedings of the 30th International Conference on Automated Planning and
Scheduling (Vol. 30, pp. 48–56). Nancy, France: Association for the Advancement
of Artificial Intelligence.'
chicago: 'Chatterjee, Krishnendu, Martin Chmelik, Deep Karkhanis, Petr Novotný,
and Amélie Royer. “Multiple-Environment Markov Decision Processes: Efficient Analysis
and Applications.” In Proceedings of the 30th International Conference on Automated
Planning and Scheduling, 30:48–56. Association for the Advancement of Artificial
Intelligence, 2020.'
ieee: 'K. Chatterjee, M. Chmelik, D. Karkhanis, P. Novotný, and A. Royer, “Multiple-environment
Markov decision processes: Efficient analysis and applications,” in Proceedings
of the 30th International Conference on Automated Planning and Scheduling,
Nancy, France, 2020, vol. 30, pp. 48–56.'
ista: 'Chatterjee K, Chmelik M, Karkhanis D, Novotný P, Royer A. 2020. Multiple-environment
Markov decision processes: Efficient analysis and applications. Proceedings of
the 30th International Conference on Automated Planning and Scheduling. ICAPS:
International Conference on Automated Planning and Scheduling vol. 30, 48–56.'
mla: 'Chatterjee, Krishnendu, et al. “Multiple-Environment Markov Decision Processes:
Efficient Analysis and Applications.” Proceedings of the 30th International
Conference on Automated Planning and Scheduling, vol. 30, Association for
the Advancement of Artificial Intelligence, 2020, pp. 48–56.'
short: K. Chatterjee, M. Chmelik, D. Karkhanis, P. Novotný, A. Royer, in:, Proceedings
of the 30th International Conference on Automated Planning and Scheduling, Association
for the Advancement of Artificial Intelligence, 2020, pp. 48–56.
conference:
end_date: 2020-10-30
location: Nancy, France
name: 'ICAPS: International Conference on Automated Planning and Scheduling'
start_date: 2020-10-26
date_created: 2020-08-02T22:00:58Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-09-07T13:16:18Z
day: '01'
department:
- _id: KrCh
intvolume: ' 30'
language:
- iso: eng
month: '06'
oa_version: None
page: 48-56
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Proceedings of the 30th International Conference on Automated Planning
and Scheduling
publication_identifier:
eissn:
- '23340843'
issn:
- '23340835'
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
related_material:
record:
- id: '8390'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'Multiple-environment Markov decision processes: Efficient analysis and applications'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 30
year: '2020'
...
---
_id: '8272'
abstract:
- lang: eng
text: We study turn-based stochastic zero-sum games with lexicographic preferences
over reachability and safety objectives. Stochastic games are standard models
in control, verification, and synthesis of stochastic reactive systems that exhibit
both randomness as well as angelic and demonic non-determinism. Lexicographic
order allows to consider multiple objectives with a strict preference order over
the satisfaction of the objectives. To the best of our knowledge, stochastic games
with lexicographic objectives have not been studied before. We establish determinacy
of such games and present strategy and computational complexity results. For strategy
complexity, we show that lexicographically optimal strategies exist that are deterministic
and memory is only required to remember the already satisfied and violated objectives.
For a constant number of objectives, we show that the relevant decision problem
is in NP∩coNP , matching the current known bound for single objectives; and
in general the decision problem is PSPACE -hard and can be solved in NEXPTIME∩coNEXPTIME
. We present an algorithm that computes the lexicographically optimal strategies
via a reduction to computation of optimal strategies in a sequence of single-objectives
games. We have implemented our algorithm and report experimental results on various
case studies.
alternative_title:
- LNCS
article_processing_charge: No
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: Joost P
full_name: Katoen, Joost P
id: 4524F760-F248-11E8-B48F-1D18A9856A87
last_name: Katoen
- first_name: Maximilian
full_name: Weininger, Maximilian
last_name: Weininger
- first_name: Tobias
full_name: Winkler, Tobias
last_name: Winkler
citation:
ama: 'Chatterjee K, Katoen JP, Weininger M, Winkler T. Stochastic games with lexicographic
reachability-safety objectives. In: International Conference on Computer Aided
Verification. Vol 12225. Springer Nature; 2020:398-420. doi:10.1007/978-3-030-53291-8_21'
apa: Chatterjee, K., Katoen, J. P., Weininger, M., & Winkler, T. (2020). Stochastic
games with lexicographic reachability-safety objectives. In International Conference
on Computer Aided Verification (Vol. 12225, pp. 398–420). Springer Nature.
https://doi.org/10.1007/978-3-030-53291-8_21
chicago: Chatterjee, Krishnendu, Joost P Katoen, Maximilian Weininger, and Tobias
Winkler. “Stochastic Games with Lexicographic Reachability-Safety Objectives.”
In International Conference on Computer Aided Verification, 12225:398–420.
Springer Nature, 2020. https://doi.org/10.1007/978-3-030-53291-8_21.
ieee: K. Chatterjee, J. P. Katoen, M. Weininger, and T. Winkler, “Stochastic games
with lexicographic reachability-safety objectives,” in International Conference
on Computer Aided Verification, 2020, vol. 12225, pp. 398–420.
ista: 'Chatterjee K, Katoen JP, Weininger M, Winkler T. 2020. Stochastic games with
lexicographic reachability-safety objectives. International Conference on Computer
Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 12225, 398–420.'
mla: Chatterjee, Krishnendu, et al. “Stochastic Games with Lexicographic Reachability-Safety
Objectives.” International Conference on Computer Aided Verification, vol.
12225, Springer Nature, 2020, pp. 398–420, doi:10.1007/978-3-030-53291-8_21.
short: K. Chatterjee, J.P. Katoen, M. Weininger, T. Winkler, in:, International
Conference on Computer Aided Verification, Springer Nature, 2020, pp. 398–420.
conference:
name: 'CAV: Computer Aided Verification'
date_created: 2020-08-16T22:00:58Z
date_published: 2020-07-14T00:00:00Z
date_updated: 2025-07-14T09:10:14Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-030-53291-8_21
ec_funded: 1
external_id:
arxiv:
- '2005.04018'
isi:
- '000695272500021'
file:
- access_level: open_access
checksum: 093d4788d7d5b2ce0ffe64fbe7820043
content_type: application/pdf
creator: dernst
date_created: 2020-08-17T11:32:44Z
date_updated: 2020-08-17T11:32:44Z
file_id: '8276'
file_name: 2020_LNCS_CAV_Chatterjee.pdf
file_size: 625056
relation: main_file
success: 1
file_date_updated: 2020-08-17T11:32:44Z
has_accepted_license: '1'
intvolume: ' 12225'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 398-420
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
publication: International Conference on Computer Aided Verification
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030532901'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '12738'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Stochastic games with lexicographic reachability-safety 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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 12225
year: '2020'
...
---
_id: '8324'
abstract:
- lang: eng
text: The notion of program sensitivity (aka Lipschitz continuity) specifies that
changes in the program input result in proportional changes to the program output.
For probabilistic programs the notion is naturally extended to expected sensitivity.
A previous approach develops a relational program logic framework for proving
expected sensitivity of probabilistic while loops, where the number of iterations
is fixed and bounded. In this work, we consider probabilistic while loops where
the number of iterations is not fixed, but randomized and depends on the initial
input values. We present a sound approach for proving expected sensitivity of
such programs. Our sound approach is martingale-based and can be automated through
existing martingale-synthesis algorithms. Furthermore, our approach is compositional
for sequential composition of while loops under a mild side condition. We demonstrate
the effectiveness of our approach on several classical examples from Gambler's
Ruin, stochastic hybrid systems and stochastic gradient descent. We also present
experimental results showing that our automated approach can handle various probabilistic
programs in the literature.
acknowledgement: We thank anonymous reviewers for helpful comments, especially for
pointing to us a scenario of piecewise-linear approximation (Remark5). The research
was partially supported by the National Natural Science Foundation of China (NSFC)
under Grant No. 61802254, 61672229, 61832015,61772336,11871221 and Austrian Science
Fund (FWF) NFN under Grant No. S11407-N23 (RiSE/SHiNE). We thank Prof. Yuxi Fu,
director of the BASICS Lab at Shanghai Jiao Tong University, for his support.
article_number: '25'
article_processing_charge: No
arxiv: 1
author:
- first_name: Peixin
full_name: Wang, Peixin
last_name: Wang
- first_name: Hongfei
full_name: Fu, Hongfei
last_name: Fu
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Yuxin
full_name: Deng, Yuxin
last_name: Deng
- first_name: Ming
full_name: Xu, Ming
last_name: Xu
citation:
ama: 'Wang P, Fu H, Chatterjee K, Deng Y, Xu M. Proving expected sensitivity of
probabilistic programs with randomized variable-dependent termination time. In:
Proceedings of the ACM on Programming Languages. Vol 4. ACM; 2020. doi:10.1145/3371093'
apa: Wang, P., Fu, H., Chatterjee, K., Deng, Y., & Xu, M. (2020). Proving expected
sensitivity of probabilistic programs with randomized variable-dependent termination
time. In Proceedings of the ACM on Programming Languages (Vol. 4). ACM.
https://doi.org/10.1145/3371093
chicago: Wang, Peixin, Hongfei Fu, Krishnendu Chatterjee, Yuxin Deng, and Ming Xu.
“Proving Expected Sensitivity of Probabilistic Programs with Randomized Variable-Dependent
Termination Time.” In Proceedings of the ACM on Programming Languages,
Vol. 4. ACM, 2020. https://doi.org/10.1145/3371093.
ieee: P. Wang, H. Fu, K. Chatterjee, Y. Deng, and M. Xu, “Proving expected sensitivity
of probabilistic programs with randomized variable-dependent termination time,”
in Proceedings of the ACM on Programming Languages, 2020, vol. 4, no. POPL.
ista: Wang P, Fu H, Chatterjee K, Deng Y, Xu M. 2020. Proving expected sensitivity
of probabilistic programs with randomized variable-dependent termination time.
Proceedings of the ACM on Programming Languages. vol. 4, 25.
mla: Wang, Peixin, et al. “Proving Expected Sensitivity of Probabilistic Programs
with Randomized Variable-Dependent Termination Time.” Proceedings of the ACM
on Programming Languages, vol. 4, no. POPL, 25, ACM, 2020, doi:10.1145/3371093.
short: P. Wang, H. Fu, K. Chatterjee, Y. Deng, M. Xu, in:, Proceedings of the ACM
on Programming Languages, ACM, 2020.
date_created: 2020-08-30T22:01:12Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2024-02-22T15:16:45Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.1145/3371093
external_id:
arxiv:
- '1902.04744'
file:
- access_level: open_access
checksum: c6193d109ff4ecb17e7a6513d8eb34c0
content_type: application/pdf
creator: cziletti
date_created: 2020-09-01T11:12:58Z
date_updated: 2020-09-01T11:12:58Z
file_id: '8328'
file_name: 2019_ACM_POPL_Wang.pdf
file_size: 564151
relation: main_file
success: 1
file_date_updated: 2020-09-01T11:12:58Z
has_accepted_license: '1'
intvolume: ' 4'
issue: POPL
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://doi.org/10.5281/zenodo.3533633
scopus_import: '1'
status: public
title: Proving expected sensitivity of probabilistic programs with randomized variable-dependent
termination time
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2020'
...
---
_id: '8533'
abstract:
- lang: eng
text: Game of Life is a simple and elegant model to study dynamical system over
networks. The model consists of a graph where every vertex has one of two types,
namely, dead or alive. A configuration is a mapping of the vertices to the types.
An update rule describes how the type of a vertex is updated given the types of
its neighbors. In every round, all vertices are updated synchronously, which leads
to a configuration update. While in general, Game of Life allows a broad range
of update rules, we focus on two simple families of update rules, namely, underpopulation
and overpopulation, that model several interesting dynamics studied in the literature.
In both settings, a dead vertex requires at least a desired number of live neighbors
to become alive. For underpopulation (resp., overpopulation), a live vertex requires
at least (resp. at most) a desired number of live neighbors to remain alive. We
study the basic computation problems, e.g., configuration reachability, for these
two families of rules. For underpopulation rules, we show that these problems
can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete.
acknowledgement: "Krishnendu Chatterjee: The research was partially supported by the
Vienna Science and\r\nTechnology Fund (WWTF) Project ICT15-003.\r\nIsmaël Jecker:
This project has received funding from the European Union’s Horizon 2020 research\r\nand
innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411."
alternative_title:
- LIPIcs
article_number: 22:1-22:13
article_processing_charge: No
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: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Simplified game of life:
Algorithms and complexity. In: 45th International Symposium on Mathematical
Foundations of Computer Science. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2020. doi:10.4230/LIPIcs.MFCS.2020.22'
apa: 'Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., & Svoboda, J. (2020).
Simplified game of life: Algorithms and complexity. In 45th International Symposium
on Mathematical Foundations of Computer Science (Vol. 170). Prague, Czech
Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2020.22'
chicago: 'Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Ismael R Jecker, and Jakub
Svoboda. “Simplified Game of Life: Algorithms and Complexity.” In 45th International
Symposium on Mathematical Foundations of Computer Science, Vol. 170. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.MFCS.2020.22.'
ieee: 'K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Simplified
game of life: Algorithms and complexity,” in 45th International Symposium on
Mathematical Foundations of Computer Science, Prague, Czech Republic, 2020,
vol. 170.'
ista: 'Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2020. Simplified game
of life: Algorithms and complexity. 45th International Symposium on Mathematical
Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of
Computer Science, LIPIcs, vol. 170, 22:1-22:13.'
mla: 'Chatterjee, Krishnendu, et al. “Simplified Game of Life: Algorithms and Complexity.”
45th International Symposium on Mathematical Foundations of Computer Science,
vol. 170, 22:1-22:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020,
doi:10.4230/LIPIcs.MFCS.2020.22.'
short: K. Chatterjee, R. Ibsen-Jensen, I.R. Jecker, J. Svoboda, in:, 45th International
Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2020.
conference:
end_date: 2020-08-28
location: Prague, Czech Republic
name: 'MFCS: Symposium on Mathematical Foundations of Computer Science'
start_date: 2020-08-24
date_created: 2020-09-20T22:01:36Z
date_published: 2020-08-18T00:00:00Z
date_updated: 2025-06-02T08:53:42Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2020.22
ec_funded: 1
external_id:
arxiv:
- '2007.02894'
file:
- access_level: open_access
checksum: bbd7c4f55d45f2ff2a0a4ef0e10a77b1
content_type: application/pdf
creator: dernst
date_created: 2020-09-21T13:57:34Z
date_updated: 2020-09-21T13:57:34Z
file_id: '8550'
file_name: 2020_LIPIcs_Chatterjee.pdf
file_size: 491374
relation: main_file
success: 1
file_date_updated: 2020-09-21T13:57:34Z
has_accepted_license: '1'
intvolume: ' 170'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 45th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
isbn:
- '9783959771597'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Simplified game of life: Algorithms and complexity'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 170
year: '2020'
...
---
_id: '8534'
abstract:
- lang: eng
text: A regular language L of finite words is composite if there are regular languages
L₁,L₂,…,L_t such that L = ⋂_{i = 1}^t L_i and the index (number of states in a
minimal DFA) of every language L_i is strictly smaller than the index of L. Otherwise,
L is prime. Primality of regular languages was introduced and studied in [O. Kupferman
and J. Mosheiff, 2015], where the complexity of deciding the primality of the
language of a given DFA was left open, with a doubly-exponential gap between the
upper and lower bounds. We study primality for unary regular languages, namely
regular languages with a singleton alphabet. A unary language corresponds to a
subset of ℕ, making the study of unary prime languages closer to that of primality
in number theory. We show that the setting of languages is richer. In particular,
while every composite number is the product of two smaller numbers, the number
t of languages necessary to decompose a composite unary language induces a strict
hierarchy. In addition, a primality witness for a unary language L, namely a word
that is not in L but is in all products of languages that contain L and have an
index smaller than L’s, may be of exponential length. Still, we are able to characterize
compositionality by structural properties of a DFA for L, leading to a LogSpace
algorithm for primality checking of unary DFAs.
acknowledgement: "Ismaël Jecker: This project has received funding from the European
Union’s Horizon\r\n2020 research and innovation programme under the Marie Skłodowska-Curie
Grant Agreement No.\r\n754411. Nicolas Mazzocchi: PhD fellowship FRIA from the F.R.S.-FNRS."
alternative_title:
- LIPIcs
article_number: 51:1-51:12
article_processing_charge: No
author:
- first_name: Ismael R
full_name: Jecker, Ismael R
id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
last_name: Jecker
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
- first_name: Nicolas
full_name: Mazzocchi, Nicolas
last_name: Mazzocchi
citation:
ama: 'Jecker IR, Kupferman O, Mazzocchi N. Unary prime languages. In: 45th International
Symposium on Mathematical Foundations of Computer Science. Vol 170. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.MFCS.2020.51'
apa: 'Jecker, I. R., Kupferman, O., & Mazzocchi, N. (2020). Unary prime languages.
In 45th International Symposium on Mathematical Foundations of Computer Science
(Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.MFCS.2020.51'
chicago: Jecker, Ismael R, Orna Kupferman, and Nicolas Mazzocchi. “Unary Prime Languages.”
In 45th International Symposium on Mathematical Foundations of Computer Science,
Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.MFCS.2020.51.
ieee: I. R. Jecker, O. Kupferman, and N. Mazzocchi, “Unary prime languages,” in
45th International Symposium on Mathematical Foundations of Computer Science,
Prague, Czech Republic, 2020, vol. 170.
ista: 'Jecker IR, Kupferman O, Mazzocchi N. 2020. Unary prime languages. 45th International
Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on
Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 51:1-51:12.'
mla: Jecker, Ismael R., et al. “Unary Prime Languages.” 45th International Symposium
on Mathematical Foundations of Computer Science, vol. 170, 51:1-51:12, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.MFCS.2020.51.
short: I.R. Jecker, O. Kupferman, N. Mazzocchi, in:, 45th International Symposium
on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2020.
conference:
end_date: 2020-08-28
location: Prague, Czech Republic
name: 'MFCS: Symposium on Mathematical Foundations of Computer Science'
start_date: 2020-08-24
date_created: 2020-09-20T22:01:36Z
date_published: 2020-08-18T00:00:00Z
date_updated: 2021-01-12T08:19:56Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2020.51
ec_funded: 1
file:
- access_level: open_access
checksum: 2dc9e2fad6becd4563aef3e27a473f70
content_type: application/pdf
creator: dernst
date_created: 2020-09-21T14:17:08Z
date_updated: 2020-09-21T14:17:08Z
file_id: '8552'
file_name: 2020_LIPIcsMFCS_Jecker.pdf
file_size: 597977
relation: main_file
success: 1
file_date_updated: 2020-09-21T14:17:08Z
has_accepted_license: '1'
intvolume: ' 170'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 45th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
isbn:
- '9783959771597'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Unary prime languages
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 170
year: '2020'
...
---
_id: '8600'
abstract:
- lang: eng
text: 'A vector addition system with states (VASS) consists of a finite set of states
and counters. A transition changes the current state to the next state, and every
counter is either incremented, or decremented, or left unchanged. A state and
value for each counter is a configuration; and a computation is an infinite sequence
of configurations with transitions between successive configurations. A probabilistic
VASS consists of a VASS along with a probability distribution over the transitions
for each state. Qualitative properties such as state and configuration reachability
have been widely studied for VASS. In this work we consider multi-dimensional
long-run average objectives for VASS and probabilistic VASS. For a counter, the
cost of a configuration is the value of the counter; and the long-run average
value of a computation for the counter is the long-run average of the costs of
the configurations in the computation. The multi-dimensional long-run average
problem given a VASS and a threshold value for each counter, asks whether there
is a computation such that for each counter the long-run average value for the
counter does not exceed the respective threshold. For probabilistic VASS, instead
of the existence of a computation, we consider whether the expected long-run average
value for each counter does not exceed the respective threshold. Our main results
are as follows: we show that the multi-dimensional long-run average problem (a)
is NP-complete for integer-valued VASS; (b) is undecidable for natural-valued
VASS (i.e., nonnegative counters); and (c) can be solved in polynomial time for
probabilistic integer-valued VASS, and probabilistic natural-valued VASS when
all computations are non-terminating.'
alternative_title:
- LIPIcs
article_number: '23'
article_processing_charge: No
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: 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. Multi-dimensional long-run average problems
for vector addition systems with states. In: 31st International Conference
on Concurrency Theory. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2020. doi:10.4230/LIPIcs.CONCUR.2020.23'
apa: 'Chatterjee, K., Henzinger, T. A., & Otop, J. (2020). Multi-dimensional
long-run average problems for vector addition systems with states. In 31st
International Conference on Concurrency Theory (Vol. 171). Virtual: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2020.23'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Multi-Dimensional
Long-Run Average Problems for Vector Addition Systems with States.” In 31st
International Conference on Concurrency Theory, Vol. 171. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.CONCUR.2020.23.
ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, “Multi-dimensional long-run average
problems for vector addition systems with states,” in 31st International Conference
on Concurrency Theory, Virtual, 2020, vol. 171.
ista: 'Chatterjee K, Henzinger TA, Otop J. 2020. Multi-dimensional long-run average
problems for vector addition systems with states. 31st International Conference
on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol.
171, 23.'
mla: Chatterjee, Krishnendu, et al. “Multi-Dimensional Long-Run Average Problems
for Vector Addition Systems with States.” 31st International Conference on
Concurrency Theory, vol. 171, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020, doi:10.4230/LIPIcs.CONCUR.2020.23.
short: K. Chatterjee, T.A. Henzinger, J. Otop, in:, 31st International Conference
on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
end_date: 2020-09-04
location: Virtual
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2020-09-01
date_created: 2020-10-04T22:01:36Z
date_published: 2020-08-06T00:00:00Z
date_updated: 2021-01-12T08:20:15Z
day: '06'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2020.23
external_id:
arxiv:
- '2007.08917'
file:
- access_level: open_access
checksum: 5039752f644c4b72b9361d21a5e31baf
content_type: application/pdf
creator: dernst
date_created: 2020-10-05T14:04:25Z
date_updated: 2020-10-05T14:04:25Z
file_id: '8610'
file_name: 2020_LIPIcsCONCUR_Chatterjee.pdf
file_size: 601231
relation: main_file
success: 1
file_date_updated: 2020-10-05T14:04:25Z
has_accepted_license: '1'
intvolume: ' 171'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication: 31st International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783959771603'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multi-dimensional long-run average problems for vector addition systems with
states
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 171
year: '2020'
...
---
_id: '8671'
abstract:
- lang: eng
text: 'We study relations between evidence theory and S-approximation spaces. Both
theories have their roots in the analysis of Dempsterchr(''39'')s multivalued
mappings and lower and upper probabilities, and have close relations to rough
sets. We show that an S-approximation space, satisfying a monotonicity condition,
can induce a natural belief structure which is a fundamental block in evidence
theory. We also demonstrate that one can induce a natural belief structure on
one set, given a belief structure on another set, if the two sets are related
by a partial monotone S-approximation space. '
acknowledgement: We are very grateful to the anonymous reviewer for detailed comments
and suggestions that significantly improved the presentation of this paper. The
research was partially supported by a DOC fellowship of the Austrian Academy of
Sciences.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: A.
full_name: Shakiba, A.
last_name: Shakiba
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: M.R.
full_name: Hooshmandasl, M.R.
last_name: Hooshmandasl
- first_name: M.
full_name: Alambardar Meybodi, M.
last_name: Alambardar Meybodi
citation:
ama: Shakiba A, Goharshady AK, Hooshmandasl MR, Alambardar Meybodi M. A note on
belief structures and s-approximation spaces. Iranian Journal of Mathematical
Sciences and Informatics. 2020;15(2):117-128. doi:10.29252/ijmsi.15.2.117
apa: Shakiba, A., Goharshady, A. K., Hooshmandasl, M. R., & Alambardar Meybodi,
M. (2020). A note on belief structures and s-approximation spaces. Iranian
Journal of Mathematical Sciences and Informatics. Iranian Academic Center
for Education, Culture and Research. https://doi.org/10.29252/ijmsi.15.2.117
chicago: Shakiba, A., Amir Kafshdar Goharshady, M.R. Hooshmandasl, and M. Alambardar
Meybodi. “A Note on Belief Structures and S-Approximation Spaces.” Iranian
Journal of Mathematical Sciences and Informatics. Iranian Academic Center
for Education, Culture and Research, 2020. https://doi.org/10.29252/ijmsi.15.2.117.
ieee: A. Shakiba, A. K. Goharshady, M. R. Hooshmandasl, and M. Alambardar Meybodi,
“A note on belief structures and s-approximation spaces,” Iranian Journal of
Mathematical Sciences and Informatics, vol. 15, no. 2. Iranian Academic Center
for Education, Culture and Research, pp. 117–128, 2020.
ista: Shakiba A, Goharshady AK, Hooshmandasl MR, Alambardar Meybodi M. 2020. A note
on belief structures and s-approximation spaces. Iranian Journal of Mathematical
Sciences and Informatics. 15(2), 117–128.
mla: Shakiba, A., et al. “A Note on Belief Structures and S-Approximation Spaces.”
Iranian Journal of Mathematical Sciences and Informatics, vol. 15, no.
2, Iranian Academic Center for Education, Culture and Research, 2020, pp. 117–28,
doi:10.29252/ijmsi.15.2.117.
short: A. Shakiba, A.K. Goharshady, M.R. Hooshmandasl, M. Alambardar Meybodi, Iranian
Journal of Mathematical Sciences and Informatics 15 (2020) 117–128.
date_created: 2020-10-18T22:01:36Z
date_published: 2020-10-01T00:00:00Z
date_updated: 2023-10-16T09:25:00Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.29252/ijmsi.15.2.117
external_id:
arxiv:
- '1805.10672'
file:
- access_level: open_access
checksum: f299661a6d51cda6d255a76be696f48d
content_type: application/pdf
creator: dernst
date_created: 2020-10-19T11:14:20Z
date_updated: 2020-10-19T11:14:20Z
file_id: '8676'
file_name: 2020_ijmsi_Shakiba_accepted.pdf
file_size: 261688
relation: main_file
success: 1
file_date_updated: 2020-10-19T11:14:20Z
has_accepted_license: '1'
intvolume: ' 15'
issue: '2'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 117-128
project:
- _id: 267066CE-B435-11E9-9278-68D0E5697425
name: Quantitative Analysis of Probablistic Systems with a focus on Crypto-currencies
publication: Iranian Journal of Mathematical Sciences and Informatics
publication_identifier:
eissn:
- 2008-9473
issn:
- 1735-4463
publication_status: published
publisher: Iranian Academic Center for Education, Culture and Research
quality_controlled: '1'
scopus_import: '1'
status: public
title: A note on belief structures and s-approximation spaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2020'
...
---
_id: '8728'
abstract:
- lang: eng
text: Discrete-time Markov Chains (MCs) and Markov Decision Processes (MDPs) are
two standard formalisms in system analysis. Their main associated quantitative
objectives are hitting probabilities, discounted sum, and mean payoff. Although
there are many techniques for computing these objectives in general MCs/MDPs,
they have not been thoroughly studied in terms of parameterized algorithms, particularly
when treewidth is used as the parameter. This is in sharp contrast to qualitative
objectives for MCs, MDPs and graph games, for which treewidth-based algorithms
yield significant complexity improvements. In this work, we show that treewidth
can also be used to obtain faster algorithms for the quantitative problems. For
an MC with n states and m transitions, we show that each of the classical quantitative
objectives can be computed in O((n+m)⋅t2) time, given a tree decomposition
of the MC with width t. Our results also imply a bound of O(κ⋅(n+m)⋅t2) for
each objective on MDPs, where κ is the number of strategy-iteration refinements
required for the given input and objective. Finally, we make an experimental evaluation
of our new algorithms on low-treewidth MCs and MDPs obtained from the DaCapo benchmark
suite. Our experiments show that on low-treewidth MCs and MDPs, our algorithms
outperform existing well-established methods by one or more orders of magnitude.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ali
full_name: Asadi, Ali
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Kiarash
full_name: Mohammadi, Kiarash
last_name: Mohammadi
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Asadi A, Chatterjee K, Goharshady AK, Mohammadi K, Pavlogiannis A. Faster
algorithms for quantitative analysis of MCs and MDPs with small treewidth. In:
Automated Technology for Verification and Analysis. Vol 12302. Springer
Nature; 2020:253-270. doi:10.1007/978-3-030-59152-6_14'
apa: 'Asadi, A., Chatterjee, K., Goharshady, A. K., Mohammadi, K., & Pavlogiannis,
A. (2020). Faster algorithms for quantitative analysis of MCs and MDPs with small
treewidth. In Automated Technology for Verification and Analysis (Vol.
12302, pp. 253–270). Hanoi, Vietnam: Springer Nature. https://doi.org/10.1007/978-3-030-59152-6_14'
chicago: Asadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Kiarash Mohammadi,
and Andreas Pavlogiannis. “Faster Algorithms for Quantitative Analysis of MCs
and MDPs with Small Treewidth.” In Automated Technology for Verification and
Analysis, 12302:253–70. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-59152-6_14.
ieee: A. Asadi, K. Chatterjee, A. K. Goharshady, K. Mohammadi, and A. Pavlogiannis,
“Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth,”
in Automated Technology for Verification and Analysis, Hanoi, Vietnam,
2020, vol. 12302, pp. 253–270.
ista: 'Asadi A, Chatterjee K, Goharshady AK, Mohammadi K, Pavlogiannis A. 2020.
Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth.
Automated Technology for Verification and Analysis. ATVA: Automated Technology
for Verification and Analysis, LNCS, vol. 12302, 253–270.'
mla: Asadi, Ali, et al. “Faster Algorithms for Quantitative Analysis of MCs and
MDPs with Small Treewidth.” Automated Technology for Verification and Analysis,
vol. 12302, Springer Nature, 2020, pp. 253–70, doi:10.1007/978-3-030-59152-6_14.
short: A. Asadi, K. Chatterjee, A.K. Goharshady, K. Mohammadi, A. Pavlogiannis,
in:, Automated Technology for Verification and Analysis, Springer Nature, 2020,
pp. 253–270.
conference:
end_date: 2020-10-23
location: Hanoi, Vietnam
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2020-10-19
date_created: 2020-11-06T07:30:05Z
date_published: 2020-10-12T00:00:00Z
date_updated: 2025-06-02T08:53:43Z
day: '12'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-030-59152-6_14
external_id:
isi:
- '000723555700014'
file:
- access_level: open_access
checksum: ae83f27e5b189d5abc2e7514f1b7e1b5
content_type: application/pdf
creator: dernst
date_created: 2020-11-06T07:41:03Z
date_updated: 2020-11-06T07:41:03Z
file_id: '8729'
file_name: 2020_LNCS_ATVA_Asadi_accepted.pdf
file_size: 726648
relation: main_file
success: 1
file_date_updated: 2020-11-06T07:41:03Z
has_accepted_license: '1'
intvolume: ' 12302'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 253-270
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
- _id: 267066CE-B435-11E9-9278-68D0E5697425
name: Quantitative Analysis of Probablistic Systems with a focus on Crypto-currencies
publication: Automated Technology for Verification and Analysis
publication_identifier:
eisbn:
- '9783030591526'
eissn:
- 1611-3349
isbn:
- '9783030591519'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12302
year: '2020'
...
---
_id: '8767'
abstract:
- lang: eng
text: Resources are rarely distributed uniformly within a population. Heterogeneity
in the concentration of a drug, the quality of breeding sites, or wealth can all
affect evolutionary dynamics. In this study, we represent a collection of properties
affecting the fitness at a given location using a color. A green node is rich
in resources while a red node is poorer. More colors can represent a broader spectrum
of resource qualities. For a population evolving according to the birth-death
Moran model, the first question we address is which structures, identified by
graph connectivity and graph coloring, are evolutionarily equivalent. We prove
that all properly two-colored, undirected, regular graphs are evolutionarily equivalent
(where “properly colored” means that no two neighbors have the same color). We
then compare the effects of background heterogeneity on properly two-colored graphs
to those with alternative schemes in which the colors are permuted. Finally, we
discuss dynamic coloring as a model for spatiotemporal resource fluctuations,
and we illustrate that random dynamic colorings often diminish the effects of
background heterogeneity relative to a proper two-coloring.
acknowledgement: 'We thank Igor Erovenko for many helpful comments on an earlier version
of this paper. : Army Research Laboratory (grant W911NF-18-2-0265) (M.A.N.); the
Bill & Melinda Gates Foundation (grant OPP1148627) (M.A.N.); the NVIDIA Corporation
(A.M.). The funders had no role in study design, data collection and analysis, decision
to publish, or preparation of the manuscript.'
article_number: e1008402
article_processing_charge: No
article_type: original
author:
- first_name: Kamran
full_name: Kaveh, Kamran
last_name: Kaveh
- first_name: Alex
full_name: McAvoy, Alex
last_name: McAvoy
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin A.
full_name: Nowak, Martin A.
last_name: Nowak
citation:
ama: Kaveh K, McAvoy A, Chatterjee K, Nowak MA. The Moran process on 2-chromatic
graphs. PLOS Computational Biology. 2020;16(11). doi:10.1371/journal.pcbi.1008402
apa: Kaveh, K., McAvoy, A., Chatterjee, K., & Nowak, M. A. (2020). The Moran
process on 2-chromatic graphs. PLOS Computational Biology. Public Library
of Science. https://doi.org/10.1371/journal.pcbi.1008402
chicago: Kaveh, Kamran, Alex McAvoy, Krishnendu Chatterjee, and Martin A. Nowak.
“The Moran Process on 2-Chromatic Graphs.” PLOS Computational Biology.
Public Library of Science, 2020. https://doi.org/10.1371/journal.pcbi.1008402.
ieee: K. Kaveh, A. McAvoy, K. Chatterjee, and M. A. Nowak, “The Moran process on
2-chromatic graphs,” PLOS Computational Biology, vol. 16, no. 11. Public
Library of Science, 2020.
ista: Kaveh K, McAvoy A, Chatterjee K, Nowak MA. 2020. The Moran process on 2-chromatic
graphs. PLOS Computational Biology. 16(11), e1008402.
mla: Kaveh, Kamran, et al. “The Moran Process on 2-Chromatic Graphs.” PLOS Computational
Biology, vol. 16, no. 11, e1008402, Public Library of Science, 2020, doi:10.1371/journal.pcbi.1008402.
short: K. Kaveh, A. McAvoy, K. Chatterjee, M.A. Nowak, PLOS Computational Biology
16 (2020).
date_created: 2020-11-18T07:20:23Z
date_published: 2020-11-05T00:00:00Z
date_updated: 2023-08-22T12:49:18Z
day: '05'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1371/journal.pcbi.1008402
external_id:
isi:
- '000591317200004'
file:
- access_level: open_access
checksum: 555456dd0e47bcf9e0994bcb95577e88
content_type: application/pdf
creator: dernst
date_created: 2020-11-18T07:26:10Z
date_updated: 2020-11-18T07:26:10Z
file_id: '8768'
file_name: 2020_PlosCompBio_Kaveh.pdf
file_size: 2498594
relation: main_file
success: 1
file_date_updated: 2020-11-18T07:26:10Z
has_accepted_license: '1'
intvolume: ' 16'
isi: 1
issue: '11'
keyword:
- Ecology
- Modelling and Simulation
- Computational Theory and Mathematics
- Genetics
- Ecology
- Evolution
- Behavior and Systematics
- Molecular Biology
- Cellular and Molecular Neuroscience
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication: PLOS Computational Biology
publication_identifier:
eissn:
- 1553-7358
issn:
- 1553-734X
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Moran process on 2-chromatic graphs
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: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 16
year: '2020'
...
---
_id: '8788'
abstract:
- lang: eng
text: 'We consider a real-time setting where an environment releases sequences of
firm-deadline tasks, and an online scheduler chooses on-the-fly the ones to execute
on a single processor so as to maximize cumulated utility. The competitive ratio
is a well-known performance measure for the scheduler: it gives the worst-case
ratio, among all possible choices for the environment, of the cumulated utility
of the online scheduler versus an offline scheduler that knows these choices in
advance. Traditionally, competitive analysis is performed by hand, while automated
techniques are rare and only handle static environments with independent tasks.
We present a quantitative-verification framework for precedence-aware competitive
analysis, where task releases may depend on preceding scheduling choices, i.e.,
the environment can respond to scheduling decisions dynamically . We consider
two general classes of precedences: 1) follower precedences force the release
of a dependent task upon the completion of a set of precursor tasks, while and
2) pairing precedences modify the characteristics of a dependent task provided
the completion of a set of precursor tasks. Precedences make competitive analysis
challenging, as the online and offline schedulers operate on diverging sequences.
We make a formal presentation of our framework, and use a GPU-based implementation
to analyze ten well-known schedulers on precedence-based application examples
taken from the existing literature: 1) a handshake protocol (HP); 2) network packet-switching;
3) query scheduling (QS); and 4) a sporadic-interrupt setting. Our experimental
results show that precedences and task parameters can vary drastically the best
scheduler. Our framework thus supports application designers in choosing the best
scheduler among a given set automatically.'
acknowledgement: 'This work was supported by the Austrian Science Foundation (FWF)
under the NFN RiSE/SHiNE under Grant S11405 and Grant S11407. This article was presented
in the International Conference on Embedded Software 2020 and appears as part of
the ESWEEK-TCAD special issue. '
article_processing_charge: No
article_type: original
author:
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Nico
full_name: Schaumberger, Nico
last_name: Schaumberger
- first_name: Ulrich
full_name: Schmid, Ulrich
last_name: Schmid
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. Precedence-aware automated
competitive analysis of real-time scheduling. IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems. 2020;39(11):3981-3992. doi:10.1109/TCAD.2020.3012803
apa: Pavlogiannis, A., Schaumberger, N., Schmid, U., & Chatterjee, K. (2020).
Precedence-aware automated competitive analysis of real-time scheduling. IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems.
IEEE. https://doi.org/10.1109/TCAD.2020.3012803
chicago: Pavlogiannis, Andreas, Nico Schaumberger, Ulrich Schmid, and Krishnendu
Chatterjee. “Precedence-Aware Automated Competitive Analysis of Real-Time Scheduling.”
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
IEEE, 2020. https://doi.org/10.1109/TCAD.2020.3012803.
ieee: A. Pavlogiannis, N. Schaumberger, U. Schmid, and K. Chatterjee, “Precedence-aware
automated competitive analysis of real-time scheduling,” IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no.
11. IEEE, pp. 3981–3992, 2020.
ista: Pavlogiannis A, Schaumberger N, Schmid U, Chatterjee K. 2020. Precedence-aware
automated competitive analysis of real-time scheduling. IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems. 39(11), 3981–3992.
mla: Pavlogiannis, Andreas, et al. “Precedence-Aware Automated Competitive Analysis
of Real-Time Scheduling.” IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, vol. 39, no. 11, IEEE, 2020, pp. 3981–92, doi:10.1109/TCAD.2020.3012803.
short: A. Pavlogiannis, N. Schaumberger, U. Schmid, K. Chatterjee, IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems 39 (2020) 3981–3992.
date_created: 2020-11-22T23:01:24Z
date_published: 2020-11-01T00:00:00Z
date_updated: 2023-08-22T13:27:05Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/TCAD.2020.3012803
external_id:
isi:
- '000587712700069'
intvolume: ' 39'
isi: 1
issue: '11'
language:
- iso: eng
month: '11'
oa_version: None
page: 3981-3992
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: IEEE Transactions on Computer-Aided Design of Integrated Circuits and
Systems
publication_identifier:
eissn:
- '19374151'
issn:
- '02780070'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Precedence-aware automated competitive analysis of real-time scheduling
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 39
year: '2020'
...
---
_id: '8789'
abstract:
- lang: eng
text: Cooperation is a ubiquitous and beneficial behavioural trait despite being
prone to exploitation by free-riders. Hence, cooperative populations are prone
to invasions by selfish individuals. However, a population consisting of only
free-riders typically does not survive. Thus, cooperators and free-riders often
coexist in some proportion. An evolutionary version of a Snowdrift Game proved
its efficiency in analysing this phenomenon. However, what if the system has already
reached its stable state but was perturbed due to a change in environmental conditions?
Then, individuals may have to re-learn their effective strategies. To address
this, we consider behavioural mistakes in strategic choice execution, which we
refer to as incompetence. Parametrising the propensity to make such mistakes allows
for a mathematical description of learning. We compare strategies based on their
relative strategic advantage relying on both fitness and learning factors. When
strategies are learned at distinct rates, allowing learning according to a prescribed
order is optimal. Interestingly, the strategy with the lowest strategic advantage
should be learnt first if we are to optimise fitness over the learning path. Then,
the differences between strategies are balanced out in order to minimise the effect
of behavioural uncertainty.
acknowledgement: "This work was supported by the European Union’s Horizon 2020 research
and innovation program under the Marie Sklodowska-Curie Grant Agreement #754411,
the Australian Research Council Discovery Grants DP160101236 and DP150100618, and
the European Research Council Consolidator Grant 863818 (FoRM-SMArt).\r\nAuthors
would like to thank Patrick McKinlay for his work on the preliminary results for
this paper."
article_number: '1945'
article_processing_charge: No
article_type: original
author:
- first_name: Maria
full_name: Kleshnina, Maria
id: 4E21749C-F248-11E8-B48F-1D18A9856A87
last_name: Kleshnina
- first_name: Sabrina
full_name: Streipert, Sabrina
last_name: Streipert
- first_name: Jerzy
full_name: Filar, Jerzy
last_name: Filar
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: Kleshnina M, Streipert S, Filar J, Chatterjee K. Prioritised learning in snowdrift-type
games. Mathematics. 2020;8(11). doi:10.3390/math8111945
apa: Kleshnina, M., Streipert, S., Filar, J., & Chatterjee, K. (2020). Prioritised
learning in snowdrift-type games. Mathematics. MDPI. https://doi.org/10.3390/math8111945
chicago: Kleshnina, Maria, Sabrina Streipert, Jerzy Filar, and Krishnendu Chatterjee.
“Prioritised Learning in Snowdrift-Type Games.” Mathematics. MDPI, 2020.
https://doi.org/10.3390/math8111945.
ieee: M. Kleshnina, S. Streipert, J. Filar, and K. Chatterjee, “Prioritised learning
in snowdrift-type games,” Mathematics, vol. 8, no. 11. MDPI, 2020.
ista: Kleshnina M, Streipert S, Filar J, Chatterjee K. 2020. Prioritised learning
in snowdrift-type games. Mathematics. 8(11), 1945.
mla: Kleshnina, Maria, et al. “Prioritised Learning in Snowdrift-Type Games.” Mathematics,
vol. 8, no. 11, 1945, MDPI, 2020, doi:10.3390/math8111945.
short: M. Kleshnina, S. Streipert, J. Filar, K. Chatterjee, Mathematics 8 (2020).
date_created: 2020-11-22T23:01:24Z
date_published: 2020-11-04T00:00:00Z
date_updated: 2025-07-14T09:09:49Z
day: '04'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.3390/math8111945
ec_funded: 1
external_id:
isi:
- '000593962100001'
file:
- access_level: open_access
checksum: 61cfcc3b35760656ce7a9385a4ace5d2
content_type: application/pdf
creator: dernst
date_created: 2020-11-23T13:06:30Z
date_updated: 2020-11-23T13:06:30Z
file_id: '8797'
file_name: 2020_Mathematics_Kleshnina.pdf
file_size: 565191
relation: main_file
success: 1
file_date_updated: 2020-11-23T13:06:30Z
has_accepted_license: '1'
intvolume: ' 8'
isi: 1
issue: '11'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Mathematics
publication_identifier:
eissn:
- '22277390'
publication_status: published
publisher: MDPI
quality_controlled: '1'
scopus_import: '1'
status: public
title: Prioritised learning in snowdrift-type games
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: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 8
year: '2020'
...
---
_id: '6918'
abstract:
- lang: eng
text: "We consider the classic problem of Network Reliability. A network is given
together with a source vertex, one or more target vertices, and probabilities
assigned to each of the edges. Each edge of the network is operable with its associated
probability and the problem is to determine the probability of having at least
one source-to-target path that is entirely composed of operable edges. This problem
is known to be NP-hard.\r\n\r\nWe provide a novel scalable algorithm to solve
the Network Reliability problem when the treewidth of the underlying network is
small. We also show our algorithm’s applicability for real-world transit networks
that have small treewidth, including the metro networks of major cities, such
as London and Tokyo. Our algorithm leverages tree decompositions to shrink the
original graph into much smaller graphs, for which reliability can be efficiently
and exactly computed using a brute force method. To the best of our knowledge,
this is the first exact algorithm for Network Reliability that can scale to handle
real-world instances of the problem."
acknowledgement: We are grateful to the anonymous reviewers for their comments, which
significantly improved the present work. The research was partially supported by
the EPSRC Early Career Fellowship EP/R023379/1, grant no. SC7-1718-01 of the London
Mathematical Society, an IBM PhD Fellowship, and a DOC Fellowship of the Austrian
Academy of Sciences (ÖAW).
article_number: '106665'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Amir Kafshdar
full_name: Goharshady, Amir Kafshdar
id: 391365CE-F248-11E8-B48F-1D18A9856A87
last_name: Goharshady
orcid: 0000-0003-1702-6584
- first_name: Fatemeh
full_name: Mohammadi, Fatemeh
last_name: Mohammadi
citation:
ama: Goharshady AK, Mohammadi F. An efficient algorithm for computing network reliability
in small treewidth. Reliability Engineering and System Safety. 2020;193.
doi:10.1016/j.ress.2019.106665
apa: Goharshady, A. K., & Mohammadi, F. (2020). An efficient algorithm for computing
network reliability in small treewidth. Reliability Engineering and System
Safety. Elsevier. https://doi.org/10.1016/j.ress.2019.106665
chicago: Goharshady, Amir Kafshdar, and Fatemeh Mohammadi. “An Efficient Algorithm
for Computing Network Reliability in Small Treewidth.” Reliability Engineering
and System Safety. Elsevier, 2020. https://doi.org/10.1016/j.ress.2019.106665.
ieee: A. K. Goharshady and F. Mohammadi, “An efficient algorithm for computing network
reliability in small treewidth,” Reliability Engineering and System Safety,
vol. 193. Elsevier, 2020.
ista: Goharshady AK, Mohammadi F. 2020. An efficient algorithm for computing network
reliability in small treewidth. Reliability Engineering and System Safety. 193,
106665.
mla: Goharshady, Amir Kafshdar, and Fatemeh Mohammadi. “An Efficient Algorithm for
Computing Network Reliability in Small Treewidth.” Reliability Engineering
and System Safety, vol. 193, 106665, Elsevier, 2020, doi:10.1016/j.ress.2019.106665.
short: A.K. Goharshady, F. Mohammadi, Reliability Engineering and System Safety
193 (2020).
date_created: 2019-09-29T22:00:44Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2024-03-25T23:30:18Z
day: '01'
department:
- _id: KrCh
doi: 10.1016/j.ress.2019.106665
external_id:
arxiv:
- '1712.09692'
isi:
- '000501641400050'
intvolume: ' 193'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1712.09692
month: '01'
oa: 1
oa_version: Preprint
project:
- _id: 266EEEC0-B435-11E9-9278-68D0E5697425
name: Quantitative Game-theoretic Analysis of Blockchain Applications and Smart
Contracts
publication: Reliability Engineering and System Safety
publication_identifier:
issn:
- '09518320'
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '8934'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: An efficient algorithm for computing network reliability in small treewidth
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 193
year: '2020'
...
---
_id: '7196'
abstract:
- lang: eng
text: 'In this thesis we study certain mathematical aspects of evolution. The two
primary forces that drive an evolutionary process are mutation and selection.
Mutation generates new variants in a population. Selection chooses among the variants
depending on the reproductive rates of individuals. Evolutionary processes are
intrinsically random – a new mutation that is initially present in the population
at low frequency can go extinct, even if it confers a reproductive advantage.
The overall rate of evolution is largely determined by two quantities: the probability
that an invading advantageous mutation spreads through the population (called
fixation probability) and the time until it does so (called fixation time). Both
those quantities crucially depend not only on the strength of the invading mutation
but also on the population structure. In this thesis, we aim to understand how
the underlying population structure affects the overall rate of evolution. Specifically,
we study population structures that increase the fixation probability of advantageous
mutants (called amplifiers of selection). Broadly speaking, our results are of
three different types: We present various strong amplifiers, we identify regimes
under which only limited amplification is feasible, and we propose population
structures that provide different tradeoffs between high fixation probability
and short fixation time.'
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
citation:
ama: Tkadlec J. A role of graphs in evolutionary processes. 2020. doi:10.15479/AT:ISTA:7196
apa: Tkadlec, J. (2020). A role of graphs in evolutionary processes. Institute
of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7196
chicago: Tkadlec, Josef. “A Role of Graphs in Evolutionary Processes.” Institute
of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7196.
ieee: J. Tkadlec, “A role of graphs in evolutionary processes,” Institute of Science
and Technology Austria, 2020.
ista: Tkadlec J. 2020. A role of graphs in evolutionary processes. Institute of
Science and Technology Austria.
mla: Tkadlec, Josef. A Role of Graphs in Evolutionary Processes. Institute
of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7196.
short: J. Tkadlec, A Role of Graphs in Evolutionary Processes, Institute of Science
and Technology Austria, 2020.
date_created: 2019-12-20T12:26:36Z
date_published: 2020-01-12T00:00:00Z
date_updated: 2023-10-17T12:29:46Z
day: '12'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: KrCh
- _id: GradSch
doi: 10.15479/AT:ISTA:7196
file:
- access_level: closed
checksum: 451f8e64b0eb26bf297644ac72bfcbe9
content_type: application/zip
creator: jtkadlec
date_created: 2020-01-12T11:49:49Z
date_updated: 2020-07-14T12:47:52Z
file_id: '7255'
file_name: thesis.zip
file_size: 21100497
relation: source_file
- access_level: open_access
checksum: d8c44cbc4f939c49a8efc9d4b8bb3985
content_type: application/pdf
creator: dernst
date_created: 2020-01-28T07:32:42Z
date_updated: 2020-07-14T12:47:52Z
file_id: '7367'
file_name: 2020_Tkadlec_Thesis.pdf
file_size: 11670983
relation: main_file
file_date_updated: 2020-07-14T12:47:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '144'
publication_identifier:
eissn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '7210'
relation: dissertation_contains
status: public
- id: '5751'
relation: dissertation_contains
status: public
- id: '7212'
relation: dissertation_contains
status: public
status: public
supervisor:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
title: A role of graphs in evolutionary processes
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_id: '7212'
abstract:
- lang: eng
text: The fixation probability of a single mutant invading a population of residents
is among the most widely-studied quantities in evolutionary dynamics. Amplifiers
of natural selection are population structures that increase the fixation probability
of advantageous mutants, compared to well-mixed populations. Extensive studies
have shown that many amplifiers exist for the Birth-death Moran process, some
of them substantially increasing the fixation probability or even guaranteeing
fixation in the limit of large population size. On the other hand, no amplifiers
are known for the death-Birth Moran process, and computer-assisted exhaustive
searches have failed to discover amplification. In this work we resolve this disparity,
by showing that any amplification under death-Birth updating is necessarily bounded
and transient. Our boundedness result states that even if a population structure
does amplify selection, the resulting fixation probability is close to that of
the well-mixed population. Our transience result states that for any population
structure there exists a threshold r⋆ such that the population structure ceases
to amplify selection if the mutant fitness advantage r is larger than r⋆. Finally,
we also extend the above results to δ-death-Birth updating, which is a combination
of Birth-death and death-Birth updating. On the positive side, we identify population
structures that maintain amplification for a wide range of values r and δ. These
results demonstrate that amplification of natural selection depends on the specific
mechanisms of the evolutionary process.
article_number: e1007494
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin A.
full_name: Nowak, Martin A.
last_name: Nowak
citation:
ama: Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Limits on amplifiers of
natural selection under death-Birth updating. PLoS computational biology.
2020;16. doi:10.1371/journal.pcbi.1007494
apa: Tkadlec, J., Pavlogiannis, A., Chatterjee, K., & Nowak, M. A. (2020). Limits
on amplifiers of natural selection under death-Birth updating. PLoS Computational
Biology. Public Library of Science. https://doi.org/10.1371/journal.pcbi.1007494
chicago: Tkadlec, Josef, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin
A. Nowak. “Limits on Amplifiers of Natural Selection under Death-Birth Updating.”
PLoS Computational Biology. Public Library of Science, 2020. https://doi.org/10.1371/journal.pcbi.1007494.
ieee: J. Tkadlec, A. Pavlogiannis, K. Chatterjee, and M. A. Nowak, “Limits on amplifiers
of natural selection under death-Birth updating,” PLoS computational biology,
vol. 16. Public Library of Science, 2020.
ista: Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. 2020. Limits on amplifiers
of natural selection under death-Birth updating. PLoS computational biology. 16,
e1007494.
mla: Tkadlec, Josef, et al. “Limits on Amplifiers of Natural Selection under Death-Birth
Updating.” PLoS Computational Biology, vol. 16, e1007494, Public Library
of Science, 2020, doi:10.1371/journal.pcbi.1007494.
short: J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, PLoS Computational
Biology 16 (2020).
date_created: 2019-12-23T13:45:11Z
date_published: 2020-01-17T00:00:00Z
date_updated: 2023-10-17T12:29:47Z
day: '17'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1371/journal.pcbi.1007494
ec_funded: 1
external_id:
arxiv:
- '1906.02785'
isi:
- '000510916500025'
file:
- access_level: open_access
checksum: ce32ee2d2f53aed832f78bbd47e882df
content_type: application/pdf
creator: dernst
date_created: 2020-02-03T07:32:42Z
date_updated: 2020-07-14T12:47:53Z
file_id: '7441'
file_name: 2020_PlosCompBio_Tkadlec.pdf
file_size: 1817531
relation: main_file
file_date_updated: 2020-07-14T12:47:53Z
has_accepted_license: '1'
intvolume: ' 16'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _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
publication: PLoS computational biology
publication_identifier:
eissn:
- '15537358'
publication_status: published
publisher: Public Library of Science
quality_controlled: '1'
related_material:
record:
- id: '7196'
relation: part_of_dissertation
status: public
scopus_import: '1'
status: public
title: Limits on amplifiers of natural selection under death-Birth updating
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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2020'
...
---
_id: '7343'
abstract:
- lang: eng
text: Coinfections with multiple pathogens can result in complex within‐host dynamics
affecting virulence and transmission. While multiple infections are intensively
studied in solitary hosts, it is so far unresolved how social host interactions
interfere with pathogen competition, and if this depends on coinfection diversity.
We studied how the collective disease defences of ants – their social immunity
– influence pathogen competition in coinfections of same or different fungal pathogen
species. Social immunity reduced virulence for all pathogen combinations, but
interfered with spore production only in different‐species coinfections. Here,
it decreased overall pathogen sporulation success while increasing co‐sporulation
on individual cadavers and maintaining a higher pathogen diversity at the community
level. Mathematical modelling revealed that host sanitary care alone can modulate
competitive outcomes between pathogens, giving advantage to fast‐germinating,
thus less grooming‐sensitive ones. Host social interactions can hence modulate
infection dynamics in coinfected group members, thereby altering pathogen communities
at the host level and population level.
acknowledged_ssus:
- _id: LifeSc
acknowledgement: "We thank Bernhardt Steinwender and Jorgen Eilenberg for the fungal
strains, Xavier Espadaler, Mireia Diaz, Christiane Wanke, Lumi Viljakainen and the
Social Immunity Team at IST Austria, for help with ant collection, and Wanda Gorecka
and Gertraud Stift of the IST Austria Life Science Facility for technical support.
We are thankful to Dieter Ebert for input at all stages of the project, Roger Mundry
for statistical advice, Hinrich Schulenburg, Paul Schmid-Hempel, Yuko\r\nUlrich
and Joachim Kurtz for project discussion, Bor Kavcic for advice on growth curves,
Marcus Roper for advice on modelling work and comments on the manuscript, as well
as Marjon de Vos, Weini Huang and the Social Immunity Team for comments on the manuscript.\r\nThis
study was funded by the German Research Foundation (DFG) within the Priority Programme
1399 Host-parasite Coevolution (CR 118/3 to S.C.) and the People Programme\r\n(Marie
Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013)
under REA grant agreement no 291734 (ISTFELLOW to B.M.). "
article_processing_charge: Yes (via OA deal)
article_type: letter_note
author:
- first_name: Barbara
full_name: Milutinovic, Barbara
id: 2CDC32B8-F248-11E8-B48F-1D18A9856A87
last_name: Milutinovic
orcid: 0000-0002-8214-4758
- first_name: Miriam
full_name: Stock, Miriam
id: 42462816-F248-11E8-B48F-1D18A9856A87
last_name: Stock
- first_name: Anna V
full_name: Grasse, Anna V
id: 406F989C-F248-11E8-B48F-1D18A9856A87
last_name: Grasse
- first_name: Elisabeth
full_name: Naderlinger, Elisabeth
id: 31757262-F248-11E8-B48F-1D18A9856A87
last_name: Naderlinger
- first_name: Christian
full_name: Hilbe, Christian
id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87
last_name: Hilbe
orcid: 0000-0001-5116-955X
- first_name: Sylvia
full_name: Cremer, Sylvia
id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87
last_name: Cremer
orcid: 0000-0002-2193-3868
citation:
ama: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. Social
immunity modulates competition between coinfecting pathogens. Ecology Letters.
2020;23(3):565-574. doi:10.1111/ele.13458
apa: Milutinovic, B., Stock, M., Grasse, A. V., Naderlinger, E., Hilbe, C., &
Cremer, S. (2020). Social immunity modulates competition between coinfecting pathogens.
Ecology Letters. Wiley. https://doi.org/10.1111/ele.13458
chicago: Milutinovic, Barbara, Miriam Stock, Anna V Grasse, Elisabeth Naderlinger,
Christian Hilbe, and Sylvia Cremer. “Social Immunity Modulates Competition between
Coinfecting Pathogens.” Ecology Letters. Wiley, 2020. https://doi.org/10.1111/ele.13458.
ieee: B. Milutinovic, M. Stock, A. V. Grasse, E. Naderlinger, C. Hilbe, and S. Cremer,
“Social immunity modulates competition between coinfecting pathogens,” Ecology
Letters, vol. 23, no. 3. Wiley, pp. 565–574, 2020.
ista: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. 2020.
Social immunity modulates competition between coinfecting pathogens. Ecology Letters.
23(3), 565–574.
mla: Milutinovic, Barbara, et al. “Social Immunity Modulates Competition between
Coinfecting Pathogens.” Ecology Letters, vol. 23, no. 3, Wiley, 2020, pp.
565–74, doi:10.1111/ele.13458.
short: B. Milutinovic, M. Stock, A.V. Grasse, E. Naderlinger, C. Hilbe, S. Cremer,
Ecology Letters 23 (2020) 565–574.
date_created: 2020-01-20T13:32:12Z
date_published: 2020-03-01T00:00:00Z
date_updated: 2023-09-05T16:04:49Z
day: '01'
ddc:
- '570'
department:
- _id: SyCr
- _id: KrCh
doi: 10.1111/ele.13458
ec_funded: 1
external_id:
isi:
- '000507515900001'
file:
- access_level: open_access
checksum: 0cd8be386fa219db02845b7c3991ce04
content_type: application/pdf
creator: dernst
date_created: 2020-11-19T11:27:10Z
date_updated: 2020-11-19T11:27:10Z
file_id: '8776'
file_name: 2020_EcologyLetters_Milutinovic.pdf
file_size: 561749
relation: main_file
success: 1
file_date_updated: 2020-11-19T11:27:10Z
has_accepted_license: '1'
intvolume: ' 23'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '03'
oa: 1
oa_version: Published Version
page: 565-574
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 25DAF0B2-B435-11E9-9278-68D0E5697425
grant_number: CR-118/3-1
name: Host-Parasite Coevolution
publication: Ecology Letters
publication_identifier:
eissn:
- 1461-0248
issn:
- 1461-023X
publication_status: published
publisher: Wiley
quality_controlled: '1'
related_material:
link:
- description: News on IST Homepage
relation: press_release
url: https://ist.ac.at/en/news/social-ants-shapes-disease-outcome/
record:
- id: '13060'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Social immunity modulates competition between coinfecting pathogens
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 23
year: '2020'
...
---
_id: '7346'
abstract:
- lang: eng
text: 'The Price of Anarchy (PoA) is a well-established game-theoretic concept to
shed light on coordination issues arising in open distributed systems. Leaving
agents to selfishly optimize comes with the risk of ending up in sub-optimal states
(in terms of performance and/or costs), compared to a centralized system design.
However, the PoA relies on strong assumptions about agents'' rationality (e.g.,
resources and information) and interactions, whereas in many distributed systems
agents interact locally with bounded resources. They do so repeatedly over time
(in contrast to "one-shot games"), and their strategies may evolve. Using a more
realistic evolutionary game model, this paper introduces a realized evolutionary
Price of Anarchy (ePoA). The ePoA allows an exploration of equilibrium selection
in dynamic distributed systems with multiple equilibria, based on local interactions
of simple memoryless agents. Considering a fundamental game related to virus propagation
on networks, we present analytical bounds on the ePoA in basic network topologies
and for different strategy update dynamics. In particular, deriving stationary
distributions of the stochastic evolutionary process, we find that the Nash equilibria
are not always the most abundant states, and that different processes can feature
significant off-equilibrium behavior, leading to a significantly higher ePoA compared
to the PoA studied traditionally in the literature. '
alternative_title:
- LIPIcs
article_number: '21'
article_processing_charge: No
arxiv: 1
author:
- first_name: Laura
full_name: Schmid, Laura
id: 38B437DE-F248-11E8-B48F-1D18A9856A87
last_name: Schmid
orcid: 0000-0002-6978-7329
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Schmid L, Chatterjee K, Schmid S. The evolutionary price of anarchy: Locally
bounded agents in a dynamic virus game. In: Proceedings of the 23rd International
Conference on Principles of Distributed Systems. Vol 153. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.OPODIS.2019.21'
apa: 'Schmid, L., Chatterjee, K., & Schmid, S. (2020). The evolutionary price
of anarchy: Locally bounded agents in a dynamic virus game. In Proceedings
of the 23rd International Conference on Principles of Distributed Systems
(Vol. 153). Neuchâtel, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.OPODIS.2019.21'
chicago: 'Schmid, Laura, Krishnendu Chatterjee, and Stefan Schmid. “The Evolutionary
Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game.” In Proceedings
of the 23rd International Conference on Principles of Distributed Systems,
Vol. 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.OPODIS.2019.21.'
ieee: 'L. Schmid, K. Chatterjee, and S. Schmid, “The evolutionary price of anarchy:
Locally bounded agents in a dynamic virus game,” in Proceedings of the 23rd
International Conference on Principles of Distributed Systems, Neuchâtel,
Switzerland, 2020, vol. 153.'
ista: 'Schmid L, Chatterjee K, Schmid S. 2020. The evolutionary price of anarchy:
Locally bounded agents in a dynamic virus game. Proceedings of the 23rd International
Conference on Principles of Distributed Systems. OPODIS: International Conference
on Principles of Distributed Systems, LIPIcs, vol. 153, 21.'
mla: 'Schmid, Laura, et al. “The Evolutionary Price of Anarchy: Locally Bounded
Agents in a Dynamic Virus Game.” Proceedings of the 23rd International Conference
on Principles of Distributed Systems, vol. 153, 21, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2020, doi:10.4230/LIPIcs.OPODIS.2019.21.'
short: L. Schmid, K. Chatterjee, S. Schmid, in:, Proceedings of the 23rd International
Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2020.
conference:
end_date: 2019-12-19
location: Neuchâtel, Switzerland
name: 'OPODIS: International Conference on Principles of Distributed Systems'
start_date: 2019-12-17
date_created: 2020-01-21T16:00:26Z
date_published: 2020-02-10T00:00:00Z
date_updated: 2023-02-23T13:05:49Z
day: '10'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.OPODIS.2019.21
external_id:
arxiv:
- '1906.00110'
file:
- access_level: open_access
checksum: 9a91916ac2c21ab42458fcda39ef0b8d
content_type: application/pdf
creator: dernst
date_created: 2020-03-23T09:14:06Z
date_updated: 2020-07-14T12:47:56Z
file_id: '7608'
file_name: 2019_LIPIcS_Schmid.pdf
file_size: 630752
relation: main_file
file_date_updated: 2020-07-14T12:47:56Z
has_accepted_license: '1'
intvolume: ' 153'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Preprint
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: Proceedings of the 23rd International Conference on Principles of Distributed
Systems
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The evolutionary price of anarchy: Locally bounded agents in a dynamic virus
game'
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: 153
year: '2020'
...
---
_id: '15055'
abstract:
- lang: eng
text: Markov decision processes (MDPs) are the defacto framework for sequential
decision making in the presence of stochastic uncertainty. A classical optimization
criterion for MDPs is to maximize the expected discounted-sum payoff, which ignores
low probability catastrophic events with highly negative impact on the system.
On the other hand, risk-averse policies require the probability of undesirable
events to be below a given threshold, but they do not account for optimization
of the expected payoff. We consider MDPs with discounted-sum payoff with failure
states which represent catastrophic outcomes. The objective of risk-constrained
planning is to maximize the expected discounted-sum payoff among risk-averse policies
that ensure the probability to encounter a failure state is below a desired threshold.
Our main contribution is an efficient risk-constrained planning algorithm that
combines UCT-like search with a predictor learned through interaction with the
MDP (in the style of AlphaZero) and with a risk-constrained action selection via
linear programming. We demonstrate the effectiveness of our approach with experiments
on classical MDPs from the literature, including benchmarks with an order of 106
states.
acknowledgement: Krishnendu Chatterjee is supported by the Austrian Science Fund (FWF)
NFN Grant No. S11407-N23 (RiSE/SHiNE), and COST Action GAMENET. Tomas Brazdil is
supported by the Grant Agency of Masaryk University grant no. MUNI/G/0739/2017 and
by the Czech Science Foundation grant No. 18-11193S. Petr Novotny and Jirı Vahala
are supported by the Czech Science Foundation grant No. GJ19-15134Y.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Tomáš
full_name: Brázdil, Tomáš
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: Petr
full_name: Novotný, Petr
last_name: Novotný
- first_name: Jiří
full_name: Vahala, Jiří
last_name: Vahala
citation:
ama: Brázdil T, Chatterjee K, Novotný P, Vahala J. Reinforcement learning of risk-constrained
policies in Markov decision processes. Proceedings of the 34th AAAI Conference
on Artificial Intelligence. 2020;34(06):9794-9801. doi:10.1609/aaai.v34i06.6531
apa: 'Brázdil, T., Chatterjee, K., Novotný, P., & Vahala, J. (2020). Reinforcement
learning of risk-constrained policies in Markov decision processes. Proceedings
of the 34th AAAI Conference on Artificial Intelligence. New York, NY, United
States: Association for the Advancement of Artificial Intelligence. https://doi.org/10.1609/aaai.v34i06.6531'
chicago: Brázdil, Tomáš, Krishnendu Chatterjee, Petr Novotný, and Jiří Vahala. “Reinforcement
Learning of Risk-Constrained Policies in Markov Decision Processes.” Proceedings
of the 34th AAAI Conference on Artificial Intelligence. Association for the
Advancement of Artificial Intelligence, 2020. https://doi.org/10.1609/aaai.v34i06.6531.
ieee: T. Brázdil, K. Chatterjee, P. Novotný, and J. Vahala, “Reinforcement learning
of risk-constrained policies in Markov decision processes,” Proceedings of
the 34th AAAI Conference on Artificial Intelligence, vol. 34, no. 06. Association
for the Advancement of Artificial Intelligence, pp. 9794–9801, 2020.
ista: Brázdil T, Chatterjee K, Novotný P, Vahala J. 2020. Reinforcement learning
of risk-constrained policies in Markov decision processes. Proceedings of the
34th AAAI Conference on Artificial Intelligence. 34(06), 9794–9801.
mla: Brázdil, Tomáš, et al. “Reinforcement Learning of Risk-Constrained Policies
in Markov Decision Processes.” Proceedings of the 34th AAAI Conference on Artificial
Intelligence, vol. 34, no. 06, Association for the Advancement of Artificial
Intelligence, 2020, pp. 9794–801, doi:10.1609/aaai.v34i06.6531.
short: T. Brázdil, K. Chatterjee, P. Novotný, J. Vahala, Proceedings of the 34th
AAAI Conference on Artificial Intelligence 34 (2020) 9794–9801.
conference:
end_date: 2020-02-12
location: New York, NY, United States
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2020-02-07
date_created: 2024-03-04T08:07:22Z
date_published: 2020-04-03T00:00:00Z
date_updated: 2024-03-04T08:30:16Z
day: '03'
department:
- _id: KrCh
doi: 10.1609/aaai.v34i06.6531
external_id:
arxiv:
- '2002.12086'
intvolume: ' 34'
issue: '06'
keyword:
- General Medicine
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2002.12086
month: '04'
oa: 1
oa_version: Preprint
page: 9794-9801
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Proceedings of the 34th AAAI Conference on Artificial Intelligence
publication_identifier:
issn:
- 2374-3468
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
status: public
title: Reinforcement learning of risk-constrained policies in Markov decision processes
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2020'
...
---
_id: '15082'
abstract:
- lang: eng
text: "Two plane drawings of geometric graphs on the same set of points are called
disjoint compatible if their union is plane and they do not have an edge in common.
For a given set S of 2n points two plane drawings of perfect matchings M1 and
M2 (which do not need to be disjoint nor compatible) are disjoint tree-compatible
if there exists a plane drawing of a spanning tree T on S which is disjoint compatible
to both M1 and M2.\r\nWe show that the graph of all disjoint tree-compatible perfect
geometric matchings on 2n points in convex position is connected if and only if
2n ≥ 10. Moreover, in that case the diameter\r\nof this graph is either 4 or 5,
independent of n."
acknowledgement: Research on this work was initiated at the 6th Austrian-Japanese-Mexican-Spanish
Workshop on Discrete Geometry and continued during the 16th European Geometric Graph-Week,
both held near Strobl, Austria. We are grateful to the participants for the inspiring
atmosphere. We especially thank Alexander Pilz for bringing this class of problems
to our attention and Birgit Vogtenhuber for inspiring discussions. D.P. is partially
supported by the FWF grant I 3340-N35 (Collaborative DACH project Arrangements and
Drawings). The research stay of P.P. at IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466
Improvement of internationalization in the field of research and development at
Charles University, through the support of quality projects MSCA-IF. This project
has received funding from the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No 734922.
article_number: '56'
article_processing_charge: No
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Julia
full_name: Obmann, Julia
last_name: Obmann
- first_name: Pavel
full_name: Patak, Pavel
id: B593B804-1035-11EA-B4F1-947645A5BB83
last_name: Patak
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
citation:
ama: 'Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. Disjoint tree-compatible
plane perfect matchings. In: 36th European Workshop on Computational Geometry.
; 2020.'
apa: Aichholzer, O., Obmann, J., Patak, P., Perz, D., & Tkadlec, J. (2020).
Disjoint tree-compatible plane perfect matchings. In 36th European Workshop
on Computational Geometry. Würzburg, Germany, Virtual.
chicago: Aichholzer, Oswin, Julia Obmann, Pavel Patak, Daniel Perz, and Josef Tkadlec.
“Disjoint Tree-Compatible Plane Perfect Matchings.” In 36th European Workshop
on Computational Geometry, 2020.
ieee: O. Aichholzer, J. Obmann, P. Patak, D. Perz, and J. Tkadlec, “Disjoint tree-compatible
plane perfect matchings,” in 36th European Workshop on Computational Geometry,
Würzburg, Germany, Virtual, 2020.
ista: 'Aichholzer O, Obmann J, Patak P, Perz D, Tkadlec J. 2020. Disjoint tree-compatible
plane perfect matchings. 36th European Workshop on Computational Geometry. EuroCG:
European Workshop on Computational Geometry, 56.'
mla: Aichholzer, Oswin, et al. “Disjoint Tree-Compatible Plane Perfect Matchings.”
36th European Workshop on Computational Geometry, 56, 2020.
short: O. Aichholzer, J. Obmann, P. Patak, D. Perz, J. Tkadlec, in:, 36th European
Workshop on Computational Geometry, 2020.
conference:
end_date: 2020-03-18
location: Würzburg, Germany, Virtual
name: 'EuroCG: European Workshop on Computational Geometry'
start_date: 2020-03-16
date_created: 2024-03-05T08:57:17Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2024-03-05T09:00:07Z
day: '01'
department:
- _id: KrCh
- _id: UlWa
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_56.pdf
month: '04'
oa: 1
oa_version: Published Version
publication: 36th European Workshop on Computational Geometry
publication_status: published
quality_controlled: '1'
status: public
title: Disjoint tree-compatible plane perfect matchings
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...
---
_id: '13060'
abstract:
- lang: eng
text: Coinfections with multiple pathogens can result in complex within-host dynamics
affecting virulence and transmission. Whilst multiple infections are intensively
studied in solitary hosts, it is so far unresolved how social host interactions
interfere with pathogen competition, and if this depends on coinfection diversity.
We studied how the collective disease defenses of ants – their social immunity
– influence pathogen competition in coinfections of same or different fungal
pathogen species. Social immunity reduced virulence for all pathogen combinations,
but interfered with spore production only in different-species coinfections. Here,
it decreased overall pathogen sporulation success, whilst simultaneously increasing
co-sporulation on individual cadavers and maintaining a higher pathogen diversity
at the community-level. Mathematical modeling revealed that host sanitary care
alone can modulate competitive outcomes between pathogens, giving advantage to
fast-germinating, thus less grooming-sensitive ones. Host social interactions
can hence modulate infection dynamics in coinfected group members, thereby altering
pathogen communities at the host- and population-level.
article_processing_charge: No
author:
- first_name: Barbara
full_name: Milutinovic, Barbara
id: 2CDC32B8-F248-11E8-B48F-1D18A9856A87
last_name: Milutinovic
orcid: 0000-0002-8214-4758
- first_name: Miriam
full_name: Stock, Miriam
id: 42462816-F248-11E8-B48F-1D18A9856A87
last_name: Stock
- first_name: Anna V
full_name: Grasse, Anna V
id: 406F989C-F248-11E8-B48F-1D18A9856A87
last_name: Grasse
- first_name: Elisabeth
full_name: Naderlinger, Elisabeth
id: 31757262-F248-11E8-B48F-1D18A9856A87
last_name: Naderlinger
- first_name: Christian
full_name: Hilbe, Christian
id: 2FDF8F3C-F248-11E8-B48F-1D18A9856A87
last_name: Hilbe
orcid: 0000-0001-5116-955X
- first_name: Sylvia
full_name: Cremer, Sylvia
id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87
last_name: Cremer
orcid: 0000-0002-2193-3868
citation:
ama: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. Social
immunity modulates competition between coinfecting pathogens. 2020. doi:10.5061/DRYAD.CRJDFN318
apa: Milutinovic, B., Stock, M., Grasse, A. V., Naderlinger, E., Hilbe, C., &
Cremer, S. (2020). Social immunity modulates competition between coinfecting pathogens.
Dryad. https://doi.org/10.5061/DRYAD.CRJDFN318
chicago: Milutinovic, Barbara, Miriam Stock, Anna V Grasse, Elisabeth Naderlinger,
Christian Hilbe, and Sylvia Cremer. “Social Immunity Modulates Competition between
Coinfecting Pathogens.” Dryad, 2020. https://doi.org/10.5061/DRYAD.CRJDFN318.
ieee: B. Milutinovic, M. Stock, A. V. Grasse, E. Naderlinger, C. Hilbe, and S. Cremer,
“Social immunity modulates competition between coinfecting pathogens.” Dryad,
2020.
ista: Milutinovic B, Stock M, Grasse AV, Naderlinger E, Hilbe C, Cremer S. 2020.
Social immunity modulates competition between coinfecting pathogens, Dryad, 10.5061/DRYAD.CRJDFN318.
mla: Milutinovic, Barbara, et al. Social Immunity Modulates Competition between
Coinfecting Pathogens. Dryad, 2020, doi:10.5061/DRYAD.CRJDFN318.
short: B. Milutinovic, M. Stock, A.V. Grasse, E. Naderlinger, C. Hilbe, S. Cremer,
(2020).
date_created: 2023-05-23T16:11:22Z
date_published: 2020-12-19T00:00:00Z
date_updated: 2023-09-05T16:04:48Z
day: '19'
ddc:
- '570'
department:
- _id: SyCr
- _id: KrCh
doi: 10.5061/DRYAD.CRJDFN318
license: https://creativecommons.org/publicdomain/zero/1.0/
main_file_link:
- open_access: '1'
url: https://doi.org/10.5061/dryad.crjdfn318
month: '12'
oa: 1
oa_version: Published Version
publisher: Dryad
related_material:
record:
- id: '7343'
relation: used_in_publication
status: public
status: public
title: Social immunity modulates competition between coinfecting pathogens
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data_reference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...