[{"author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"}],"file_date_updated":"2020-07-14T12:46:45Z","department":[{"_id":"KrCh"}],"title":"The complexity of ergodic games","date_updated":"2023-02-23T10:30:55Z","citation":{"mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-127-v1-1.","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2013). The complexity of ergodic games. IST Austria. https://doi.org/10.15479/AT:IST-2013-127-v1-1","ama":"Chatterjee K, Ibsen-Jensen R. The Complexity of Ergodic Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-127-v1-1","short":"K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria, 2013.","ieee":"K. Chatterjee and R. Ibsen-Jensen, The complexity of ergodic games. IST Austria, 2013.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-127-v1-1.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000","005"],"type":"technical_report","pubrep_id":"127","status":"public","_id":"5404","page":"29","date_created":"2018-12-12T11:39:08Z","date_published":"2013-07-03T00:00:00Z","doi":"10.15479/AT:IST-2013-127-v1-1","related_material":{"record":[{"relation":"later_version","status":"public","id":"2162"}]},"year":"2013","publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","language":[{"iso":"eng"}],"day":"03","file":[{"date_created":"2018-12-12T11:53:35Z","file_name":"IST-2013-127-v1+1_ergodic.pdf","creator":"system","date_updated":"2020-07-14T12:46:45Z","file_size":517275,"file_id":"5496","checksum":"79ee5e677a82611ce06e0360c69d494a","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"oa":1,"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","month":"07","abstract":[{"lang":"eng","text":"We study finite-state two-player (zero-sum) concurrent mean-payoff games played on a graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound 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); (2) the approximation problem lie in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP and coNP is the long-standing best known bound). We show that the exact value can be expressed in the existential theory of the reals, and also establish square-root sum hardness for a related class of games."}],"oa_version":"Published Version"},{"type":"technical_report","pubrep_id":"128","status":"public","_id":"5405","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Doyen","full_name":"Doyen, Laurent","first_name":"Laurent"},{"first_name":"Hugo","full_name":"Gimbert, Hugo","last_name":"Gimbert"},{"first_name":"Youssouf","last_name":"Oualhadj","full_name":"Oualhadj, Youssouf"}],"department":[{"_id":"KrCh"}],"title":"Perfect-information stochastic mean-payoff parity games","file_date_updated":"2020-07-14T12:46:45Z","date_updated":"2023-02-23T10:33:08Z","citation":{"ista":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2013. Perfect-information stochastic mean-payoff parity games, IST Austria, 22p.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. Perfect-Information Stochastic Mean-Payoff Parity Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-128-v1-1.","ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, Perfect-information stochastic mean-payoff parity games. IST Austria, 2013.","short":"K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, Perfect-Information Stochastic Mean-Payoff Parity Games, IST Austria, 2013.","apa":"Chatterjee, K., Doyen, L., Gimbert, H., & Oualhadj, Y. (2013). Perfect-information stochastic mean-payoff parity games. IST Austria. https://doi.org/10.15479/AT:IST-2013-128-v1-1","ama":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. Perfect-Information Stochastic Mean-Payoff Parity Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-128-v1-1","mla":"Chatterjee, Krishnendu, et al. Perfect-Information Stochastic Mean-Payoff Parity Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-128-v1-1."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000","005","510"],"oa":1,"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","month":"07","abstract":[{"lang":"eng","text":"The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running\r\nin time O(d · n^{2d}·MeanGame) to compute the set of almost-sure winning states from which the objective\r\ncan be ensured with probability 1, where n is the number of states of the game, d the number of priorities\r\nof the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states\r\nin 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems\r\nwith both functional requirement (given as a qualitative objective) and performance requirement (given\r\nas a quantitative objective)."}],"oa_version":"Published Version","page":"22","date_created":"2018-12-12T11:39:09Z","doi":"10.15479/AT:IST-2013-128-v1-1","date_published":"2013-07-08T00:00:00Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"2212"}]},"publication_status":"published","year":"2013","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","language":[{"iso":"eng"}],"day":"08","file":[{"file_id":"5516","checksum":"ede787a10e74e4f7db302fab8f12f3ca","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"IST-2013-128-v1+1_full_stoch_mpp.pdf","date_created":"2018-12-12T11:53:54Z","creator":"system","file_size":387467,"date_updated":"2020-07-14T12:46:45Z"}]},{"status":"public","pubrep_id":"144","type":"technical_report","_id":"5409","file_date_updated":"2020-07-14T12:46:46Z","department":[{"_id":"KrCh"}],"title":"Edit distance for timed automata","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Rupak","full_name":"Majumdar, Rupak","last_name":"Majumdar"}],"ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T10:33:18Z","citation":{"mla":"Chatterjee, Krishnendu, et al. Edit Distance for Timed Automata. IST Austria, 2013, doi:10.15479/AT:IST-2013-144-v1-1.","ama":"Chatterjee K, Ibsen-Jensen R, Majumdar R. Edit Distance for Timed Automata. IST Austria; 2013. doi:10.15479/AT:IST-2013-144-v1-1","apa":"Chatterjee, K., Ibsen-Jensen, R., & Majumdar, R. (2013). Edit distance for timed automata. IST Austria. https://doi.org/10.15479/AT:IST-2013-144-v1-1","short":"K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, Edit Distance for Timed Automata, IST Austria, 2013.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, Edit distance for timed automata. IST Austria, 2013.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Rupak Majumdar. Edit Distance for Timed Automata. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-144-v1-1.","ista":"Chatterjee K, Ibsen-Jensen R, Majumdar R. 2013. Edit distance for timed automata, IST Austria, 12p."},"month":"10","publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. \r\nIn this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in timestamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than delta away from the parameter, for delta>0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and we show analogous decidability results for rectangular automata."}],"doi":"10.15479/AT:IST-2013-144-v1-1","date_published":"2013-10-30T00:00:00Z","related_material":{"record":[{"relation":"later_version","id":"2216","status":"public"}]},"date_created":"2018-12-12T11:39:10Z","page":"12","day":"30","file":[{"file_size":336377,"date_updated":"2020-07-14T12:46:46Z","creator":"system","file_name":"IST-2013-144-v1+1_main.pdf","date_created":"2018-12-12T11:53:08Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"5469","checksum":"0f7633081ba8299c543322f0ad08571f"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"publication_status":"published","year":"2013"},{"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"last_name":"Otop","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis"}],"publist_id":"5835","title":"Distributed synthesis for LTL fragments","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"citation":{"ista":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis for LTL fragments. 13th International Conference on Formal Methods in Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design, 18–25.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. “Distributed Synthesis for LTL Fragments.” In 13th International Conference on Formal Methods in Computer-Aided Design, 18–25. IEEE, 2013. https://doi.org/10.1109/FMCAD.2013.6679386.","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, “Distributed synthesis for LTL fragments,” in 13th International Conference on Formal Methods in Computer-Aided Design, Portland, OR, United States, 2013, pp. 18–25.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25.","ama":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed synthesis for LTL fragments. In: 13th International Conference on Formal Methods in Computer-Aided Design. IEEE; 2013:18-25. doi:10.1109/FMCAD.2013.6679386","apa":"Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013). Distributed synthesis for LTL fragments. In 13th International Conference on Formal Methods in Computer-Aided Design (pp. 18–25). Portland, OR, United States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679386","mla":"Chatterjee, Krishnendu, et al. “Distributed Synthesis for LTL Fragments.” 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25, doi:10.1109/FMCAD.2013.6679386."},"date_updated":"2023-02-23T12:24:53Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","conference":{"end_date":"2013-10-23","location":"Portland, OR, United States","start_date":"2013-10-20","name":"FMCAD: Formal Methods in Computer-Aided Design"},"status":"public","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":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"_id":"1376","page":"18 - 25","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5406"}]},"doi":"10.1109/FMCAD.2013.6679386","date_published":"2013-12-11T00:00:00Z","date_created":"2018-12-11T11:51:40Z","ec_funded":1,"year":"2013","publication_status":"published","day":"11","language":[{"iso":"eng"}],"publication":"13th International Conference on Formal Methods in Computer-Aided Design","publisher":"IEEE","quality_controlled":"1","month":"12","abstract":[{"text":"We consider the distributed synthesis problem for temporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTL and our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3) Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.","lang":"eng"}],"oa_version":"None"},{"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis"}],"file_date_updated":"2020-07-14T12:46:45Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Distributed synthesis for LTL Fragments","date_updated":"2023-02-21T17:01:26Z","citation":{"chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. Distributed Synthesis for LTL Fragments. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-130-v1-1.","ista":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis for LTL Fragments, IST Austria, 11p.","mla":"Chatterjee, Krishnendu, et al. Distributed Synthesis for LTL Fragments. IST Austria, 2013, doi:10.15479/AT:IST-2013-130-v1-1.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, Distributed Synthesis for LTL Fragments, IST Austria, 2013.","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, Distributed synthesis for LTL Fragments. IST Austria, 2013.","apa":"Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013). Distributed synthesis for LTL Fragments. IST Austria. https://doi.org/10.15479/AT:IST-2013-130-v1-1","ama":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed Synthesis for LTL Fragments. IST Austria; 2013. doi:10.15479/AT:IST-2013-130-v1-1"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["005"],"type":"technical_report","pubrep_id":"130","status":"public","_id":"5406","page":"11","date_created":"2018-12-12T11:39:09Z","date_published":"2013-07-08T00:00:00Z","doi":"10.15479/AT:IST-2013-130-v1-1","related_material":{"record":[{"status":"public","id":"1376","relation":"later_version"}]},"publication_status":"published","year":"2013","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","language":[{"iso":"eng"}],"day":"08","file":[{"file_size":467895,"date_updated":"2020-07-14T12:46:45Z","creator":"system","file_name":"IST-2013-130-v1+1_Distributed_Synthesis.pdf","date_created":"2018-12-12T11:54:18Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"855513ebaf6f72228800c5fdb522f93c","file_id":"5540"}],"oa":1,"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","month":"07","abstract":[{"text":"We consider the distributed synthesis problem fortemporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTLand our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3)Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.","lang":"eng"}],"oa_version":"Published Version"},{"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa":1,"month":"09","abstract":[{"lang":"eng","text":"We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are \r\nEXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. "}],"oa_version":"Published Version","page":"17","related_material":{"record":[{"id":"2213","status":"public","relation":"later_version"}]},"doi":"10.15479/AT:IST-2013-141-v1-1","date_published":"2013-09-12T00:00:00Z","date_created":"2018-12-12T11:39:10Z","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"year":"2013","publication_status":"published","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"226bc791124f8d3138379778ce834e86","file_id":"5477","creator":"system","date_updated":"2020-07-14T12:46:46Z","file_size":300481,"date_created":"2018-12-12T11:53:16Z","file_name":"IST-2013-141-v1+1_main-tech-rpt.pdf"}],"day":"12","language":[{"iso":"eng"}],"type":"technical_report","status":"public","pubrep_id":"141","_id":"5408","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"},{"last_name":"Nain","full_name":"Nain, Sumit","first_name":"Sumit"},{"first_name":"Moshe","last_name":"Vardi","full_name":"Vardi, Moshe"}],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:46Z","title":"The complexity of partial-observation stochastic parity games with finite-memory strategies","date_updated":"2023-02-23T10:33:11Z","citation":{"ista":"Chatterjee K, Doyen L, Nain S, Vardi M. 2013. The complexity of partial-observation stochastic parity games with finite-memory strategies, IST Austria, 17p.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-141-v1-1.","apa":"Chatterjee, K., Doyen, L., Nain, S., & Vardi, M. (2013). The complexity of partial-observation stochastic parity games with finite-memory strategies. IST Austria. https://doi.org/10.15479/AT:IST-2013-141-v1-1","ama":"Chatterjee K, Doyen L, Nain S, Vardi M. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria; 2013. doi:10.15479/AT:IST-2013-141-v1-1","ieee":"K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, The complexity of partial-observation stochastic parity games with finite-memory strategies. IST Austria, 2013.","short":"K. Chatterjee, L. Doyen, S. Nain, M. Vardi, The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies, IST Austria, 2013.","mla":"Chatterjee, Krishnendu, et al. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria, 2013, doi:10.15479/AT:IST-2013-141-v1-1."},"ddc":["000","005"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"month":"12","oa":1,"alternative_title":["IST Austria Technical Report"],"publisher":"IST Austria","oa_version":"Published Version","abstract":[{"text":"Board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in development of mathematical and logical skills, but also in emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. \r\nOur approach generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. Also, the presence of such states for standard game variants like Tic-Tac-Toe on board size 4x4 opens up new games to be played that have not been played for ages since the default start state is heavily biased. ","lang":"eng"}],"date_created":"2018-12-12T11:39:10Z","date_published":"2013-12-03T00:00:00Z","doi":"10.15479/AT:IST-2013-146-v1-1","related_material":{"record":[{"relation":"later_version","status":"public","id":"1481"}]},"page":"13","language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"5528","checksum":"409f3aaaf1184e4057b89cbb449dac80","file_size":818189,"date_updated":"2020-07-14T12:46:46Z","creator":"system","file_name":"IST-2013-146-v1+1_main.pdf","date_created":"2018-12-12T11:54:06Z"}],"day":"03","publication_status":"published","year":"2013","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","pubrep_id":"146","status":"public","type":"technical_report","_id":"5410","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:46:46Z","title":"Automatic generation of alternative starting positions for traditional board games","author":[{"last_name":"Ahmed","full_name":"Ahmed, Umair","first_name":"Umair"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Gulwani, Sumit","last_name":"Gulwani","first_name":"Sumit"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000","005"],"date_updated":"2023-02-23T10:00:50Z","citation":{"chicago":"Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-146-v1-1.","ista":"Ahmed U, Chatterjee K, Gulwani S. 2013. Automatic generation of alternative starting positions for traditional board games, IST Austria, 13p.","mla":"Ahmed, Umair, et al. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-146-v1-1.","ama":"Ahmed U, Chatterjee K, Gulwani S. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-146-v1-1","apa":"Ahmed, U., Chatterjee, K., & Gulwani, S. (2013). Automatic generation of alternative starting positions for traditional board games. IST Austria. https://doi.org/10.15479/AT:IST-2013-146-v1-1","ieee":"U. Ahmed, K. Chatterjee, and S. Gulwani, Automatic generation of alternative starting positions for traditional board games. IST Austria, 2013.","short":"U. Ahmed, K. Chatterjee, S. Gulwani, Automatic Generation of Alternative Starting Positions for Traditional Board Games, IST Austria, 2013."}},{"title":"Hyperplane separation technique for multidimensional mean-payoff games","external_id":{"arxiv":["1210.3141"]},"publist_id":"4597","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"full_name":"Velner, Yaron","last_name":"Velner","first_name":"Yaron"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Chatterjee K, Velner Y. 2013. Hyperplane separation technique for multidimensional mean-payoff games. 8052, 500–515.","chicago":"Chatterjee, Krishnendu, and Yaron Velner. “Hyperplane Separation Technique for Multidimensional Mean-Payoff Games.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40184-8_35.","short":"K. Chatterjee, Y. Velner, 8052 (2013) 500–515.","ieee":"K. Chatterjee and Y. Velner, “Hyperplane separation technique for multidimensional mean-payoff games,” vol. 8052. Springer, pp. 500–515, 2013.","ama":"Chatterjee K, Velner Y. Hyperplane separation technique for multidimensional mean-payoff games. 2013;8052:500-515. doi:10.1007/978-3-642-40184-8_35","apa":"Chatterjee, K., & Velner, Y. (2013). Hyperplane separation technique for multidimensional mean-payoff games. Presented at the CONCUR: Concurrency Theory, Buenos Aires, Argentinia: Springer. https://doi.org/10.1007/978-3-642-40184-8_35","mla":"Chatterjee, Krishnendu, and Yaron Velner. Hyperplane Separation Technique for Multidimensional Mean-Payoff Games. Vol. 8052, Springer, 2013, pp. 500–15, doi:10.1007/978-3-642-40184-8_35."},"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"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"}],"date_created":"2018-12-11T11:57:01Z","date_published":"2013-08-01T00:00:00Z","doi":"10.1007/978-3-642-40184-8_35","page":"500 - 515","day":"01","year":"2013","oa":1,"publisher":"Springer","quality_controlled":"1","department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T13:00:42Z","status":"public","conference":{"name":"CONCUR: Concurrency Theory","start_date":"2013-08-27","location":"Buenos Aires, Argentinia","end_date":"2013-08-30"},"type":"conference","series_title":"Lecture Notes in Computer Science","_id":"2329","ec_funded":1,"related_material":{"record":[{"relation":"later_version","status":"public","id":"717"}]},"volume":8052,"language":[{"iso":"eng"}],"publication_status":"published","intvolume":" 8052","month":"08","main_file_link":[{"url":"http://arxiv.org/abs/1210.3141","open_access":"1"}],"alternative_title":["LNCS"],"scopus_import":1,"oa_version":"Preprint","abstract":[{"text":"Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work, we consider both finite-state game graphs, and recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion. The objectives we study are multidimensional mean-payoff objectives, where the goal of player 1 is to ensure that the mean-payoff is non-negative in all dimensions. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation. Our main contributions are as follows: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of the weights are fixed; whereas if the number of dimensions is arbitrary, then the problem is known to be coNP-complete. (2) We show that pushdown graphs with multidimensional mean-payoff objectives can be solved in polynomial time. For both (1) and (2) our algorithms are based on hyperplane separation technique. (3) For pushdown games under global strategies both one and multidimensional mean-payoff objectives problems are known to be undecidable, and we show that under modular strategies the multidimensional problem is also undecidable; under modular strategies the one-dimensional problem is NP-complete. We show that if the number of modules, the number of exits, and the maximal absolute value of the weights are fixed, then pushdown games under modular strategies with one-dimensional mean-payoff objectives can be solved in polynomial time, and if either the number of exits or the number of modules is unbounded, then the problem is NP-hard. (4) Finally we show that a fixed parameter tractable algorithm for finite-state multidimensional mean-payoff games or pushdown games under modular strategies with one-dimensional mean-payoff objectives would imply the fixed parameter tractability of parity games.","lang":"eng"}]},{"_id":"9749","type":"research_data_reference","status":"public","citation":{"chicago":"Zagorsky, Benjamin, Johannes Reiter, Krishnendu Chatterjee, and Martin Nowak. “Forgiver Triumphs in Alternating Prisoner’s Dilemma .” Public Library of Science, 2013. https://doi.org/10.1371/journal.pone.0080814.s001.","ista":"Zagorsky B, Reiter J, Chatterjee K, Nowak M. 2013. Forgiver triumphs in alternating prisoner’s dilemma , Public Library of Science, 10.1371/journal.pone.0080814.s001.","mla":"Zagorsky, Benjamin, et al. Forgiver Triumphs in Alternating Prisoner’s Dilemma . Public Library of Science, 2013, doi:10.1371/journal.pone.0080814.s001.","ieee":"B. Zagorsky, J. Reiter, K. Chatterjee, and M. Nowak, “Forgiver triumphs in alternating prisoner’s dilemma .” Public Library of Science, 2013.","short":"B. Zagorsky, J. Reiter, K. Chatterjee, M. Nowak, (2013).","ama":"Zagorsky B, Reiter J, Chatterjee K, Nowak M. Forgiver triumphs in alternating prisoner’s dilemma . 2013. doi:10.1371/journal.pone.0080814.s001","apa":"Zagorsky, B., Reiter, J., Chatterjee, K., & Nowak, M. (2013). Forgiver triumphs in alternating prisoner’s dilemma . Public Library of Science. https://doi.org/10.1371/journal.pone.0080814.s001"},"date_updated":"2023-02-23T10:34:39Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","author":[{"full_name":"Zagorsky, Benjamin","last_name":"Zagorsky","first_name":"Benjamin"},{"id":"4A918E98-F248-11E8-B48F-1D18A9856A87","first_name":"Johannes","orcid":"0000-0002-0170-7353","full_name":"Reiter, Johannes","last_name":"Reiter"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","full_name":"Nowak, Martin","last_name":"Nowak"}],"department":[{"_id":"KrCh"}],"title":"Forgiver triumphs in alternating prisoner's dilemma ","abstract":[{"lang":"eng","text":"Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise."}],"oa_version":"Published Version","publisher":"Public Library of Science","month":"12","year":"2013","day":"12","date_created":"2021-07-28T15:45:07Z","related_material":{"record":[{"id":"2247","status":"public","relation":"used_in_publication"}]},"doi":"10.1371/journal.pone.0080814.s001","date_published":"2013-12-12T00:00:00Z"},{"date_updated":"2023-09-05T15:10:38Z","department":[{"_id":"KrCh"}],"series_title":"LNCS","_id":"10902","status":"public","conference":{"name":"LATA: Conference on Language and Automata Theory and Applications","start_date":"2013-04-02","location":"Bilbao, Spain","end_date":"2013-04-05"},"type":"conference","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"eisbn":["9783642370649"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783642370632"]},"ec_funded":1,"volume":7810,"oa_version":"None","abstract":[{"lang":"eng","text":"We consider how to edit strings from a source language so that the edited strings belong to a target language, where the languages are given as deterministic finite automata. Non-streaming (or offline) transducers perform edits given the whole source string. We show that the class of deterministic one-pass transducers with registers along with increment and min operation suffices for computing optimal edit distance, whereas the same class of transducers without the min operation is not sufficient. Streaming (or online) transducers perform edits as the letters of the source string are received. We present a polynomial time algorithm for the partial-repair problem that given a bound α asks for the construction of a deterministic streaming transducer (if one exists) that ensures that the ‘maximum fraction’ η of the strings of the source language are edited, within cost α, to the target language."}],"intvolume":" 7810","place":"Berlin, Heidelberg","month":"04","scopus_import":"1","alternative_title":["LNCS"],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Chatterjee, Krishnendu, et al. “How to Travel between Languages.” 7th International Conference on Language and Automata Theory and Applications, vol. 7810, Springer Nature, 2013, pp. 214–25, doi:10.1007/978-3-642-37064-9_20.","ama":"Chatterjee K, Chaubal S, Rubin S. How to travel between languages. In: 7th International Conference on Language and Automata Theory and Applications. Vol 7810. LNCS. Berlin, Heidelberg: Springer Nature; 2013:214-225. doi:10.1007/978-3-642-37064-9_20","apa":"Chatterjee, K., Chaubal, S., & Rubin, S. (2013). How to travel between languages. In 7th International Conference on Language and Automata Theory and Applications (Vol. 7810, pp. 214–225). Berlin, Heidelberg: Springer Nature. https://doi.org/10.1007/978-3-642-37064-9_20","ieee":"K. Chatterjee, S. Chaubal, and S. Rubin, “How to travel between languages,” in 7th International Conference on Language and Automata Theory and Applications, Bilbao, Spain, 2013, vol. 7810, pp. 214–225.","short":"K. Chatterjee, S. Chaubal, S. Rubin, in:, 7th International Conference on Language and Automata Theory and Applications, Springer Nature, Berlin, Heidelberg, 2013, pp. 214–225.","chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Sasha Rubin. “How to Travel between Languages.” In 7th International Conference on Language and Automata Theory and Applications, 7810:214–25. LNCS. Berlin, Heidelberg: Springer Nature, 2013. https://doi.org/10.1007/978-3-642-37064-9_20.","ista":"Chatterjee K, Chaubal S, Rubin S. 2013. How to travel between languages. 7th International Conference on Language and Automata Theory and Applications. LATA: Conference on Language and Automata Theory and ApplicationsLNCS, LNCS, vol. 7810, 214–225."},"title":"How to travel between languages","article_processing_charge":"No","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Siddhesh","full_name":"Chaubal, Siddhesh","last_name":"Chaubal"},{"id":"2EC51194-F248-11E8-B48F-1D18A9856A87","first_name":"Sasha","full_name":"Rubin, Sasha","last_name":"Rubin"}],"project":[{"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":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"publication":"7th International Conference on Language and Automata Theory and Applications","day":"15","year":"2013","date_created":"2022-03-21T07:56:21Z","doi":"10.1007/978-3-642-37064-9_20","date_published":"2013-04-15T00:00:00Z","page":"214-225","acknowledgement":"The research was supported by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award. Thanks to Gabriele Puppis for suggesting the problem of identifying a deterministic transducer to compute the optimal cost, and to Martin Chmelik for his comments on the introduction.","publisher":"Springer Nature","quality_controlled":"1"}]