[{"publication_identifier":{"issn":["18688969"],"isbn":["9783959771603"]},"month":"08","doi":"10.4230/LIPIcs.CONCUR.2020.23","conference":{"start_date":"2020-09-01","location":"Virtual","end_date":"2020-09-04","name":"CONCUR: Conference on Concurrency Theory"},"language":[{"iso":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","short":"CC BY (3.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2007.08917"]},"oa":1,"project":[{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23"},{"name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"quality_controlled":"1","file_date_updated":"2020-10-05T14:04:25Z","license":"https://creativecommons.org/licenses/by/3.0/","article_number":"23","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Otop, Jan","first_name":"Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"volume":171,"date_created":"2020-10-04T22:01:36Z","date_updated":"2021-01-12T08:20:15Z","year":"2020","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication_status":"published","article_processing_charge":"No","has_accepted_license":"1","day":"06","scopus_import":"1","date_published":"2020-08-06T00:00:00Z","citation":{"ama":"Chatterjee K, Henzinger TA, Otop J. Multi-dimensional long-run average problems for vector addition systems with states. In: 31st International Conference on Concurrency Theory. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.CONCUR.2020.23","ista":"Chatterjee K, Henzinger TA, Otop J. 2020. Multi-dimensional long-run average problems for vector addition systems with states. 31st International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 171, 23.","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2020). Multi-dimensional long-run average problems for vector addition systems with states. In 31st International Conference on Concurrency Theory (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2020.23","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Multi-dimensional long-run average problems for vector addition systems with states,” in 31st International Conference on Concurrency Theory, Virtual, 2020, vol. 171.","mla":"Chatterjee, Krishnendu, et al. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” 31st International Conference on Concurrency Theory, vol. 171, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.CONCUR.2020.23.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” In 31st International Conference on Concurrency Theory, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.CONCUR.2020.23."},"publication":"31st International Conference on Concurrency Theory","abstract":[{"lang":"eng","text":"A vector addition system with states (VASS) consists of a finite set of states and counters. A transition changes the current state to the next state, and every counter is either incremented, or decremented, or left unchanged. A state and value for each counter is a configuration; and a computation is an infinite sequence of configurations with transitions between successive configurations. A probabilistic VASS consists of a VASS along with a probability distribution over the transitions for each state. Qualitative properties such as state and configuration reachability have been widely studied for VASS. In this work we consider multi-dimensional long-run average objectives for VASS and probabilistic VASS. For a counter, the cost of a configuration is the value of the counter; and the long-run average value of a computation for the counter is the long-run average of the costs of the configurations in the computation. The multi-dimensional long-run average problem given a VASS and a threshold value for each counter, asks whether there is a computation such that for each counter the long-run average value for the counter does not exceed the respective threshold. For probabilistic VASS, instead of the existence of a computation, we consider whether the expected long-run average value for each counter does not exceed the respective threshold. Our main results are as follows: we show that the multi-dimensional long-run average problem (a) is NP-complete for integer-valued VASS; (b) is undecidable for natural-valued VASS (i.e., nonnegative counters); and (c) can be solved in polynomial time for probabilistic integer-valued VASS, and probabilistic natural-valued VASS when all computations are non-terminating."}],"type":"conference","alternative_title":["LIPIcs"],"file":[{"date_created":"2020-10-05T14:04:25Z","date_updated":"2020-10-05T14:04:25Z","success":1,"checksum":"5039752f644c4b72b9361d21a5e31baf","file_id":"8610","relation":"main_file","creator":"dernst","content_type":"application/pdf","file_size":601231,"file_name":"2020_LIPIcsCONCUR_Chatterjee.pdf","access_level":"open_access"}],"oa_version":"Published Version","_id":"8600","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 171","ddc":["000"],"status":"public","title":"Multi-dimensional long-run average problems for vector addition systems with states"},{"month":"08","publication_identifier":{"issn":["18688969"],"isbn":["9783959771603"]},"quality_controlled":"1","project":[{"call_identifier":"FWF","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","short":"CC BY (3.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"conference":{"name":"CONCUR: Conference on Concurrency Theory","start_date":"2020-09-01","location":"Virtual","end_date":"2020-09-04"},"doi":"10.4230/LIPIcs.CONCUR.2020.2","article_number":"2","file_date_updated":"2020-10-05T14:13:19Z","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"ToHe"}],"year":"2020","acknowledgement":"We would like to thank all our collaborators Milad Aghajohari, Ventsislav Chonev, Rasmus Ibsen-Jensen, Ismäel Jecker, Petr Novotný, Josef Tkadlec, and Ðorđe Žikelić; we hope the collaboration was as fun and meaningful for you as it was for us.","date_created":"2020-10-04T22:01:36Z","date_updated":"2021-01-12T08:20:13Z","volume":171,"author":[{"id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5588-8287","first_name":"Guy","last_name":"Avni","full_name":"Avni, Guy"},{"full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"}],"scopus_import":"1","day":"06","article_processing_charge":"No","has_accepted_license":"1","publication":"31st International Conference on Concurrency Theory","citation":{"ama":"Avni G, Henzinger TA. A survey of bidding games on graphs. In: 31st International Conference on Concurrency Theory. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.CONCUR.2020.2","ista":"Avni G, Henzinger TA. 2020. A survey of bidding games on graphs. 31st International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 171, 2.","apa":"Avni, G., & Henzinger, T. A. (2020). A survey of bidding games on graphs. In 31st International Conference on Concurrency Theory (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2020.2","ieee":"G. Avni and T. A. Henzinger, “A survey of bidding games on graphs,” in 31st International Conference on Concurrency Theory, Virtual, 2020, vol. 171.","mla":"Avni, Guy, and Thomas A. Henzinger. “A Survey of Bidding Games on Graphs.” 31st International Conference on Concurrency Theory, vol. 171, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.CONCUR.2020.2.","short":"G. Avni, T.A. Henzinger, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Avni, Guy, and Thomas A Henzinger. “A Survey of Bidding Games on Graphs.” In 31st International Conference on Concurrency Theory, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.CONCUR.2020.2."},"date_published":"2020-08-06T00:00:00Z","alternative_title":["LIPIcs"],"type":"conference","abstract":[{"text":"A graph game is a two-player zero-sum game in which the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. In bidding games, both players have budgets, and in each turn, we hold an \"auction\" (bidding) to determine which player moves the token. In this survey, we consider several bidding mechanisms and study their effect on the properties of the game. Specifically, bidding games, and in particular bidding games of infinite duration, have an intriguing equivalence with random-turn games in which in each turn, the player who moves is chosen randomly. We show how minor changes in the bidding mechanism lead to unexpected differences in the equivalence with random-turn games.","lang":"eng"}],"title":"A survey of bidding games on graphs","status":"public","ddc":["000"],"intvolume":" 171","_id":"8599","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"2020_LIPIcsCONCUR_Avni.pdf","creator":"dernst","file_size":868510,"content_type":"application/pdf","file_id":"8611","relation":"main_file","success":1,"checksum":"8f33b098e73724e0ac817f764d8e1a2d","date_updated":"2020-10-05T14:13:19Z","date_created":"2020-10-05T14:13:19Z"}]}]