[{"type":"journal_article","volume":"228-229","citation":{"ieee":"K. Chatterjee and V. Prabhu, “Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems,” <i>Information and Computation</i>, vol. 228–229. Elsevier, pp. 83–119, 2013.","apa":"Chatterjee, K., &#38; Prabhu, V. (2013). Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2013.04.003\">https://doi.org/10.1016/j.ic.2013.04.003</a>","ama":"Chatterjee K, Prabhu V. Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems. <i>Information and Computation</i>. 2013;228-229:83-119. doi:<a href=\"https://doi.org/10.1016/j.ic.2013.04.003\">10.1016/j.ic.2013.04.003</a>","short":"K. Chatterjee, V. Prabhu, Information and Computation 228–229 (2013) 83–119.","ista":"Chatterjee K, Prabhu V. 2013. Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems. Information and Computation. 228–229, 83–119.","mla":"Chatterjee, Krishnendu, and Vinayak Prabhu. “Synthesis of Memory-Efficient, Clock-Memory Free, and Non-Zeno Safety Controllers for Timed Systems.” <i>Information and Computation</i>, vol. 228–229, Elsevier, 2013, pp. 83–119, doi:<a href=\"https://doi.org/10.1016/j.ic.2013.04.003\">10.1016/j.ic.2013.04.003</a>.","chicago":"Chatterjee, Krishnendu, and Vinayak Prabhu. “Synthesis of Memory-Efficient, Clock-Memory Free, and Non-Zeno Safety Controllers for Timed Systems.” <i>Information and Computation</i>. Elsevier, 2013. <a href=\"https://doi.org/10.1016/j.ic.2013.04.003\">https://doi.org/10.1016/j.ic.2013.04.003</a>."},"publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"2824","scopus_import":"1","month":"04","publist_id":"3977","year":"2013","quality_controlled":"1","page":"83-119","external_id":{"isi":["000322295300005"]},"language":[{"iso":"eng"}],"doi":"10.1016/j.ic.2013.04.003","date_published":"2013-04-24T00:00:00Z","publisher":"Elsevier","abstract":[{"text":"We study synthesis of controllers for real-time systems, where the objective is to stay in a given safe set. The problem is solved by obtaining winning strategies in the setting of concurrent two player timed automaton games with safety objectives. To prevent a player from winning by blocking time, we restrict each player to strategies that ensure that the player cannot be responsible for causing a Zeno run. We construct winning strategies for the controller which require access only to (1) the system clocks (thus, controllers which require their own internal infinitely precise clocks are not necessary), and (2) a logarithmic (in the number of clocks) number of memory bits (i.e. a linear number of memory states). Precisely, we show that for safety objectives, a memory of size (3 + lg (| C | + 1)) bits suffices for winning controller strategies, where C is the set of clocks of the timed automaton game, significantly improving the previous known exponential memory states bound. We also settle the open question of whether winning region-based strategies require memory for safety objectives by showing with an example the necessity of memory for such strategies to win for safety objectives. Finally, we show that the decision problem of determining if there exists a receptive player-1 winning strategy for safety objectives is EXPTIME-complete over timed automaton games.","lang":"eng"}],"date_updated":"2025-09-29T13:56:16Z","oa_version":"None","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Prabhu","full_name":"Prabhu, Vinayak","first_name":"Vinayak"}],"project":[{"grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"department":[{"_id":"KrCh"}],"isi":1,"day":"24","title":"Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems","publication":"Information and Computation","ec_funded":1,"article_processing_charge":"No","status":"public","date_created":"2018-12-11T11:59:47Z"},{"related_material":{"record":[{"id":"3342","relation":"earlier_version","status":"public"}]},"publication":"Formal Methods in System Design","ec_funded":1,"article_processing_charge":"No","status":"public","date_created":"2018-12-11T11:59:49Z","main_file_link":[{"url":"http://arxiv.org/abs/1104.3348","open_access":"1"}],"abstract":[{"text":"We consider Markov decision processes (MDPs) with Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes O(n · √ m) symbolic steps as compared to the previous known algorithm that takes O(n 2) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes O(n · √ n) symbolic steps, as compared to the previous known O(n 2) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires O(n · √ K) symbolic steps, where K is the maximal number of edges of strongly connected components (scc's) of the MDP. The win-lose algorithm requires symbolic computation of scc's. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5×n symbolic steps, whereas our new algorithm takes 4×n symbolic steps.","lang":"eng"}],"intvolume":"        42","date_updated":"2025-09-29T13:50:32Z","oa_version":"Preprint","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Joglekar","full_name":"Joglekar, Manas","first_name":"Manas"},{"full_name":"Shah, Nisarg","last_name":"Shah","first_name":"Nisarg"}],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF","name":"Game Theory"},{"call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"}],"isi":1,"day":"01","title":"Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives","year":"2013","quality_controlled":"1","page":"301 - 327","external_id":{"isi":["000319151400003"],"arxiv":["1104.3348"]},"issue":"3","doi":"10.1007/s10703-012-0180-2","publisher":"Springer","date_published":"2013-06-01T00:00:00Z","language":[{"iso":"eng"}],"oa":1,"type":"journal_article","corr_author":"1","volume":42,"citation":{"ieee":"K. Chatterjee, M. Henzinger, M. Joglekar, and N. Shah, “Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives,” <i>Formal Methods in System Design</i>, vol. 42, no. 3. Springer, pp. 301–327, 2013.","apa":"Chatterjee, K., Henzinger, M., Joglekar, M., &#38; Shah, N. (2013). Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-012-0180-2\">https://doi.org/10.1007/s10703-012-0180-2</a>","ama":"Chatterjee K, Henzinger M, Joglekar M, Shah N. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. <i>Formal Methods in System Design</i>. 2013;42(3):301-327. doi:<a href=\"https://doi.org/10.1007/s10703-012-0180-2\">10.1007/s10703-012-0180-2</a>","ista":"Chatterjee K, Henzinger M, Joglekar M, Shah N. 2013. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. Formal Methods in System Design. 42(3), 301–327.","mla":"Chatterjee, Krishnendu, et al. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” <i>Formal Methods in System Design</i>, vol. 42, no. 3, Springer, 2013, pp. 301–27, doi:<a href=\"https://doi.org/10.1007/s10703-012-0180-2\">10.1007/s10703-012-0180-2</a>.","chicago":"Chatterjee, Krishnendu, Monika Henzinger, Manas Joglekar, and Nisarg Shah. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” <i>Formal Methods in System Design</i>. Springer, 2013. <a href=\"https://doi.org/10.1007/s10703-012-0180-2\">https://doi.org/10.1007/s10703-012-0180-2</a>.","short":"K. Chatterjee, M. Henzinger, M. Joglekar, N. Shah, Formal Methods in System Design 42 (2013) 301–327."},"publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"2831","month":"06","scopus_import":"1","publist_id":"3968","arxiv":1},{"publication":"Formal Aspects of Computing","ec_funded":1,"article_processing_charge":"No","main_file_link":[{"url":"http://arxiv.org/abs/1004.2697","open_access":"1"}],"date_created":"2018-12-11T11:59:51Z","status":"public","oa_version":"Preprint","intvolume":"        26","date_updated":"2025-09-29T13:47:26Z","abstract":[{"text":"We study the automatic synthesis of fair non-repudiation protocols, a class of fair exchange protocols, used for digital contract signing. First, we show how to specify the objectives of the participating agents and the trusted third party as path formulas in linear temporal logic and prove that the satisfaction of these objectives imply fairness; a property required of fair exchange protocols. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of AGS as follows: (a) any solution of AGS is attack-free; no subset of participants can violate the objectives of the other participants; (b) the Asokan-Shoup-Waidner certified mail protocol that has known vulnerabilities is not a solution of AGS; (c) the Kremer-Markowitch non-repudiation protocol is a solution of AGS; and (d) AGS presents a new and symmetric fair non-repudiation protocol that is attack-free. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can both automatically discover vulnerabilities in protocols and generate correct protocols. The solution to AGS can be computed efficiently as the secure equilibrium solution of three-player graph games. ","lang":"eng"}],"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Raman, Vishwanath","last_name":"Raman","first_name":"Vishwanath"}],"isi":1,"department":[{"_id":"KrCh"}],"project":[{"grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"title":"Assume-guarantee synthesis for digital contract signing","day":"04","quality_controlled":"1","year":"2013","external_id":{"arxiv":["1004.2697"],"isi":["000339105100007"]},"page":"825 - 859","oa":1,"language":[{"iso":"eng"}],"publisher":"Springer","doi":"10.1007/s00165-013-0283-6","date_published":"2013-07-04T00:00:00Z","issue":"4","publication_status":"published","citation":{"ieee":"K. Chatterjee and V. Raman, “Assume-guarantee synthesis for digital contract signing,” <i>Formal Aspects of Computing</i>, vol. 26, no. 4. Springer, pp. 825–859, 2013.","ama":"Chatterjee K, Raman V. Assume-guarantee synthesis for digital contract signing. <i>Formal Aspects of Computing</i>. 2013;26(4):825-859. doi:<a href=\"https://doi.org/10.1007/s00165-013-0283-6\">10.1007/s00165-013-0283-6</a>","apa":"Chatterjee, K., &#38; Raman, V. (2013). Assume-guarantee synthesis for digital contract signing. <i>Formal Aspects of Computing</i>. Springer. <a href=\"https://doi.org/10.1007/s00165-013-0283-6\">https://doi.org/10.1007/s00165-013-0283-6</a>","mla":"Chatterjee, Krishnendu, and Vishwanath Raman. “Assume-Guarantee Synthesis for Digital Contract Signing.” <i>Formal Aspects of Computing</i>, vol. 26, no. 4, Springer, 2013, pp. 825–59, doi:<a href=\"https://doi.org/10.1007/s00165-013-0283-6\">10.1007/s00165-013-0283-6</a>.","chicago":"Chatterjee, Krishnendu, and Vishwanath Raman. “Assume-Guarantee Synthesis for Digital Contract Signing.” <i>Formal Aspects of Computing</i>. Springer, 2013. <a href=\"https://doi.org/10.1007/s00165-013-0283-6\">https://doi.org/10.1007/s00165-013-0283-6</a>.","ista":"Chatterjee K, Raman V. 2013. Assume-guarantee synthesis for digital contract signing. Formal Aspects of Computing. 26(4), 825–859.","short":"K. Chatterjee, V. Raman, Formal Aspects of Computing 26 (2013) 825–859."},"type":"journal_article","volume":26,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"2836","publist_id":"3963","arxiv":1,"scopus_import":"1","month":"07"},{"_id":"2854","tmp":{"short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode"},"month":"08","scopus_import":"1","publist_id":"3938","volume":79,"corr_author":"1","type":"journal_article","citation":{"ama":"Chatterjee K, De Alfaro L, Henzinger TA. Strategy improvement for concurrent reachability and turn based stochastic safety games. <i>Journal of Computer and System Sciences</i>. 2013;79(5):640-657. doi:<a href=\"https://doi.org/10.1016/j.jcss.2012.12.001\">10.1016/j.jcss.2012.12.001</a>","apa":"Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2013). Strategy improvement for concurrent reachability and turn based stochastic safety games. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcss.2012.12.001\">https://doi.org/10.1016/j.jcss.2012.12.001</a>","ieee":"K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Strategy improvement for concurrent reachability and turn based stochastic safety games,” <i>Journal of Computer and System Sciences</i>, vol. 79, no. 5. Elsevier, pp. 640–657, 2013.","chicago":"Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Strategy Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2013. <a href=\"https://doi.org/10.1016/j.jcss.2012.12.001\">https://doi.org/10.1016/j.jcss.2012.12.001</a>.","mla":"Chatterjee, Krishnendu, et al. “Strategy Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.” <i>Journal of Computer and System Sciences</i>, vol. 79, no. 5, Elsevier, 2013, pp. 640–57, doi:<a href=\"https://doi.org/10.1016/j.jcss.2012.12.001\">10.1016/j.jcss.2012.12.001</a>.","ista":"Chatterjee K, De Alfaro L, Henzinger TA. 2013. Strategy improvement for concurrent reachability and turn based stochastic safety games. Journal of Computer and System Sciences. 79(5), 640–657.","short":"K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System Sciences 79 (2013) 640–657."},"publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_type":"original","issue":"5","date_published":"2013-08-01T00:00:00Z","doi":"10.1016/j.jcss.2012.12.001","publisher":"Elsevier","language":[{"iso":"eng"}],"oa":1,"file":[{"file_name":"IST-2015-388-v1+1_1-s2.0-S0022000012001778-main.pdf","access_level":"open_access","checksum":"6d3ee12cceb946a0abe69594b6a22409","file_id":"5370","file_size":425488,"content_type":"application/pdf","date_updated":"2020-07-14T12:45:51Z","date_created":"2018-12-12T10:18:48Z","creator":"system","relation":"main_file"}],"year":"2013","quality_controlled":"1","page":"640 - 657","external_id":{"isi":["000316837300011"]},"project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"call_identifier":"FWF","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"isi":1,"has_accepted_license":"1","day":"01","ddc":["000"],"title":"Strategy improvement for concurrent reachability and turn based stochastic safety games","abstract":[{"text":"We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. First, we present a simple proof of the fact that in concurrent reachability games, for all ε&gt;0, memoryless ε-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an ε-optimal strategy achieves the objective with probability within ε of the value of the game. In contrast to previous proofs of this fact, our proof is more elementary and more combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives. Finally, we present a strategy-improvement algorithm for turn-based stochastic games (where each player selects moves in turns) with safety objectives. Our algorithms yield sequences of player-1 strategies which ensure probabilities of winning that converge monotonically (from below) to the value of the game. © 2012 Elsevier Inc.","lang":"eng"}],"date_updated":"2025-09-29T13:40:38Z","intvolume":"        79","oa_version":"Published Version","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"De Alfaro, Luca","last_name":"De Alfaro","first_name":"Luca"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"}],"article_processing_charge":"No","acknowledgement":"This work was partially supported in part by the NSF grants CCR-0132780, CNS-0720884, CCR-0225610, by the Swiss National Science Foundation, ERC Start Grant Graph Games (Project No. 279307), FWF NFN Grant S11407-N23 (RiSE), and a Microsoft faculty fellows","file_date_updated":"2020-07-14T12:45:51Z","status":"public","date_created":"2018-12-11T11:59:57Z","publication":"Journal of Computer and System Sciences","pubrep_id":"388","ec_funded":1},{"status":"public","file_date_updated":"2020-07-14T12:45:51Z","date_created":"2018-12-11T11:59:58Z","article_processing_charge":"No","ec_funded":1,"pubrep_id":"415","related_material":{"record":[{"relation":"dissertation_contains","id":"1400","status":"public"}]},"publication":"Evolutionary Applications","title":"The effect of one additional driver mutation on tumor progression","day":"01","ddc":["570"],"isi":1,"has_accepted_license":"1","project":[{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF","name":"Game Theory"}],"department":[{"_id":"KrCh"}],"license":"https://creativecommons.org/licenses/by/4.0/","author":[{"orcid":"0000-0002-0170-7353","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","first_name":"Johannes","full_name":"Reiter, Johannes","last_name":"Reiter"},{"last_name":"Božić","full_name":"Božić, Ivana","first_name":"Ivana"},{"id":"135B5B70-E9D2-11E9-BD74-BB415DA2B523","first_name":"Benjamin","full_name":"Allen, Benjamin","last_name":"Allen"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"intvolume":"         6","date_updated":"2026-04-09T14:26:23Z","oa_version":"Published Version","abstract":[{"text":"Tumor growth is caused by the acquisition of driver mutations, which enhance the net reproductive rate of cells. Driver mutations may increase cell division, reduce cell death, or allow cells to overcome density-limiting effects. We study the dynamics of tumor growth as one additional driver mutation is acquired. Our models are based on two-type branching processes that terminate in either tumor disappearance or tumor detection. In our first model, both cell types grow exponentially, with a faster rate for cells carrying the additional driver. We find that the additional driver mutation does not affect the survival probability of the lesion, but can substantially reduce the time to reach the detectable size if the lesion is slow growing. In our second model, cells lacking the additional driver cannot exceed a fixed carrying capacity, due to density limitations. In this case, the time to detection depends strongly on this carrying capacity. Our model provides a quantitative framework for studying tumor dynamics during different stages of progression. We observe that early, small lesions need additional drivers, while late stage metastases are only marginally affected by them. These results help to explain why additional driver mutations are typically not detected in fast-growing metastases.","lang":"eng"}],"oa":1,"file":[{"file_name":"IST-2016-415-v1+1_Reiter_et_al-2013-Evolutionary_Applications.pdf","access_level":"open_access","checksum":"e2955b3889f8a823c3d5a72cb16f8957","file_id":"5173","file_size":1172037,"content_type":"application/pdf","date_updated":"2020-07-14T12:45:51Z","date_created":"2018-12-12T10:15:50Z","creator":"system","relation":"main_file"}],"issue":"1","doi":"10.1111/eva.12020","language":[{"iso":"eng"}],"publisher":"Wiley-Blackwell","date_published":"2013-01-01T00:00:00Z","external_id":{"isi":["000313878800004"]},"page":"34 - 45","year":"2013","quality_controlled":"1","publist_id":"3931","month":"01","scopus_import":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"_id":"2858","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","citation":{"ama":"Reiter J, Božić I, Allen B, Chatterjee K, Nowak M. The effect of one additional driver mutation on tumor progression. <i>Evolutionary Applications</i>. 2013;6(1):34-45. doi:<a href=\"https://doi.org/10.1111/eva.12020\">10.1111/eva.12020</a>","apa":"Reiter, J., Božić, I., Allen, B., Chatterjee, K., &#38; Nowak, M. (2013). The effect of one additional driver mutation on tumor progression. <i>Evolutionary Applications</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/eva.12020\">https://doi.org/10.1111/eva.12020</a>","ieee":"J. Reiter, I. Božić, B. Allen, K. Chatterjee, and M. Nowak, “The effect of one additional driver mutation on tumor progression,” <i>Evolutionary Applications</i>, vol. 6, no. 1. Wiley-Blackwell, pp. 34–45, 2013.","short":"J. Reiter, I. Božić, B. Allen, K. Chatterjee, M. Nowak, Evolutionary Applications 6 (2013) 34–45.","mla":"Reiter, Johannes, et al. “The Effect of One Additional Driver Mutation on Tumor Progression.” <i>Evolutionary Applications</i>, vol. 6, no. 1, Wiley-Blackwell, 2013, pp. 34–45, doi:<a href=\"https://doi.org/10.1111/eva.12020\">10.1111/eva.12020</a>.","chicago":"Reiter, Johannes, Ivana Božić, Benjamin Allen, Krishnendu Chatterjee, and Martin Nowak. “The Effect of One Additional Driver Mutation on Tumor Progression.” <i>Evolutionary Applications</i>. Wiley-Blackwell, 2013. <a href=\"https://doi.org/10.1111/eva.12020\">https://doi.org/10.1111/eva.12020</a>.","ista":"Reiter J, Božić I, Allen B, Chatterjee K, Nowak M. 2013. The effect of one additional driver mutation on tumor progression. Evolutionary Applications. 6(1), 34–45."},"publication_status":"published","volume":6,"type":"journal_article","corr_author":"1"},{"article_processing_charge":"No","status":"public","date_created":"2018-12-11T12:00:09Z","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1209.4499"}],"conference":{"start_date":"2012-10-25","location":"Znojmo, Czech Republic","name":"MEMICS: Mathematical and Engineering Methods in Computer Science","end_date":"2012-10-28"},"ec_funded":1,"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory"},{"grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"}],"alternative_title":["LNCS"],"day":"09","title":"Controllable-choice message sequence graphs","abstract":[{"text":"We focus on the realizability problem of Message Sequence Graphs (MSG), i.e. the problem whether a given MSG specification is correctly distributable among parallel components communicating via messages. This fundamental problem of MSG is known to be undecidable. We introduce a well motivated restricted class of MSG, so called controllable-choice MSG, and show that all its models are realizable and moreover it is decidable whether a given MSG model is a member of this class. In more detail, this class of MSG specifications admits a deadlock-free realization by overloading existing messages with additional bounded control data. We also show that the presented class is the largest known subclass of MSG that allows for deadlock-free realization.","lang":"eng"}],"date_updated":"2025-06-11T08:05:09Z","intvolume":"      7721","oa_version":"Submitted Version","author":[{"last_name":"Chmelik","full_name":"Chmelik, Martin","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Řehák","full_name":"Řehák, Vojtěch","first_name":"Vojtěch"}],"publisher":"Springer","date_published":"2013-01-09T00:00:00Z","doi":"10.1007/978-3-642-36046-6_12","language":[{"iso":"eng"}],"oa":1,"year":"2013","quality_controlled":"1","page":"118 - 130","external_id":{"arxiv":["1209.4499"]},"_id":"2886","scopus_import":"1","month":"01","publist_id":"3873","arxiv":1,"corr_author":"1","type":"conference","volume":7721,"citation":{"apa":"Chmelik, M., &#38; Řehák, V. (2013). Controllable-choice message sequence graphs. Presented at the MEMICS: Mathematical and Engineering Methods in Computer Science, Znojmo, Czech Republic: Springer. <a href=\"https://doi.org/10.1007/978-3-642-36046-6_12\">https://doi.org/10.1007/978-3-642-36046-6_12</a>","ama":"Chmelik M, Řehák V. Controllable-choice message sequence graphs. 2013;7721:118-130. doi:<a href=\"https://doi.org/10.1007/978-3-642-36046-6_12\">10.1007/978-3-642-36046-6_12</a>","ieee":"M. Chmelik and V. Řehák, “Controllable-choice message sequence graphs,” vol. 7721. Springer, pp. 118–130, 2013.","ista":"Chmelik M, Řehák V. 2013. Controllable-choice message sequence graphs. 7721, 118–130.","chicago":"Chmelik, Martin, and Vojtěch Řehák. “Controllable-Choice Message Sequence Graphs.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-36046-6_12\">https://doi.org/10.1007/978-3-642-36046-6_12</a>.","mla":"Chmelik, Martin, and Vojtěch Řehák. <i>Controllable-Choice Message Sequence Graphs</i>. Vol. 7721, Springer, 2013, pp. 118–30, doi:<a href=\"https://doi.org/10.1007/978-3-642-36046-6_12\">10.1007/978-3-642-36046-6_12</a>.","short":"M. Chmelik, V. Řehák, 7721 (2013) 118–130."},"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","series_title":"Lecture Notes in Computer Science"},{"series_title":"Leibniz International Proceedings in Informatics","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","citation":{"ieee":"K. Chatterjee and N. Fijalkow, “Infinite-state games with finitary conditions,” in <i>22nd EACSL Annual Conference on Computer Science Logic</i>, Torino, Italy, 2013, vol. 23, pp. 181–196.","apa":"Chatterjee, K., &#38; Fijalkow, N. (2013). Infinite-state games with finitary conditions. In <i>22nd EACSL Annual Conference on Computer Science Logic</i> (Vol. 23, pp. 181–196). Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.181\">https://doi.org/10.4230/LIPIcs.CSL.2013.181</a>","ama":"Chatterjee K, Fijalkow N. Infinite-state games with finitary conditions. In: <i>22nd EACSL Annual Conference on Computer Science Logic</i>. Vol 23. Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2013:181-196. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.181\">10.4230/LIPIcs.CSL.2013.181</a>","mla":"Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Infinite-State Games with Finitary Conditions.” <i>22nd EACSL Annual Conference on Computer Science Logic</i>, vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–96, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.181\">10.4230/LIPIcs.CSL.2013.181</a>.","chicago":"Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Infinite-State Games with Finitary Conditions.” In <i>22nd EACSL Annual Conference on Computer Science Logic</i>, 23:181–96. Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2013.181\">https://doi.org/10.4230/LIPIcs.CSL.2013.181</a>.","ista":"Chatterjee K, Fijalkow N. 2013. Infinite-state games with finitary conditions. 22nd EACSL Annual Conference on Computer Science Logic. CSL: Computer Science LogicLeibniz International Proceedings in Informatics, LIPIcs, vol. 23, 181–196.","short":"K. Chatterjee, N. Fijalkow, in:, 22nd EACSL Annual Conference on Computer Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–196."},"corr_author":"1","volume":23,"type":"conference","publist_id":"5837","month":"09","scopus_import":1,"_id":"1374","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"page":"181 - 196","quality_controlled":"1","year":"2013","file":[{"creator":"system","relation":"main_file","date_created":"2018-12-12T10:13:38Z","file_size":547296,"date_updated":"2020-07-14T12:44:47Z","content_type":"application/pdf","access_level":"open_access","checksum":"b7091a3866db573c0db5ec486952255e","file_name":"IST-2016-624-v1+1_ChKr_Infinite-state_games_2013_17.pdf","file_id":"5023"}],"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"date_published":"2013-09-01T00:00:00Z","doi":"10.4230/LIPIcs.CSL.2013.181","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"full_name":"Fijalkow, Nathanaël","last_name":"Fijalkow","first_name":"Nathanaël"}],"oa_version":"Published Version","intvolume":"        23","date_updated":"2024-10-09T20:55:23Z","abstract":[{"lang":"eng","text":"We study two-player zero-sum games over infinite-state graphs equipped with ωB and finitary conditions. Our first contribution is about the strategy complexity, i.e the memory required for winning strategies: we prove that over general infinite-state graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory suffices for finitary parity games. We then study pushdown games with boundedness conditions, with two contributions. First we prove a collapse result for pushdown games with ωB-conditions, implying the decidability of solving these games. Second we consider pushdown games with finitary parity along with stack boundedness conditions, and show that solving these games is EXPTIME-complete."}],"title":"Infinite-state games with finitary conditions","ddc":["000"],"day":"01","alternative_title":["LIPIcs"],"has_accepted_license":"1","department":[{"_id":"KrCh"}],"project":[{"call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"ec_funded":1,"conference":{"location":"Torino, Italy","start_date":"203-09-02","name":"CSL: Computer Science Logic","end_date":"2013-09-05"},"pubrep_id":"624","publication":"22nd EACSL Annual Conference on Computer Science Logic","date_created":"2018-12-11T11:51:39Z","file_date_updated":"2020-07-14T12:44:47Z","status":"public"},{"oa":1,"date_published":"2013-12-11T00:00:00Z","publisher":"IEEE","language":[{"iso":"eng"}],"doi":"10.1109/FMCAD.2013.6679386","year":"2013","quality_controlled":"1","page":"18 - 25","_id":"1376","publist_id":"5835","month":"12","scopus_import":"1","citation":{"apa":"Chatterjee, K., Henzinger, T. A., Otop, J., &#38; Pavlogiannis, A. (2013). Distributed synthesis for LTL fragments. In <i>13th International Conference on Formal Methods in Computer-Aided Design</i> (pp. 18–25). Portland, OR, United States: IEEE. <a href=\"https://doi.org/10.1109/FMCAD.2013.6679386\">https://doi.org/10.1109/FMCAD.2013.6679386</a>","ama":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed synthesis for LTL fragments. In: <i>13th International Conference on Formal Methods in Computer-Aided Design</i>. IEEE; 2013:18-25. doi:<a href=\"https://doi.org/10.1109/FMCAD.2013.6679386\">10.1109/FMCAD.2013.6679386</a>","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, “Distributed synthesis for LTL fragments,” in <i>13th International Conference on Formal Methods in Computer-Aided Design</i>, Portland, OR, United States, 2013, pp. 18–25.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. “Distributed Synthesis for LTL Fragments.” In <i>13th International Conference on Formal Methods in Computer-Aided Design</i>, 18–25. IEEE, 2013. <a href=\"https://doi.org/10.1109/FMCAD.2013.6679386\">https://doi.org/10.1109/FMCAD.2013.6679386</a>.","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.","mla":"Chatterjee, Krishnendu, et al. “Distributed Synthesis for LTL Fragments.” <i>13th International Conference on Formal Methods in Computer-Aided Design</i>, IEEE, 2013, pp. 18–25, doi:<a href=\"https://doi.org/10.1109/FMCAD.2013.6679386\">10.1109/FMCAD.2013.6679386</a>.","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."},"publication_status":"published","type":"conference","corr_author":"1","OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","status":"public","date_created":"2018-12-11T11:51:40Z","main_file_link":[{"url":"https://doi.org/10.15479/AT:IST-2013-130-v1-1","open_access":"1"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5406"}]},"publication":"13th International Conference on Formal Methods in Computer-Aided Design","conference":{"end_date":"2013-10-23","name":"FMCAD: Formal Methods in Computer-Aided Design","start_date":"2013-10-20","location":"Portland, OR, United States"},"ec_funded":1,"OA_type":"green","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Distributed synthesis for LTL fragments","day":"11","date_updated":"2025-06-26T08:33:43Z","oa_version":"Preprint","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"}],"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan"},{"orcid":"0000-0002-8943-0722","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis"}]},{"department":[{"_id":"KrCh"}],"_id":"5399","has_accepted_license":"1","month":"01","alternative_title":["IST Austria Technical Report"],"day":"11","ddc":["000"],"title":"TTP: Tool for Tumor Progression","abstract":[{"lang":"eng","text":"In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics."}],"type":"technical_report","date_updated":"2025-04-15T08:12:25Z","citation":{"mla":"Reiter, Johannes, et al. <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">10.15479/AT:IST-2013-104-v1-1</a>.","ista":"Reiter J, Bozic I, Chatterjee K, Nowak M. 2013. TTP: Tool for Tumor Progression, IST Austria, 17p.","chicago":"Reiter, Johannes, Ivana Bozic, Krishnendu Chatterjee, and Martin Nowak. <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">https://doi.org/10.15479/AT:IST-2013-104-v1-1</a>.","short":"J. Reiter, I. Bozic, K. Chatterjee, M. Nowak, TTP: Tool for Tumor Progression, IST Austria, 2013.","ama":"Reiter J, Bozic I, Chatterjee K, Nowak M. <i>TTP: Tool for Tumor Progression</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">10.15479/AT:IST-2013-104-v1-1</a>","apa":"Reiter, J., Bozic, I., Chatterjee, K., &#38; Nowak, M. (2013). <i>TTP: Tool for Tumor Progression</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-104-v1-1\">https://doi.org/10.15479/AT:IST-2013-104-v1-1</a>","ieee":"J. Reiter, I. Bozic, K. Chatterjee, and M. Nowak, <i>TTP: Tool for Tumor Progression</i>. IST Austria, 2013."},"oa_version":"Published Version","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Reiter, Johannes","last_name":"Reiter","orcid":"0000-0002-0170-7353","first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Bozic, Ivana","last_name":"Bozic","first_name":"Ivana"},{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"full_name":"Nowak, Martin","last_name":"Nowak","first_name":"Martin"}],"publisher":"IST Austria","doi":"10.15479/AT:IST-2013-104-v1-1","date_published":"2013-01-11T00:00:00Z","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:44Z","oa":1,"status":"public","date_created":"2018-12-12T11:39:07Z","file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:46:44Z","file_size":1471954,"file_id":"5542","file_name":"IST-2013-104-v1+1_tumortool.pdf","access_level":"open_access","checksum":"2cc8c6e157eca1271128db80bb3dec80","creator":"system","relation":"main_file","date_created":"2018-12-12T11:54:20Z"}],"related_material":{"record":[{"id":"2000","relation":"later_version","status":"public"}]},"year":"2013","publication_identifier":{"issn":["2664-1690"]},"page":"17","pubrep_id":"104"},{"file_date_updated":"2020-07-14T12:46:44Z","status":"public","oa":1,"file":[{"date_created":"2018-12-12T11:53:06Z","relation":"main_file","creator":"system","access_level":"open_access","checksum":"cbba40210788a1b22c6cf06433b5ed6f","file_name":"IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf","file_id":"5467","file_size":483407,"date_updated":"2020-07-14T12:46:44Z","content_type":"application/pdf"}],"date_created":"2018-12-12T11:39:07Z","doi":"10.15479/AT:IST-2013-109-v1-1","publisher":"IST Austria","language":[{"iso":"eng"}],"date_published":"2013-02-20T00:00:00Z","publication_identifier":{"issn":["2664-1690"]},"pubrep_id":"109","page":"41","year":"2013","related_material":{"record":[{"status":"public","id":"2295","relation":"later_version"},{"id":"1477","relation":"later_version","status":"public"}]},"title":"What is decidable about partially observable Markov decision processes with ω-regular objectives","day":"20","month":"02","alternative_title":["IST Austria Technical Report"],"ddc":["000","005"],"_id":"5400","has_accepted_license":"1","department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik","full_name":"Chmelik, Martin"},{"last_name":"Tracol","full_name":"Tracol, Mathieu","first_name":"Mathieu","id":"3F54FA38-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2025-09-18T11:38:38Z","citation":{"ista":"Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with ω-regular objectives, IST Austria, 41p.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">10.15479/AT:IST-2013-109-v1-1</a>.","short":"K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013.","apa":"Chatterjee, K., Chmelik, M., &#38; Tracol, M. (2013). <i>What is decidable about partially observable Markov decision processes with ω-regular objectives</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">https://doi.org/10.15479/AT:IST-2013-109-v1-1</a>","ama":"Chatterjee K, Chmelik M, Tracol M. <i>What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-109-v1-1\">10.15479/AT:IST-2013-109-v1-1</a>","ieee":"K. Chatterjee, M. Chmelik, and M. Tracol, <i>What is decidable about partially observable Markov decision processes with ω-regular objectives</i>. IST Austria, 2013."},"oa_version":"Published Version","publication_status":"published","type":"technical_report","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"}]},{"day":"03","month":"07","alternative_title":["IST Austria Technical Report"],"ddc":["000","005"],"title":"Qualitative analysis of concurrent mean-payoff games","department":[{"_id":"KrCh"}],"_id":"5403","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"}],"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."}],"type":"technical_report","date_updated":"2025-09-23T09:56:27Z","citation":{"chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">https://doi.org/10.15479/AT:IST-2013-126-v1-1</a>.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">10.15479/AT:IST-2013-126-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff games, IST Austria, 33p.","short":"K. Chatterjee, R. Ibsen-Jensen, Qualitative Analysis of Concurrent Mean-Payoff Games, IST Austria, 2013.","ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>Qualitative analysis of concurrent mean-payoff games</i>. IST Austria, 2013.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2013). <i>Qualitative analysis of concurrent mean-payoff games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">https://doi.org/10.15479/AT:IST-2013-126-v1-1</a>","ama":"Chatterjee K, Ibsen-Jensen R. <i>Qualitative Analysis of Concurrent Mean-Payoff Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-126-v1-1\">10.15479/AT:IST-2013-126-v1-1</a>"},"publication_status":"published","oa_version":"Published Version","date_published":"2013-07-03T00:00:00Z","doi":"10.15479/AT:IST-2013-126-v1-1","language":[{"iso":"eng"}],"publisher":"IST Austria","oa":1,"status":"public","file_date_updated":"2020-07-14T12:46:45Z","date_created":"2018-12-12T11:39:08Z","file":[{"checksum":"063868c665beec37bf28160e2a695746","access_level":"open_access","file_name":"IST-2013-126-v1+1_soda_full.pdf","file_id":"5510","file_size":434523,"date_updated":"2020-07-14T12:46:45Z","content_type":"application/pdf","date_created":"2018-12-12T11:53:49Z","relation":"main_file","creator":"system"}],"publication_identifier":{"issn":["2664-1690"]},"page":"33","pubrep_id":"126","related_material":{"record":[{"status":"public","id":"524","relation":"later_version"}]},"year":"2013"},{"pubrep_id":"127","page":"29","publication_identifier":{"issn":["2664-1690"]},"related_material":{"record":[{"status":"public","id":"2162","relation":"later_version"}]},"year":"2013","publisher":"IST Austria","language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2013-127-v1-1","date_published":"2013-07-03T00:00:00Z","date_created":"2018-12-12T11:39:08Z","file":[{"relation":"main_file","creator":"system","date_created":"2018-12-12T11:53:35Z","file_size":517275,"content_type":"application/pdf","date_updated":"2020-07-14T12:46:45Z","file_name":"IST-2013-127-v1+1_ergodic.pdf","access_level":"open_access","checksum":"79ee5e677a82611ce06e0360c69d494a","file_id":"5496"}],"file_date_updated":"2020-07-14T12:46:45Z","status":"public","oa":1,"author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"technical_report","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."}],"publication_status":"published","oa_version":"Published Version","date_updated":"2025-04-15T07:55:59Z","citation":{"ieee":"K. Chatterjee and R. Ibsen-Jensen, <i>The complexity of ergodic games</i>. IST Austria, 2013.","ama":"Chatterjee K, Ibsen-Jensen R. <i>The Complexity of Ergodic Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">10.15479/AT:IST-2013-127-v1-1</a>","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2013). <i>The complexity of ergodic games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">https://doi.org/10.15479/AT:IST-2013-127-v1-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria, 2013.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Ergodic Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">10.15479/AT:IST-2013-127-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. <i>The Complexity of Ergodic Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-127-v1-1\">https://doi.org/10.15479/AT:IST-2013-127-v1-1</a>."},"ddc":["000","005"],"alternative_title":["IST Austria Technical Report"],"month":"07","day":"03","title":"The complexity of ergodic games","department":[{"_id":"KrCh"}],"has_accepted_license":"1","_id":"5404"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"last_name":"Gimbert","full_name":"Gimbert, Hugo","first_name":"Hugo"},{"last_name":"Oualhadj","full_name":"Oualhadj, Youssouf","first_name":"Youssouf"}],"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)."}],"type":"technical_report","citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. <i>Perfect-Information Stochastic Mean-Payoff Parity Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-128-v1-1\">https://doi.org/10.15479/AT:IST-2013-128-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Perfect-Information Stochastic Mean-Payoff Parity Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-128-v1-1\">10.15479/AT:IST-2013-128-v1-1</a>.","ista":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2013. Perfect-information stochastic mean-payoff parity games, IST Austria, 22p.","short":"K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, Perfect-Information Stochastic Mean-Payoff Parity Games, IST Austria, 2013.","ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, <i>Perfect-information stochastic mean-payoff parity games</i>. IST Austria, 2013.","ama":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. <i>Perfect-Information Stochastic Mean-Payoff Parity Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-128-v1-1\">10.15479/AT:IST-2013-128-v1-1</a>","apa":"Chatterjee, K., Doyen, L., Gimbert, H., &#38; Oualhadj, Y. (2013). <i>Perfect-information stochastic mean-payoff parity games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-128-v1-1\">https://doi.org/10.15479/AT:IST-2013-128-v1-1</a>"},"date_updated":"2025-04-15T07:56:00Z","publication_status":"published","oa_version":"Published Version","alternative_title":["IST Austria Technical Report"],"day":"08","month":"07","ddc":["000","005","510"],"title":"Perfect-information stochastic mean-payoff parity games","department":[{"_id":"KrCh"}],"_id":"5405","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"pubrep_id":"128","page":"22","related_material":{"record":[{"status":"public","id":"2212","relation":"later_version"}]},"year":"2013","doi":"10.15479/AT:IST-2013-128-v1-1","publisher":"IST Austria","date_published":"2013-07-08T00:00:00Z","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:45Z","status":"public","oa":1,"file":[{"date_created":"2018-12-12T11:53:54Z","creator":"system","relation":"main_file","checksum":"ede787a10e74e4f7db302fab8f12f3ca","access_level":"open_access","file_name":"IST-2013-128-v1+1_full_stoch_mpp.pdf","file_id":"5516","file_size":387467,"date_updated":"2020-07-14T12:46:45Z","content_type":"application/pdf"}],"date_created":"2018-12-12T11:39:09Z"},{"citation":{"short":"K. Chatterjee, T.A. Henzinger, J. Otop, 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.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. <i>Distributed Synthesis for LTL Fragments</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-130-v1-1\">https://doi.org/10.15479/AT:IST-2013-130-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Distributed Synthesis for LTL Fragments</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-130-v1-1\">10.15479/AT:IST-2013-130-v1-1</a>.","ieee":"K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, <i>Distributed synthesis for LTL Fragments</i>. IST Austria, 2013.","ama":"Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. <i>Distributed Synthesis for LTL Fragments</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-130-v1-1\">10.15479/AT:IST-2013-130-v1-1</a>","apa":"Chatterjee, K., Henzinger, T. A., Otop, J., &#38; Pavlogiannis, A. (2013). <i>Distributed synthesis for LTL Fragments</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-130-v1-1\">https://doi.org/10.15479/AT:IST-2013-130-v1-1</a>"},"date_updated":"2025-06-26T08:33:42Z","publication_status":"published","oa_version":"Published Version","type":"technical_report","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."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"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","orcid":"0000-0002-8943-0722","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas"}],"_id":"5406","has_accepted_license":"1","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Distributed synthesis for LTL Fragments","month":"07","alternative_title":["IST Austria Technical Report"],"day":"08","ddc":["005"],"year":"2013","related_material":{"record":[{"status":"public","id":"1376","relation":"later_version"}]},"publication_identifier":{"issn":["2664-1690"]},"pubrep_id":"130","page":"11","oa":1,"status":"public","file_date_updated":"2020-07-14T12:46:45Z","date_created":"2018-12-12T11:39:09Z","file":[{"creator":"system","relation":"main_file","date_created":"2018-12-12T11:54:18Z","date_updated":"2020-07-14T12:46:45Z","content_type":"application/pdf","file_size":467895,"file_id":"5540","access_level":"open_access","checksum":"855513ebaf6f72228800c5fdb522f93c","file_name":"IST-2013-130-v1+1_Distributed_Synthesis.pdf"}],"publisher":"IST Austria","doi":"10.15479/AT:IST-2013-130-v1-1","date_published":"2013-07-08T00:00:00Z","language":[{"iso":"eng"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"full_name":"Nain, Sumit","last_name":"Nain","first_name":"Sumit"},{"full_name":"Vardi, Moshe","last_name":"Vardi","first_name":"Moshe"}],"date_updated":"2025-04-15T07:56:00Z","citation":{"mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-141-v1-1\">10.15479/AT:IST-2013-141-v1-1</a>.","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. <i>The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-141-v1-1\">https://doi.org/10.15479/AT:IST-2013-141-v1-1</a>.","short":"K. Chatterjee, L. Doyen, S. Nain, M. Vardi, The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies, IST Austria, 2013.","ieee":"K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, <i>The complexity of partial-observation stochastic parity games with finite-memory strategies</i>. IST Austria, 2013.","ama":"Chatterjee K, Doyen L, Nain S, Vardi M. <i>The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-141-v1-1\">10.15479/AT:IST-2013-141-v1-1</a>","apa":"Chatterjee, K., Doyen, L., Nain, S., &#38; Vardi, M. (2013). <i>The complexity of partial-observation stochastic parity games with finite-memory strategies</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-141-v1-1\">https://doi.org/10.15479/AT:IST-2013-141-v1-1</a>"},"publication_status":"published","oa_version":"Published Version","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. "}],"type":"technical_report","title":"The complexity of partial-observation stochastic parity games with finite-memory strategies","month":"09","day":"12","alternative_title":["IST Austria Technical Report"],"ddc":["000","005"],"_id":"5408","has_accepted_license":"1","department":[{"_id":"KrCh"}],"publication_identifier":{"issn":["2664-1690"]},"page":"17","pubrep_id":"141","year":"2013","related_material":{"record":[{"status":"public","relation":"later_version","id":"2213"}]},"oa":1,"status":"public","file_date_updated":"2020-07-14T12:46:46Z","date_created":"2018-12-12T11:39:10Z","file":[{"date_created":"2018-12-12T11:53:16Z","relation":"main_file","creator":"system","file_id":"5477","checksum":"226bc791124f8d3138379778ce834e86","access_level":"open_access","file_name":"IST-2013-141-v1+1_main-tech-rpt.pdf","date_updated":"2020-07-14T12:46:46Z","content_type":"application/pdf","file_size":300481}],"date_published":"2013-09-12T00:00:00Z","language":[{"iso":"eng"}],"publisher":"IST Austria","doi":"10.15479/AT:IST-2013-141-v1-1"},{"file_date_updated":"2020-07-14T12:46:46Z","oa":1,"status":"public","date_created":"2018-12-12T11:39:10Z","file":[{"date_updated":"2020-07-14T12:46:46Z","content_type":"application/pdf","file_size":336377,"file_id":"5469","access_level":"open_access","checksum":"0f7633081ba8299c543322f0ad08571f","file_name":"IST-2013-144-v1+1_main.pdf","creator":"system","relation":"main_file","date_created":"2018-12-12T11:53:08Z"}],"language":[{"iso":"eng"}],"date_published":"2013-10-30T00:00:00Z","doi":"10.15479/AT:IST-2013-144-v1-1","publisher":"IST Austria","year":"2013","related_material":{"record":[{"status":"public","id":"2216","relation":"later_version"}]},"publication_identifier":{"issn":["2664-1690"]},"pubrep_id":"144","page":"12","_id":"5409","has_accepted_license":"1","department":[{"_id":"KrCh"}],"title":"Edit distance for timed automata","day":"30","alternative_title":["IST Austria Technical Report"],"month":"10","ddc":["000"],"date_updated":"2024-10-21T06:02:53Z","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, <i>Edit distance for timed automata</i>. IST Austria, 2013.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Majumdar, R. (2013). <i>Edit distance for timed automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-144-v1-1\">https://doi.org/10.15479/AT:IST-2013-144-v1-1</a>","ama":"Chatterjee K, Ibsen-Jensen R, Majumdar R. <i>Edit Distance for Timed Automata</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-144-v1-1\">10.15479/AT:IST-2013-144-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>Edit Distance for Timed Automata</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-144-v1-1\">10.15479/AT:IST-2013-144-v1-1</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Rupak Majumdar. <i>Edit Distance for Timed Automata</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-144-v1-1\">https://doi.org/10.15479/AT:IST-2013-144-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Majumdar R. 2013. Edit distance for timed automata, IST Austria, 12p.","short":"K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, Edit Distance for Timed Automata, IST Austria, 2013."},"oa_version":"Published Version","publication_status":"published","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."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389"},{"first_name":"Rupak","last_name":"Majumdar","full_name":"Majumdar, Rupak"}]},{"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"}],"type":"technical_report","oa_version":"Published Version","publication_status":"published","citation":{"ieee":"U. Ahmed, K. Chatterjee, and S. Gulwani, <i>Automatic generation of alternative starting positions for traditional board games</i>. IST Austria, 2013.","apa":"Ahmed, U., Chatterjee, K., &#38; Gulwani, S. (2013). <i>Automatic generation of alternative starting positions for traditional board games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2013-146-v1-1\">https://doi.org/10.15479/AT:IST-2013-146-v1-1</a>","ama":"Ahmed U, Chatterjee K, Gulwani S. <i>Automatic Generation of Alternative Starting Positions for Traditional Board Games</i>. IST Austria; 2013. doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-146-v1-1\">10.15479/AT:IST-2013-146-v1-1</a>","short":"U. Ahmed, K. Chatterjee, S. Gulwani, Automatic Generation of Alternative Starting Positions for Traditional Board Games, IST Austria, 2013.","mla":"Ahmed, Umair, et al. <i>Automatic Generation of Alternative Starting Positions for Traditional Board Games</i>. IST Austria, 2013, doi:<a href=\"https://doi.org/10.15479/AT:IST-2013-146-v1-1\">10.15479/AT:IST-2013-146-v1-1</a>.","ista":"Ahmed U, Chatterjee K, Gulwani S. 2013. Automatic generation of alternative starting positions for traditional board games, IST Austria, 13p.","chicago":"Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. <i>Automatic Generation of Alternative Starting Positions for Traditional Board Games</i>. IST Austria, 2013. <a href=\"https://doi.org/10.15479/AT:IST-2013-146-v1-1\">https://doi.org/10.15479/AT:IST-2013-146-v1-1</a>."},"date_updated":"2025-05-19T11:10:16Z","author":[{"first_name":"Umair","last_name":"Ahmed","full_name":"Ahmed, Umair"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"last_name":"Gulwani","full_name":"Gulwani, Sumit","first_name":"Sumit"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"has_accepted_license":"1","_id":"5410","ddc":["000","005"],"day":"03","alternative_title":["IST Austria Technical Report"],"month":"12","title":"Automatic generation of alternative starting positions for traditional board games","related_material":{"record":[{"relation":"later_version","id":"1481","status":"public"}]},"year":"2013","page":"13","pubrep_id":"146","publication_identifier":{"issn":["2664-1690"]},"date_published":"2013-12-03T00:00:00Z","language":[{"iso":"eng"}],"publisher":"IST Austria","doi":"10.15479/AT:IST-2013-146-v1-1","date_created":"2018-12-12T11:39:10Z","file":[{"date_created":"2018-12-12T11:54:06Z","creator":"system","relation":"main_file","file_name":"IST-2013-146-v1+1_main.pdf","access_level":"open_access","checksum":"409f3aaaf1184e4057b89cbb449dac80","file_id":"5528","file_size":818189,"content_type":"application/pdf","date_updated":"2020-07-14T12:46:46Z"}],"status":"public","oa":1,"file_date_updated":"2020-07-14T12:46:46Z"},{"oa_version":"Preprint","date_updated":"2025-09-23T09:24:13Z","intvolume":"      7721","abstract":[{"text":"Markov decision processes (MDPs) and simple stochastic games (SSGs) provide a rich mathematical framework to study many important problems related to probabilistic systems. MDPs and SSGs with finite-horizon objectives, where the goal is to maximize the probability to reach a target state in a given finite time, is a classical and well-studied problem. In this work we consider the strategy complexity of finite-horizon MDPs and SSGs. We show that for all ε > 0, the natural class of counter-based strategies require at most log log/(1/ε) + n + 1 memory states, and memory of size Omega(log log(1/ε) + n) is required, for ε-optimality, where n is the number of states of the MDP (resp. SSG). Thus our bounds are asymptotically optimal. We then study the periodic property of optimal strategies, and show a sub-exponential lower bound on the period for optimal strategies.","lang":"eng"}],"author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"orcid":"0000-0003-4783-0389","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen"}],"OA_type":"green","department":[{"_id":"KrCh"}],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications"}],"title":"Strategy complexity of finite-horizon Markov decision processes and simple stochastic games","day":"17","alternative_title":["LNCS"],"publication":"Mathematical and Engineering Methods in Computer Science","ec_funded":1,"conference":{"end_date":"2012-10-28","name":"MEMICS: Mathematical and Engineering Methods in Computer Science","location":"Znojmo, Czech Republic","start_date":"2012-10-25"},"publication_identifier":{"isbn":["9783642360442"],"eissn":["1611-3349"],"eisbn":["9783642360466"],"issn":["0302-9743"]},"article_processing_charge":"No","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1209.3617","open_access":"1"}],"date_created":"2025-07-10T14:08:49Z","status":"public","acknowledgement":"Work of the second author supported by the Sino-Danish Center for the Theory of Interactive Computation, funded by the Danish National Research Foundation and the National Science Foundation of China (under the grant 61061130540). The second author acknowledge support from the Center for research in the Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. The first author was supported by FWF Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","publication_status":"published","citation":{"ama":"Chatterjee K, Ibsen-Jensen R. Strategy complexity of finite-horizon Markov decision processes and simple stochastic games. In: <i>Mathematical and Engineering Methods in Computer Science</i>. Vol 7721. Springer Nature; 2013:106-117. doi:<a href=\"https://doi.org/10.1007/978-3-642-36046-6_11\">10.1007/978-3-642-36046-6_11</a>","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2013). Strategy complexity of finite-horizon Markov decision processes and simple stochastic games. In <i>Mathematical and Engineering Methods in Computer Science</i> (Vol. 7721, pp. 106–117). Znojmo, Czech Republic: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-36046-6_11\">https://doi.org/10.1007/978-3-642-36046-6_11</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, “Strategy complexity of finite-horizon Markov decision processes and simple stochastic games,” in <i>Mathematical and Engineering Methods in Computer Science</i>, Znojmo, Czech Republic, 2013, vol. 7721, pp. 106–117.","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Strategy Complexity of Finite-Horizon Markov Decision Processes and Simple Stochastic Games.” In <i>Mathematical and Engineering Methods in Computer Science</i>, 7721:106–17. Springer Nature, 2013. <a href=\"https://doi.org/10.1007/978-3-642-36046-6_11\">https://doi.org/10.1007/978-3-642-36046-6_11</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2013. Strategy complexity of finite-horizon Markov decision processes and simple stochastic games. Mathematical and Engineering Methods in Computer Science. MEMICS: Mathematical and Engineering Methods in Computer Science, LNCS, vol. 7721, 106–117.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Strategy Complexity of Finite-Horizon Markov Decision Processes and Simple Stochastic Games.” <i>Mathematical and Engineering Methods in Computer Science</i>, vol. 7721, Springer Nature, 2013, pp. 106–17, doi:<a href=\"https://doi.org/10.1007/978-3-642-36046-6_11\">10.1007/978-3-642-36046-6_11</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, in:, Mathematical and Engineering Methods in Computer Science, Springer Nature, 2013, pp. 106–117."},"volume":7721,"corr_author":"1","type":"conference","OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"19995","arxiv":1,"scopus_import":"1","month":"01","quality_controlled":"1","year":"2013","external_id":{"arxiv":["1209.3617"]},"page":"106-117","oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-642-36046-6_11","date_published":"2013-01-17T00:00:00Z","publisher":"Springer Nature"},{"publication":"Proceedings of 25th Int. Conf. on Computer Aided Verification","related_material":{"record":[{"relation":"earlier_version","id":"5399","status":"public"},{"status":"public","relation":"dissertation_contains","id":"1400"}]},"conference":{"end_date":"2013-07-19","name":"CAV: Computer Aided Verification","location":"St. Petersburg, Russia","start_date":"2013-07-13"},"ec_funded":1,"status":"public","date_created":"2018-12-11T11:55:08Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1303.5251"}],"abstract":[{"lang":"eng","text":"In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics."}],"intvolume":"      8044","date_updated":"2026-04-09T14:26:23Z","oa_version":"Preprint","author":[{"first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0170-7353","last_name":"Reiter","full_name":"Reiter, Johannes"},{"full_name":"Božić, Ivana","last_name":"Božić","first_name":"Ivana"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"project":[{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"department":[{"_id":"KrCh"}],"day":"01","alternative_title":["LNCS"],"title":"TTP: Tool for tumor progression","year":"2013","quality_controlled":"1","page":"101 - 106","external_id":{"arxiv":["1303.5251"]},"date_published":"2013-01-01T00:00:00Z","publisher":"Springer","language":[{"iso":"eng"}],"doi":"10.1007/978-3-642-39799-8_6","oa":1,"type":"conference","volume":8044,"citation":{"apa":"Reiter, J., Božić, I., Chatterjee, K., &#38; Nowak, M. (2013). TTP: Tool for tumor progression. In <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i> (Vol. 8044, pp. 101–106). St. Petersburg, Russia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">https://doi.org/10.1007/978-3-642-39799-8_6</a>","ama":"Reiter J, Božić I, Chatterjee K, Nowak M. TTP: Tool for tumor progression. In: <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>. Vol 8044. Lecture Notes in Computer Science. Springer; 2013:101-106. doi:<a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">10.1007/978-3-642-39799-8_6</a>","ieee":"J. Reiter, I. Božić, K. Chatterjee, and M. Nowak, “TTP: Tool for tumor progression,” in <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, St. Petersburg, Russia, 2013, vol. 8044, pp. 101–106.","short":"J. Reiter, I. Božić, K. Chatterjee, M. Nowak, in:, Proceedings of 25th Int. Conf. on Computer Aided Verification, Springer, 2013, pp. 101–106.","ista":"Reiter J, Božić I, Chatterjee K, Nowak M. 2013. TTP: Tool for tumor progression. Proceedings of 25th Int. Conf. on Computer Aided Verification. CAV: Computer Aided VerificationLecture Notes in Computer Science, LNCS, vol. 8044, 101–106.","chicago":"Reiter, Johannes, Ivana Božić, Krishnendu Chatterjee, and Martin Nowak. “TTP: Tool for Tumor Progression.” In <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, 8044:101–6. Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">https://doi.org/10.1007/978-3-642-39799-8_6</a>.","mla":"Reiter, Johannes, et al. “TTP: Tool for Tumor Progression.” <i>Proceedings of 25th Int. Conf. on Computer Aided Verification</i>, vol. 8044, Springer, 2013, pp. 101–06, doi:<a href=\"https://doi.org/10.1007/978-3-642-39799-8_6\">10.1007/978-3-642-39799-8_6</a>."},"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","series_title":"Lecture Notes in Computer Science","_id":"2000","month":"01","scopus_import":1,"arxiv":1,"publist_id":"5077"},{"acknowledgement":"This research was supported in part by the National Science Foundation CAREER award CCR-0132780, by the ONR grant N00014-02-1-0671, by the National Science Foundation grants CCR-0427202 and CCR-0234690, and by the ARP award TO.030.MM.D.","date_created":"2018-12-11T12:01:29Z","status":"public","article_processing_charge":"No","publication":"Formal Methods in System Design","day":"01","title":"Code aware resource management","department":[{"_id":"KrCh"}],"isi":1,"author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"first_name":"Luca","last_name":"De Alfaro","full_name":"De Alfaro, Luca"},{"full_name":"Faella, Marco","last_name":"Faella","first_name":"Marco"},{"first_name":"Ritankar","last_name":"Majumdar","full_name":"Majumdar, Ritankar"},{"first_name":"Vishwanath","full_name":"Raman, Vishwanath","last_name":"Raman"}],"abstract":[{"lang":"eng","text":"Multithreaded programs coordinate their interaction through synchronization primitives like mutexes and semaphores, which are managed by an OS-provided resource manager. We propose algorithms for the automatic construction of code-aware resource managers for multithreaded embedded applications. Such managers use knowledge about the structure and resource usage (mutex and semaphore usage) of the threads to guarantee deadlock freedom and progress while managing resources in an efficient way. Our algorithms compute managers as winning strategies in certain infinite games, and produce a compact code description of these strategies. We have implemented the algorithms in the tool Cynthesis. Given a multithreaded program in C, the tool produces C code implementing a code-aware resource manager. We show in experiments that Cynthesis produces compact resource managers within a few minutes on a set of embedded benchmarks with up to 6 threads. © 2012 Springer Science+Business Media, LLC."}],"oa_version":"None","intvolume":"        42","date_updated":"2025-09-29T13:24:54Z","publisher":"Springer","language":[{"iso":"eng"}],"date_published":"2013-04-01T00:00:00Z","doi":"10.1007/s10703-012-0170-4","issue":"2","page":"142 - 174","external_id":{"isi":["000316677500002"]},"quality_controlled":"1","year":"2013","month":"04","scopus_import":"1","publist_id":"3583","_id":"3116","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","volume":42,"type":"journal_article","publication_status":"published","citation":{"ieee":"K. Chatterjee, L. De Alfaro, M. Faella, R. Majumdar, and V. Raman, “Code aware resource management,” <i>Formal Methods in System Design</i>, vol. 42, no. 2. Springer, pp. 142–174, 2013.","apa":"Chatterjee, K., De Alfaro, L., Faella, M., Majumdar, R., &#38; Raman, V. (2013). Code aware resource management. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-012-0170-4\">https://doi.org/10.1007/s10703-012-0170-4</a>","ama":"Chatterjee K, De Alfaro L, Faella M, Majumdar R, Raman V. Code aware resource management. <i>Formal Methods in System Design</i>. 2013;42(2):142-174. doi:<a href=\"https://doi.org/10.1007/s10703-012-0170-4\">10.1007/s10703-012-0170-4</a>","short":"K. Chatterjee, L. De Alfaro, M. Faella, R. Majumdar, V. Raman, Formal Methods in System Design 42 (2013) 142–174.","ista":"Chatterjee K, De Alfaro L, Faella M, Majumdar R, Raman V. 2013. Code aware resource management. Formal Methods in System Design. 42(2), 142–174.","mla":"Chatterjee, Krishnendu, et al. “Code Aware Resource Management.” <i>Formal Methods in System Design</i>, vol. 42, no. 2, Springer, 2013, pp. 142–74, doi:<a href=\"https://doi.org/10.1007/s10703-012-0170-4\">10.1007/s10703-012-0170-4</a>.","chicago":"Chatterjee, Krishnendu, Luca De Alfaro, Marco Faella, Ritankar Majumdar, and Vishwanath Raman. “Code Aware Resource Management.” <i>Formal Methods in System Design</i>. Springer, 2013. <a href=\"https://doi.org/10.1007/s10703-012-0170-4\">https://doi.org/10.1007/s10703-012-0170-4</a>."}}]