[{"related_material":{"record":[{"id":"1477","status":"public","relation":"later_version"},{"status":"public","relation":"earlier_version","id":"5400"}]},"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","last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin"},{"last_name":"Tracol","first_name":"Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87","full_name":"Tracol, Mathieu"}],"volume":23,"date_updated":"2023-02-23T12:24:38Z","date_created":"2018-12-11T11:56:50Z","year":"2013","department":[{"_id":"KrCh"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","publist_id":"4633","ec_funded":1,"file_date_updated":"2020-07-14T12:45:37Z","license":"https://creativecommons.org/licenses/by/4.0/","doi":"10.4230/LIPIcs.CSL.2013.165","conference":{"location":"Torino, Italy","start_date":"2013-09-02","end_date":"2013-09-05","name":"CSL: Computer Science Logic"},"language":[{"iso":"eng"}],"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":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","month":"08","pubrep_id":"756","file":[{"checksum":"ba2828322955574d9283bea0e17a37a6","date_created":"2018-12-12T10:09:42Z","date_updated":"2020-07-14T12:45:37Z","relation":"main_file","file_id":"4766","content_type":"application/pdf","file_size":345171,"creator":"system","access_level":"open_access","file_name":"IST-2017-756-v1+1_2.pdf"}],"oa_version":"Published Version","_id":"2295","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 23","title":"What is decidable about partially observable Markov decision processes with omega-regular objectives","status":"public","ddc":["000"],"abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The qualitative analysis problem given a POMDP 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, we establish decidability (with optimal EXPTIME-complete complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite-memory strategies. We also establish asymptotically optimal (exponential) memory bounds."}],"type":"conference","alternative_title":["LIPIcs"],"date_published":"2013-08-27T00:00:00Z","citation":{"mla":"Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable Markov Decision Processes with Omega-Regular Objectives. Vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 165–80, doi:10.4230/LIPIcs.CSL.2013.165.","short":"K. Chatterjee, M. Chmelik, M. Tracol, 23 (2013) 165–180.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. “What Is Decidable about Partially Observable Markov Decision Processes with Omega-Regular Objectives.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.165.","ama":"Chatterjee K, Chmelik M, Tracol M. What is decidable about partially observable Markov decision processes with omega-regular objectives. 2013;23:165-180. doi:10.4230/LIPIcs.CSL.2013.165","ista":"Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with omega-regular objectives. 23, 165–180.","apa":"Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable about partially observable Markov decision processes with omega-regular objectives. Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2013.165","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, “What is decidable about partially observable Markov decision processes with omega-regular objectives,” vol. 23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 165–180, 2013."},"page":"165 - 180","has_accepted_license":"1","day":"27","scopus_import":1,"series_title":"Leibniz International Proceedings in Informatics"},{"type":"technical_report","alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","text":"We consider concurrent games played by two-players on a finite state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to every transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of mean-payoff games) that is not known to be in polynomial time."}],"file_date_updated":"2020-07-14T12:46:45Z","year":"2013","_id":"5403","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000","005"],"title":"Qualitative analysis of concurrent mean-payoff games","publication_status":"published","status":"public","department":[{"_id":"KrCh"}],"publisher":"IST Austria","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","first_name":"Rasmus"}],"pubrep_id":"126","related_material":{"record":[{"id":"524","relation":"later_version","status":"public"}]},"date_updated":"2023-02-23T12:22:53Z","date_created":"2018-12-12T11:39:08Z","file":[{"access_level":"open_access","file_name":"IST-2013-126-v1+1_soda_full.pdf","creator":"system","content_type":"application/pdf","file_size":434523,"file_id":"5510","relation":"main_file","checksum":"063868c665beec37bf28160e2a695746","date_created":"2018-12-12T11:53:49Z","date_updated":"2020-07-14T12:46:45Z"}],"oa_version":"Published Version","day":"03","month":"07","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"oa":1,"citation":{"chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. Qualitative Analysis of Concurrent Mean-Payoff Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-126-v1-1.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. Qualitative Analysis of Concurrent Mean-Payoff Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-126-v1-1.","short":"K. Chatterjee, R. Ibsen-Jensen, Qualitative Analysis of Concurrent Mean-Payoff Games, IST Austria, 2013.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff games, IST Austria, 33p.","ieee":"K. Chatterjee and R. Ibsen-Jensen, Qualitative analysis of concurrent mean-payoff games. IST Austria, 2013.","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2013). Qualitative analysis of concurrent mean-payoff games. IST Austria. https://doi.org/10.15479/AT:IST-2013-126-v1-1","ama":"Chatterjee K, Ibsen-Jensen R. Qualitative Analysis of Concurrent Mean-Payoff Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-126-v1-1"},"page":"33","date_published":"2013-07-03T00:00:00Z","doi":"10.15479/AT:IST-2013-126-v1-1","language":[{"iso":"eng"}]},{"date_created":"2018-12-12T11:39:07Z","date_updated":"2020-07-14T23:04:47Z","file":[{"file_name":"IST-2013-123-v1+1_main-concur2013.pdf","access_level":"open_access","creator":"system","content_type":"application/pdf","file_size":249790,"file_id":"5480","relation":"main_file","date_updated":"2020-07-14T12:46:45Z","date_created":"2018-12-12T11:53:19Z","checksum":"ce580605ae9756a8c99d7b403ebb8eed"}],"oa_version":"Published Version","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"full_name":"Sezgin, Ali","first_name":"Ali","last_name":"Sezgin","id":"4C7638DA-F248-11E8-B48F-1D18A9856A87"}],"pubrep_id":"123","publication_status":"published","status":"public","title":"How free is your linearizable concurrent data structure?","ddc":["000","004"],"department":[{"_id":"ToHe"}],"publisher":"IST Austria","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5402","year":"2013","abstract":[{"text":"Linearizability requires that the outcome of calls by competing threads to a concurrent data structure is the same as some sequential execution where each thread has exclusive access to the data structure. In an ordered data structure, such as a queue or a stack, linearizability is ensured by requiring threads commit in the order dictated by the sequential semantics of the data structure; e.g., in a concurrent queue implementation a dequeue can only remove the oldest element. \r\nIn this paper, we investigate the impact of this strict ordering, by comparing what linearizability allows to what existing implementations do. We first give an operational definition for linearizability which allows us to build the most general linearizable implementation as a transition system for any given sequential specification. We then use this operational definition to categorize linearizable implementations based on whether they are bound or free. In a bound implementation, whenever all threads observe the same logical state, the updates to the logical state and the temporal order of commits coincide. All existing queue implementations we know of are bound. We then proceed to present, to the best of our knowledge, the first ever free queue implementation. Our experiments show that free implementations have the potential for better performance by suffering less from contention.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:45Z","alternative_title":["IST Austria Technical Report"],"type":"technical_report","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2013-123-v1-1","date_published":"2013-06-12T00:00:00Z","page":"16","citation":{"ama":"Henzinger TA, Sezgin A. How Free Is Your Linearizable Concurrent Data Structure? IST Austria; 2013. doi:10.15479/AT:IST-2013-123-v1-1","ista":"Henzinger TA, Sezgin A. 2013. How free is your linearizable concurrent data structure?, IST Austria, 16p.","ieee":"T. A. Henzinger and A. Sezgin, How free is your linearizable concurrent data structure? IST Austria, 2013.","apa":"Henzinger, T. A., & Sezgin, A. (2013). How free is your linearizable concurrent data structure? IST Austria. https://doi.org/10.15479/AT:IST-2013-123-v1-1","mla":"Henzinger, Thomas A., and Ali Sezgin. How Free Is Your Linearizable Concurrent Data Structure? IST Austria, 2013, doi:10.15479/AT:IST-2013-123-v1-1.","short":"T.A. Henzinger, A. Sezgin, How Free Is Your Linearizable Concurrent Data Structure?, IST Austria, 2013.","chicago":"Henzinger, Thomas A, and Ali Sezgin. How Free Is Your Linearizable Concurrent Data Structure? IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-123-v1-1."},"oa":1,"day":"12","month":"06","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1"},{"alternative_title":["IST Austria Technical Report"],"type":"technical_report","file_date_updated":"2020-07-14T12:46:44Z","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish asymptotically optimal (exponential) memory bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives.","lang":"eng"}],"department":[{"_id":"KrCh"}],"publisher":"IST Austria","ddc":["000","005"],"title":"What is decidable about partially observable Markov decision processes with ω-regular objectives","status":"public","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5400","year":"2013","file":[{"relation":"main_file","file_id":"5467","date_created":"2018-12-12T11:53:06Z","date_updated":"2020-07-14T12:46:44Z","checksum":"cbba40210788a1b22c6cf06433b5ed6f","file_name":"IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf","access_level":"open_access","content_type":"application/pdf","file_size":483407,"creator":"system"}],"oa_version":"Published Version","date_updated":"2023-02-23T10:36:45Z","date_created":"2018-12-12T11:39:07Z","pubrep_id":"109","related_material":{"record":[{"id":"1477","relation":"later_version","status":"public"},{"status":"public","relation":"later_version","id":"2295"}]},"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik","full_name":"Chmelik, Martin"},{"full_name":"Tracol, Mathieu","first_name":"Mathieu","last_name":"Tracol","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87"}],"publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","day":"20","month":"02","page":"41","oa":1,"citation":{"short":"K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013.","mla":"Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria, 2013, doi:10.15479/AT:IST-2013-109-v1-1.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-109-v1-1.","ama":"Chatterjee K, Chmelik M, Tracol M. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria; 2013. doi:10.15479/AT:IST-2013-109-v1-1","apa":"Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable about partially observable Markov decision processes with ω-regular objectives. IST Austria. https://doi.org/10.15479/AT:IST-2013-109-v1-1","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, What is decidable about partially observable Markov decision processes with ω-regular objectives. IST Austria, 2013.","ista":"Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with ω-regular objectives, IST Austria, 41p."},"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2013-109-v1-1","date_published":"2013-02-20T00:00:00Z"},{"doi":"10.15479/AT:IST-2013-127-v1-1","date_published":"2013-07-03T00:00:00Z","language":[{"iso":"eng"}],"oa":1,"citation":{"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.","short":"K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria, 2013.","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","ieee":"K. Chatterjee and R. Ibsen-Jensen, The complexity of ergodic games. IST Austria, 2013.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p.","ama":"Chatterjee K, Ibsen-Jensen R. The Complexity of Ergodic Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-127-v1-1"},"page":"29","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","month":"07","day":"03","related_material":{"record":[{"status":"public","relation":"later_version","id":"2162"}]},"pubrep_id":"127","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"file":[{"creator":"system","file_size":517275,"content_type":"application/pdf","file_name":"IST-2013-127-v1+1_ergodic.pdf","access_level":"open_access","date_updated":"2020-07-14T12:46:45Z","date_created":"2018-12-12T11:53:35Z","checksum":"79ee5e677a82611ce06e0360c69d494a","file_id":"5496","relation":"main_file"}],"oa_version":"Published Version","date_created":"2018-12-12T11:39:08Z","date_updated":"2023-02-23T10:30:55Z","year":"2013","_id":"5404","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"publisher":"IST Austria","publication_status":"published","ddc":["000","005"],"status":"public","title":"The complexity of ergodic games","file_date_updated":"2020-07-14T12:46:45Z","abstract":[{"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.","lang":"eng"}],"type":"technical_report","alternative_title":["IST Austria Technical Report"]},{"file_date_updated":"2020-07-14T12:46:45Z","abstract":[{"text":"This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the actual initiatives, projects and standards related to the project. It supports the preparation of standards and specifications for the project, which should be considered and followed to ensure interoperability and visibility of the uploaded data.","lang":"eng"}],"type":"report","oa_version":"Published Version","file":[{"relation":"main_file","file_id":"5536","checksum":"d68712db838432ecdacf9ffb1de8f8a6","date_created":"2018-12-12T11:54:14Z","date_updated":"2020-07-14T12:46:45Z","access_level":"open_access","file_name":"IST-2013-113-v1+1_Initiatives_and_projects_related_to_RD.pdf","file_size":151208,"content_type":"application/pdf","creator":"system"}],"date_updated":"2020-07-14T23:04:47Z","date_created":"2018-12-12T11:39:07Z","pubrep_id":"113","author":[{"id":"3252EDC2-F248-11E8-B48F-1D18A9856A87","first_name":"Jana","last_name":"Porsche","full_name":"Porsche, Jana"}],"department":[{"_id":"E-Lib"}],"publisher":"IST Austria","ddc":["020"],"publication_status":"published","title":"Initiatives and projects related to RD","status":"public","year":"2013","_id":"5401","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","month":"03","day":"20","language":[{"iso":"eng"}],"date_published":"2013-03-20T00:00:00Z","citation":{"chicago":"Porsche, Jana. Initiatives and Projects Related to RD. IST Austria, 2013.","mla":"Porsche, Jana. Initiatives and Projects Related to RD. IST Austria, 2013.","short":"J. Porsche, Initiatives and Projects Related to RD, IST Austria, 2013.","ista":"Porsche J. 2013. Initiatives and projects related to RD, IST Austria,p.","apa":"Porsche, J. (2013). Initiatives and projects related to RD. IST Austria.","ieee":"J. Porsche, Initiatives and projects related to RD. IST Austria, 2013.","ama":"Porsche J. Initiatives and Projects Related to RD. IST Austria; 2013."},"oa":1},{"_id":"5405","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2013","department":[{"_id":"KrCh"}],"publisher":"IST Austria","status":"public","title":"Perfect-information stochastic mean-payoff parity games","publication_status":"published","ddc":["000","005","510"],"pubrep_id":"128","related_material":{"record":[{"id":"2212","status":"public","relation":"later_version"}]},"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"},{"full_name":"Gimbert, Hugo","last_name":"Gimbert","first_name":"Hugo"},{"full_name":"Oualhadj, Youssouf","first_name":"Youssouf","last_name":"Oualhadj"}],"oa_version":"Published Version","file":[{"creator":"system","file_size":387467,"content_type":"application/pdf","file_name":"IST-2013-128-v1+1_full_stoch_mpp.pdf","access_level":"open_access","date_updated":"2020-07-14T12:46:45Z","date_created":"2018-12-12T11:53:54Z","checksum":"ede787a10e74e4f7db302fab8f12f3ca","file_id":"5516","relation":"main_file"}],"date_created":"2018-12-12T11:39:09Z","date_updated":"2023-02-23T10:33:08Z","type":"technical_report","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:45Z","abstract":[{"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).","lang":"eng"}],"oa":1,"citation":{"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.","mla":"Chatterjee, Krishnendu, et al. Perfect-Information Stochastic Mean-Payoff Parity Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-128-v1-1.","short":"K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, Perfect-Information Stochastic Mean-Payoff Parity Games, IST Austria, 2013.","ista":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2013. Perfect-information stochastic mean-payoff parity games, IST Austria, 22p.","ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and 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"},"page":"22","date_published":"2013-07-08T00:00:00Z","doi":"10.15479/AT:IST-2013-128-v1-1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","day":"08","month":"07"},{"alternative_title":["IST Austria Technical Report"],"type":"technical_report","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."}],"file_date_updated":"2020-07-14T12:46:46Z","publication_status":"published","status":"public","ddc":["000"],"title":"Edit distance for timed automata","publisher":"IST Austria","department":[{"_id":"KrCh"}],"_id":"5409","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2013","date_created":"2018-12-12T11:39:10Z","date_updated":"2023-02-23T10:33:18Z","file":[{"file_size":336377,"content_type":"application/pdf","creator":"system","file_name":"IST-2013-144-v1+1_main.pdf","access_level":"open_access","date_created":"2018-12-12T11:53:08Z","date_updated":"2020-07-14T12:46:46Z","checksum":"0f7633081ba8299c543322f0ad08571f","relation":"main_file","file_id":"5469"}],"oa_version":"Published Version","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Majumdar, Rupak","last_name":"Majumdar","first_name":"Rupak"}],"pubrep_id":"144","related_material":{"record":[{"status":"public","relation":"later_version","id":"2216"}]},"day":"30","month":"10","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"page":"12","oa":1,"citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Majumdar R. 2013. Edit distance for timed automata, IST Austria, 12p.","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","ieee":"K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, Edit distance for timed automata. IST Austria, 2013.","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","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.","mla":"Chatterjee, Krishnendu, et al. Edit Distance for Timed Automata. IST Austria, 2013, doi:10.15479/AT:IST-2013-144-v1-1.","short":"K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, Edit Distance for Timed Automata, IST Austria, 2013."},"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2013-144-v1-1","date_published":"2013-10-30T00:00:00Z"},{"quality_controlled":"1","project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","call_identifier":"FP7","name":"Quantitative Reactive Modeling"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"page":"18 - 25","publication":"13th International Conference on Formal Methods in Computer-Aided Design","citation":{"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","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.","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.","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.","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.","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."},"language":[{"iso":"eng"}],"conference":{"end_date":"2013-10-23","location":"Portland, OR, United States","start_date":"2013-10-20","name":"FMCAD: Formal Methods in Computer-Aided Design"},"doi":"10.1109/FMCAD.2013.6679386","date_published":"2013-12-11T00:00:00Z","month":"12","day":"11","publication_status":"published","status":"public","title":"Distributed synthesis for LTL fragments","publisher":"IEEE","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"_id":"1376","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2013","date_created":"2018-12-11T11:51:40Z","date_updated":"2023-02-23T12:24:53Z","oa_version":"None","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5406"}]},"type":"conference","abstract":[{"lang":"eng","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."}],"ec_funded":1,"publist_id":"5835"},{"abstract":[{"lang":"eng","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."}],"file_date_updated":"2020-07-14T12:46:45Z","type":"technical_report","alternative_title":["IST Austria Technical Report"],"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"first_name":"Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan"},{"full_name":"Pavlogiannis, Andreas","first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722"}],"pubrep_id":"130","related_material":{"record":[{"id":"1376","status":"public","relation":"later_version"}]},"date_updated":"2023-02-21T17:01:26Z","date_created":"2018-12-12T11:39:09Z","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"IST-2013-130-v1+1_Distributed_Synthesis.pdf","creator":"system","content_type":"application/pdf","file_size":467895,"file_id":"5540","relation":"main_file","checksum":"855513ebaf6f72228800c5fdb522f93c","date_created":"2018-12-12T11:54:18Z","date_updated":"2020-07-14T12:46:45Z"}],"_id":"5406","year":"2013","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","status":"public","ddc":["005"],"title":"Distributed synthesis for LTL Fragments","publisher":"IST Austria","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"month":"07","day":"08","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"date_published":"2013-07-08T00:00:00Z","doi":"10.15479/AT:IST-2013-130-v1-1","language":[{"iso":"eng"}],"citation":{"short":"K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, Distributed Synthesis for LTL Fragments, IST Austria, 2013.","mla":"Chatterjee, Krishnendu, et al. Distributed Synthesis for LTL Fragments. IST Austria, 2013, doi:10.15479/AT:IST-2013-130-v1-1.","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.","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","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","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, Distributed synthesis for LTL Fragments. IST Austria, 2013.","ista":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis for LTL Fragments, IST Austria, 11p."},"oa":1,"page":"11"}]