[{"language":[{"iso":"eng"}],"doi":"10.1007/978-3-662-53413-7_2","project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z211"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"}],"day":"31","type":"conference","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"},{"last_name":"Otop","first_name":"Jan","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"alternative_title":["LNCS"],"citation":{"short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Springer, 2016, pp. 23–38.","ama":"Chatterjee K, Henzinger TA, Otop J. Quantitative monitor automata. In: Vol 9837. Springer; 2016:23-38. doi:<a href=\"https://doi.org/10.1007/978-3-662-53413-7_2\">10.1007/978-3-662-53413-7_2</a>","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2016). Quantitative monitor automata (Vol. 9837, pp. 23–38). Presented at the SAS: Static Analysis Symposium, Edinburgh, United Kingdom: Springer. <a href=\"https://doi.org/10.1007/978-3-662-53413-7_2\">https://doi.org/10.1007/978-3-662-53413-7_2</a>","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Quantitative Monitor Automata,” 9837:23–38. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-53413-7_2\">https://doi.org/10.1007/978-3-662-53413-7_2</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Quantitative monitor automata,” presented at the SAS: Static Analysis Symposium, Edinburgh, United Kingdom, 2016, vol. 9837, pp. 23–38.","ista":"Chatterjee K, Henzinger TA, Otop J. 2016. Quantitative monitor automata. SAS: Static Analysis Symposium, LNCS, vol. 9837, 23–38.","mla":"Chatterjee, Krishnendu, et al. <i>Quantitative Monitor Automata</i>. Vol. 9837, Springer, 2016, pp. 23–38, doi:<a href=\"https://doi.org/10.1007/978-3-662-53413-7_2\">10.1007/978-3-662-53413-7_2</a>."},"ec_funded":1,"title":"Quantitative monitor automata","conference":{"start_date":"2016-09-08","end_date":"2016-09-10","name":"SAS: Static Analysis Symposium","location":"Edinburgh, United Kingdom"},"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"quality_controlled":"1","status":"public","intvolume":"      9837","publisher":"Springer","month":"08","date_created":"2018-12-11T11:51:26Z","page":"23 - 38","scopus_import":1,"date_updated":"2021-01-12T06:49:58Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"5932","year":"2016","oa_version":"Preprint","volume":9837,"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.06764"}],"date_published":"2016-08-31T00:00:00Z","_id":"1335","abstract":[{"lang":"eng","text":"In this paper we review various automata-theoretic formalisms for expressing quantitative properties. We start with finite-state Boolean automata that express the traditional regular properties. We then consider weighted ω-automata that can measure the average density of events, which finite-state Boolean automata cannot. However, even weighted ω-automata cannot express basic performance properties like average response time. We finally consider two formalisms of weighted ω-automata with monitors, where the monitors are either (a) counters or (b) weighted automata themselves. We present a translation result to establish that these two formalisms are equivalent. Weighted ω-automata with monitors generalize weighted ω-automata, and can express average response time property. They present a natural, robust, and expressive framework for quantitative specifications, with important decidable properties."}]},{"volume":9928,"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1604.07634","open_access":"1"}],"publication_status":"published","_id":"1340","date_published":"2016-09-01T00:00:00Z","abstract":[{"lang":"eng","text":"We study repeated games with absorbing states, a type of two-player, zero-sum concurrent mean-payoff games with the prototypical example being the Big Match of Gillete (1957). These games may not allow optimal strategies but they always have ε-optimal strategies. In this paper we design ε-optimal strategies for Player 1 in these games that use only O(log log T) space. Furthermore, we construct strategies for Player 1 that use space s(T), for an arbitrary small unbounded non-decreasing function s, and which guarantee an ε-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Ω(log T) and it was known that no strategy can use constant space if it is ε-optimal even in the limit superior sense. We also give a complementary lower bound. Furthermore, we also show that no Markov strategy, even extended with finite memory, can ensure value greater than 0 in the Big Match, answering a question posed by Neyman [11]."}],"date_updated":"2021-01-12T06:50:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"oa_version":"Preprint","year":"2016","publist_id":"5927","status":"public","intvolume":"      9928","department":[{"_id":"KrCh"}],"quality_controlled":"1","publisher":"Springer","date_created":"2018-12-11T11:51:28Z","month":"09","page":"64 - 76","doi":"10.1007/978-3-662-53354-3_6","language":[{"iso":"eng"}],"project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}],"alternative_title":["LNCS"],"type":"conference","author":[{"first_name":"Kristoffer","full_name":"Hansen, Kristoffer","last_name":"Hansen"},{"orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"},{"first_name":"Michal","full_name":"Koucký, Michal","last_name":"Koucký"}],"day":"01","conference":{"name":"SAGT: Symposium on Algorithmic Game Theory","end_date":"2016-09-21","start_date":"2016-09-19","location":"Liverpool, United Kingdom"},"title":"The big match in small space","ec_funded":1,"citation":{"chicago":"Hansen, Kristoffer, Rasmus Ibsen-Jensen, and Michal Koucký. “The Big Match in Small Space,” 9928:64–76. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-53354-3_6\">https://doi.org/10.1007/978-3-662-53354-3_6</a>.","ista":"Hansen K, Ibsen-Jensen R, Koucký M. 2016. The big match in small space. SAGT: Symposium on Algorithmic Game Theory, LNCS, vol. 9928, 64–76.","ieee":"K. Hansen, R. Ibsen-Jensen, and M. Koucký, “The big match in small space,” presented at the SAGT: Symposium on Algorithmic Game Theory, Liverpool, United Kingdom, 2016, vol. 9928, pp. 64–76.","mla":"Hansen, Kristoffer, et al. <i>The Big Match in Small Space</i>. Vol. 9928, Springer, 2016, pp. 64–76, doi:<a href=\"https://doi.org/10.1007/978-3-662-53354-3_6\">10.1007/978-3-662-53354-3_6</a>.","short":"K. Hansen, R. Ibsen-Jensen, M. Koucký, in:, Springer, 2016, pp. 64–76.","ama":"Hansen K, Ibsen-Jensen R, Koucký M. The big match in small space. In: Vol 9928. Springer; 2016:64-76. doi:<a href=\"https://doi.org/10.1007/978-3-662-53354-3_6\">10.1007/978-3-662-53354-3_6</a>","apa":"Hansen, K., Ibsen-Jensen, R., &#38; Koucký, M. (2016). The big match in small space (Vol. 9928, pp. 64–76). Presented at the SAGT: Symposium on Algorithmic Game Theory, Liverpool, United Kingdom: Springer. <a href=\"https://doi.org/10.1007/978-3-662-53354-3_6\">https://doi.org/10.1007/978-3-662-53354-3_6</a>"}},{"scopus_import":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"date_updated":"2021-01-12T06:50:17Z","doi":"10.1145/2857050","citation":{"apa":"Chonev, V. K., Ouaknine, J., &#38; Worrell, J. (2016). On the complexity of the orbit problem. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/2857050\">https://doi.org/10.1145/2857050</a>","ama":"Chonev VK, Ouaknine J, Worrell J. On the complexity of the orbit problem. <i>Journal of the ACM</i>. 2016;63(3). doi:<a href=\"https://doi.org/10.1145/2857050\">10.1145/2857050</a>","short":"V.K. Chonev, J. Ouaknine, J. Worrell, Journal of the ACM 63 (2016).","mla":"Chonev, Ventsislav K., et al. “On the Complexity of the Orbit Problem.” <i>Journal of the ACM</i>, vol. 63, no. 3, 23, ACM, 2016, doi:<a href=\"https://doi.org/10.1145/2857050\">10.1145/2857050</a>.","ieee":"V. K. Chonev, J. Ouaknine, and J. Worrell, “On the complexity of the orbit problem,” <i>Journal of the ACM</i>, vol. 63, no. 3. ACM, 2016.","ista":"Chonev VK, Ouaknine J, Worrell J. 2016. On the complexity of the orbit problem. Journal of the ACM. 63(3), 23.","chicago":"Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On the Complexity of the Orbit Problem.” <i>Journal of the ACM</i>. ACM, 2016. <a href=\"https://doi.org/10.1145/2857050\">https://doi.org/10.1145/2857050</a>."},"title":"On the complexity of the orbit problem","day":"01","publist_id":"5831","type":"journal_article","author":[{"id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87","last_name":"Chonev","first_name":"Ventsislav K","full_name":"Chonev, Ventsislav K"},{"first_name":"Joël","full_name":"Ouaknine, Joël","last_name":"Ouaknine"},{"full_name":"Worrell, James","first_name":"James","last_name":"Worrell"}],"oa_version":"Preprint","year":"2016","publication_status":"published","publisher":"ACM","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1303.2981"}],"oa":1,"publication":"Journal of the ACM","department":[{"_id":"KrCh"}],"quality_controlled":"1","intvolume":"        63","status":"public","volume":63,"issue":"3","month":"06","article_number":"23","_id":"1380","date_created":"2018-12-11T11:51:41Z","abstract":[{"lang":"eng","text":"We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem - determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NPRP."}],"date_published":"2016-06-01T00:00:00Z"},{"date_created":"2018-12-11T11:51:43Z","month":"07","page":"3 - 22","status":"public","intvolume":"      9779","department":[{"_id":"KrCh"}],"quality_controlled":"1","publisher":"Springer","alternative_title":["LNCS"],"type":"conference","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","last_name":"Fu","first_name":"Hongfei","full_name":"Fu, Hongfei"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584","last_name":"Goharshady","first_name":"Amir","full_name":"Goharshady, Amir"}],"day":"01","conference":{"name":"CAV: Computer Aided Verification","start_date":"2016-07-17","end_date":"2016-07-23","location":"Toronto, Canada"},"title":"Termination analysis of probabilistic programs through Positivstellensatz's","ec_funded":1,"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Termination Analysis of Probabilistic Programs through Positivstellensatz’s</i>. Vol. 9779, Springer, 2016, pp. 3–22, doi:<a href=\"https://doi.org/10.1007/978-3-319-41528-4_1\">10.1007/978-3-319-41528-4_1</a>.","ieee":"K. Chatterjee, H. Fu, and A. K. Goharshady, “Termination analysis of probabilistic programs through Positivstellensatz’s,” presented at the CAV: Computer Aided Verification, Toronto, Canada, 2016, vol. 9779, pp. 3–22.","ista":"Chatterjee K, Fu H, Goharshady AK. 2016. Termination analysis of probabilistic programs through Positivstellensatz’s. CAV: Computer Aided Verification, LNCS, vol. 9779, 3–22.","chicago":"Chatterjee, Krishnendu, Hongfei Fu, and Amir Kafshdar Goharshady. “Termination Analysis of Probabilistic Programs through Positivstellensatz’s,” 9779:3–22. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-41528-4_1\">https://doi.org/10.1007/978-3-319-41528-4_1</a>.","apa":"Chatterjee, K., Fu, H., &#38; Goharshady, A. K. (2016). Termination analysis of probabilistic programs through Positivstellensatz’s (Vol. 9779, pp. 3–22). Presented at the CAV: Computer Aided Verification, Toronto, Canada: Springer. <a href=\"https://doi.org/10.1007/978-3-319-41528-4_1\">https://doi.org/10.1007/978-3-319-41528-4_1</a>","ama":"Chatterjee K, Fu H, Goharshady AK. Termination analysis of probabilistic programs through Positivstellensatz’s. In: Vol 9779. Springer; 2016:3-22. doi:<a href=\"https://doi.org/10.1007/978-3-319-41528-4_1\">10.1007/978-3-319-41528-4_1</a>","short":"K. Chatterjee, H. Fu, A.K. Goharshady, in:, Springer, 2016, pp. 3–22."},"doi":"10.1007/978-3-319-41528-4_1","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"8934","relation":"dissertation_contains","status":"public"}]},"project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling"}],"abstract":[{"lang":"eng","text":"We consider nondeterministic probabilistic programs with the most basic liveness property of termination. We present efficient methods for termination analysis of nondeterministic probabilistic programs with polynomial guards and assignments. Our approach is through synthesis of polynomial ranking supermartingales, that on one hand significantly generalizes linear ranking supermartingales and on the other hand is a counterpart of polynomial ranking-functions for proving termination of nonprobabilistic programs. The approach synthesizes polynomial ranking-supermartingales through Positivstellensatz's, yielding an efficient method which is not only sound, but also semi-complete over a large subclass of programs. We show experimental results to demonstrate that our approach can handle several classical programs with complex polynomial guards and assignments, and can synthesize efficient quadratic ranking-supermartingales when a linear one does not exist even for simple affine programs."}],"_id":"1386","date_published":"2016-07-01T00:00:00Z","volume":9779,"main_file_link":[{"url":"http://arxiv.org/abs/1604.07169","open_access":"1"}],"oa":1,"publication_status":"published","year":"2016","oa_version":"Preprint","publist_id":"5824","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-03-25T23:30:18Z","scopus_import":1},{"status":"public","department":[{"_id":"KrCh"}],"quality_controlled":"1","publication":"LICS '16","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1507.03632","open_access":"1"}],"publication_status":"published","publisher":"IEEE","date_created":"2018-12-11T11:51:44Z","_id":"1389","abstract":[{"text":"The continuous evolution of a wide variety of systems, including continous-time Markov chains and linear hybrid automata, can be\r\ndescribed in terms of linear differential equations. In this paper we study the decision problem of whether the solution x(t) of a system of linear differential equations dx/dt = Ax reaches a target halfspace infinitely often. This recurrent reachability problem can\r\nequivalently be formulated as the following Infinite Zeros Problem: does a real-valued function f:R≥0 --&gt; R satisfying a given linear\r\ndifferential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most 7, then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order 9 (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.","lang":"eng"}],"date_published":"2016-07-05T00:00:00Z","month":"07","page":"515 - 524","doi":"10.1145/2933575.2934548","date_updated":"2021-01-12T06:50:20Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"scopus_import":1,"project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"year":"2016","oa_version":"Preprint","type":"conference","author":[{"last_name":"Chonev","full_name":"Chonev, Ventsislav K","first_name":"Ventsislav K","id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ouaknine, Joël","first_name":"Joël","last_name":"Ouaknine"},{"last_name":"Worrell","first_name":"James","full_name":"Worrell, James"}],"publist_id":"5820","day":"05","conference":{"location":"New York, NY, USA","start_date":"2018-07-05","end_date":"2018-07-08","name":"LICS: Logic in Computer Science"},"title":"On recurrent reachability for continuous linear dynamical systems","ec_funded":1,"citation":{"ieee":"V. K. Chonev, J. Ouaknine, and J. Worrell, “On recurrent reachability for continuous linear dynamical systems,” in <i>LICS ’16</i>, New York, NY, USA, 2016, pp. 515–524.","ista":"Chonev VK, Ouaknine J, Worrell J. 2016. On recurrent reachability for continuous linear dynamical systems. LICS ’16. LICS: Logic in Computer Science, 515–524.","chicago":"Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On Recurrent Reachability for Continuous Linear Dynamical Systems.” In <i>LICS ’16</i>, 515–24. IEEE, 2016. <a href=\"https://doi.org/10.1145/2933575.2934548\">https://doi.org/10.1145/2933575.2934548</a>.","mla":"Chonev, Ventsislav K., et al. “On Recurrent Reachability for Continuous Linear Dynamical Systems.” <i>LICS ’16</i>, IEEE, 2016, pp. 515–24, doi:<a href=\"https://doi.org/10.1145/2933575.2934548\">10.1145/2933575.2934548</a>.","short":"V.K. Chonev, J. Ouaknine, J. Worrell, in:, LICS ’16, IEEE, 2016, pp. 515–524.","apa":"Chonev, V. K., Ouaknine, J., &#38; Worrell, J. (2016). On recurrent reachability for continuous linear dynamical systems. In <i>LICS ’16</i> (pp. 515–524). New York, NY, USA: IEEE. <a href=\"https://doi.org/10.1145/2933575.2934548\">https://doi.org/10.1145/2933575.2934548</a>","ama":"Chonev VK, Ouaknine J, Worrell J. On recurrent reachability for continuous linear dynamical systems. In: <i>LICS ’16</i>. IEEE; 2016:515-524. doi:<a href=\"https://doi.org/10.1145/2933575.2934548\">10.1145/2933575.2934548</a>"}},{"publication_identifier":{"issn":["2663-337X"]},"language":[{"iso":"eng"}],"date_updated":"2023-09-07T11:54:58Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","type":"dissertation","author":[{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin"}],"year":"2016","oa_version":"None","alternative_title":["ISTA Thesis"],"day":"01","publist_id":"5810","title":"Algorithms for partially observable markov decision processes","citation":{"mla":"Chmelik, Martin. <i>Algorithms for Partially Observable Markov Decision Processes</i>. Institute of Science and Technology Austria, 2016.","chicago":"Chmelik, Martin. “Algorithms for Partially Observable Markov Decision Processes.” Institute of Science and Technology Austria, 2016.","ieee":"M. Chmelik, “Algorithms for partially observable markov decision processes,” Institute of Science and Technology Austria, 2016.","ista":"Chmelik M. 2016. Algorithms for partially observable markov decision processes. Institute of Science and Technology Austria.","ama":"Chmelik M. Algorithms for partially observable markov decision processes. 2016.","apa":"Chmelik, M. (2016). <i>Algorithms for partially observable markov decision processes</i>. Institute of Science and Technology Austria.","short":"M. Chmelik, Algorithms for Partially Observable Markov Decision Processes, Institute of Science and Technology Austria, 2016."},"status":"public","department":[{"_id":"KrCh"}],"degree_awarded":"PhD","publisher":"Institute of Science and Technology Austria","publication_status":"published","supervisor":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2018-12-11T11:51:47Z","_id":"1397","abstract":[{"text":"We study partially observable Markov decision processes (POMDPs) with objectives used in verification and artificial intelligence. The qualitative analysis problem given a POMDP and an objective asks whether there is a strategy (policy) to ensure that the objective is satisfied almost surely (with probability 1), resp. with positive probability (with probability greater than 0). For POMDPs with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards, we consider two types of path constraints: (i) a quantitative limit-average constraint defines the set of paths where the payoff is at least a given threshold L1 = 1. Our main results for qualitative limit-average constraint under almost-sure winning are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative limit-average constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We present a prototype implementation of our EXPTIME algorithm. For POMDPs with w-regular conditions specified as parity objectives, while the qualitative analysis problems are known to be undecidable even for very special case of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. Based on our theoretical algorithms we also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of well-known POMDP examples for robotics applications. For POMDPs with a set of target states and an integer cost associated with every transition, we study the optimization objective that asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely. We show that for general integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double and exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms that extend existing algorithms for POMDPs with finite-horizon objectives. We show experimentally that it performs well in many examples of interest. We study more deeply the problem of almost-sure reachability, where  given a set of target states, the question is to decide whether there is a strategy to ensure that the target set is reached almost surely. While in general the problem EXPTIME-complete, in many practical cases strategies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. We first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. Decentralized POMDPs (DEC-POMDPs) extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. In this work we consider Goal DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the real-time dynamic programming approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. In the end we present a short summary of a few other results related to verification of MDPs and POMDPs.","lang":"eng"}],"date_published":"2016-02-01T00:00:00Z","month":"02","article_processing_charge":"No","page":"232"},{"abstract":[{"text":"Direct reciprocity is a mechanism for the evolution of cooperation based on repeated interactions. When individuals meet repeatedly, they can use conditional strategies to enforce cooperative outcomes that would not be feasible in one-shot social dilemmas. Direct reciprocity requires that individuals keep track of their past interactions and find the right response. However, there are natural bounds on strategic complexity: Humans find it difficult to remember past interactions accurately, especially over long timespans. Given these limitations, it is natural to ask how complex strategies need to be for cooperation to evolve. Here, we study stochastic evolutionary game dynamics in finite populations to systematically compare the evolutionary performance of reactive strategies, which only respond to the co-player's previous move, and memory-one strategies, which take into account the own and the co-player's previous move. In both cases, we compare deterministic strategy and stochastic strategy spaces. For reactive strategies and small costs, we find that stochasticity benefits cooperation, because it allows for generous-tit-for-tat. For memory one strategies and small costs, we find that stochasticity does not increase the propensity for cooperation, because the deterministic rule of win-stay, lose-shift works best. For memory one strategies and large costs, however, stochasticity can augment cooperation.","lang":"eng"}],"_id":"1423","date_published":"2016-05-10T00:00:00Z","file":[{"date_created":"2018-12-12T10:18:08Z","relation":"main_file","file_id":"5327","content_type":"application/pdf","checksum":"ee17c482370d2e1b3add393710d3c696","access_level":"open_access","date_updated":"2020-07-14T12:44:53Z","file_size":1349915,"creator":"system","file_name":"IST-2016-590-v1+1_srep25676.pdf"}],"article_number":"25676","volume":6,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"pubrep_id":"590","file_date_updated":"2020-07-14T12:44:53Z","oa":1,"publication_status":"published","year":"2016","has_accepted_license":"1","oa_version":"Published Version","publist_id":"5784","date_updated":"2021-01-12T06:50:38Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"date_created":"2018-12-11T11:51:56Z","month":"05","intvolume":"         6","status":"public","quality_controlled":"1","department":[{"_id":"KrCh"}],"publication":"Scientific Reports","publisher":"Nature Publishing Group","author":[{"first_name":"Seung","full_name":"Baek, Seung","last_name":"Baek"},{"last_name":"Jeong","first_name":"Hyeongchai","full_name":"Jeong, Hyeongchai"},{"last_name":"Hilbe","first_name":"Christian","full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","full_name":"Nowak, Martin","last_name":"Nowak"}],"type":"journal_article","day":"10","title":"Comparing reactive and memory-one strategies of direct reciprocity","citation":{"short":"S. Baek, H. Jeong, C. Hilbe, M. Nowak, Scientific Reports 6 (2016).","apa":"Baek, S., Jeong, H., Hilbe, C., &#38; Nowak, M. (2016). Comparing reactive and memory-one strategies of direct reciprocity. <i>Scientific Reports</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/srep25676\">https://doi.org/10.1038/srep25676</a>","ama":"Baek S, Jeong H, Hilbe C, Nowak M. Comparing reactive and memory-one strategies of direct reciprocity. <i>Scientific Reports</i>. 2016;6. doi:<a href=\"https://doi.org/10.1038/srep25676\">10.1038/srep25676</a>","ista":"Baek S, Jeong H, Hilbe C, Nowak M. 2016. Comparing reactive and memory-one strategies of direct reciprocity. Scientific Reports. 6, 25676.","ieee":"S. Baek, H. Jeong, C. Hilbe, and M. Nowak, “Comparing reactive and memory-one strategies of direct reciprocity,” <i>Scientific Reports</i>, vol. 6. Nature Publishing Group, 2016.","chicago":"Baek, Seung, Hyeongchai Jeong, Christian Hilbe, and Martin Nowak. “Comparing Reactive and Memory-One Strategies of Direct Reciprocity.” <i>Scientific Reports</i>. Nature Publishing Group, 2016. <a href=\"https://doi.org/10.1038/srep25676\">https://doi.org/10.1038/srep25676</a>.","mla":"Baek, Seung, et al. “Comparing Reactive and Memory-One Strategies of Direct Reciprocity.” <i>Scientific Reports</i>, vol. 6, 25676, Nature Publishing Group, 2016, doi:<a href=\"https://doi.org/10.1038/srep25676\">10.1038/srep25676</a>."},"ddc":["000"],"doi":"10.1038/srep25676","language":[{"iso":"eng"}],"acknowledgement":"C.H. acknowledges generous funding from the Schrödinger scholarship of the Austrian Science Fund (FWF), J3475."},{"month":"05","date_created":"2018-12-11T11:51:57Z","publisher":"Royal Society, The","quality_controlled":"1","department":[{"_id":"KrCh"}],"publication":"Royal Society Open Science","status":"public","intvolume":"         3","citation":{"ama":"Chakra M, Hilbe C, Traulsen A. Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites. <i>Royal Society Open Science</i>. 2016;3(5). doi:<a href=\"https://doi.org/10.1098/rsos.160036\">10.1098/rsos.160036</a>","apa":"Chakra, M., Hilbe, C., &#38; Traulsen, A. (2016). Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites. <i>Royal Society Open Science</i>. Royal Society, The. <a href=\"https://doi.org/10.1098/rsos.160036\">https://doi.org/10.1098/rsos.160036</a>","short":"M. Chakra, C. Hilbe, A. Traulsen, Royal Society Open Science 3 (2016).","mla":"Chakra, Maria, et al. “Coevolutionary Interactions between Farmers and Mafia Induce Host Acceptance of Avian Brood Parasites.” <i>Royal Society Open Science</i>, vol. 3, no. 5, 160036, Royal Society, The, 2016, doi:<a href=\"https://doi.org/10.1098/rsos.160036\">10.1098/rsos.160036</a>.","chicago":"Chakra, Maria, Christian Hilbe, and Arne Traulsen. “Coevolutionary Interactions between Farmers and Mafia Induce Host Acceptance of Avian Brood Parasites.” <i>Royal Society Open Science</i>. Royal Society, The, 2016. <a href=\"https://doi.org/10.1098/rsos.160036\">https://doi.org/10.1098/rsos.160036</a>.","ista":"Chakra M, Hilbe C, Traulsen A. 2016. Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites. Royal Society Open Science. 3(5), 160036.","ieee":"M. Chakra, C. Hilbe, and A. Traulsen, “Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites,” <i>Royal Society Open Science</i>, vol. 3, no. 5. Royal Society, The, 2016."},"title":"Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites","day":"01","type":"journal_article","author":[{"full_name":"Chakra, Maria","first_name":"Maria","last_name":"Chakra"},{"first_name":"Christian","full_name":"Hilbe, Christian","last_name":"Hilbe","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5116-955X"},{"first_name":"Arne","full_name":"Traulsen, Arne","last_name":"Traulsen"}],"acknowledgement":"C.H. gratefully acknowledges funding by the Schrödinger scholarship of the Austrian Science Fund (FWF) J3475.","language":[{"iso":"eng"}],"doi":"10.1098/rsos.160036","ddc":["000"],"issue":"5","file":[{"relation":"main_file","file_id":"5104","content_type":"application/pdf","date_created":"2018-12-12T10:14:49Z","file_size":937002,"creator":"system","file_name":"IST-2016-589-v1+1_160036.full.pdf","checksum":"bf84211b31fe87451e738ba301d729c3","access_level":"open_access","date_updated":"2020-07-14T12:44:53Z"}],"article_number":"160036","_id":"1426","abstract":[{"text":"Brood parasites exploit their host in order to increase their own fitness. Typically, this results in an arms race between parasite trickery and host defence. Thus, it is puzzling to observe hosts that accept parasitism without any resistance. The ‘mafia’ hypothesis suggests that these hosts accept parasitism to avoid retaliation. Retaliation has been shown to evolve when the hosts condition their response to mafia parasites, who use depredation as a targeted response to rejection. However, it is unclear if acceptance would also emerge when ‘farming’ parasites are present in the population. Farming parasites use depredation to synchronize the timing with the host, destroying mature clutches to force the host to re-nest. Herein, we develop an evolutionary model to analyse the interaction between depredatory parasites and their hosts. We show that coevolutionary cycles between farmers and mafia can still induce host acceptance of brood parasites. However, this equilibrium is unstable and in the long-run the dynamics of this host–parasite interaction exhibits strong oscillations: when farmers are the majority, accepters conditional to mafia (the host will reject first and only accept after retaliation by the parasite) have a higher fitness than unconditional accepters (the host always accepts parasitism). This leads to an increase in mafia parasites’ fitness and in turn induce an optimal environment for accepter hosts.","lang":"eng"}],"date_published":"2016-05-01T00:00:00Z","publication_status":"published","oa":1,"file_date_updated":"2020-07-14T12:44:53Z","volume":3,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"pubrep_id":"589","publist_id":"5776","has_accepted_license":"1","oa_version":"Published Version","year":"2016","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:50:39Z","scopus_import":1},{"related_material":{"link":[{"relation":"table_of_contents","url":"https://www.ijcai.org/proceedings/2016"}]},"project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","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"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling"}],"language":[{"iso":"eng"}],"date_updated":"2023-02-21T10:04:26Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"conference":{"location":"New York, NY, USA","start_date":"2016-07-09","end_date":"2016-07-15","name":"IJCAI: International Joint Conference on Artificial Intelligence"},"title":"Robust draws in balanced knockout tournaments","ec_funded":1,"citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, J. Tkadlec, in:, AAAI Press, 2016, pp. 172–179.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Tkadlec, J. (2016). Robust draws in balanced knockout tournaments (Vol. 2016–January, pp. 172–179). Presented at the IJCAI: International Joint Conference on Artificial Intelligence, New York, NY, USA: AAAI Press.","ama":"Chatterjee K, Ibsen-Jensen R, Tkadlec J. Robust draws in balanced knockout tournaments. In: Vol 2016-January. AAAI Press; 2016:172-179.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and J. Tkadlec, “Robust draws in balanced knockout tournaments,” presented at the IJCAI: International Joint Conference on Artificial Intelligence, New York, NY, USA, 2016, vol. 2016–January, pp. 172–179.","ista":"Chatterjee K, Ibsen-Jensen R, Tkadlec J. 2016. Robust draws in balanced knockout tournaments. IJCAI: International Joint Conference on Artificial Intelligence vol. 2016–January, 172–179.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Josef Tkadlec. “Robust Draws in Balanced Knockout Tournaments,” 2016–January:172–79. AAAI Press, 2016.","mla":"Chatterjee, Krishnendu, et al. <i>Robust Draws in Balanced Knockout Tournaments</i>. Vol. 2016–January, AAAI Press, 2016, pp. 172–79."},"year":"2016","oa_version":"Preprint","type":"conference","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tkadlec, Josef","first_name":"Josef","last_name":"Tkadlec","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684"}],"publist_id":"6171","day":"01","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1604.05090v1","open_access":"1"}],"publisher":"AAAI Press","publication_status":"published","volume":"2016-January","status":"public","quality_controlled":"1","department":[{"_id":"KrCh"}],"page":"172 - 179","abstract":[{"lang":"eng","text":"Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decisionmaking and elections. The traditional computational question, that asks to compute a draw (optimal draw) that maximizes the winning probability for a distinguished player, has received a lot of attention. Previous works consider the problem where the pairwise winning probabilities are known precisely, while we study how robust is the winning probability with respect to small errors in the pairwise winning probabilities. First, we present several illuminating examples to establish: (a) there exist deterministic tournaments (where the pairwise winning probabilities are 0 or 1) where one optimal draw is much more robust than the other; and (b) in general, there exist tournaments with slightly suboptimal draws that are more robust than all the optimal draws. The above examples motivate the study of the computational problem of robust draws that guarantee a specified winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufficiently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NP-complete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomial-time algorithms to compute robust optimal draws."}],"_id":"1182","date_published":"2016-01-01T00:00:00Z","date_created":"2018-12-11T11:50:35Z","month":"01"},{"page":"29 - 31","month":"12","date_created":"2018-12-11T11:50:40Z","publisher":"Elsevier","department":[{"_id":"KrCh"}],"quality_controlled":"1","publication":"Physics of Life Reviews","status":"public","intvolume":"        19","ec_funded":1,"citation":{"ista":"Hilbe C, Traulsen A. 2016. Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze. Physics of Life Reviews. 19, 29–31.","ieee":"C. Hilbe and A. Traulsen, “Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on ‘Evolutionary game theory using agent-based methods’ by C. Adami, J. Schossau and A. Hintze,” <i>Physics of Life Reviews</i>, vol. 19. Elsevier, pp. 29–31, 2016.","chicago":"Hilbe, Christian, and Arne Traulsen. “Only the Combination of Mathematics and Agent Based Simulations Can Leverage the Full Potential of Evolutionary Modeling: Comment on ‘Evolutionary Game Theory Using Agent-Based Methods’ by C. Adami, J. Schossau and A. Hintze.” <i>Physics of Life Reviews</i>. Elsevier, 2016. <a href=\"https://doi.org/10.1016/j.plrev.2016.10.004\">https://doi.org/10.1016/j.plrev.2016.10.004</a>.","mla":"Hilbe, Christian, and Arne Traulsen. “Only the Combination of Mathematics and Agent Based Simulations Can Leverage the Full Potential of Evolutionary Modeling: Comment on ‘Evolutionary Game Theory Using Agent-Based Methods’ by C. Adami, J. Schossau and A. Hintze.” <i>Physics of Life Reviews</i>, vol. 19, Elsevier, 2016, pp. 29–31, doi:<a href=\"https://doi.org/10.1016/j.plrev.2016.10.004\">10.1016/j.plrev.2016.10.004</a>.","short":"C. Hilbe, A. Traulsen, Physics of Life Reviews 19 (2016) 29–31.","apa":"Hilbe, C., &#38; Traulsen, A. (2016). Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze. <i>Physics of Life Reviews</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.plrev.2016.10.004\">https://doi.org/10.1016/j.plrev.2016.10.004</a>","ama":"Hilbe C, Traulsen A. Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze. <i>Physics of Life Reviews</i>. 2016;19:29-31. doi:<a href=\"https://doi.org/10.1016/j.plrev.2016.10.004\">10.1016/j.plrev.2016.10.004</a>"},"title":"Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze","day":"01","author":[{"id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5116-955X","full_name":"Hilbe, Christian","first_name":"Christian","last_name":"Hilbe"},{"last_name":"Traulsen","first_name":"Arne","full_name":"Traulsen, Arne"}],"type":"journal_article","acknowledgement":"C.H. acknowledges generous support from the ISTFELLOW program.","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"language":[{"iso":"eng"}],"ddc":["530"],"doi":"10.1016/j.plrev.2016.10.004","file":[{"file_name":"IST-2017-798-v1+1_comment_adami.pdf","file_size":171352,"creator":"system","checksum":"95e6dc78278334b99dacbf8822509364","date_updated":"2020-07-14T12:44:39Z","access_level":"open_access","content_type":"application/pdf","file_id":"4855","relation":"main_file","date_created":"2018-12-12T10:11:02Z"}],"date_published":"2016-12-01T00:00:00Z","_id":"1200","publication_status":"published","oa":1,"file_date_updated":"2020-07-14T12:44:39Z","volume":19,"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","image":"/images/cc_by_nc_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)"},"pubrep_id":"798","publist_id":"6150","oa_version":"Submitted Version","year":"2016","has_accepted_license":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:49:03Z","scopus_import":1},{"publication_status":"published","volume":26,"issue":"Februar-2016","_id":"1245","date_published":"2016-02-27T00:00:00Z","abstract":[{"text":"To facilitate collaboration in massive online classrooms, instructors must make many decisions. For instance, the following parameters need to be decided when designing a peer-feedback system where students review each others' essays: the number of students each student must provide feedback to, an algorithm to map feedback providers to receivers, constraints that ensure students do not become free-riders (receiving feedback but not providing it), the best times to receive feedback to improve learning etc. While instructors can answer these questions by running experiments or invoking past experience, game-theoretic models with data from online learning platforms can identify better initial designs for further improvements. As an example, we explore the design space of a peer feedback system by modeling it using game theory. Our simulations show that incentivizing students to provide feedback requires the value obtained from receiving a feedback to exceed the cost of providing it by a large factor (greater than 7). Furthermore, hiding feedback from low-effort students incentivizes them to provide more feedback.","lang":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:49:22Z","scopus_import":1,"year":"2016","oa_version":"None","publist_id":"6083","publisher":"ACM","intvolume":"        26","status":"public","department":[{"_id":"KrCh"}],"quality_controlled":"1","publication":"Proceedings of the ACM Conference on Computer Supported Cooperative Work","page":"365 - 368","date_created":"2018-12-11T11:50:55Z","month":"02","acknowledgement":"ERC Start Grant Graph Games 279307 supported this  research. ","project":[{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"doi":"10.1145/2818052.2869122","language":[{"iso":"eng"}],"conference":{"location":"San Francisco, CA, USA","name":"CSCW: Computer Supported Cooperative Work and Social Computing","end_date":"2016-03-02","start_date":"2016-02-26"},"title":"Game-theoretic models identify useful principles for peer collaboration in online learning platforms","ec_funded":1,"citation":{"mla":"Pandey, Vineet, and Krishnendu Chatterjee. “Game-Theoretic Models Identify Useful Principles for Peer Collaboration in Online Learning Platforms.” <i>Proceedings of the ACM Conference on Computer Supported Cooperative Work</i>, vol. 26, no. Februar-2016, ACM, 2016, pp. 365–68, doi:<a href=\"https://doi.org/10.1145/2818052.2869122\">10.1145/2818052.2869122</a>.","chicago":"Pandey, Vineet, and Krishnendu Chatterjee. “Game-Theoretic Models Identify Useful Principles for Peer Collaboration in Online Learning Platforms.” In <i>Proceedings of the ACM Conference on Computer Supported Cooperative Work</i>, 26:365–68. ACM, 2016. <a href=\"https://doi.org/10.1145/2818052.2869122\">https://doi.org/10.1145/2818052.2869122</a>.","ieee":"V. Pandey and K. Chatterjee, “Game-theoretic models identify useful principles for peer collaboration in online learning platforms,” in <i>Proceedings of the ACM Conference on Computer Supported Cooperative Work</i>, San Francisco, CA, USA, 2016, vol. 26, no. Februar-2016, pp. 365–368.","ista":"Pandey V, Chatterjee K. 2016. Game-theoretic models identify useful principles for peer collaboration in online learning platforms. Proceedings of the ACM Conference on Computer Supported Cooperative Work. CSCW: Computer Supported Cooperative Work and Social Computing vol. 26, 365–368.","ama":"Pandey V, Chatterjee K. Game-theoretic models identify useful principles for peer collaboration in online learning platforms. In: <i>Proceedings of the ACM Conference on Computer Supported Cooperative Work</i>. Vol 26. ACM; 2016:365-368. doi:<a href=\"https://doi.org/10.1145/2818052.2869122\">10.1145/2818052.2869122</a>","apa":"Pandey, V., &#38; Chatterjee, K. (2016). Game-theoretic models identify useful principles for peer collaboration in online learning platforms. In <i>Proceedings of the ACM Conference on Computer Supported Cooperative Work</i> (Vol. 26, pp. 365–368). San Francisco, CA, USA: ACM. <a href=\"https://doi.org/10.1145/2818052.2869122\">https://doi.org/10.1145/2818052.2869122</a>","short":"V. Pandey, K. Chatterjee, in:, Proceedings of the ACM Conference on Computer Supported Cooperative Work, ACM, 2016, pp. 365–368."},"author":[{"last_name":"Pandey","first_name":"Vineet","full_name":"Pandey, Vineet"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"}],"type":"conference","day":"27"},{"oa_version":"Published Version","year":"2016","author":[{"id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5116-955X","first_name":"Christian","full_name":"Hilbe, Christian","last_name":"Hilbe"},{"first_name":"Kristin","full_name":"Hagel, Kristin","last_name":"Hagel"},{"last_name":"Milinski","full_name":"Milinski, Manfred","first_name":"Manfred"}],"type":"research_data_reference","day":"04","title":"Experimental game instructions","citation":{"chicago":"Hilbe, Christian, Kristin Hagel, and Manfred Milinski. “Experimental Game Instructions.” Public Library of Science, 2016. <a href=\"https://doi.org/10.1371/journal.pone.0163867.s008\">https://doi.org/10.1371/journal.pone.0163867.s008</a>.","ista":"Hilbe C, Hagel K, Milinski M. 2016. Experimental game instructions, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pone.0163867.s008\">10.1371/journal.pone.0163867.s008</a>.","ieee":"C. Hilbe, K. Hagel, and M. Milinski, “Experimental game instructions.” Public Library of Science, 2016.","mla":"Hilbe, Christian, et al. <i>Experimental Game Instructions</i>. Public Library of Science, 2016, doi:<a href=\"https://doi.org/10.1371/journal.pone.0163867.s008\">10.1371/journal.pone.0163867.s008</a>.","short":"C. Hilbe, K. Hagel, M. Milinski, (2016).","ama":"Hilbe C, Hagel K, Milinski M. Experimental game instructions. 2016. doi:<a href=\"https://doi.org/10.1371/journal.pone.0163867.s008\">10.1371/journal.pone.0163867.s008</a>","apa":"Hilbe, C., Hagel, K., &#38; Milinski, M. (2016). Experimental game instructions. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0163867.s008\">https://doi.org/10.1371/journal.pone.0163867.s008</a>"},"doi":"10.1371/journal.pone.0163867.s008","date_updated":"2023-02-21T16:59:01Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","related_material":{"record":[{"relation":"used_in_publication","id":"1322","status":"public"}]},"date_created":"2021-08-10T08:42:00Z","_id":"9867","abstract":[{"lang":"eng","text":"In the beginning of our experiment, subjects were asked to read a few pages on their computer screens that would explain the rules of the subsequent game. Here, we provide these instructions, translated from German."}],"month":"10","article_processing_charge":"No","status":"public","department":[{"_id":"KrCh"}],"publisher":"Public Library of Science"},{"type":"research_data_reference","author":[{"id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5116-955X","last_name":"Hilbe","first_name":"Christian","full_name":"Hilbe, Christian"},{"first_name":"Kristin","full_name":"Hagel, Kristin","last_name":"Hagel"},{"first_name":"Manfred","full_name":"Milinski, Manfred","last_name":"Milinski"}],"oa_version":"Published Version","year":"2016","day":"04","title":"Experimental data","citation":{"chicago":"Hilbe, Christian, Kristin Hagel, and Manfred Milinski. “Experimental Data.” Public Library of Science, 2016. <a href=\"https://doi.org/10.1371/journal.pone.0163867.s009\">https://doi.org/10.1371/journal.pone.0163867.s009</a>.","ieee":"C. Hilbe, K. Hagel, and M. Milinski, “Experimental data.” Public Library of Science, 2016.","ista":"Hilbe C, Hagel K, Milinski M. 2016. Experimental data, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pone.0163867.s009\">10.1371/journal.pone.0163867.s009</a>.","mla":"Hilbe, Christian, et al. <i>Experimental Data</i>. Public Library of Science, 2016, doi:<a href=\"https://doi.org/10.1371/journal.pone.0163867.s009\">10.1371/journal.pone.0163867.s009</a>.","short":"C. Hilbe, K. Hagel, M. Milinski, (2016).","ama":"Hilbe C, Hagel K, Milinski M. Experimental data. 2016. doi:<a href=\"https://doi.org/10.1371/journal.pone.0163867.s009\">10.1371/journal.pone.0163867.s009</a>","apa":"Hilbe, C., Hagel, K., &#38; Milinski, M. (2016). Experimental data. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0163867.s009\">https://doi.org/10.1371/journal.pone.0163867.s009</a>"},"doi":"10.1371/journal.pone.0163867.s009","date_updated":"2023-02-21T16:59:01Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","related_material":{"record":[{"relation":"used_in_publication","id":"1322","status":"public"}]},"date_published":"2016-10-04T00:00:00Z","_id":"9868","abstract":[{"text":"The raw data file containing the experimental decisions of all our study subjects.","lang":"eng"}],"date_created":"2021-08-10T08:45:00Z","month":"10","article_processing_charge":"No","status":"public","department":[{"_id":"KrCh"}],"publisher":"Public Library of Science"},{"type":"conference","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","last_name":"Ibsen-Jensen"}],"day":"01","title":"The value 1 problem under finite-memory strategies for concurrent mean-payoff games","conference":{"location":"San Diego, CA, United States","end_date":"2015-01-06","start_date":"2015-01-04","name":"SODA: Symposium on Discrete Algorithms"},"citation":{"ista":"Chatterjee K, Ibsen-Jensen R. 2015. The value 1 problem under finite-memory strategies for concurrent mean-payoff games. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2015, 1018–1029.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “The value 1 problem under finite-memory strategies for concurrent mean-payoff games,” in <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, San Diego, CA, United States, 2015, vol. 2015, no. 1, pp. 1018–1029.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under Finite-Memory Strategies for Concurrent Mean-Payoff Games.” In <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2015:1018–29. SIAM, 2015. <a href=\"https://doi.org/10.1137/1.9781611973730.69\">https://doi.org/10.1137/1.9781611973730.69</a>.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Value 1 Problem under Finite-Memory Strategies for Concurrent Mean-Payoff Games.” <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2015, no. 1, SIAM, 2015, pp. 1018–29, doi:<a href=\"https://doi.org/10.1137/1.9781611973730.69\">10.1137/1.9781611973730.69</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, in:, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2015, pp. 1018–1029.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2015). The value 1 problem under finite-memory strategies for concurrent mean-payoff games. In <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2015, pp. 1018–1029). San Diego, CA, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611973730.69\">https://doi.org/10.1137/1.9781611973730.69</a>","ama":"Chatterjee K, Ibsen-Jensen R. The value 1 problem under finite-memory strategies for concurrent mean-payoff games. In: <i>Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2015. SIAM; 2015:1018-1029. doi:<a href=\"https://doi.org/10.1137/1.9781611973730.69\">10.1137/1.9781611973730.69</a>"},"ec_funded":1,"doi":"10.1137/1.9781611973730.69","language":[{"iso":"eng"}],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"S11407","name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"acknowledgement":"The research was partly supported by FWF Grant No P 23499-N23, FWF NFN Grant\r\nNo S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","date_created":"2022-02-25T12:18:43Z","month":"01","page":"1018-1029","intvolume":"      2015","status":"public","publication":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms","department":[{"_id":"KrCh"}],"quality_controlled":"1","publisher":"SIAM","year":"2015","oa_version":"Preprint","publication_identifier":{"isbn":["978-161197374-7"]},"external_id":{"arxiv":["1409.6690"]},"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2022-02-25T12:33:32Z","abstract":[{"text":"We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).","lang":"eng"}],"_id":"10796","date_published":"2015-01-01T00:00:00Z","article_processing_charge":"No","issue":"1","arxiv":1,"volume":2015,"publication_status":"published"},{"oa_version":"Published Version","year":"2015","has_accepted_license":"1","publist_id":"5536","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:52:05Z","scopus_import":1,"abstract":[{"lang":"eng","text":"Population structure can facilitate evolution of cooperation. In a structured population, cooperators can form clusters which resist exploitation by defectors. Recently, it was observed that a shift update rule is an extremely strong amplifier of cooperation in a one dimensional spatial model. For the shift update rule, an individual is chosen for reproduction proportional to fecundity; the offspring is placed next to the parent; a random individual dies. Subsequently, the population is rearranged (shifted) until all individual cells are again evenly spaced out. For large population size and a one dimensional population structure, the shift update rule favors cooperation for any benefit-to-cost ratio greater than one. But every attempt to generalize shift updating to higher dimensions while maintaining its strong effect has failed. The reason is that in two dimensions the clusters are fragmented by the movements caused by rearranging the cells. Here we introduce the natural phenomenon of a repulsive force between cells of different types. After a birth and death event, the cells are being rearranged minimizing the overall energy expenditure. If the repulsive force is sufficiently high, shift becomes a strong promoter of cooperation in two dimensions."}],"_id":"1624","date_published":"2015-11-25T00:00:00Z","article_number":"17147","file":[{"creator":"system","file_size":1021931,"file_name":"IST-2016-466-v1+1_srep17147.pdf","access_level":"open_access","date_updated":"2020-07-14T12:45:07Z","checksum":"38e06d8310d2087cae5f6d4d4bfe082b","file_id":"4947","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:12:29Z"}],"volume":5,"pubrep_id":"466","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"file_date_updated":"2020-07-14T12:45:07Z","oa":1,"publication_status":"published","author":[{"first_name":"Andreas","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Adlam","full_name":"Adlam, Ben","first_name":"Ben"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"}],"type":"journal_article","day":"25","title":"Cellular cooperation with shift updating and repulsion","ec_funded":1,"citation":{"mla":"Pavlogiannis, Andreas, et al. “Cellular Cooperation with Shift Updating and Repulsion.” <i>Scientific Reports</i>, vol. 5, 17147, Nature Publishing Group, 2015, doi:<a href=\"https://doi.org/10.1038/srep17147\">10.1038/srep17147</a>.","ista":"Pavlogiannis A, Chatterjee K, Adlam B, Nowak M. 2015. Cellular cooperation with shift updating and repulsion. Scientific Reports. 5, 17147.","ieee":"A. Pavlogiannis, K. Chatterjee, B. Adlam, and M. Nowak, “Cellular cooperation with shift updating and repulsion,” <i>Scientific Reports</i>, vol. 5. Nature Publishing Group, 2015.","chicago":"Pavlogiannis, Andreas, Krishnendu Chatterjee, Ben Adlam, and Martin Nowak. “Cellular Cooperation with Shift Updating and Repulsion.” <i>Scientific Reports</i>. Nature Publishing Group, 2015. <a href=\"https://doi.org/10.1038/srep17147\">https://doi.org/10.1038/srep17147</a>.","apa":"Pavlogiannis, A., Chatterjee, K., Adlam, B., &#38; Nowak, M. (2015). Cellular cooperation with shift updating and repulsion. <i>Scientific Reports</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/srep17147\">https://doi.org/10.1038/srep17147</a>","ama":"Pavlogiannis A, Chatterjee K, Adlam B, Nowak M. Cellular cooperation with shift updating and repulsion. <i>Scientific Reports</i>. 2015;5. doi:<a href=\"https://doi.org/10.1038/srep17147\">10.1038/srep17147</a>","short":"A. Pavlogiannis, K. Chatterjee, B. Adlam, M. Nowak, Scientific Reports 5 (2015)."},"doi":"10.1038/srep17147","ddc":["000"],"language":[{"iso":"eng"}],"acknowledgement":"The research was supported by the Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307: Graph Games), and Microsoft Faculty Fellows award. Support from the John Templeton foundation is gratefully acknowledged.","project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"date_created":"2018-12-11T11:53:06Z","month":"11","status":"public","intvolume":"         5","quality_controlled":"1","department":[{"_id":"KrCh"}],"publication":"Scientific Reports","publisher":"Nature Publishing Group"},{"month":"07","date_created":"2018-12-11T11:53:17Z","quality_controlled":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication":"Proceedings - Symposium on Logic in Computer Science","status":"public","publisher":"IEEE","day":"31","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Otop","full_name":"Otop, Jan","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","ec_funded":1,"citation":{"chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Nested Weighted Automata.” In <i>Proceedings - Symposium on Logic in Computer Science</i>, Vol. 2015–July. IEEE, 2015. <a href=\"https://doi.org/10.1109/LICS.2015.72\">https://doi.org/10.1109/LICS.2015.72</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Nested weighted automata,” in <i>Proceedings - Symposium on Logic in Computer Science</i>, Kyoto, Japan, 2015, vol. 2015–July.","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174926.","mla":"Chatterjee, Krishnendu, et al. “Nested Weighted Automata.” <i>Proceedings - Symposium on Logic in Computer Science</i>, vol. 2015–July, 7174926, IEEE, 2015, doi:<a href=\"https://doi.org/10.1109/LICS.2015.72\">10.1109/LICS.2015.72</a>.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.","ama":"Chatterjee K, Henzinger TA, Otop J. Nested weighted automata. In: <i>Proceedings - Symposium on Logic in Computer Science</i>. Vol 2015-July. IEEE; 2015. doi:<a href=\"https://doi.org/10.1109/LICS.2015.72\">10.1109/LICS.2015.72</a>","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2015). Nested weighted automata. In <i>Proceedings - Symposium on Logic in Computer Science</i> (Vol. 2015–July). Kyoto, Japan: IEEE. <a href=\"https://doi.org/10.1109/LICS.2015.72\">https://doi.org/10.1109/LICS.2015.72</a>"},"conference":{"location":"Kyoto, Japan","start_date":"2015-07-06","end_date":"2015-07-10","name":"LICS: Logic in Computer Science"},"title":"Nested weighted automata","language":[{"iso":"eng"}],"doi":"10.1109/LICS.2015.72","acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402-N23 (RiSE), Z211-N23 (Wittgenstein Award), FWF Grant No P23499- N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.\r\nA Technical Report of the paper is available at: \r\nhttps://repository.ist.ac.at/331/\r\n","related_material":{"record":[{"relation":"later_version","id":"467","status":"public"},{"id":"5415","relation":"earlier_version","status":"public"},{"status":"public","id":"5436","relation":"earlier_version"}]},"project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z211","name":"The Wittgenstein Prize"},{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"article_number":"7174926","_id":"1656","date_published":"2015-07-31T00:00:00Z","abstract":[{"lang":"eng","text":"Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time. In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties."}],"arxiv":1,"volume":"2015-July","publication_status":"published","publist_id":"5494","year":"2015","oa_version":"None","date_updated":"2023-02-23T12:26:19Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1606.03598"]},"scopus_import":1},{"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","conference":{"name":"LICS: Logic in Computer Science","end_date":"2015-07-10","start_date":"2015-07-06","location":"Kyoto, Japan"},"citation":{"apa":"Chatterjee, K., Komárková, Z., &#38; Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. Presented at the LICS: Logic in Computer Science, Kyoto, Japan: IEEE. <a href=\"https://doi.org/10.1109/LICS.2015.32\">https://doi.org/10.1109/LICS.2015.32</a>","ama":"Chatterjee K, Komárková Z, Kretinsky J. Unifying two views on multiple mean-payoff objectives in Markov decision processes. 2015:244-256. doi:<a href=\"https://doi.org/10.1109/LICS.2015.32\">10.1109/LICS.2015.32</a>","short":"K. Chatterjee, Z. Komárková, J. Kretinsky, (2015) 244–256.","mla":"Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IEEE, 2015, pp. 244–56, doi:<a href=\"https://doi.org/10.1109/LICS.2015.32\">10.1109/LICS.2015.32</a>.","ista":"Chatterjee K, Komárková Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes. , 244–256.","ieee":"K. Chatterjee, Z. Komárková, and J. Kretinsky, “Unifying two views on multiple mean-payoff objectives in Markov decision processes.” IEEE, pp. 244–256, 2015.","chicago":"Chatterjee, Krishnendu, Zuzana Komárková, and Jan Kretinsky. “Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes.” LICS. IEEE, 2015. <a href=\"https://doi.org/10.1109/LICS.2015.32\">https://doi.org/10.1109/LICS.2015.32</a>."},"ec_funded":1,"type":"conference","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Komárková","first_name":"Zuzana","full_name":"Komárková, Zuzana"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","last_name":"Kretinsky","first_name":"Jan","full_name":"Kretinsky, Jan"}],"alternative_title":["LICS"],"day":"01","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z211","name":"The Wittgenstein Prize"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"grant_number":"267989","name":"Quantitative Reactive Modeling","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"related_material":{"record":[{"status":"public","id":"466","relation":"later_version"},{"status":"public","relation":"earlier_version","id":"5429"},{"status":"public","relation":"earlier_version","id":"5435"}]},"acknowledgement":"A Technical Report of this paper is available at:  https://repository.ist.ac.at/327\r\n","doi":"10.1109/LICS.2015.32","language":[{"iso":"eng"}],"page":"244 - 256","date_created":"2018-12-11T11:53:18Z","series_title":"LICS","month":"07","publisher":"IEEE","status":"public","quality_controlled":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"oa_version":"None","year":"2015","publist_id":"5493","scopus_import":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T12:26:16Z","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i) ~the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) ~the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., Ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems, which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem. "}],"_id":"1657","date_published":"2015-07-01T00:00:00Z","publication_status":"published"},{"doi":"10.1109/LICS.2015.15","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"date_updated":"2021-01-12T06:52:20Z","scopus_import":1,"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"oa_version":"Preprint","year":"2015","alternative_title":["LICS"],"author":[{"last_name":"Brázdil","first_name":"Tomáš","full_name":"Brázdil, Tomáš"},{"last_name":"Kiefer","full_name":"Kiefer, Stefan","first_name":"Stefan"},{"full_name":"Kučera, Antonín","first_name":"Antonín","last_name":"Kučera"},{"last_name":"Novotny","full_name":"Novotny, Petr","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","publist_id":"5490","day":"01","conference":{"name":"LICS: Logic in Computer Science","end_date":"2015-07-10","start_date":"2015-07-06","location":"Kyoto, Japan"},"title":"Long-run average behaviour of probabilistic vector addition systems","ec_funded":1,"citation":{"mla":"Brázdil, Tomáš, et al. <i>Long-Run Average Behaviour of Probabilistic Vector Addition Systems</i>. IEEE, 2015, pp. 44–55, doi:<a href=\"https://doi.org/10.1109/LICS.2015.15\">10.1109/LICS.2015.15</a>.","ista":"Brázdil T, Kiefer S, Kučera A, Novotný P. 2015. Long-run average behaviour of probabilistic vector addition systems. LICS: Logic in Computer Science, LICS, , 44–55.","ieee":"T. Brázdil, S. Kiefer, A. Kučera, and P. Novotný, “Long-run average behaviour of probabilistic vector addition systems,” presented at the LICS: Logic in Computer Science, Kyoto, Japan, 2015, pp. 44–55.","chicago":"Brázdil, Tomáš, Stefan Kiefer, Antonín Kučera, and Petr Novotný. “Long-Run Average Behaviour of Probabilistic Vector Addition Systems,” 44–55. IEEE, 2015. <a href=\"https://doi.org/10.1109/LICS.2015.15\">https://doi.org/10.1109/LICS.2015.15</a>.","apa":"Brázdil, T., Kiefer, S., Kučera, A., &#38; Novotný, P. (2015). Long-run average behaviour of probabilistic vector addition systems (pp. 44–55). Presented at the LICS: Logic in Computer Science, Kyoto, Japan: IEEE. <a href=\"https://doi.org/10.1109/LICS.2015.15\">https://doi.org/10.1109/LICS.2015.15</a>","ama":"Brázdil T, Kiefer S, Kučera A, Novotný P. Long-run average behaviour of probabilistic vector addition systems. In: IEEE; 2015:44-55. doi:<a href=\"https://doi.org/10.1109/LICS.2015.15\">10.1109/LICS.2015.15</a>","short":"T. Brázdil, S. Kiefer, A. Kučera, P. Novotný, in:, IEEE, 2015, pp. 44–55."},"status":"public","quality_controlled":"1","department":[{"_id":"KrCh"}],"oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1505.02655","open_access":"1"}],"publication_status":"published","publisher":"IEEE","date_created":"2018-12-11T11:53:19Z","_id":"1660","date_published":"2015-07-01T00:00:00Z","abstract":[{"lang":"eng","text":"We study the pattern frequency vector for runs in probabilistic Vector Addition Systems with States (pVASS). Intuitively, each configuration of a given pVASS is assigned one of finitely many patterns, and every run can thus be seen as an infinite sequence of these patterns. The pattern frequency vector assigns to each run the limit of pattern frequencies computed for longer and longer prefixes of the run. If the limit does not exist, then the vector is undefined. We show that for one-counter pVASS, the pattern frequency vector is defined and takes one of finitely many values for almost all runs. Further, these values and their associated probabilities can be approximated up to an arbitrarily small relative error in polynomial time. For stable two-counter pVASS, we show the same result, but we do not provide any upper complexity bound. As a byproduct of our study, we discover counterexamples falsifying some classical results about stochastic Petri nets published in the 80s."}],"month":"07","page":"44 - 55"},{"title":"Improved algorithms for one-pair and k-pair Streett objectives","conference":{"name":"LICS: Logic in Computer Science","start_date":"2015-07-06","end_date":"2015-07-10","location":"Kyoto, Japan"},"citation":{"mla":"Chatterjee, Krishnendu, et al. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” <i>Proceedings - Symposium on Logic in Computer Science</i>, vol. 2015–July, 7174888, IEEE, 2015, doi:<a href=\"https://doi.org/10.1109/LICS.2015.34\">10.1109/LICS.2015.34</a>.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” In <i>Proceedings - Symposium on Logic in Computer Science</i>, Vol. 2015–July. IEEE, 2015. <a href=\"https://doi.org/10.1109/LICS.2015.34\">https://doi.org/10.1109/LICS.2015.34</a>.","ieee":"K. Chatterjee, M. H. Henzinger, and V. Loitzenbauer, “Improved algorithms for one-pair and k-pair Streett objectives,” in <i>Proceedings - Symposium on Logic in Computer Science</i>, Kyoto, Japan, 2015, vol. 2015–July.","ista":"Chatterjee K, Henzinger MH, Loitzenbauer V. 2015. Improved algorithms for one-pair and k-pair Streett objectives. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174888.","ama":"Chatterjee K, Henzinger MH, Loitzenbauer V. Improved algorithms for one-pair and k-pair Streett objectives. In: <i>Proceedings - Symposium on Logic in Computer Science</i>. Vol 2015-July. IEEE; 2015. doi:<a href=\"https://doi.org/10.1109/LICS.2015.34\">10.1109/LICS.2015.34</a>","apa":"Chatterjee, K., Henzinger, M. H., &#38; Loitzenbauer, V. (2015). Improved algorithms for one-pair and k-pair Streett objectives. In <i>Proceedings - Symposium on Logic in Computer Science</i> (Vol. 2015–July). Kyoto, Japan: IEEE. <a href=\"https://doi.org/10.1109/LICS.2015.34\">https://doi.org/10.1109/LICS.2015.34</a>","short":"K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015."},"ec_funded":1,"type":"conference","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H"},{"first_name":"Veronika","full_name":"Loitzenbauer, Veronika","last_name":"Loitzenbauer"}],"day":"01","related_material":{"record":[{"status":"public","id":"464","relation":"later_version"}]},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"acknowledgement":"K. C. is supported by the Austrian Science Fund (FWF): P23499-N23 and S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award. M. H. is supported by the Austrian Science Fund (FWF): P23499-N23 and the Vienna Science and Technology Fund (WWTF) grant ICT10-002. V. L. is supported by the Vienna Science and Technology Fund (WWTF) grant ICT10-002. The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 340506.","doi":"10.1109/LICS.2015.34","language":[{"iso":"eng"}],"date_created":"2018-12-11T11:53:19Z","month":"07","publisher":"IEEE","status":"public","publication":"Proceedings - Symposium on Logic in Computer Science","quality_controlled":"1","department":[{"_id":"KrCh"}],"year":"2015","oa_version":"Submitted Version","publist_id":"5489","scopus_import":"1","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","date_updated":"2025-06-02T08:53:41Z","article_processing_charge":"No","_id":"1661","abstract":[{"text":"The computation of the winning set for one-pair Streett objectives and for k-pair Streett objectives in (standard) graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formed ness of specifications, and the synthesis of reactive systems. We give faster algorithms for the computation of the winning set for (1) one-pair Streett objectives (aka parity-3 problem) in game graphs and (2) for k-pair Streett objectives in graphs. For both problems this represents the first improvement in asymptotic running time in 15 years.","lang":"eng"}],"date_published":"2015-07-01T00:00:00Z","article_number":"7174888","main_file_link":[{"url":"https://eprints.cs.univie.ac.at/4368/","open_access":"1"}],"oa":1,"publication_status":"published","volume":"2015-July"},{"publisher":"Nature Publishing Group","status":"public","intvolume":"       526","quality_controlled":"1","department":[{"_id":"KrCh"}],"publication":"Nature","page":"525 - 530","date_created":"2018-12-11T11:53:21Z","month":"10","project":[{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"}],"pmid":1,"doi":"10.1038/nature15395","language":[{"iso":"eng"}],"title":"Mutations driving CLL and their evolution in progression and relapse","ec_funded":1,"citation":{"short":"D. Landau, E. Tausch, A. Taylor Weiner, C. Stewart, J. Reiter, J. Bahlo, S. Kluth, I. Božić, M. Lawrence, S. Böttcher, S. Carter, K. Cibulskis, D. Mertens, C. Sougnez, M. Rosenberg, J. Hess, J. Edelmann, S. Kless, M. Kneba, M. Ritgen, A. Fink, K. Fischer, S. Gabriel, E. Lander, M. Nowak, H. Döhner, M. Hallek, D. Neuberg, G. Getz, S. Stilgenbauer, C. Wu, Nature 526 (2015) 525–530.","apa":"Landau, D., Tausch, E., Taylor Weiner, A., Stewart, C., Reiter, J., Bahlo, J., … Wu, C. (2015). Mutations driving CLL and their evolution in progression and relapse. <i>Nature</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nature15395\">https://doi.org/10.1038/nature15395</a>","ama":"Landau D, Tausch E, Taylor Weiner A, et al. Mutations driving CLL and their evolution in progression and relapse. <i>Nature</i>. 2015;526(7574):525-530. doi:<a href=\"https://doi.org/10.1038/nature15395\">10.1038/nature15395</a>","ista":"Landau D, Tausch E, Taylor Weiner A, Stewart C, Reiter J, Bahlo J, Kluth S, Božić I, Lawrence M, Böttcher S, Carter S, Cibulskis K, Mertens D, Sougnez C, Rosenberg M, Hess J, Edelmann J, Kless S, Kneba M, Ritgen M, Fink A, Fischer K, Gabriel S, Lander E, Nowak M, Döhner H, Hallek M, Neuberg D, Getz G, Stilgenbauer S, Wu C. 2015. Mutations driving CLL and their evolution in progression and relapse. Nature. 526(7574), 525–530.","ieee":"D. Landau <i>et al.</i>, “Mutations driving CLL and their evolution in progression and relapse,” <i>Nature</i>, vol. 526, no. 7574. Nature Publishing Group, pp. 525–530, 2015.","chicago":"Landau, Dan, Eugen Tausch, Amaro Taylor Weiner, Chip Stewart, Johannes Reiter, Jasmin Bahlo, Sandra Kluth, et al. “Mutations Driving CLL and Their Evolution in Progression and Relapse.” <i>Nature</i>. Nature Publishing Group, 2015. <a href=\"https://doi.org/10.1038/nature15395\">https://doi.org/10.1038/nature15395</a>.","mla":"Landau, Dan, et al. “Mutations Driving CLL and Their Evolution in Progression and Relapse.” <i>Nature</i>, vol. 526, no. 7574, Nature Publishing Group, 2015, pp. 525–30, doi:<a href=\"https://doi.org/10.1038/nature15395\">10.1038/nature15395</a>."},"author":[{"last_name":"Landau","full_name":"Landau, Dan","first_name":"Dan"},{"full_name":"Tausch, Eugen","first_name":"Eugen","last_name":"Tausch"},{"last_name":"Taylor Weiner","first_name":"Amaro","full_name":"Taylor Weiner, Amaro"},{"full_name":"Stewart, Chip","first_name":"Chip","last_name":"Stewart"},{"orcid":"0000-0002-0170-7353","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter","full_name":"Reiter, Johannes","first_name":"Johannes"},{"full_name":"Bahlo, Jasmin","first_name":"Jasmin","last_name":"Bahlo"},{"last_name":"Kluth","first_name":"Sandra","full_name":"Kluth, Sandra"},{"first_name":"Ivana","full_name":"Božić, Ivana","last_name":"Božić"},{"last_name":"Lawrence","first_name":"Michael","full_name":"Lawrence, Michael"},{"last_name":"Böttcher","first_name":"Sebastian","full_name":"Böttcher, Sebastian"},{"last_name":"Carter","first_name":"Scott","full_name":"Carter, Scott"},{"full_name":"Cibulskis, Kristian","first_name":"Kristian","last_name":"Cibulskis"},{"last_name":"Mertens","first_name":"Daniel","full_name":"Mertens, Daniel"},{"first_name":"Carrie","full_name":"Sougnez, Carrie","last_name":"Sougnez"},{"first_name":"Mara","full_name":"Rosenberg, Mara","last_name":"Rosenberg"},{"last_name":"Hess","first_name":"Julian","full_name":"Hess, Julian"},{"first_name":"Jennifer","full_name":"Edelmann, Jennifer","last_name":"Edelmann"},{"first_name":"Sabrina","full_name":"Kless, Sabrina","last_name":"Kless"},{"first_name":"Michael","full_name":"Kneba, Michael","last_name":"Kneba"},{"first_name":"Matthias","full_name":"Ritgen, Matthias","last_name":"Ritgen"},{"full_name":"Fink, Anna","first_name":"Anna","last_name":"Fink"},{"last_name":"Fischer","full_name":"Fischer, Kirsten","first_name":"Kirsten"},{"last_name":"Gabriel","first_name":"Stacey","full_name":"Gabriel, Stacey"},{"full_name":"Lander, Eric","first_name":"Eric","last_name":"Lander"},{"last_name":"Nowak","first_name":"Martin","full_name":"Nowak, Martin"},{"last_name":"Döhner","first_name":"Hartmut","full_name":"Döhner, Hartmut"},{"last_name":"Hallek","first_name":"Michael","full_name":"Hallek, Michael"},{"full_name":"Neuberg, Donna","first_name":"Donna","last_name":"Neuberg"},{"full_name":"Getz, Gad","first_name":"Gad","last_name":"Getz"},{"last_name":"Stilgenbauer","first_name":"Stephan","full_name":"Stilgenbauer, Stephan"},{"full_name":"Wu, Catherine","first_name":"Catherine","last_name":"Wu"}],"type":"journal_article","day":"22","oa":1,"main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4815041/","open_access":"1"}],"publication_status":"published","volume":526,"issue":"7574","article_processing_charge":"No","date_published":"2015-10-22T00:00:00Z","_id":"1665","abstract":[{"lang":"eng","text":"Which genetic alterations drive tumorigenesis and how they evolve over the course of disease and therapy are central questions in cancer biology. Here we identify 44 recurrently mutated genes and 11 recurrent somatic copy number variations through whole-exome sequencing of 538 chronic lymphocytic leukaemia (CLL) and matched germline DNA samples, 278 of which were collected in a prospective clinical trial. These include previously unrecognized putative cancer drivers (RPS15, IKZF3), and collectively identify RNA processing and export, MYC activity, and MAPK signalling as central pathways involved in CLL. Clonality analysis of this large data set further enabled reconstruction of temporal relationships between driver events. Direct comparison between matched pre-treatment and relapse samples from 59 patients demonstrated highly frequent clonal evolution. Thus, large sequencing data sets of clinically informative samples enable the discovery of novel genes associated with cancer, the network of relationships between the driver events, and their impact on disease relapse and clinical outcome."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:52:23Z","external_id":{"pmid":["26466571"]},"scopus_import":1,"oa_version":"Submitted Version","year":"2015","publist_id":"5484","article_type":"original"}]