--- _id: '5408' abstract: - lang: eng text: "We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are \r\nEXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. " alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen - first_name: Sumit full_name: Nain, Sumit last_name: Nain - first_name: Moshe full_name: Vardi, Moshe last_name: Vardi citation: ama: Chatterjee K, Doyen L, Nain S, Vardi M. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria; 2013. doi:10.15479/AT:IST-2013-141-v1-1 apa: Chatterjee, K., Doyen, L., Nain, S., & Vardi, M. (2013). The complexity of partial-observation stochastic parity games with finite-memory strategies. IST Austria. https://doi.org/10.15479/AT:IST-2013-141-v1-1 chicago: Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-141-v1-1. ieee: K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, The complexity of partial-observation stochastic parity games with finite-memory strategies. IST Austria, 2013. ista: Chatterjee K, Doyen L, Nain S, Vardi M. 2013. The complexity of partial-observation stochastic parity games with finite-memory strategies, IST Austria, 17p. mla: Chatterjee, Krishnendu, et al. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria, 2013, doi:10.15479/AT:IST-2013-141-v1-1. short: K. Chatterjee, L. Doyen, S. Nain, M. Vardi, The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies, IST Austria, 2013. date_created: 2018-12-12T11:39:10Z date_published: 2013-09-12T00:00:00Z date_updated: 2023-02-23T10:33:11Z day: '12' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2013-141-v1-1 file: - access_level: open_access checksum: 226bc791124f8d3138379778ce834e86 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:16Z date_updated: 2020-07-14T12:46:46Z file_id: '5477' file_name: IST-2013-141-v1+1_main-tech-rpt.pdf file_size: 300481 relation: main_file file_date_updated: 2020-07-14T12:46:46Z has_accepted_license: '1' language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: '17' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '141' related_material: record: - id: '2213' relation: later_version status: public status: public title: The complexity of partial-observation stochastic parity games with finite-memory strategies type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5410' abstract: - lang: eng text: "Board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in development of mathematical and logical skills, but also in emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. \r\nOur approach generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. Also, the presence of such states for standard game variants like Tic-Tac-Toe on board size 4x4 opens up new games to be played that have not been played for ages since the default start state is heavily biased. " alternative_title: - IST Austria Technical Report author: - first_name: Umair full_name: Ahmed, Umair last_name: Ahmed - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Sumit full_name: Gulwani, Sumit last_name: Gulwani citation: ama: Ahmed U, Chatterjee K, Gulwani S. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-146-v1-1 apa: Ahmed, U., Chatterjee, K., & Gulwani, S. (2013). Automatic generation of alternative starting positions for traditional board games. IST Austria. https://doi.org/10.15479/AT:IST-2013-146-v1-1 chicago: Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-146-v1-1. ieee: U. Ahmed, K. Chatterjee, and S. Gulwani, Automatic generation of alternative starting positions for traditional board games. IST Austria, 2013. ista: Ahmed U, Chatterjee K, Gulwani S. 2013. Automatic generation of alternative starting positions for traditional board games, IST Austria, 13p. mla: Ahmed, Umair, et al. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-146-v1-1. short: U. Ahmed, K. Chatterjee, S. Gulwani, Automatic Generation of Alternative Starting Positions for Traditional Board Games, IST Austria, 2013. date_created: 2018-12-12T11:39:10Z date_published: 2013-12-03T00:00:00Z date_updated: 2023-02-23T10:00:50Z day: '03' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2013-146-v1-1 file: - access_level: open_access checksum: 409f3aaaf1184e4057b89cbb449dac80 content_type: application/pdf creator: system date_created: 2018-12-12T11:54:06Z date_updated: 2020-07-14T12:46:46Z file_id: '5528' file_name: IST-2013-146-v1+1_main.pdf file_size: 818189 relation: main_file file_date_updated: 2020-07-14T12:46:46Z has_accepted_license: '1' language: - iso: eng month: '12' oa: 1 oa_version: Published Version page: '13' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '146' related_material: record: - id: '1481' relation: later_version status: public status: public title: Automatic generation of alternative starting positions for traditional board games type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2329' abstract: - lang: eng text: 'Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work, we consider both finite-state game graphs, and recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion. The objectives we study are multidimensional mean-payoff objectives, where the goal of player 1 is to ensure that the mean-payoff is non-negative in all dimensions. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation. Our main contributions are as follows: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of the weights are fixed; whereas if the number of dimensions is arbitrary, then the problem is known to be coNP-complete. (2) We show that pushdown graphs with multidimensional mean-payoff objectives can be solved in polynomial time. For both (1) and (2) our algorithms are based on hyperplane separation technique. (3) For pushdown games under global strategies both one and multidimensional mean-payoff objectives problems are known to be undecidable, and we show that under modular strategies the multidimensional problem is also undecidable; under modular strategies the one-dimensional problem is NP-complete. We show that if the number of modules, the number of exits, and the maximal absolute value of the weights are fixed, then pushdown games under modular strategies with one-dimensional mean-payoff objectives can be solved in polynomial time, and if either the number of exits or the number of modules is unbounded, then the problem is NP-hard. (4) Finally we show that a fixed parameter tractable algorithm for finite-state multidimensional mean-payoff games or pushdown games under modular strategies with one-dimensional mean-payoff objectives would imply the fixed parameter tractability of parity games.' alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Yaron full_name: Velner, Yaron last_name: Velner citation: ama: Chatterjee K, Velner Y. Hyperplane separation technique for multidimensional mean-payoff games. 2013;8052:500-515. doi:10.1007/978-3-642-40184-8_35 apa: 'Chatterjee, K., & Velner, Y. (2013). Hyperplane separation technique for multidimensional mean-payoff games. Presented at the CONCUR: Concurrency Theory, Buenos Aires, Argentinia: Springer. https://doi.org/10.1007/978-3-642-40184-8_35' chicago: Chatterjee, Krishnendu, and Yaron Velner. “Hyperplane Separation Technique for Multidimensional Mean-Payoff Games.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40184-8_35. ieee: K. Chatterjee and Y. Velner, “Hyperplane separation technique for multidimensional mean-payoff games,” vol. 8052. Springer, pp. 500–515, 2013. ista: Chatterjee K, Velner Y. 2013. Hyperplane separation technique for multidimensional mean-payoff games. 8052, 500–515. mla: Chatterjee, Krishnendu, and Yaron Velner. Hyperplane Separation Technique for Multidimensional Mean-Payoff Games. Vol. 8052, Springer, 2013, pp. 500–15, doi:10.1007/978-3-642-40184-8_35. short: K. Chatterjee, Y. Velner, 8052 (2013) 500–515. conference: end_date: 2013-08-30 location: Buenos Aires, Argentinia name: 'CONCUR: Concurrency Theory' start_date: 2013-08-27 date_created: 2018-12-11T11:57:01Z date_published: 2013-08-01T00:00:00Z date_updated: 2023-02-23T13:00:42Z day: '01' department: - _id: KrCh doi: 10.1007/978-3-642-40184-8_35 ec_funded: 1 external_id: arxiv: - '1210.3141' intvolume: ' 8052' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1210.3141 month: '08' oa: 1 oa_version: Preprint page: 500 - 515 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication_status: published publisher: Springer publist_id: '4597' quality_controlled: '1' related_material: record: - id: '717' relation: later_version status: public scopus_import: 1 series_title: Lecture Notes in Computer Science status: public title: Hyperplane separation technique for multidimensional mean-payoff games type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8052 year: '2013' ... --- _id: '9749' abstract: - lang: eng text: Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise. article_processing_charge: No author: - first_name: Benjamin full_name: Zagorsky, Benjamin last_name: Zagorsky - first_name: Johannes full_name: Reiter, Johannes id: 4A918E98-F248-11E8-B48F-1D18A9856A87 last_name: Reiter orcid: 0000-0002-0170-7353 - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Zagorsky B, Reiter J, Chatterjee K, Nowak M. Forgiver triumphs in alternating prisoner’s dilemma . 2013. doi:10.1371/journal.pone.0080814.s001 apa: Zagorsky, B., Reiter, J., Chatterjee, K., & Nowak, M. (2013). Forgiver triumphs in alternating prisoner’s dilemma . Public Library of Science. https://doi.org/10.1371/journal.pone.0080814.s001 chicago: Zagorsky, Benjamin, Johannes Reiter, Krishnendu Chatterjee, and Martin Nowak. “Forgiver Triumphs in Alternating Prisoner’s Dilemma .” Public Library of Science, 2013. https://doi.org/10.1371/journal.pone.0080814.s001. ieee: B. Zagorsky, J. Reiter, K. Chatterjee, and M. Nowak, “Forgiver triumphs in alternating prisoner’s dilemma .” Public Library of Science, 2013. ista: Zagorsky B, Reiter J, Chatterjee K, Nowak M. 2013. Forgiver triumphs in alternating prisoner’s dilemma , Public Library of Science, 10.1371/journal.pone.0080814.s001. mla: Zagorsky, Benjamin, et al. Forgiver Triumphs in Alternating Prisoner’s Dilemma . Public Library of Science, 2013, doi:10.1371/journal.pone.0080814.s001. short: B. Zagorsky, J. Reiter, K. Chatterjee, M. Nowak, (2013). date_created: 2021-07-28T15:45:07Z date_published: 2013-12-12T00:00:00Z date_updated: 2023-02-23T10:34:39Z day: '12' department: - _id: KrCh doi: 10.1371/journal.pone.0080814.s001 month: '12' oa_version: Published Version publisher: Public Library of Science related_material: record: - id: '2247' relation: used_in_publication status: public status: public title: 'Forgiver triumphs in alternating prisoner''s dilemma ' type: research_data_reference user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf year: '2013' ... --- _id: '10902' abstract: - lang: eng text: We consider how to edit strings from a source language so that the edited strings belong to a target language, where the languages are given as deterministic finite automata. Non-streaming (or offline) transducers perform edits given the whole source string. We show that the class of deterministic one-pass transducers with registers along with increment and min operation suffices for computing optimal edit distance, whereas the same class of transducers without the min operation is not sufficient. Streaming (or online) transducers perform edits as the letters of the source string are received. We present a polynomial time algorithm for the partial-repair problem that given a bound α asks for the construction of a deterministic streaming transducer (if one exists) that ensures that the ‘maximum fraction’ η of the strings of the source language are edited, within cost α, to the target language. acknowledgement: 'The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award. Thanks to Gabriele Puppis for suggesting the problem of identifying a deterministic transducer to compute the optimal cost, and to Martin Chmelik for his comments on the introduction.' 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: Siddhesh full_name: Chaubal, Siddhesh last_name: Chaubal - first_name: Sasha full_name: Rubin, Sasha id: 2EC51194-F248-11E8-B48F-1D18A9856A87 last_name: Rubin citation: ama: 'Chatterjee K, Chaubal S, Rubin S. How to travel between languages. In: 7th International Conference on Language and Automata Theory and Applications. Vol 7810. LNCS. Berlin, Heidelberg: Springer Nature; 2013:214-225. doi:10.1007/978-3-642-37064-9_20' apa: 'Chatterjee, K., Chaubal, S., & Rubin, S. (2013). How to travel between languages. In 7th International Conference on Language and Automata Theory and Applications (Vol. 7810, pp. 214–225). Berlin, Heidelberg: Springer Nature. https://doi.org/10.1007/978-3-642-37064-9_20' chicago: 'Chatterjee, Krishnendu, Siddhesh Chaubal, and Sasha Rubin. “How to Travel between Languages.” In 7th International Conference on Language and Automata Theory and Applications, 7810:214–25. LNCS. Berlin, Heidelberg: Springer Nature, 2013. https://doi.org/10.1007/978-3-642-37064-9_20.' ieee: K. Chatterjee, S. Chaubal, and S. Rubin, “How to travel between languages,” in 7th International Conference on Language and Automata Theory and Applications, Bilbao, Spain, 2013, vol. 7810, pp. 214–225. ista: 'Chatterjee K, Chaubal S, Rubin S. 2013. How to travel between languages. 7th International Conference on Language and Automata Theory and Applications. LATA: Conference on Language and Automata Theory and ApplicationsLNCS, LNCS, vol. 7810, 214–225.' mla: Chatterjee, Krishnendu, et al. “How to Travel between Languages.” 7th International Conference on Language and Automata Theory and Applications, vol. 7810, Springer Nature, 2013, pp. 214–25, doi:10.1007/978-3-642-37064-9_20. short: K. Chatterjee, S. Chaubal, S. Rubin, in:, 7th International Conference on Language and Automata Theory and Applications, Springer Nature, Berlin, Heidelberg, 2013, pp. 214–225. conference: end_date: 2013-04-05 location: Bilbao, Spain name: 'LATA: Conference on Language and Automata Theory and Applications' start_date: 2013-04-02 date_created: 2022-03-21T07:56:21Z date_published: 2013-04-15T00:00:00Z date_updated: 2023-09-05T15:10:38Z day: '15' department: - _id: KrCh doi: 10.1007/978-3-642-37064-9_20 ec_funded: 1 intvolume: ' 7810' language: - iso: eng month: '04' oa_version: None page: 214-225 place: Berlin, Heidelberg project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: 7th International Conference on Language and Automata Theory and Applications publication_identifier: eisbn: - '9783642370649' eissn: - 1611-3349 isbn: - '9783642370632' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' series_title: LNCS status: public title: How to travel between languages type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 7810 year: '2013' ... --- _id: '2247' abstract: - lang: eng text: Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise. article_number: e80814 author: - first_name: Benjamin full_name: Zagorsky, Benjamin last_name: Zagorsky - first_name: Johannes full_name: Reiter, Johannes id: 4A918E98-F248-11E8-B48F-1D18A9856A87 last_name: Reiter orcid: 0000-0002-0170-7353 - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Zagorsky B, Reiter J, Chatterjee K, Nowak M. Forgiver triumphs in alternating prisoner’s dilemma . PLoS One. 2013;8(12). doi:10.1371/journal.pone.0080814 apa: Zagorsky, B., Reiter, J., Chatterjee, K., & Nowak, M. (2013). Forgiver triumphs in alternating prisoner’s dilemma . PLoS One. Public Library of Science. https://doi.org/10.1371/journal.pone.0080814 chicago: Zagorsky, Benjamin, Johannes Reiter, Krishnendu Chatterjee, and Martin Nowak. “Forgiver Triumphs in Alternating Prisoner’s Dilemma .” PLoS One. Public Library of Science, 2013. https://doi.org/10.1371/journal.pone.0080814. ieee: B. Zagorsky, J. Reiter, K. Chatterjee, and M. Nowak, “Forgiver triumphs in alternating prisoner’s dilemma ,” PLoS One, vol. 8, no. 12. Public Library of Science, 2013. ista: Zagorsky B, Reiter J, Chatterjee K, Nowak M. 2013. Forgiver triumphs in alternating prisoner’s dilemma . PLoS One. 8(12), e80814. mla: Zagorsky, Benjamin, et al. “Forgiver Triumphs in Alternating Prisoner’s Dilemma .” PLoS One, vol. 8, no. 12, e80814, Public Library of Science, 2013, doi:10.1371/journal.pone.0080814. short: B. Zagorsky, J. Reiter, K. Chatterjee, M. Nowak, PLoS One 8 (2013). date_created: 2018-12-11T11:56:33Z date_published: 2013-12-12T00:00:00Z date_updated: 2023-09-07T11:40:43Z day: '12' ddc: - '000' department: - _id: KrCh doi: 10.1371/journal.pone.0080814 ec_funded: 1 file: - access_level: open_access checksum: 808e8b9e6e89658bee4ffbbfac1bd19d content_type: application/pdf creator: system date_created: 2018-12-12T10:11:15Z date_updated: 2020-07-14T12:45:34Z file_id: '4868' file_name: IST-2016-409-v1+1_journal.pone.0080814.pdf file_size: 1050042 relation: main_file file_date_updated: 2020-07-14T12:45:34Z has_accepted_license: '1' intvolume: ' 8' issue: '12' language: - iso: eng month: '12' 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: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: PLoS One publication_status: published publisher: Public Library of Science publist_id: '4702' pubrep_id: '409' quality_controlled: '1' related_material: record: - id: '9749' relation: research_data status: public - id: '1400' relation: dissertation_contains status: public scopus_import: 1 status: public title: 'Forgiver triumphs in alternating prisoner''s dilemma ' 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: 8 year: '2013' ... --- _id: '2858' abstract: - lang: eng text: Tumor growth is caused by the acquisition of driver mutations, which enhance the net reproductive rate of cells. Driver mutations may increase cell division, reduce cell death, or allow cells to overcome density-limiting effects. We study the dynamics of tumor growth as one additional driver mutation is acquired. Our models are based on two-type branching processes that terminate in either tumor disappearance or tumor detection. In our first model, both cell types grow exponentially, with a faster rate for cells carrying the additional driver. We find that the additional driver mutation does not affect the survival probability of the lesion, but can substantially reduce the time to reach the detectable size if the lesion is slow growing. In our second model, cells lacking the additional driver cannot exceed a fixed carrying capacity, due to density limitations. In this case, the time to detection depends strongly on this carrying capacity. Our model provides a quantitative framework for studying tumor dynamics during different stages of progression. We observe that early, small lesions need additional drivers, while late stage metastases are only marginally affected by them. These results help to explain why additional driver mutations are typically not detected in fast-growing metastases. author: - first_name: Johannes full_name: Reiter, Johannes id: 4A918E98-F248-11E8-B48F-1D18A9856A87 last_name: Reiter orcid: 0000-0002-0170-7353 - first_name: Ivana full_name: Božić, Ivana last_name: Božić - first_name: Benjamin full_name: Allen, Benjamin id: 135B5B70-E9D2-11E9-BD74-BB415DA2B523 last_name: Allen - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Reiter J, Božić I, Allen B, Chatterjee K, Nowak M. The effect of one additional driver mutation on tumor progression. Evolutionary Applications. 2013;6(1):34-45. doi:10.1111/eva.12020 apa: Reiter, J., Božić, I., Allen, B., Chatterjee, K., & Nowak, M. (2013). The effect of one additional driver mutation on tumor progression. Evolutionary Applications. Wiley-Blackwell. https://doi.org/10.1111/eva.12020 chicago: Reiter, Johannes, Ivana Božić, Benjamin Allen, Krishnendu Chatterjee, and Martin Nowak. “The Effect of One Additional Driver Mutation on Tumor Progression.” Evolutionary Applications. Wiley-Blackwell, 2013. https://doi.org/10.1111/eva.12020. ieee: J. Reiter, I. Božić, B. Allen, K. Chatterjee, and M. Nowak, “The effect of one additional driver mutation on tumor progression,” Evolutionary Applications, vol. 6, no. 1. Wiley-Blackwell, pp. 34–45, 2013. ista: Reiter J, Božić I, Allen B, Chatterjee K, Nowak M. 2013. The effect of one additional driver mutation on tumor progression. Evolutionary Applications. 6(1), 34–45. mla: Reiter, Johannes, et al. “The Effect of One Additional Driver Mutation on Tumor Progression.” Evolutionary Applications, vol. 6, no. 1, Wiley-Blackwell, 2013, pp. 34–45, doi:10.1111/eva.12020. short: J. Reiter, I. Božić, B. Allen, K. Chatterjee, M. Nowak, Evolutionary Applications 6 (2013) 34–45. date_created: 2018-12-11T11:59:58Z date_published: 2013-01-01T00:00:00Z date_updated: 2023-09-07T11:40:43Z day: '01' ddc: - '570' department: - _id: KrCh doi: 10.1111/eva.12020 ec_funded: 1 file: - access_level: open_access checksum: e2955b3889f8a823c3d5a72cb16f8957 content_type: application/pdf creator: system date_created: 2018-12-12T10:15:50Z date_updated: 2020-07-14T12:45:51Z file_id: '5173' file_name: IST-2016-415-v1+1_Reiter_et_al-2013-Evolutionary_Applications.pdf file_size: 1172037 relation: main_file file_date_updated: 2020-07-14T12:45:51Z has_accepted_license: '1' intvolume: ' 6' issue: '1' language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: 34 - 45 project: - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory publication: Evolutionary Applications publication_status: published publisher: Wiley-Blackwell publist_id: '3931' pubrep_id: '415' quality_controlled: '1' related_material: record: - id: '1400' relation: dissertation_contains status: public scopus_import: 1 status: public title: The effect of one additional driver mutation on tumor progression 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: 6 year: '2013' ... --- _id: '2816' abstract: - lang: eng text: In solid tumors, targeted treatments can lead to dramatic regressions, but responses are often short-lived because resistant cancer cells arise. The major strategy proposed for overcoming resistance is combination therapy. We present a mathematical model describing the evolutionary dynamics of lesions in response to treatment. We first studied 20 melanoma patients receiving vemurafenib. We then applied our model to an independent set of pancreatic, colorectal, and melanoma cancer patients with metastatic disease. We find that dual therapy results in long-term disease control for most patients, if there are no single mutations that cause cross-resistance to both drugs; in patients with large disease burden, triple therapy is needed. We also find that simultaneous therapy with two drugs is much more effective than sequential therapy. Our results provide realistic expectations for the efficacy of new drug combinations and inform the design of trials for new cancer therapeutics. article_number: e00747 author: - first_name: Ivana full_name: Božić, Ivana last_name: Božić - first_name: Johannes full_name: Reiter, Johannes id: 4A918E98-F248-11E8-B48F-1D18A9856A87 last_name: Reiter orcid: 0000-0002-0170-7353 - first_name: Benjamin full_name: Allen, Benjamin last_name: Allen - first_name: Tibor full_name: Antal, Tibor last_name: Antal - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Preya full_name: Shah, Preya last_name: Shah - first_name: Yo full_name: Moon, Yo last_name: Moon - first_name: Amin full_name: Yaqubie, Amin last_name: Yaqubie - first_name: Nicole full_name: Kelly, Nicole last_name: Kelly - first_name: Dung full_name: Le, Dung last_name: Le - first_name: Evan full_name: Lipson, Evan last_name: Lipson - first_name: Paul full_name: Chapman, Paul last_name: Chapman - first_name: Luis full_name: Diaz, Luis last_name: Diaz - first_name: Bert full_name: Vogelstein, Bert last_name: Vogelstein - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Božić I, Reiter J, Allen B, et al. Evolutionary dynamics of cancer in response to targeted combination therapy. eLife. 2013;2. doi:10.7554/eLife.00747 apa: Božić, I., Reiter, J., Allen, B., Antal, T., Chatterjee, K., Shah, P., … Nowak, M. (2013). Evolutionary dynamics of cancer in response to targeted combination therapy. ELife. eLife Sciences Publications. https://doi.org/10.7554/eLife.00747 chicago: Božić, Ivana, Johannes Reiter, Benjamin Allen, Tibor Antal, Krishnendu Chatterjee, Preya Shah, Yo Moon, et al. “Evolutionary Dynamics of Cancer in Response to Targeted Combination Therapy.” ELife. eLife Sciences Publications, 2013. https://doi.org/10.7554/eLife.00747. ieee: I. Božić et al., “Evolutionary dynamics of cancer in response to targeted combination therapy,” eLife, vol. 2. eLife Sciences Publications, 2013. ista: Božić I, Reiter J, Allen B, Antal T, Chatterjee K, Shah P, Moon Y, Yaqubie A, Kelly N, Le D, Lipson E, Chapman P, Diaz L, Vogelstein B, Nowak M. 2013. Evolutionary dynamics of cancer in response to targeted combination therapy. eLife. 2, e00747. mla: Božić, Ivana, et al. “Evolutionary Dynamics of Cancer in Response to Targeted Combination Therapy.” ELife, vol. 2, e00747, eLife Sciences Publications, 2013, doi:10.7554/eLife.00747. short: I. Božić, J. Reiter, B. Allen, T. Antal, K. Chatterjee, P. Shah, Y. Moon, A. Yaqubie, N. Kelly, D. Le, E. Lipson, P. Chapman, L. Diaz, B. Vogelstein, M. Nowak, ELife 2 (2013). date_created: 2018-12-11T11:59:45Z date_published: 2013-06-25T00:00:00Z date_updated: 2023-09-07T11:40:43Z day: '25' ddc: - '570' - '610' department: - _id: KrCh doi: 10.7554/eLife.00747 file: - access_level: open_access checksum: 2c38c47815eacd8fa66cb8b404cf7c61 content_type: application/pdf creator: system date_created: 2018-12-12T10:12:48Z date_updated: 2020-07-14T12:45:49Z file_id: '4967' file_name: IST-2013-134-v1+1_e00747.full.pdf file_size: 3358321 relation: main_file file_date_updated: 2020-07-14T12:45:49Z has_accepted_license: '1' intvolume: ' 2' language: - iso: eng month: '06' oa: 1 oa_version: Published Version publication: eLife publication_status: published publisher: eLife Sciences Publications publist_id: '3985' pubrep_id: '134' quality_controlled: '1' related_material: record: - id: '1400' relation: dissertation_contains status: public scopus_import: 1 status: public title: Evolutionary dynamics of cancer in response to targeted combination therapy 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: 2 year: '2013' ... --- _id: '2000' abstract: - lang: eng text: In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics. alternative_title: - LNCS author: - first_name: Johannes full_name: Reiter, Johannes id: 4A918E98-F248-11E8-B48F-1D18A9856A87 last_name: Reiter orcid: 0000-0002-0170-7353 - first_name: Ivana full_name: Božić, Ivana last_name: Božić - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: 'Reiter J, Božić I, Chatterjee K, Nowak M. TTP: Tool for tumor progression. In: Proceedings of 25th Int. Conf. on Computer Aided Verification. Vol 8044. Lecture Notes in Computer Science. Springer; 2013:101-106. doi:10.1007/978-3-642-39799-8_6' apa: 'Reiter, J., Božić, I., Chatterjee, K., & Nowak, M. (2013). TTP: Tool for tumor progression. In Proceedings of 25th Int. Conf. on Computer Aided Verification (Vol. 8044, pp. 101–106). St. Petersburg, Russia: Springer. https://doi.org/10.1007/978-3-642-39799-8_6' chicago: 'Reiter, Johannes, Ivana Božić, Krishnendu Chatterjee, and Martin Nowak. “TTP: Tool for Tumor Progression.” In Proceedings of 25th Int. Conf. on Computer Aided Verification, 8044:101–6. Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-39799-8_6.' ieee: 'J. Reiter, I. Božić, K. Chatterjee, and M. Nowak, “TTP: Tool for tumor progression,” in Proceedings of 25th Int. Conf. on Computer Aided Verification, St. Petersburg, Russia, 2013, vol. 8044, pp. 101–106.' ista: 'Reiter J, Božić I, Chatterjee K, Nowak M. 2013. TTP: Tool for tumor progression. Proceedings of 25th Int. Conf. on Computer Aided Verification. CAV: Computer Aided VerificationLecture Notes in Computer Science, LNCS, vol. 8044, 101–106.' mla: 'Reiter, Johannes, et al. “TTP: Tool for Tumor Progression.” Proceedings of 25th Int. Conf. on Computer Aided Verification, vol. 8044, Springer, 2013, pp. 101–06, doi:10.1007/978-3-642-39799-8_6.' short: J. Reiter, I. Božić, K. Chatterjee, M. Nowak, in:, Proceedings of 25th Int. Conf. on Computer Aided Verification, Springer, 2013, pp. 101–106. conference: end_date: 2013-07-19 location: St. Petersburg, Russia name: 'CAV: Computer Aided Verification' start_date: 2013-07-13 date_created: 2018-12-11T11:55:08Z date_published: 2013-01-01T00:00:00Z date_updated: 2023-09-07T11:40:43Z day: '01' department: - _id: KrCh doi: 10.1007/978-3-642-39799-8_6 ec_funded: 1 external_id: arxiv: - '1303.5251' intvolume: ' 8044' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1303.5251 month: '01' oa: 1 oa_version: Preprint page: 101 - 106 project: - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: Proceedings of 25th Int. Conf. on Computer Aided Verification publication_status: published publisher: Springer publist_id: '5077' quality_controlled: '1' related_material: record: - id: '5399' relation: earlier_version status: public - id: '1400' relation: dissertation_contains status: public scopus_import: 1 series_title: Lecture Notes in Computer Science status: public title: 'TTP: Tool for tumor progression' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8044 year: '2013' ... --- _id: '2305' abstract: - lang: eng text: We study the complexity of central controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize both the expected mean-payoff performance of the system and its stability. e argue that the basic theoretical notion of expressing the stability in terms of the variance of the mean-payoff (called global variance in our paper) is not always sufficient, since it ignores possible instabilities on respective runs. For this reason we propose alernative definitions of stability, which we call local and hybrid variance, and which express how rewards on each run deviate from the run's own mean-payoff and from the expected mean-payoff, respectively. We show that a strategy ensuring both the expected mean-payoff and the variance below given bounds requires randomization and memory, under all the above semantics of variance. We then look at the problem of determining whether there is a such a strategy. For the global variance, we show that the problem is in PSPACE, and that the answer can be approximated in pseudo-polynomial time. For the hybrid variance, the analogous decision problem is in NP, and a polynomial-time approximating algorithm also exists. For local variance, we show that the decision problem is in NP. Since the overall performance can be traded for stability (and vice versa), we also present algorithms for approximating the associated Pareto curve in all the three cases. Finally, we study a special case of the decision problems, where we require a given expected mean-payoff together with zero variance. Here we show that the problems can be all solved in polynomial time. 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: Vojtěch full_name: Forejt, Vojtěch last_name: Forejt - first_name: Antonín full_name: Kučera, Antonín last_name: Kučera citation: ama: 'Brázdil T, Chatterjee K, Forejt V, Kučera A. Trading performance for stability in Markov decision processes. In: 28th Annual ACM/IEEE Symposium. IEEE; 2013:331-340. doi:10.1109/LICS.2013.39' apa: 'Brázdil, T., Chatterjee, K., Forejt, V., & Kučera, A. (2013). Trading performance for stability in Markov decision processes. In 28th Annual ACM/IEEE Symposium (pp. 331–340). New Orleans, LA, United States: IEEE. https://doi.org/10.1109/LICS.2013.39' chicago: Brázdil, Tomáš, Krishnendu Chatterjee, Vojtěch Forejt, and Antonín Kučera. “Trading Performance for Stability in Markov Decision Processes.” In 28th Annual ACM/IEEE Symposium, 331–40. IEEE, 2013. https://doi.org/10.1109/LICS.2013.39. ieee: T. Brázdil, K. Chatterjee, V. Forejt, and A. Kučera, “Trading performance for stability in Markov decision processes,” in 28th Annual ACM/IEEE Symposium, New Orleans, LA, United States, 2013, pp. 331–340. ista: 'Brázdil T, Chatterjee K, Forejt V, Kučera A. 2013. Trading performance for stability in Markov decision processes. 28th Annual ACM/IEEE Symposium. LICS: Logic in Computer Science, 331–340.' mla: Brázdil, Tomáš, et al. “Trading Performance for Stability in Markov Decision Processes.” 28th Annual ACM/IEEE Symposium, IEEE, 2013, pp. 331–40, doi:10.1109/LICS.2013.39. short: T. Brázdil, K. Chatterjee, V. Forejt, A. Kučera, in:, 28th Annual ACM/IEEE Symposium, IEEE, 2013, pp. 331–340. conference: end_date: 2013-06-28 location: New Orleans, LA, United States name: 'LICS: Logic in Computer Science' start_date: 2013-06-25 date_created: 2018-12-11T11:56:53Z date_published: 2013-08-01T00:00:00Z date_updated: 2023-09-20T11:15:30Z day: '01' department: - _id: KrCh doi: 10.1109/LICS.2013.39 ec_funded: 1 external_id: arxiv: - '1305.4103' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1305.4103 month: '08' oa: 1 oa_version: Preprint page: 331 - 340 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: 28th Annual ACM/IEEE Symposium publication_status: published publisher: IEEE publist_id: '4622' quality_controlled: '1' related_material: record: - id: '1294' relation: later_version status: public scopus_import: 1 status: public title: Trading performance for stability in Markov decision processes type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ...