[{"article_number":"10","publist_id":"5944","ec_funded":1,"file_date_updated":"2020-07-14T12:44:44Z","license":"https://creativecommons.org/licenses/by/4.0/","year":"2016","acknowledgement":"The work has been supported by the Czech Science Foundation, grant No. 15-17564S, by EPSRC grant\r\nEP/M023656/1, and by the People Programme (Marie Curie Actions) of the European Union’s Seventh\r\nFramework Programme (FP7/2007-2013) under REA grant agreement no [291734]","department":[{"_id":"KrCh"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","author":[{"full_name":"Brázdil, Tomáš","first_name":"Tomáš","last_name":"Brázdil"},{"last_name":"Forejt","first_name":"Vojtěch","full_name":"Forejt, Vojtěch"},{"full_name":"Kučera, Antonín","last_name":"Kučera","first_name":"Antonín"},{"full_name":"Novotny, Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","first_name":"Petr","last_name":"Novotny"}],"volume":59,"date_created":"2018-12-11T11:51:23Z","date_updated":"2021-01-12T06:49:53Z","month":"08","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"quality_controlled":"1","doi":"10.4230/LIPIcs.CONCUR.2016.10","conference":{"location":"Quebec City, Canada","start_date":"2016-08-23","end_date":"2016-08-26","name":"CONCUR: Concurrency Theory"},"language":[{"iso":"eng"}],"type":"conference","alternative_title":["LIPIcs"],"abstract":[{"text":"We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.","lang":"eng"}],"_id":"1325","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","intvolume":" 59","title":"Stability in graphs and games","status":"public","ddc":["004"],"pubrep_id":"665","file":[{"checksum":"3c2dc6ab0358f8aa8f7aa7d6c1293159","date_updated":"2020-07-14T12:44:44Z","date_created":"2018-12-12T10:16:40Z","file_id":"5229","relation":"main_file","creator":"system","file_size":553648,"content_type":"application/pdf","access_level":"open_access","file_name":"IST-2016-665-v1+1_Forejt_et_al__Stability_in_graphs_and_games.pdf"}],"oa_version":"Published Version","scopus_import":1,"has_accepted_license":"1","day":"01","citation":{"chicago":"Brázdil, Tomáš, Vojtěch Forejt, Antonín Kučera, and Petr Novotný. “Stability in Graphs and Games,” Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPIcs.CONCUR.2016.10.","short":"T. Brázdil, V. Forejt, A. Kučera, P. Novotný, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.","mla":"Brázdil, Tomáš, et al. Stability in Graphs and Games. Vol. 59, 10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPIcs.CONCUR.2016.10.","ieee":"T. Brázdil, V. Forejt, A. Kučera, and P. Novotný, “Stability in graphs and games,” presented at the CONCUR: Concurrency Theory, Quebec City, Canada, 2016, vol. 59.","apa":"Brázdil, T., Forejt, V., Kučera, A., & Novotný, P. (2016). Stability in graphs and games (Vol. 59). Presented at the CONCUR: Concurrency Theory, Quebec City, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2016.10","ista":"Brázdil T, Forejt V, Kučera A, Novotný P. 2016. Stability in graphs and games. CONCUR: Concurrency Theory, LIPIcs, vol. 59, 10.","ama":"Brázdil T, Forejt V, Kučera A, Novotný P. Stability in graphs and games. In: Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPIcs.CONCUR.2016.10"},"date_published":"2016-08-01T00:00:00Z"},{"type":"conference","abstract":[{"text":"DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. Copyright ","lang":"eng"}],"ec_funded":1,"publist_id":"5946","title":"Indefinite-horizon reachability in Goal-DEC-POMDPs","status":"public","publication_status":"published","department":[{"_id":"KrCh"}],"publisher":"AAAI Press","_id":"1324","year":"2016","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T11:51:22Z","date_updated":"2021-01-12T06:49:53Z","oa_version":"None","volume":"2016-January","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik","full_name":"Chmelik, Martin"}],"scopus_import":1,"day":"01","month":"01","quality_controlled":"1","page":"88 - 96","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"}],"publication":"Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling","citation":{"ama":"Chatterjee K, Chmelik M. Indefinite-horizon reachability in Goal-DEC-POMDPs. In: Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling. Vol 2016-January. AAAI Press; 2016:88-96.","ista":"Chatterjee K, Chmelik M. 2016. Indefinite-horizon reachability in Goal-DEC-POMDPs. Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling. ICAPS: International Conference on Automated Planning and Scheduling vol. 2016–January, 88–96.","apa":"Chatterjee, K., & Chmelik, M. (2016). Indefinite-horizon reachability in Goal-DEC-POMDPs. In Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling (Vol. 2016–January, pp. 88–96). London, United Kingdom: AAAI Press.","ieee":"K. Chatterjee and M. Chmelik, “Indefinite-horizon reachability in Goal-DEC-POMDPs,” in Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, London, United Kingdom, 2016, vol. 2016–January, pp. 88–96.","mla":"Chatterjee, Krishnendu, and Martin Chmelik. “Indefinite-Horizon Reachability in Goal-DEC-POMDPs.” Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, vol. 2016–January, AAAI Press, 2016, pp. 88–96.","short":"K. Chatterjee, M. Chmelik, in:, Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, AAAI Press, 2016, pp. 88–96.","chicago":"Chatterjee, Krishnendu, and Martin Chmelik. “Indefinite-Horizon Reachability in Goal-DEC-POMDPs.” In Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling, 2016–January:88–96. AAAI Press, 2016."},"main_file_link":[{"url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/12999"}],"language":[{"iso":"eng"}],"conference":{"end_date":"2016-06-17","location":"London, United Kingdom","start_date":"2016-06-12","name":"ICAPS: International Conference on Automated Planning and Scheduling"},"date_published":"2016-01-01T00:00:00Z"},{"scopus_import":1,"month":"01","day":"01","publication":"Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems","citation":{"apa":"Brázdil, T., Chatterjee, K., Chmelik, M., Gupta, A., & Novotný, P. (2016). Stochastic shortest path with energy constraints in POMDPs. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (pp. 1465–1466). Singapore: ACM.","ieee":"T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, and P. Novotný, “Stochastic shortest path with energy constraints in POMDPs,” in Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, Singapore, 2016, pp. 1465–1466.","ista":"Brázdil T, Chatterjee K, Chmelik M, Gupta A, Novotný P. 2016. Stochastic shortest path with energy constraints in POMDPs. Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems. AAMAS: Autonomous Agents & Multiagent Systems, 1465–1466.","ama":"Brázdil T, Chatterjee K, Chmelik M, Gupta A, Novotný P. Stochastic shortest path with energy constraints in POMDPs. In: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems. ACM; 2016:1465-1466.","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Anchit Gupta, and Petr Novotný. “Stochastic Shortest Path with Energy Constraints in POMDPs.” In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, 1465–66. ACM, 2016.","short":"T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, P. Novotný, in:, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–1466.","mla":"Brázdil, Tomáš, et al. “Stochastic Shortest Path with Energy Constraints in POMDPs.” Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–66."},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.07565"}],"oa":1,"quality_controlled":"1","page":"1465 - 1466","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}],"conference":{"name":"AAMAS: Autonomous Agents & Multiagent Systems","start_date":"2016-05-09","location":"Singapore","end_date":"2016-05-13"},"date_published":"2016-01-01T00:00:00Z","language":[{"iso":"eng"}],"type":"conference","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels. ","lang":"eng"}],"ec_funded":1,"publist_id":"5942","_id":"1327","year":"2016","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Stochastic shortest path with energy constraints in POMDPs","publication_status":"published","publisher":"ACM","department":[{"_id":"KrCh"}],"author":[{"last_name":"Brázdil","first_name":"Tomáš","full_name":"Brázdil, Tomáš"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","first_name":"Martin"},{"first_name":"Anchit","last_name":"Gupta","full_name":"Gupta, Anchit"},{"full_name":"Novotny, Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","first_name":"Petr","last_name":"Novotny"}],"date_updated":"2021-01-12T06:49:54Z","date_created":"2018-12-11T11:51:23Z","oa_version":"Preprint"},{"language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-46520-3_3","conference":{"start_date":"2016-10-17","location":"Chiba, Japan","end_date":"2016-10-20","name":"ATVA: Automated Technology for Verification and Analysis"},"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1607.00678","open_access":"1"}],"oa":1,"month":"09","volume":9938,"date_updated":"2021-01-12T06:49:53Z","date_created":"2018-12-11T11:51:23Z","author":[{"full_name":"Brázdil, Tomáš","last_name":"Brázdil","first_name":"Tomáš"},{"last_name":"Kučera","first_name":"Antonín","full_name":"Kučera, Antonín"},{"last_name":"Novotny","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","full_name":"Novotny, Petr"}],"publisher":"Springer","department":[{"_id":"KrCh"}],"publication_status":"published","year":"2016","acknowledgement":"The research was funded by the Czech Science Foundation Grant No. P202/12/G061 and by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].","publist_id":"5943","ec_funded":1,"date_published":"2016-09-22T00:00:00Z","page":"32 - 49","citation":{"chicago":"Brázdil, Tomáš, Antonín Kučera, and Petr Novotný. “Optimizing the Expected Mean Payoff in Energy Markov Decision Processes,” 9938:32–49. Springer, 2016. https://doi.org/10.1007/978-3-319-46520-3_3.","mla":"Brázdil, Tomáš, et al. Optimizing the Expected Mean Payoff in Energy Markov Decision Processes. Vol. 9938, Springer, 2016, pp. 32–49, doi:10.1007/978-3-319-46520-3_3.","short":"T. Brázdil, A. Kučera, P. Novotný, in:, Springer, 2016, pp. 32–49.","ista":"Brázdil T, Kučera A, Novotný P. 2016. Optimizing the expected mean payoff in Energy Markov Decision Processes. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 9938, 32–49.","apa":"Brázdil, T., Kučera, A., & Novotný, P. (2016). Optimizing the expected mean payoff in Energy Markov Decision Processes (Vol. 9938, pp. 32–49). Presented at the ATVA: Automated Technology for Verification and Analysis, Chiba, Japan: Springer. https://doi.org/10.1007/978-3-319-46520-3_3","ieee":"T. Brázdil, A. Kučera, and P. Novotný, “Optimizing the expected mean payoff in Energy Markov Decision Processes,” presented at the ATVA: Automated Technology for Verification and Analysis, Chiba, Japan, 2016, vol. 9938, pp. 32–49.","ama":"Brázdil T, Kučera A, Novotný P. Optimizing the expected mean payoff in Energy Markov Decision Processes. In: Vol 9938. Springer; 2016:32-49. doi:10.1007/978-3-319-46520-3_3"},"day":"22","scopus_import":1,"oa_version":"Preprint","intvolume":" 9938","status":"public","title":"Optimizing the expected mean payoff in Energy Markov Decision Processes","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1326","abstract":[{"text":"Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff. ","lang":"eng"}],"alternative_title":["LNCS"],"type":"conference"},{"citation":{"ista":"Milinski M, Hilbe C, Semmann D, Sommerfeld R, Marotzke J. 2016. Humans choose representatives who enforce cooperation in social dilemmas through extortion. Nature Communications. 7, 10915.","apa":"Milinski, M., Hilbe, C., Semmann, D., Sommerfeld, R., & Marotzke, J. (2016). Humans choose representatives who enforce cooperation in social dilemmas through extortion. Nature Communications. Nature Publishing Group. https://doi.org/10.1038/ncomms10915","ieee":"M. Milinski, C. Hilbe, D. Semmann, R. Sommerfeld, and J. Marotzke, “Humans choose representatives who enforce cooperation in social dilemmas through extortion,” Nature Communications, vol. 7. Nature Publishing Group, 2016.","ama":"Milinski M, Hilbe C, Semmann D, Sommerfeld R, Marotzke J. Humans choose representatives who enforce cooperation in social dilemmas through extortion. Nature Communications. 2016;7. doi:10.1038/ncomms10915","chicago":"Milinski, Manfred, Christian Hilbe, Dirk Semmann, Ralf Sommerfeld, and Jochem Marotzke. “Humans Choose Representatives Who Enforce Cooperation in Social Dilemmas through Extortion.” Nature Communications. Nature Publishing Group, 2016. https://doi.org/10.1038/ncomms10915.","mla":"Milinski, Manfred, et al. “Humans Choose Representatives Who Enforce Cooperation in Social Dilemmas through Extortion.” Nature Communications, vol. 7, 10915, Nature Publishing Group, 2016, doi:10.1038/ncomms10915.","short":"M. Milinski, C. Hilbe, D. Semmann, R. Sommerfeld, J. Marotzke, Nature Communications 7 (2016)."},"publication":"Nature Communications","date_published":"2016-03-07T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"07","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1333","intvolume":" 7","status":"public","title":"Humans choose representatives who enforce cooperation in social dilemmas through extortion","ddc":["519","530","599"],"pubrep_id":"661","file":[{"access_level":"open_access","file_name":"IST-2016-661-v1+1_ncomms10915.pdf","creator":"system","file_size":1432577,"content_type":"application/pdf","file_id":"4834","relation":"main_file","checksum":"9ea0d7ce59a555a1cb8353d5559407cb","date_created":"2018-12-12T10:10:44Z","date_updated":"2020-07-14T12:44:44Z"}],"oa_version":"Published Version","type":"journal_article","abstract":[{"lang":"eng","text":"Social dilemmas force players to balance between personal and collective gain. In many dilemmas, such as elected governments negotiating climate-change mitigation measures, the decisions are made not by individual players but by their representatives. However, the behaviour of representatives in social dilemmas has not been investigated experimentally. Here inspired by the negotiations for greenhouse-gas emissions reductions, we experimentally study a collective-risk social dilemma that involves representatives deciding on behalf of their fellow group members. Representatives can be re-elected or voted out after each consecutive collective-risk game. Selfish players are preferentially elected and are hence found most frequently in the "representatives" treatment. Across all treatments, we identify the selfish players as extortioners. As predicted by our mathematical model, their steadfast strategies enforce cooperation from fair players who finally compensate almost completely the deficit caused by the extortionate co-players. Everybody gains, but the extortionate representatives and their groups gain the most."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","doi":"10.1038/ncomms10915","language":[{"iso":"eng"}],"month":"03","acknowledgement":"We thank the students for participation; H.-J. Krambeck for writing the software for the game; H. Arndt, T. Bakker, L. Becks, H. Brendelberger, S. Dobler and T. Reusch for support; and the Max Planck Society for the Advancement of Science for funding.","year":"2016","department":[{"_id":"KrCh"}],"publisher":"Nature Publishing Group","publication_status":"published","author":[{"full_name":"Milinski, Manfred","first_name":"Manfred","last_name":"Milinski"},{"full_name":"Hilbe, Christian","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5116-955X","first_name":"Christian","last_name":"Hilbe"},{"first_name":"Dirk","last_name":"Semmann","full_name":"Semmann, Dirk"},{"full_name":"Sommerfeld, Ralf","first_name":"Ralf","last_name":"Sommerfeld"},{"first_name":"Jochem","last_name":"Marotzke","full_name":"Marotzke, Jochem"}],"volume":7,"date_created":"2018-12-11T11:51:25Z","date_updated":"2021-01-12T06:49:57Z","article_number":"10915","publist_id":"5935","file_date_updated":"2020-07-14T12:44:44Z"},{"scopus_import":1,"day":"31","page":"23 - 38","citation":{"ama":"Chatterjee K, Henzinger TA, Otop J. Quantitative monitor automata. In: Vol 9837. Springer; 2016:23-38. doi:10.1007/978-3-662-53413-7_2","ista":"Chatterjee K, Henzinger TA, Otop J. 2016. Quantitative monitor automata. SAS: Static Analysis Symposium, LNCS, vol. 9837, 23–38.","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.","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2016). Quantitative monitor automata (Vol. 9837, pp. 23–38). Presented at the SAS: Static Analysis Symposium, Edinburgh, United Kingdom: Springer. https://doi.org/10.1007/978-3-662-53413-7_2","mla":"Chatterjee, Krishnendu, et al. Quantitative Monitor Automata. Vol. 9837, Springer, 2016, pp. 23–38, doi:10.1007/978-3-662-53413-7_2.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Springer, 2016, pp. 23–38.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Quantitative Monitor Automata,” 9837:23–38. Springer, 2016. https://doi.org/10.1007/978-3-662-53413-7_2."},"date_published":"2016-08-31T00:00:00Z","alternative_title":["LNCS"],"type":"conference","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."}],"status":"public","title":"Quantitative monitor automata","intvolume":" 9837","_id":"1335","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","month":"08","quality_controlled":"1","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"The Wittgenstein Prize"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"}],"main_file_link":[{"url":"https://arxiv.org/abs/1604.06764","open_access":"1"}],"oa":1,"language":[{"iso":"eng"}],"conference":{"name":"SAS: Static Analysis Symposium","location":"Edinburgh, United Kingdom","start_date":"2016-09-08","end_date":"2016-09-10"},"doi":"10.1007/978-3-662-53413-7_2","publist_id":"5932","ec_funded":1,"publication_status":"published","publisher":"Springer","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"year":"2016","date_updated":"2021-01-12T06:49:58Z","date_created":"2018-12-11T11:51:26Z","volume":9837,"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"},{"first_name":"Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan"}]},{"day":"01","scopus_import":1,"date_published":"2016-09-01T00:00:00Z","page":"64 - 76","citation":{"ama":"Hansen K, Ibsen-Jensen R, Koucký M. The big match in small space. In: Vol 9928. Springer; 2016:64-76. doi:10.1007/978-3-662-53354-3_6","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.","apa":"Hansen, K., Ibsen-Jensen, R., & 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. https://doi.org/10.1007/978-3-662-53354-3_6","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.","short":"K. Hansen, R. Ibsen-Jensen, M. Koucký, in:, Springer, 2016, pp. 64–76.","mla":"Hansen, Kristoffer, et al. The Big Match in Small Space. Vol. 9928, Springer, 2016, pp. 64–76, doi:10.1007/978-3-662-53354-3_6.","chicago":"Hansen, Kristoffer, Rasmus Ibsen-Jensen, and Michal Koucký. “The Big Match in Small Space,” 9928:64–76. Springer, 2016. https://doi.org/10.1007/978-3-662-53354-3_6."},"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]."}],"alternative_title":["LNCS"],"type":"conference","oa_version":"Preprint","intvolume":" 9928","title":"The big match in small space","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1340","month":"09","language":[{"iso":"eng"}],"doi":"10.1007/978-3-662-53354-3_6","conference":{"name":"SAGT: Symposium on Algorithmic Game Theory","end_date":"2016-09-21","start_date":"2016-09-19","location":"Liverpool, United Kingdom"},"project":[{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"}],"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1604.07634","open_access":"1"}],"oa":1,"publist_id":"5927","ec_funded":1,"volume":9928,"date_created":"2018-12-11T11:51:28Z","date_updated":"2021-01-12T06:50:00Z","author":[{"full_name":"Hansen, Kristoffer","last_name":"Hansen","first_name":"Kristoffer"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus"},{"last_name":"Koucký","first_name":"Michal","full_name":"Koucký, Michal"}],"department":[{"_id":"KrCh"}],"publisher":"Springer","publication_status":"published","year":"2016"},{"_id":"1380","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","year":"2016","publication_status":"published","status":"public","title":"On the complexity of the orbit problem","publisher":"ACM","department":[{"_id":"KrCh"}],"intvolume":" 63","author":[{"full_name":"Chonev, Ventsislav K","last_name":"Chonev","first_name":"Ventsislav K","id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ouaknine, Joël","first_name":"Joël","last_name":"Ouaknine"},{"first_name":"James","last_name":"Worrell","full_name":"Worrell, James"}],"date_created":"2018-12-11T11:51:41Z","date_updated":"2021-01-12T06:50:17Z","volume":63,"oa_version":"Preprint","article_number":"23","type":"journal_article","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."}],"issue":"3","publist_id":"5831","publication":"Journal of the ACM","oa":1,"citation":{"chicago":"Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On the Complexity of the Orbit Problem.” Journal of the ACM. ACM, 2016. https://doi.org/10.1145/2857050.","mla":"Chonev, Ventsislav K., et al. “On the Complexity of the Orbit Problem.” Journal of the ACM, vol. 63, no. 3, 23, ACM, 2016, doi:10.1145/2857050.","short":"V.K. Chonev, J. Ouaknine, J. Worrell, Journal of the ACM 63 (2016).","ista":"Chonev VK, Ouaknine J, Worrell J. 2016. On the complexity of the orbit problem. Journal of the ACM. 63(3), 23.","ieee":"V. K. Chonev, J. Ouaknine, and J. Worrell, “On the complexity of the orbit problem,” Journal of the ACM, vol. 63, no. 3. ACM, 2016.","apa":"Chonev, V. K., Ouaknine, J., & Worrell, J. (2016). On the complexity of the orbit problem. Journal of the ACM. ACM. https://doi.org/10.1145/2857050","ama":"Chonev VK, Ouaknine J, Worrell J. On the complexity of the orbit problem. Journal of the ACM. 2016;63(3). doi:10.1145/2857050"},"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1303.2981"}],"quality_controlled":"1","doi":"10.1145/2857050","date_published":"2016-06-01T00:00:00Z","language":[{"iso":"eng"}],"scopus_import":1,"day":"01","month":"06"},{"scopus_import":1,"month":"07","day":"05","project":[{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"}],"page":"515 - 524","quality_controlled":"1","citation":{"apa":"Chonev, V. K., Ouaknine, J., & Worrell, J. (2016). On recurrent reachability for continuous linear dynamical systems. In LICS ’16 (pp. 515–524). New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2934548","ieee":"V. K. Chonev, J. Ouaknine, and J. Worrell, “On recurrent reachability for continuous linear dynamical systems,” in LICS ’16, 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.","ama":"Chonev VK, Ouaknine J, Worrell J. On recurrent reachability for continuous linear dynamical systems. In: LICS ’16. IEEE; 2016:515-524. doi:10.1145/2933575.2934548","chicago":"Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On Recurrent Reachability for Continuous Linear Dynamical Systems.” In LICS ’16, 515–24. IEEE, 2016. https://doi.org/10.1145/2933575.2934548.","short":"V.K. Chonev, J. Ouaknine, J. Worrell, in:, LICS ’16, IEEE, 2016, pp. 515–524.","mla":"Chonev, Ventsislav K., et al. “On Recurrent Reachability for Continuous Linear Dynamical Systems.” LICS ’16, IEEE, 2016, pp. 515–24, doi:10.1145/2933575.2934548."},"main_file_link":[{"url":"https://arxiv.org/abs/1507.03632","open_access":"1"}],"oa":1,"publication":"LICS '16","language":[{"iso":"eng"}],"doi":"10.1145/2933575.2934548","date_published":"2016-07-05T00:00:00Z","conference":{"name":"LICS: Logic in Computer Science","start_date":"2018-07-05","location":"New York, NY, USA","end_date":"2018-07-08"},"type":"conference","ec_funded":1,"publist_id":"5820","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 --> 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"}],"department":[{"_id":"KrCh"}],"publisher":"IEEE","publication_status":"published","status":"public","title":"On recurrent reachability for continuous linear dynamical systems","year":"2016","_id":"1389","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","date_created":"2018-12-11T11:51:44Z","date_updated":"2021-01-12T06:50:20Z","author":[{"id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87","first_name":"Ventsislav K","last_name":"Chonev","full_name":"Chonev, Ventsislav K"},{"full_name":"Ouaknine, Joël","first_name":"Joël","last_name":"Ouaknine"},{"first_name":"James","last_name":"Worrell","full_name":"Worrell, James"}]},{"publist_id":"5776","file_date_updated":"2020-07-14T12:44:53Z","article_number":"160036","author":[{"full_name":"Chakra, Maria","last_name":"Chakra","first_name":"Maria"},{"full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","last_name":"Hilbe","first_name":"Christian"},{"full_name":"Traulsen, Arne","last_name":"Traulsen","first_name":"Arne"}],"volume":3,"date_updated":"2021-01-12T06:50:39Z","date_created":"2018-12-11T11:51:57Z","year":"2016","acknowledgement":"C.H. gratefully acknowledges funding by the Schrödinger scholarship of the Austrian Science Fund (FWF) J3475.","department":[{"_id":"KrCh"}],"publisher":"Royal Society, The","publication_status":"published","month":"05","doi":"10.1098/rsos.160036","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","issue":"5","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"}],"type":"journal_article","pubrep_id":"589","oa_version":"Published Version","file":[{"file_name":"IST-2016-589-v1+1_160036.full.pdf","access_level":"open_access","content_type":"application/pdf","file_size":937002,"creator":"system","relation":"main_file","file_id":"5104","date_updated":"2020-07-14T12:44:53Z","date_created":"2018-12-12T10:14:49Z","checksum":"bf84211b31fe87451e738ba301d729c3"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1426","intvolume":" 3","status":"public","ddc":["000"],"title":"Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites","has_accepted_license":"1","day":"01","scopus_import":1,"date_published":"2016-05-01T00:00:00Z","citation":{"mla":"Chakra, Maria, et al. “Coevolutionary Interactions between Farmers and Mafia Induce Host Acceptance of Avian Brood Parasites.” Royal Society Open Science, vol. 3, no. 5, 160036, Royal Society, The, 2016, doi:10.1098/rsos.160036.","short":"M. Chakra, C. Hilbe, A. Traulsen, Royal Society Open Science 3 (2016).","chicago":"Chakra, Maria, Christian Hilbe, and Arne Traulsen. “Coevolutionary Interactions between Farmers and Mafia Induce Host Acceptance of Avian Brood Parasites.” Royal Society Open Science. Royal Society, The, 2016. https://doi.org/10.1098/rsos.160036.","ama":"Chakra M, Hilbe C, Traulsen A. Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites. Royal Society Open Science. 2016;3(5). doi:10.1098/rsos.160036","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,” Royal Society Open Science, vol. 3, no. 5. Royal Society, The, 2016.","apa":"Chakra, M., Hilbe, C., & Traulsen, A. (2016). Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites. Royal Society Open Science. Royal Society, The. https://doi.org/10.1098/rsos.160036"},"publication":"Royal Society Open Science"}]