--- _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 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: '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 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' ... --- _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 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: 2023-10-03T11:36:13Z 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: '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 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: '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 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: '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: '9814' abstract: - lang: eng text: Data and mathematica notebooks for plotting figures from Language learning with communication between learners article_processing_charge: No author: - 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: Josef full_name: Tkadlec, Josef id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87 last_name: Tkadlec orcid: 0000-0002-1097-9684 - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners. 2020. doi:10.6084/m9.figshare.5973013.v1 apa: Ibsen-Jensen, R., Tkadlec, J., Chatterjee, K., & Nowak, M. (2020). Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners. Royal Society. https://doi.org/10.6084/m9.figshare.5973013.v1 chicago: Ibsen-Jensen, Rasmus, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak. “Data and Mathematica Notebooks for Plotting Figures from Language Learning with Communication between Learners from Language Acquisition with Communication between Learners.” Royal Society, 2020. https://doi.org/10.6084/m9.figshare.5973013.v1. ieee: R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, and M. Nowak, “Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners.” Royal Society, 2020. ista: Ibsen-Jensen R, Tkadlec J, Chatterjee K, Nowak M. 2020. Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners, Royal Society, 10.6084/m9.figshare.5973013.v1. mla: Ibsen-Jensen, Rasmus, et al. Data and Mathematica Notebooks for Plotting Figures from Language Learning with Communication between Learners from Language Acquisition with Communication between Learners. Royal Society, 2020, doi:10.6084/m9.figshare.5973013.v1. short: R. Ibsen-Jensen, J. Tkadlec, K. Chatterjee, M. Nowak, (2020). date_created: 2021-08-06T13:09:57Z date_published: 2020-10-15T00:00:00Z date_updated: 2023-10-18T06:36:00Z day: '15' department: - _id: KrCh doi: 10.6084/m9.figshare.5973013.v1 main_file_link: - open_access: '1' url: https://doi.org/10.6084/m9.figshare.5973013.v1 month: '10' oa: 1 oa_version: Published Version publisher: Royal Society related_material: record: - id: '198' relation: used_in_publication status: public status: public title: Data and mathematica notebooks for plotting figures from language learning with communication between learners from language acquisition with communication between learners type: research_data_reference user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf 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 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: '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 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: '7810' abstract: - lang: eng text: "Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointers analysis. The most widely-used framework for interprocedural data-flow analysis is IFDS, which encompasses distributive data-flow functions over a finite domain. On-demand data-flow analyses restrict the focus of the analysis on specific program locations and data facts. This setting provides a natural split between (i) an offline (or preprocessing) phase, where the program is partially analyzed and analysis summaries are created, and (ii) an online (or query) phase, where analysis queries arrive on demand and the summaries are used to speed up answering queries.\r\nIn this work, we consider on-demand IFDS analyses where the queries concern program locations of the same procedure (aka same-context queries). We exploit the fact that flow graphs of programs have low treewidth to develop faster algorithms that are space and time optimal for many common data-flow analyses, in both the preprocessing and the query phase. We also use treewidth to develop query solutions that are embarrassingly parallelizable, i.e. the total work for answering each query is split to a number of threads such that each thread performs only a constant amount of work. Finally, we implement a static analyzer based on our algorithms, and perform a series of on-demand analysis experiments on standard benchmarks. Our experimental results show a drastic speed-up of the queries after only a lightweight preprocessing phase, which significantly outperforms existing techniques." alternative_title: - LNCS 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: Amir Kafshdar full_name: Goharshady, Amir Kafshdar id: 391365CE-F248-11E8-B48F-1D18A9856A87 last_name: Goharshady orcid: 0000-0003-1702-6584 - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 citation: ama: 'Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In: European Symposium on Programming. Vol 12075. Springer Nature; 2020:112-140. doi:10.1007/978-3-030-44914-8_5' apa: 'Chatterjee, K., Goharshady, A. K., Ibsen-Jensen, R., & Pavlogiannis, A. (2020). Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In European Symposium on Programming (Vol. 12075, pp. 112–140). Dublin, Ireland: Springer Nature. https://doi.org/10.1007/978-3-030-44914-8_5' chicago: Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Optimal and Perfectly Parallel Algorithms for On-Demand Data-Flow Analysis.” In European Symposium on Programming, 12075:112–40. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-44914-8_5. ieee: K. Chatterjee, A. K. Goharshady, R. Ibsen-Jensen, and A. Pavlogiannis, “Optimal and perfectly parallel algorithms for on-demand data-flow analysis,” in European Symposium on Programming, Dublin, Ireland, 2020, vol. 12075, pp. 112–140. ista: 'Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A. 2020. Optimal and perfectly parallel algorithms for on-demand data-flow analysis. European Symposium on Programming. ESOP: Programming Languages and Systems, LNCS, vol. 12075, 112–140.' mla: Chatterjee, Krishnendu, et al. “Optimal and Perfectly Parallel Algorithms for On-Demand Data-Flow Analysis.” European Symposium on Programming, vol. 12075, Springer Nature, 2020, pp. 112–40, doi:10.1007/978-3-030-44914-8_5. short: K. Chatterjee, A.K. Goharshady, R. Ibsen-Jensen, A. Pavlogiannis, in:, European Symposium on Programming, Springer Nature, 2020, pp. 112–140. conference: end_date: 2020-04-30 location: Dublin, Ireland name: 'ESOP: Programming Languages and Systems' start_date: 2020-04-25 date_created: 2020-05-10T22:00:50Z date_published: 2020-04-18T00:00:00Z date_updated: 2024-03-28T23:30:34Z day: '18' ddc: - '000' department: - _id: KrCh doi: 10.1007/978-3-030-44914-8_5 external_id: isi: - '000681656800005' file: - access_level: open_access checksum: 8618b80f4cf7b39a60e61a6445ad9807 content_type: application/pdf creator: dernst date_created: 2020-05-26T13:34:48Z date_updated: 2020-07-14T12:48:03Z file_id: '7895' file_name: 2020_LNCS_Chatterjee.pdf file_size: 651250 relation: main_file file_date_updated: 2020-07-14T12:48:03Z has_accepted_license: '1' intvolume: ' 12075' isi: 1 language: - iso: eng month: '04' oa: 1 oa_version: Published Version page: 112-140 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: 266EEEC0-B435-11E9-9278-68D0E5697425 name: Quantitative Game-theoretic Analysis of Blockchain Applications and Smart Contracts - _id: 267066CE-B435-11E9-9278-68D0E5697425 name: Quantitative Analysis of Probablistic Systems with a focus on Crypto-currencies publication: European Symposium on Programming publication_identifier: eissn: - '16113349' isbn: - '9783030449131' issn: - '03029743' 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: Optimal and perfectly parallel algorithms for on-demand data-flow analysis 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: 12075 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: 2024-03-28T23:30:34Z 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: '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 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: 2024-03-28T23:30:34Z 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: '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 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-28T23:30:34Z 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: '6887' abstract: - lang: eng text: 'The fundamental model-checking problem, given as input a model and a specification, asks for the algorithmic verification of whether the model satisfies the specification. Two classical models for reactive systems are graphs and Markov decision processes (MDPs). A basic specification formalism in the verification of reactive systems is the strong fairness (aka Streett) objective, where given different types of requests and corresponding grants, the requirement is that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All omega-regular objectives can be expressed as Streett objectives and hence they are canonical in verification. Consider graphs/MDPs with n vertices, m edges, and a Streett objectives with k pairs, and let b denote the size of the description of the Streett objective for the sets of requests and grants. The current best-known algorithm for the problem requires time O(min(n^2, m sqrt{m log n}) + b log n). In this work we present randomized near-linear time algorithms, with expected running time O~(m + b), where the O~ notation hides poly-log factors. Our randomized algorithms are near-linear in the size of the input, and hence optimal up to poly-log factors. ' alternative_title: - LIPIcs article_number: '7' 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: Wolfgang full_name: Dvorák, Wolfgang last_name: Dvorák - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Alexander full_name: Svozil, Alexander last_name: Svozil citation: ama: 'Chatterjee K, Dvorák W, Henzinger MH, Svozil A. Near-linear time algorithms for Streett objectives in graphs and MDPs. In: Leibniz International Proceedings in Informatics. Vol 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.CONCUR.2019.7' apa: 'Chatterjee, K., Dvorák, W., Henzinger, M. H., & Svozil, A. (2019). Near-linear time algorithms for Streett objectives in graphs and MDPs. In Leibniz International Proceedings in Informatics (Vol. 140). Amsterdam, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.CONCUR.2019.7' chicago: Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Alexander Svozil. “Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs.” In Leibniz International Proceedings in Informatics, Vol. 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.CONCUR.2019.7. ieee: K. Chatterjee, W. Dvorák, M. H. Henzinger, and A. Svozil, “Near-linear time algorithms for Streett objectives in graphs and MDPs,” in Leibniz International Proceedings in Informatics, Amsterdam, Netherlands, 2019, vol. 140. ista: 'Chatterjee K, Dvorák W, Henzinger MH, Svozil A. 2019. Near-linear time algorithms for Streett objectives in graphs and MDPs. Leibniz International Proceedings in Informatics. CONCUR: International Conference on Concurrency Theory, LIPIcs, vol. 140, 7.' mla: Chatterjee, Krishnendu, et al. “Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs.” Leibniz International Proceedings in Informatics, vol. 140, 7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.CONCUR.2019.7. short: K. Chatterjee, W. Dvorák, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. conference: end_date: 2019-08-30 location: Amsterdam, Netherlands name: 'CONCUR: International Conference on Concurrency Theory' start_date: 2019-08-27 date_created: 2019-09-18T08:07:58Z date_published: 2019-08-01T00:00:00Z date_updated: 2022-08-12T10:54:34Z day: '01' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPICS.CONCUR.2019.7 ec_funded: 1 file: - access_level: open_access checksum: e1f0e4061212454574f34a1368d018ec content_type: application/pdf creator: kschuh date_created: 2019-10-01T08:20:30Z date_updated: 2020-07-14T12:47:43Z file_id: '6922' file_name: 2019_LIPIcs_Chatterjee.pdf file_size: 730112 relation: main_file file_date_updated: 2020-07-14T12:47:43Z has_accepted_license: '1' intvolume: ' 140' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' publication: Leibniz International Proceedings in Informatics publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Near-linear time algorithms for Streett objectives in graphs and MDPs 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: 6785fbc1-c503-11eb-8a32-93094b40e1cf volume: 140 year: '2019' ... --- _id: '6885' abstract: - lang: eng text: 'A vector addition system with states (VASS) consists of a finite set of states and counters. A configuration is a state and a value for each counter; a transition changes the state and each counter is incremented, decremented, or left unchanged. While qualitative properties such as state and configuration reachability have been studied for VASS, we consider the long-run average cost of infinite computations of VASS. The cost of a configuration is for each state, a linear combination of the counter values. In the special case of uniform cost functions, the linear combination is the same for all states. The (regular) long-run emptiness problem is, given a VASS, a cost function, and a threshold value, if there is a (lasso-shaped) computation such that the long-run average value of the cost function does not exceed the threshold. For uniform cost functions, we show that the regular long-run emptiness problem is (a) decidable in polynomial time for integer-valued VASS, and (b) decidable but nonelementarily hard for natural-valued VASS (i.e., nonnegative counters). For general cost functions, we show that the problem is (c) NP-complete for integer-valued VASS, and (d) undecidable for natural-valued VASS. Our most interesting result is for (c) integer-valued VASS with general cost functions, where we establish a connection between the regular long-run emptiness problem and quadratic Diophantine inequalities. The general (nonregular) long-run emptiness problem is equally hard as the regular problem in all cases except (c), where it remains open. ' alternative_title: - LIPIcs article_number: '27' 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 last_name: Otop citation: ama: 'Chatterjee K, Henzinger TA, Otop J. Long-run average behavior of vector addition systems with states. In: Vol 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.CONCUR.2019.27' apa: 'Chatterjee, K., Henzinger, T. A., & Otop, J. (2019). Long-run average behavior of vector addition systems with states (Vol. 140). Presented at the CONCUR: International Conference on Concurrency Theory, Amsterdam, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.CONCUR.2019.27' chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Long-Run Average Behavior of Vector Addition Systems with States,” Vol. 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.CONCUR.2019.27. ieee: 'K. Chatterjee, T. A. Henzinger, and J. Otop, “Long-run average behavior of vector addition systems with states,” presented at the CONCUR: International Conference on Concurrency Theory, Amsterdam, Netherlands, 2019, vol. 140.' ista: 'Chatterjee K, Henzinger TA, Otop J. 2019. Long-run average behavior of vector addition systems with states. CONCUR: International Conference on Concurrency Theory, LIPIcs, vol. 140, 27.' mla: Chatterjee, Krishnendu, et al. Long-Run Average Behavior of Vector Addition Systems with States. Vol. 140, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.CONCUR.2019.27. short: K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. conference: end_date: 2019-08-30 location: Amsterdam, Netherlands name: 'CONCUR: International Conference on Concurrency Theory' start_date: 2019-08-27 date_created: 2019-09-18T08:06:14Z date_published: 2019-08-01T00:00:00Z date_updated: 2021-01-12T08:09:27Z day: '01' ddc: - '000' department: - _id: ToHe - _id: KrCh doi: 10.4230/LIPICS.CONCUR.2019.27 file: - access_level: open_access checksum: 4985e26e1572d1575d64d38acabd71d6 content_type: application/pdf creator: kschuh date_created: 2019-09-27T12:09:35Z date_updated: 2020-07-14T12:47:43Z file_id: '6914' file_name: 2019_LIPIcs_Chatterjee.pdf file_size: 538120 relation: main_file file_date_updated: 2020-07-14T12:47:43Z has_accepted_license: '1' intvolume: ' 140' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 25F2ACDE-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Rigorous Systems Engineering publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Long-run average behavior of vector addition systems with states 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: 140 year: '2019' ... --- _id: '6889' abstract: - lang: eng text: 'We study Markov decision processes and turn-based stochastic games with parity conditions. There are three qualitative winning criteria, namely, sure winning, which requires all paths to satisfy the condition, almost-sure winning, which requires the condition to be satisfied with probability 1, and limit-sure winning, which requires the condition to be satisfied with probability arbitrarily close to 1. We study the combination of two of these criteria for parity conditions, e.g., there are two parity conditions one of which must be won surely, and the other almost-surely. The problem has been studied recently by Berthon et al. for MDPs with combination of sure and almost-sure winning, under infinite-memory strategies, and the problem has been established to be in NP cap co-NP. Even in MDPs there is a difference between finite-memory and infinite-memory strategies. Our main results for combination of sure and almost-sure winning are as follows: (a) we show that for MDPs with finite-memory strategies the problem is in NP cap co-NP; (b) we show that for turn-based stochastic games the problem is co-NP-complete, both for finite-memory and infinite-memory strategies; and (c) we present algorithmic results for the finite-memory case, both for MDPs and turn-based stochastic games, by reduction to non-stochastic parity games. In addition we show that all the above complexity results also carry over to combination of sure and limit-sure winning, and results for all other combinations can be derived from existing results in the literature. Thus we present a complete picture for the study of combinations of two qualitative winning criteria for parity conditions in MDPs and turn-based stochastic games. ' alternative_title: - LIPIcs article_number: '6' author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Nir full_name: Piterman, Nir last_name: Piterman citation: ama: 'Chatterjee K, Piterman N. Combinations of Qualitative Winning for Stochastic Parity Games. In: Vol 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.CONCUR.2019.6' apa: 'Chatterjee, K., & Piterman, N. (2019). Combinations of Qualitative Winning for Stochastic Parity Games (Vol. 140). Presented at the CONCUR: International Conference on Concurrency Theory, Amsterdam, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.CONCUR.2019.6' chicago: Chatterjee, Krishnendu, and Nir Piterman. “Combinations of Qualitative Winning for Stochastic Parity Games,” Vol. 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.CONCUR.2019.6. ieee: 'K. Chatterjee and N. Piterman, “Combinations of Qualitative Winning for Stochastic Parity Games,” presented at the CONCUR: International Conference on Concurrency Theory, Amsterdam, Netherlands, 2019, vol. 140.' ista: 'Chatterjee K, Piterman N. 2019. Combinations of Qualitative Winning for Stochastic Parity Games. CONCUR: International Conference on Concurrency Theory, LIPIcs, vol. 140, 6.' mla: Chatterjee, Krishnendu, and Nir Piterman. Combinations of Qualitative Winning for Stochastic Parity Games. Vol. 140, 6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.CONCUR.2019.6. short: K. Chatterjee, N. Piterman, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. conference: end_date: 2019-08-30 location: Amsterdam, Netherlands name: 'CONCUR: International Conference on Concurrency Theory' start_date: 2019-08-27 date_created: 2019-09-18T08:11:43Z date_published: 2019-08-01T00:00:00Z date_updated: 2021-01-12T08:09:28Z day: '01' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPICS.CONCUR.2019.6 file: - access_level: open_access checksum: 7b2ecfd4d9d02360308c0ca986fc10a7 content_type: application/pdf creator: kschuh date_created: 2019-10-01T08:49:45Z date_updated: 2020-07-14T12:47:43Z file_id: '6923' file_name: 2019_LIPIcs_Chatterjee.pdf file_size: 509163 relation: main_file file_date_updated: 2020-07-14T12:47:43Z has_accepted_license: '1' intvolume: ' 140' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 25892FC0-B435-11E9-9278-68D0E5697425 grant_number: ICT15-003 name: Efficient Algorithms for Computer Aided Verification publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: 1 status: public title: Combinations of Qualitative Winning for Stochastic Parity 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: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 140 year: '2019' ... --- _id: '6884' abstract: - lang: eng text: 'In two-player games on graphs, the players move a token through a graph to produce a finite or infinite path, which determines the qualitative winner or quantitative payoff of the game. We study bidding games in which the players bid for the right to move the token. Several bidding rules were studied previously. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the "bank" rather than the other player. Taxman bidding spans the spectrum between Richman and poorman bidding. They are parameterized by a constant tau in [0,1]: portion tau of the winning bid is paid to the other player, and portion 1-tau to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games. It was previously shown that both Richman and poorman infinite-duration games with qualitative objectives reduce to reachability games, and we show a similar result here. Our most interesting results concern quantitative taxman games, namely mean-payoff games, where poorman and Richman bidding differ significantly. A central quantity in these games is the ratio between the two players'' initial budgets. While in poorman mean-payoff games, the optimal payoff of a player depends on the initial ratio, in Richman bidding, the payoff depends only on the structure of the game. In both games the optimal payoffs can be found using (different) probabilistic connections with random-turn games in which in each turn, instead of bidding, a coin is tossed to determine which player moves. While the value with Richman bidding equals the value of a random-turn game with an un-biased coin, with poorman bidding, the bias in the coin is the initial ratio of the budgets. We give a complete classification of mean-payoff taxman games that is based on a probabilistic connection: the value of a taxman bidding game with parameter tau and initial ratio r, equals the value of a random-turn game that uses a coin with bias F(tau, r) = (r+tau * (1-r))/(1+tau). Thus, we show that Richman bidding is the exception; namely, for every tau <1, the value of the game depends on the initial ratio. Our proof technique simplifies and unifies the previous proof techniques for both Richman and poorman bidding. ' alternative_title: - LIPIcs article_number: '11' author: - first_name: Guy full_name: Avni, Guy id: 463C8BC2-F248-11E8-B48F-1D18A9856A87 last_name: Avni orcid: 0000-0001-5588-8287 - 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: Dorde full_name: Zikelic, Dorde id: 294AA7A6-F248-11E8-B48F-1D18A9856A87 last_name: Zikelic citation: ama: 'Avni G, Henzinger TA, Zikelic D. Bidding mechanisms in graph games. In: Vol 138. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019. doi:10.4230/LIPICS.MFCS.2019.11' apa: 'Avni, G., Henzinger, T. A., & Zikelic, D. (2019). Bidding mechanisms in graph games (Vol. 138). Presented at the MFCS: nternational Symposium on Mathematical Foundations of Computer Science, Aachen, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.MFCS.2019.11' chicago: Avni, Guy, Thomas A Henzinger, and Dorde Zikelic. “Bidding Mechanisms in Graph Games,” Vol. 138. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.MFCS.2019.11. ieee: 'G. Avni, T. A. Henzinger, and D. Zikelic, “Bidding mechanisms in graph games,” presented at the MFCS: nternational Symposium on Mathematical Foundations of Computer Science, Aachen, Germany, 2019, vol. 138.' ista: 'Avni G, Henzinger TA, Zikelic D. 2019. Bidding mechanisms in graph games. MFCS: nternational Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 138, 11.' mla: Avni, Guy, et al. Bidding Mechanisms in Graph Games. Vol. 138, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.MFCS.2019.11. short: G. Avni, T.A. Henzinger, D. Zikelic, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. conference: end_date: 2019-08-30 location: Aachen, Germany name: 'MFCS: nternational Symposium on Mathematical Foundations of Computer Science' start_date: 2019-08-26 date_created: 2019-09-18T08:04:26Z date_published: 2019-08-01T00:00:00Z date_updated: 2023-08-07T14:08:34Z day: '01' ddc: - '004' department: - _id: ToHe - _id: KrCh doi: 10.4230/LIPICS.MFCS.2019.11 ec_funded: 1 external_id: arxiv: - '1905.03835' file: - access_level: open_access checksum: 6346e116a4f4ed1414174d96d2c4fbd7 content_type: application/pdf creator: kschuh date_created: 2019-09-27T11:45:15Z date_updated: 2020-07-14T12:47:42Z file_id: '6913' file_name: 2019_LIPIcs_Avni.pdf file_size: 554457 relation: main_file file_date_updated: 2020-07-14T12:47:42Z has_accepted_license: '1' intvolume: ' 138' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 2564DBCA-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '665385' name: International IST Doctoral Program - _id: 264B3912-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02369 name: Formal Methods meets Algorithmic Game Theory - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize - _id: 25F2ACDE-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Rigorous Systems Engineering publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '9239' relation: later_version status: public scopus_import: 1 status: public title: Bidding mechanisms in graph 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: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 138 year: '2019' ... --- _id: '5948' abstract: - lang: eng text: We study the termination problem for nondeterministic probabilistic programs. We consider the bounded termination problem that asks whether the supremum of the expected termination time over all schedulers is bounded. First, we show that ranking supermartingales (RSMs) are both sound and complete for proving bounded termination over nondeterministic probabilistic programs. For nondeterministic probabilistic programs a previous result claimed that RSMs are not complete for bounded termination, whereas our result corrects the previous flaw and establishes completeness with a rigorous proof. Second, we present the first sound approach to establish lower bounds on expected termination time through RSMs. alternative_title: - LNCS article_processing_charge: No author: - 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 citation: ama: 'Fu H, Chatterjee K. Termination of nondeterministic probabilistic programs. In: International Conference on Verification, Model Checking, and Abstract Interpretation. Vol 11388. Springer Nature; 2019:468-490. doi:10.1007/978-3-030-11245-5_22' apa: 'Fu, H., & Chatterjee, K. (2019). Termination of nondeterministic probabilistic programs. In International Conference on Verification, Model Checking, and Abstract Interpretation (Vol. 11388, pp. 468–490). Cascais, Portugal: Springer Nature. https://doi.org/10.1007/978-3-030-11245-5_22' chicago: Fu, Hongfei, and Krishnendu Chatterjee. “Termination of Nondeterministic Probabilistic Programs.” In International Conference on Verification, Model Checking, and Abstract Interpretation, 11388:468–90. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-11245-5_22. ieee: H. Fu and K. Chatterjee, “Termination of nondeterministic probabilistic programs,” in International Conference on Verification, Model Checking, and Abstract Interpretation, Cascais, Portugal, 2019, vol. 11388, pp. 468–490. ista: 'Fu H, Chatterjee K. 2019. Termination of nondeterministic probabilistic programs. International Conference on Verification, Model Checking, and Abstract Interpretation. VMCAI: Verification, Model Checking, and Abstract Interpretation, LNCS, vol. 11388, 468–490.' mla: Fu, Hongfei, and Krishnendu Chatterjee. “Termination of Nondeterministic Probabilistic Programs.” International Conference on Verification, Model Checking, and Abstract Interpretation, vol. 11388, Springer Nature, 2019, pp. 468–90, doi:10.1007/978-3-030-11245-5_22. short: H. Fu, K. Chatterjee, in:, International Conference on Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2019, pp. 468–490. conference: end_date: 2019-01-15 location: Cascais, Portugal name: 'VMCAI: Verification, Model Checking, and Abstract Interpretation' start_date: 2019-01-13 date_created: 2019-02-10T22:59:17Z date_published: 2019-01-11T00:00:00Z date_updated: 2023-08-24T14:42:22Z day: '11' department: - _id: KrCh doi: 10.1007/978-3-030-11245-5_22 external_id: arxiv: - '1701.02944' isi: - '000931943000022' intvolume: ' 11388' isi: 1 language: - iso: eng main_file_link: - url: https://arxiv.org/abs/1701.02944 month: '01' oa_version: Preprint page: 468-490 project: - _id: 25892FC0-B435-11E9-9278-68D0E5697425 grant_number: ICT15-003 name: Efficient Algorithms for Computer Aided Verification - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering publication: International Conference on Verification, Model Checking, and Abstract Interpretation publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Termination of nondeterministic probabilistic programs type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 11388 year: '2019' ...