[{"publisher":"Springer","quality_controlled":"1","oa":1,"day":"31","year":"2016","doi":"10.1007/978-3-662-53413-7_2","date_published":"2016-08-31T00:00:00Z","date_created":"2018-12-11T11:51:26Z","page":"23 - 38","project":[{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","name":"The Wittgenstein Prize"},{"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"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Henzinger TA, Otop J. 2016. Quantitative monitor automata. SAS: Static Analysis Symposium, LNCS, vol. 9837, 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.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Springer, 2016, pp. 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","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","mla":"Chatterjee, Krishnendu, et al. Quantitative Monitor Automata. Vol. 9837, Springer, 2016, pp. 23–38, doi:10.1007/978-3-662-53413-7_2."},"title":"Quantitative monitor automata","author":[{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan"}],"publist_id":"5932","oa_version":"Preprint","abstract":[{"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.","lang":"eng"}],"month":"08","intvolume":" 9837","alternative_title":["LNCS"],"scopus_import":1,"main_file_link":[{"url":"https://arxiv.org/abs/1604.06764","open_access":"1"}],"language":[{"iso":"eng"}],"publication_status":"published","volume":9837,"ec_funded":1,"_id":"1335","status":"public","type":"conference","conference":{"name":"SAS: Static Analysis Symposium","start_date":"2016-09-08","end_date":"2016-09-10","location":"Edinburgh, United Kingdom"},"date_updated":"2021-01-12T06:49:58Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}]},{"scopus_import":1,"alternative_title":["LNCS"],"main_file_link":[{"url":"https://arxiv.org/abs/1604.07634","open_access":"1"}],"month":"09","intvolume":" 9928","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]."}],"oa_version":"Preprint","volume":9928,"ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"type":"conference","conference":{"name":"SAGT: Symposium on Algorithmic Game Theory","location":"Liverpool, United Kingdom","end_date":"2016-09-21","start_date":"2016-09-19"},"status":"public","_id":"1340","department":[{"_id":"KrCh"}],"date_updated":"2021-01-12T06:50:00Z","quality_controlled":"1","publisher":"Springer","oa":1,"page":"64 - 76","date_published":"2016-09-01T00:00:00Z","doi":"10.1007/978-3-662-53354-3_6","date_created":"2018-12-11T11:51:28Z","year":"2016","day":"01","project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}],"author":[{"last_name":"Hansen","full_name":"Hansen, Kristoffer","first_name":"Kristoffer"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"},{"last_name":"Koucký","full_name":"Koucký, Michal","first_name":"Michal"}],"publist_id":"5927","title":"The big match in small space","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","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","short":"K. Hansen, R. Ibsen-Jensen, M. Koucký, in:, Springer, 2016, pp. 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. The Big Match in Small Space. Vol. 9928, Springer, 2016, pp. 64–76, doi: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.","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."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},{"publist_id":"5831","author":[{"full_name":"Chonev, Ventsislav K","last_name":"Chonev","first_name":"Ventsislav K","id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Ouaknine","full_name":"Ouaknine, Joël","first_name":"Joël"},{"first_name":"James","last_name":"Worrell","full_name":"Worrell, James"}],"title":"On the complexity of the orbit problem","department":[{"_id":"KrCh"}],"date_updated":"2021-01-12T06:50:17Z","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.","ista":"Chonev VK, Ouaknine J, Worrell J. 2016. On the complexity of the orbit problem. Journal of the ACM. 63(3), 23.","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).","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"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","type":"journal_article","status":"public","_id":"1380","article_number":"23","date_published":"2016-06-01T00:00:00Z","issue":"3","doi":"10.1145/2857050","volume":63,"date_created":"2018-12-11T11:51:41Z","year":"2016","publication_status":"published","day":"01","publication":"Journal of the ACM","language":[{"iso":"eng"}],"publisher":"ACM","quality_controlled":"1","scopus_import":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1303.2981"}],"oa":1,"month":"06","intvolume":" 63","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."}],"oa_version":"Preprint"},{"year":"2016","publication_status":"published","language":[{"iso":"eng"}],"publication":"LICS '16","day":"05","page":"515 - 524","ec_funded":1,"date_created":"2018-12-11T11:51:44Z","date_published":"2016-07-05T00:00:00Z","doi":"10.1145/2933575.2934548","abstract":[{"lang":"eng","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."}],"oa_version":"Preprint","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1507.03632","open_access":"1"}],"publisher":"IEEE","scopus_import":1,"quality_controlled":"1","month":"07","date_updated":"2021-01-12T06:50:20Z","citation":{"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.","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","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.","short":"V.K. Chonev, J. Ouaknine, J. Worrell, in:, LICS ’16, IEEE, 2016, pp. 515–524.","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.","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."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87","first_name":"Ventsislav K","last_name":"Chonev","full_name":"Chonev, Ventsislav K"},{"full_name":"Ouaknine, Joël","last_name":"Ouaknine","first_name":"Joël"},{"last_name":"Worrell","full_name":"Worrell, James","first_name":"James"}],"publist_id":"5820","department":[{"_id":"KrCh"}],"title":"On recurrent reachability for continuous linear dynamical systems","_id":"1389","conference":{"location":"New York, NY, USA","end_date":"2018-07-08","start_date":"2018-07-05","name":"LICS: Logic in Computer Science"},"type":"conference","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"}],"status":"public"},{"date_updated":"2021-01-12T06:50:39Z","ddc":["000"],"file_date_updated":"2020-07-14T12:44:53Z","department":[{"_id":"KrCh"}],"_id":"1426","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","pubrep_id":"589","publication_status":"published","file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"bf84211b31fe87451e738ba301d729c3","file_id":"5104","creator":"system","file_size":937002,"date_updated":"2020-07-14T12:44:53Z","file_name":"IST-2016-589-v1+1_160036.full.pdf","date_created":"2018-12-12T10:14:49Z"}],"language":[{"iso":"eng"}],"issue":"5","volume":3,"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"}],"oa_version":"Published Version","scopus_import":1,"month":"05","intvolume":" 3","citation":{"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.","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.","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","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","short":"M. Chakra, C. Hilbe, A. Traulsen, Royal Society Open Science 3 (2016).","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.","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."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"5776","author":[{"first_name":"Maria","full_name":"Chakra, Maria","last_name":"Chakra"},{"full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","last_name":"Hilbe","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","first_name":"Christian"},{"full_name":"Traulsen, Arne","last_name":"Traulsen","first_name":"Arne"}],"title":"Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites","article_number":"160036","has_accepted_license":"1","year":"2016","day":"01","publication":"Royal Society Open Science","date_published":"2016-05-01T00:00:00Z","doi":"10.1098/rsos.160036","date_created":"2018-12-11T11:51:57Z","acknowledgement":"C.H. gratefully acknowledges funding by the Schrödinger scholarship of the Austrian Science Fund (FWF) J3475.","quality_controlled":"1","publisher":"Royal Society, The","oa":1}]