[{"file_date_updated":"2020-07-14T12:46:52Z","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.\r\nOur problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.\r\nFinally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["IST Austria Technical Report"],"date_updated":"2026-07-06T13:26:26Z","fulldoi":"https://doi.org/10.15479/AT:IST-2015-318-v1-1","ddc":["004"],"date_published":"2015-01-12T00:00:00Z","has_accepted_license":"1","citation":{"ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","ama":"Chatterjee K, Komarkova Z, Kretinsky J. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria; 2015. doi:10.15479/AT:IST-2015-318-v1-1","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria, 2015.","apa":"Chatterjee, K., Komarkova, Z., & Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. IST Austria. https://doi.org/10.15479/AT:IST-2015-318-v1-1","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-318-v1-1.","short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IST Austria, 2015, doi:10.15479/AT:IST-2015-318-v1-1."},"year":"2015","publisher":"IST Austria","day":"12","oa_version":"Published Version","status":"public","_id":"5429","file":[{"checksum":"e4869a584567c506349abda9c8ec7db3","access_level":"open_access","relation":"main_file","creator":"system","date_updated":"2020-07-14T12:46:52Z","content_type":"application/pdf","file_id":"5533","file_size":689863,"date_created":"2018-12-12T11:54:11Z","file_name":"IST-2015-318-v1+1_main.pdf"}],"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"full_name":"Komarkova, Zuzana","last_name":"Komarkova","first_name":"Zuzana"},{"last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan","first_name":"Jan","orcid":"0000-0002-8122-2881"}],"doi":"10.15479/AT:IST-2015-318-v1-1","type":"technical_report","publication_identifier":{"issn":["2664-1690"]},"oa":1,"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","month":"01","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"publication_status":"published","pubrep_id":"318","page":"41","related_material":{"record":[{"status":"public","relation":"later_version","id":"5435"},{"relation":"later_version","id":"1657","status":"public"},{"status":"public","id":"466","relation":"later_version"}]},"date_created":"2018-12-12T11:39:17Z"},{"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A"},{"last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","first_name":"Rasmus"},{"full_name":"Otop, Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"type":"technical_report","doi":"10.15479/AT:IST-2015-334-v1-1","oa":1,"title":"Edit distance for pushdown automata","publication_identifier":{"issn":["2664-1690"]},"month":"05","publication_status":"published","pubrep_id":"334","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"page":"15","related_material":{"record":[{"status":"public","id":"1610","relation":"later_version"},{"status":"public","relation":"later_version","id":"465"}]},"date_created":"2018-12-12T11:39:20Z","file_date_updated":"2020-07-14T12:46:55Z","abstract":[{"text":"The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.\r\nThe problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k. ","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-07-06T13:27:53Z","alternative_title":["IST Austria Technical Report"],"fulldoi":"https://doi.org/10.15479/AT:IST-2015-334-v1-1","date_published":"2015-05-05T00:00:00Z","has_accepted_license":"1","ddc":["004"],"publisher":"IST Austria","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, Edit distance for pushdown automata. IST Austria, 2015.","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit distance for pushdown automata. IST Austria. https://doi.org/10.15479/AT:IST-2015-334-v1-1","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.","ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit Distance for Pushdown Automata. IST Austria; 2015. doi:10.15479/AT:IST-2015-334-v1-1","mla":"Chatterjee, Krishnendu, et al. Edit Distance for Pushdown Automata. IST Austria, 2015, doi:10.15479/AT:IST-2015-334-v1-1.","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. Edit Distance for Pushdown Automata. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-334-v1-1."},"year":"2015","day":"05","oa_version":"Published Version","status":"public","_id":"5438","file":[{"date_created":"2018-12-12T11:53:56Z","file_size":422573,"file_name":"IST-2015-334-v1+1_report.pdf","file_id":"5518","creator":"system","content_type":"application/pdf","date_updated":"2020-07-14T12:46:55Z","relation":"main_file","checksum":"8a5f2d77560e552af87eb1982437a43b","access_level":"open_access"}]},{"external_id":{"isi":["000380427100026"]},"status":"public","_id":"1661","oa_version":"Submitted Version","day":"01","isi":1,"citation":{"mla":"Chatterjee, Krishnendu, et al. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” Proceedings - Symposium on Logic in Computer Science, vol. 2015–July, 7174888, IEEE, 2015, doi:10.1109/LICS.2015.34.","short":"K. Chatterjee, M. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.","chicago":"Chatterjee, Krishnendu, Monika Henzinger, and Veronika Loitzenbauer. “Improved Algorithms for One-Pair and k-Pair Streett Objectives.” In Proceedings - Symposium on Logic in Computer Science, Vol. 2015–July. IEEE, 2015. https://doi.org/10.1109/LICS.2015.34.","apa":"Chatterjee, K., Henzinger, M., & Loitzenbauer, V. (2015). Improved algorithms for one-pair and k-pair Streett objectives. In Proceedings - Symposium on Logic in Computer Science (Vol. 2015–July). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.34","ieee":"K. Chatterjee, M. Henzinger, and V. Loitzenbauer, “Improved algorithms for one-pair and k-pair Streett objectives,” in Proceedings - Symposium on Logic in Computer Science, Kyoto, Japan, 2015, vol. 2015–July.","ista":"Chatterjee K, Henzinger M, Loitzenbauer V. 2015. Improved algorithms for one-pair and k-pair Streett objectives. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174888.","ama":"Chatterjee K, Henzinger M, Loitzenbauer V. Improved algorithms for one-pair and k-pair Streett objectives. In: Proceedings - Symposium on Logic in Computer Science. Vol 2015-July. IEEE; 2015. doi:10.1109/LICS.2015.34"},"year":"2015","acknowledgement":"K. C. is supported by the Austrian Science Fund (FWF): P23499-N23 and S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games), and a Microsoft Faculty Fellows Award. M. H. is supported by the Austrian Science Fund (FWF): P23499-N23 and the Vienna Science and Technology Fund (WWTF) grant ICT10-002. V. L. is supported by the Vienna Science and Technology Fund (WWTF) grant ICT10-002. The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 340506.","publisher":"IEEE","date_published":"2015-07-01T00:00:00Z","fulldoi":"https://doi.org/10.1109/LICS.2015.34","date_updated":"2026-07-06T13:28:05Z","publist_id":"5489","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"abstract":[{"text":"The computation of the winning set for one-pair Streett objectives and for k-pair Streett objectives in (standard) graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formed ness of specifications, and the synthesis of reactive systems. We give faster algorithms for the computation of the winning set for (1) one-pair Streett objectives (aka parity-3 problem) in game graphs and (2) for k-pair Streett objectives in graphs. For both problems this represents the first improvement in asymptotic running time in 15 years.","lang":"eng"}],"date_created":"2018-12-11T11:53:19Z","article_processing_charge":"No","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}],"quality_controlled":"1","related_material":{"record":[{"status":"public","id":"464","relation":"later_version"}]},"language":[{"iso":"eng"}],"volume":"2015-July","department":[{"_id":"KrCh"}],"publication_status":"published","month":"07","oa":1,"title":"Improved algorithms for one-pair and k-pair Streett objectives","main_file_link":[{"url":"https://eprints.cs.univie.ac.at/4368/","open_access":"1"}],"doi":"10.1109/LICS.2015.34","type":"conference","article_number":"7174888","conference":{"start_date":"2015-07-06","name":"LICS: Logic in Computer Science","end_date":"2015-07-10","location":"Kyoto, Japan"},"scopus_import":"1","publication":"Proceedings - Symposium on Logic in Computer Science","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Veronika","last_name":"Loitzenbauer","full_name":"Loitzenbauer, Veronika"}]},{"date_created":"2018-12-11T11:55:20Z","article_processing_charge":"No","project":[{"grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","page":"52 - 59","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"volume":115,"publication_status":"published","month":"01","oa":1,"title":"Probabilistic opacity for Markov decision processes","main_file_link":[{"url":"http://arxiv.org/abs/1407.4225","open_access":"1"}],"doi":"10.1016/j.ipl.2014.09.001","type":"journal_article","scopus_import":"1","publication":"Information Processing Letters","author":[{"last_name":"Bérard","full_name":"Bérard, Béatrice","first_name":"Béatrice"},{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Sznajder, Nathalie","last_name":"Sznajder","first_name":"Nathalie"}],"external_id":{"isi":["000345478700010"],"arxiv":["1407.4225"]},"issue":"1","intvolume":" 115","_id":"2034","status":"public","oa_version":"Preprint","arxiv":1,"day":"01","das_tickbox":"1","isi":1,"citation":{"short":"B. Bérard, K. Chatterjee, N. Sznajder, Information Processing Letters 115 (2015) 52–59.","mla":"Bérard, Béatrice, et al. “Probabilistic Opacity for Markov Decision Processes.” Information Processing Letters, vol. 115, no. 1, Elsevier, 2015, pp. 52–59, doi:10.1016/j.ipl.2014.09.001.","chicago":"Bérard, Béatrice, Krishnendu Chatterjee, and Nathalie Sznajder. “Probabilistic Opacity for Markov Decision Processes.” Information Processing Letters. Elsevier, 2015. https://doi.org/10.1016/j.ipl.2014.09.001.","apa":"Bérard, B., Chatterjee, K., & Sznajder, N. (2015). Probabilistic opacity for Markov decision processes. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2014.09.001","ieee":"B. Bérard, K. Chatterjee, and N. Sznajder, “Probabilistic opacity for Markov decision processes,” Information Processing Letters, vol. 115, no. 1. Elsevier, pp. 52–59, 2015.","ista":"Bérard B, Chatterjee K, Sznajder N. 2015. Probabilistic opacity for Markov decision processes. Information Processing Letters. 115(1), 52–59.","ama":"Bérard B, Chatterjee K, Sznajder N. Probabilistic opacity for Markov decision processes. Information Processing Letters. 2015;115(1):52-59. doi:10.1016/j.ipl.2014.09.001"},"year":"2015","publisher":"Elsevier","date_published":"2015-01-01T00:00:00Z","fulldoi":"https://doi.org/10.1016/j.ipl.2014.09.001","publist_id":"5025","date_updated":"2026-07-07T13:10:27Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.","lang":"eng"}],"ec_funded":1},{"OA_place":"repository","OA_type":"green","date_published":"2015-07-31T00:00:00Z","fulldoi":"https://doi.org/10.1109/LICS.2015.72","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"abstract":[{"text":"Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time. In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.","lang":"eng"}],"publist_id":"5494","date_updated":"2026-07-07T14:01:10Z","external_id":{"isi":["000380427100064"],"arxiv":["1606.03598"]},"isi":1,"arxiv":1,"day":"31","publisher":"IEEE","acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402-N23 (RiSE), Z211-N23 (Wittgenstein Award), FWF Grant No P23499- N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.\r\nA Technical Report of the paper is available at: \r\nhttps://repository.ist.ac.at/331/\r\n","citation":{"apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2015). Nested weighted automata. In Proceedings - Symposium on Logic in Computer Science (Vol. 2015–July). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.72","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Nested weighted automata,” in Proceedings - Symposium on Logic in Computer Science, Kyoto, Japan, 2015, vol. 2015–July.","ama":"Chatterjee K, Henzinger TA, Otop J. Nested weighted automata. In: Proceedings - Symposium on Logic in Computer Science. Vol 2015-July. IEEE; 2015. doi:10.1109/LICS.2015.72","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata. Proceedings - Symposium on Logic in Computer Science. LICS: Logic in Computer Science vol. 2015–July, 7174926.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.","mla":"Chatterjee, Krishnendu, et al. “Nested Weighted Automata.” Proceedings - Symposium on Logic in Computer Science, vol. 2015–July, 7174926, IEEE, 2015, doi:10.1109/LICS.2015.72.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Nested Weighted Automata.” In Proceedings - Symposium on Logic in Computer Science, Vol. 2015–July. IEEE, 2015. https://doi.org/10.1109/LICS.2015.72."},"year":"2015","status":"public","_id":"1656","oa_version":"Preprint","article_number":"7174926","oa":1,"title":"Nested weighted automata","type":"conference","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1606.03598"}],"doi":"10.1109/LICS.2015.72","publication":"Proceedings - Symposium on Logic in Computer Science","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A"},{"first_name":"Jan","full_name":"Otop, Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"conference":{"start_date":"2015-07-06","location":"Kyoto, Japan","name":"LICS: Logic in Computer Science","end_date":"2015-07-10"},"corr_author":"1","scopus_import":"1","project":[{"grant_number":"267989","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"grant_number":"S 11407_N23","call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems","grant_number":"Z211"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23"},{"grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","related_material":{"record":[{"id":"5415","relation":"earlier_version","status":"public"},{"relation":"earlier_version","id":"5436","status":"public"},{"status":"public","id":"467","relation":"later_version"}]},"article_processing_charge":"No","date_created":"2018-12-11T11:53:17Z","month":"07","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"volume":"2015-July"},{"status":"public","_id":"5436","oa_version":"Published Version","day":"24","publisher":"IST Austria","citation":{"ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, Nested weighted automata. IST Austria, 2015.","apa":"Chatterjee, K., Henzinger, T. A., & Otop, J. (2015). Nested weighted automata. IST Austria. https://doi.org/10.15479/AT:IST-2015-170-v2-2","ama":"Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria; 2015. doi:10.15479/AT:IST-2015-170-v2-2","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria, 29p.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. Nested Weighted Automata. IST Austria, 2015, doi:10.15479/AT:IST-2015-170-v2-2.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. Nested Weighted Automata. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-170-v2-2."},"year":"2015","file":[{"file_size":569991,"date_created":"2018-12-12T11:54:19Z","file_name":"IST-2015-170-v2+2_report.pdf","file_id":"5541","creator":"system","date_updated":"2020-07-14T12:46:54Z","content_type":"application/pdf","access_level":"open_access","checksum":"3c402f47d3669c28d04d1af405a08e3f","relation":"main_file"}],"alternative_title":["IST Austria Technical Report"],"date_updated":"2026-07-07T14:01:10Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:54Z","abstract":[{"text":"Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time.\r\nIn nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.","lang":"eng"}],"has_accepted_license":"1","date_published":"2015-04-24T00:00:00Z","ddc":["000"],"fulldoi":"https://doi.org/10.15479/AT:IST-2015-170-v2-2","page":"29","pubrep_id":"331","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"month":"04","date_created":"2018-12-12T11:39:19Z","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5415"},{"id":"1656","relation":"later_version","status":"public"},{"id":"467","relation":"later_version","status":"public"}]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop","first_name":"Jan"}],"oa":1,"title":"Nested weighted automata","publication_identifier":{"issn":["2664-1690"]},"type":"technical_report","doi":"10.15479/AT:IST-2015-170-v2-2"},{"date_published":"2015-07-15T00:00:00Z","fulldoi":"https://doi.org/10.1098/rspb.2015.1041","article_type":"original","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"text":"The competition for resources among cells, individuals or species is a fundamental characteristic of evolution. Biological all-pay auctions have been used to model situations where multiple individuals compete for a single resource. However, in many situations multiple resources with various values exist and single reward auctions are not applicable. We generalize the model to multiple rewards and study the evolution of strategies. In biological all-pay auctions the bid of an individual corresponds to its strategy and is equivalent to its payment in the auction. The decreasingly ordered rewards are distributed according to the decreasingly ordered bids of the participating individuals. The reproductive success of an individual is proportional to its fitness given by the sum of the rewards won minus its payments. Hence, successful bidding strategies spread in the population. We find that the results for the multiple reward case are very different from the single reward case. While the mixed strategy equilibrium in the single reward case with more than two players consists of mostly low-bidding individuals, we show that the equilibrium can convert to many high-bidding individuals and a few low-bidding individuals in the multiple reward case. Some reward values lead to a specialization among the individuals where one subpopulation competes for the rewards and the other subpopulation largely avoids costly competitions. Whether the mixed strategy equilibrium is an evolutionarily stable strategy (ESS) depends on the specific values of the rewards.","lang":"eng"}],"publist_id":"5425","date_updated":"2026-07-29T10:15:25Z","issue":"1812","external_id":{"isi":["000362305500021"],"pmid":["26180069"]},"intvolume":" 282","isi":1,"day":"15","publisher":"Royal Society","citation":{"chicago":"Reiter, Johannes, Ayush Kanodia, Raghav Gupta, Martin Nowak, and Krishnendu Chatterjee. “Biological Auctions with Multiple Rewards.” Proceedings of the Royal Society of London Series B Biological Sciences. Royal Society, 2015. https://doi.org/10.1098/rspb.2015.1041.","short":"J. Reiter, A. Kanodia, R. Gupta, M. Nowak, K. Chatterjee, Proceedings of the Royal Society of London Series B Biological Sciences 282 (2015).","mla":"Reiter, Johannes, et al. “Biological Auctions with Multiple Rewards.” Proceedings of the Royal Society of London Series B Biological Sciences, vol. 282, no. 1812, Royal Society, 2015, doi:10.1098/rspb.2015.1041.","ama":"Reiter J, Kanodia A, Gupta R, Nowak M, Chatterjee K. Biological auctions with multiple rewards. Proceedings of the Royal Society of London Series B Biological Sciences. 2015;282(1812). doi:10.1098/rspb.2015.1041","ista":"Reiter J, Kanodia A, Gupta R, Nowak M, Chatterjee K. 2015. Biological auctions with multiple rewards. Proceedings of the Royal Society of London Series B Biological Sciences. 282(1812).","ieee":"J. Reiter, A. Kanodia, R. Gupta, M. Nowak, and K. Chatterjee, “Biological auctions with multiple rewards,” Proceedings of the Royal Society of London Series B Biological Sciences, vol. 282, no. 1812. Royal Society, 2015.","apa":"Reiter, J., Kanodia, A., Gupta, R., Nowak, M., & Chatterjee, K. (2015). Biological auctions with multiple rewards. Proceedings of the Royal Society of London Series B Biological Sciences. Royal Society. https://doi.org/10.1098/rspb.2015.1041"},"year":"2015","acknowledgement":"This work was supported by grants from the John Templeton Foundation, ERC Start Grant (279307: Graph Games), FWF NFN Grant (No S11407N23 RiSE/SHiNE), FWF Grant (No P23499N23) and a Microsoft faculty fellows award.","_id":"1709","status":"public","oa_version":"Submitted Version","title":"Biological auctions with multiple rewards","oa":1,"pmid":1,"type":"journal_article","doi":"10.1098/rspb.2015.1041","main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4528522/","open_access":"1"}],"publication":"Proceedings of the Royal Society of London Series B Biological Sciences","author":[{"orcid":"0000-0002-0170-7353","first_name":"Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter","full_name":"Reiter, Johannes"},{"last_name":"Kanodia","full_name":"Kanodia, Ayush","first_name":"Ayush"},{"first_name":"Raghav","last_name":"Gupta","full_name":"Gupta, Raghav"},{"last_name":"Nowak","full_name":"Nowak, Martin","first_name":"Martin"},{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"}],"corr_author":"1","scopus_import":"1","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","related_material":{"record":[{"id":"1400","relation":"dissertation_contains","status":"public"}]},"article_processing_charge":"No","date_created":"2018-12-11T11:53:35Z","month":"07","publication_status":"published","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"volume":282},{"oa_version":"None","publication_status":"published","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"language":[{"iso":"eng"}],"_id":"1400","status":"public","page":"183","publisher":"Institute of Science and Technology Austria","citation":{"short":"J. Reiter, The Subclonal Evolution of Cancer, Institute of Science and Technology Austria, 2015.","mla":"Reiter, Johannes. The Subclonal Evolution of Cancer. Institute of Science and Technology Austria, 2015.","chicago":"Reiter, Johannes. “The Subclonal Evolution of Cancer.” Institute of Science and Technology Austria, 2015.","ieee":"J. Reiter, “The subclonal evolution of cancer,” Institute of Science and Technology Austria, 2015.","apa":"Reiter, J. (2015). The subclonal evolution of cancer. Institute of Science and Technology Austria.","ama":"Reiter J. The subclonal evolution of cancer. 2015.","ista":"Reiter J. 2015. The subclonal evolution of cancer. Institute of Science and Technology Austria."},"year":"2015","month":"04","supervisor":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"}],"day":"01","article_processing_charge":"No","date_created":"2018-12-11T11:51:48Z","related_material":{"record":[{"status":"public","id":"2000","relation":"part_of_dissertation"},{"id":"1709","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"2858","status":"public"},{"relation":"part_of_dissertation","id":"2816","status":"public"},{"status":"public","id":"2247","relation":"part_of_dissertation"},{"status":"public","relation":"part_of_dissertation","id":"3260"},{"status":"public","id":"3157","relation":"part_of_dissertation"}]},"degree_awarded":"PhD","alternative_title":["ISTA Thesis"],"publist_id":"5807","date_updated":"2026-07-29T10:15:25Z","corr_author":"1","author":[{"orcid":"0000-0002-0170-7353","first_name":"Johannes","full_name":"Reiter, Johannes","id":"4A918E98-F248-11E8-B48F-1D18A9856A87","last_name":"Reiter"}],"abstract":[{"lang":"eng","text":"Cancer results from an uncontrolled growth of abnormal cells. Sequentially accumulated genetic and epigenetic alterations decrease cell death and increase cell replication. We used mathematical models to quantify the effect of driver gene mutations. The recently developed targeted therapies can lead to dramatic regressions. However, in solid cancers, clinical responses are often short-lived because resistant cancer cells evolve. We estimated that approximately 50 different mutations can confer resistance to a typical targeted therapeutic agent. We find that resistant cells are likely to be present in expanded subclones before the start of the treatment. The dominant strategy to prevent the evolution of resistance is combination therapy. Our analytical results suggest that in most patients, dual therapy, but not monotherapy, can result in long-term disease control. However, long-term control can only occur if there are no possible mutations in the genome that can cause cross-resistance to both drugs. Furthermore, we showed that simultaneous therapy with two drugs is much more likely to result in long-term disease control than sequential therapy with the same drugs. To improve our understanding of the underlying subclonal evolution we reconstruct the evolutionary history of a patient's cancer from next-generation sequencing data of spatially-distinct DNA samples. Using a quantitative measure of genetic relatedness, we found that pancreatic cancers and their metastases demonstrated a higher level of relatedness than that expected for any two cells randomly taken from a normal tissue. This minimal amount of genetic divergence among advanced lesions indicates that genetic heterogeneity, when quantitatively defined, is not a fundamental feature of the natural history of untreated pancreatic cancers. Our newly developed, phylogenomic tool Treeomics finds evidence for seeding patterns of metastases and can directly be used to discover rules governing the evolution of solid malignancies to transform cancer into a more predictable disease."}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","type":"dissertation","date_published":"2015-04-01T00:00:00Z","title":"The subclonal evolution of cancer","publication_identifier":{"issn":["2663-337X"]},"doi_confirm":"1","OA_place":"publisher"},{"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","full_name":"Chmelik, Martin"},{"last_name":"Gupta","full_name":"Gupta, Raghav","first_name":"Raghav"},{"full_name":"Kanodia, Ayush","last_name":"Kanodia","first_name":"Ayush"}],"publication":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence ","scopus_import":"1","corr_author":"1","conference":{"end_date":"2015-01-30","name":"IAAI: Innovative Applications of Artificial Intelligence","location":"Austin, TX, USA","start_date":"2015-01-25"},"doi":"10.1609/aaai.v29i1.9683","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1411.3880"}],"type":"conference","oa":1,"title":"Optimal cost almost-sure reachability in POMDPs","month":"06","language":[{"iso":"eng"}],"volume":5,"department":[{"_id":"KrCh"}],"publication_status":"published","page":"3496-3502","quality_controlled":"1","related_material":{"record":[{"status":"public","id":"1529","relation":"later_version"}]},"project":[{"grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_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","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307"}],"date_created":"2018-12-11T11:54:11Z","article_processing_charge":"No","abstract":[{"text":"We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objec- tive we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present ap- proximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst- case running time of our algorithm is double exponential, we present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples.","lang":"eng"}],"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"5286","date_updated":"2026-08-19T09:31:47Z","alternative_title":["Artifical Intelligence"],"fulldoi":"https://doi.org/10.1609/aaai.v29i1.9683","date_published":"2015-06-01T00:00:00Z","citation":{"ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Optimal cost almost-sure reachability in POMDPs,” in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , Austin, TX, USA, 2015, vol. 5, pp. 3496–3502.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2015). Optimal cost almost-sure reachability in POMDPs. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (Vol. 5, pp. 3496–3502). Austin, TX, USA: AAAI Press. https://doi.org/10.1609/aaai.v29i1.9683","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Optimal cost almost-sure reachability in POMDPs. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence . IAAI: Innovative Applications of Artificial Intelligence, Artifical Intelligence, vol. 5, 3496–3502.","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. Optimal cost almost-sure reachability in POMDPs. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence . Vol 5. AAAI Press; 2015:3496-3502. doi:10.1609/aaai.v29i1.9683","mla":"Chatterjee, Krishnendu, et al. “Optimal Cost Almost-Sure Reachability in POMDPs.” Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , vol. 5, AAAI Press, 2015, pp. 3496–502, doi:10.1609/aaai.v29i1.9683.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , AAAI Press, 2015, pp. 3496–3502.","chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Optimal Cost Almost-Sure Reachability in POMDPs.” In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , 5:3496–3502. AAAI Press, 2015. https://doi.org/10.1609/aaai.v29i1.9683."},"acknowledgement":" The research was partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","year":"2015","publisher":"AAAI Press","day":"01","arxiv":1,"isi":1,"oa_version":"Preprint","status":"public","_id":"1820","intvolume":" 5","external_id":{"isi":["000372683700002"],"arxiv":["1411.3880"]}},{"date_updated":"2025-04-15T06:29:59Z","alternative_title":["LNCS"],"abstract":[{"text":"We revisit the parameterized model checking problem for token-passing systems and specifications in indexed CTL ∗ \\X. Emerson and Namjoshi (1995, 2003) have shown that parameterized model checking of indexed CTL ∗ \\X in uni-directional token rings can be reduced to checking rings up to some cutoff size. Clarke et al. (2004) have shown a similar result for general topologies and indexed LTL \\X, provided processes cannot choose the directions for sending or receiving the token.\r\nWe unify and substantially extend these results by systematically exploring fragments of indexed CTL ∗ \\X with respect to general topologies. For each fragment we establish whether a cutoff exists, and for some concrete topologies, such as rings, cliques and stars, we infer small cutoffs. Finally, we show that the problem becomes undecidable, and thus no cutoffs exist, if processes are allowed to choose the directions in which they send or from which they receive the token.","lang":"eng"}],"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1007/978-3-642-54013-4_15","date_published":"2014-01-30T00:00:00Z","oa_version":"Preprint","_id":"10884","status":"public","citation":{"short":"B. Aminof, S. Jacobs, A. Khalimov, S. Rubin, in:, Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 262–281.","mla":"Aminof, Benjamin, et al. “Parameterized Model Checking of Token-Passing Systems.” Verification, Model Checking, and Abstract Interpretation, vol. 8318, Springer Nature, 2014, pp. 262–81, doi:10.1007/978-3-642-54013-4_15.","chicago":"Aminof, Benjamin, Swen Jacobs, Ayrat Khalimov, and Sasha Rubin. “Parameterized Model Checking of Token-Passing Systems.” In Verification, Model Checking, and Abstract Interpretation, 8318:262–81. Springer Nature, 2014. https://doi.org/10.1007/978-3-642-54013-4_15.","ieee":"B. Aminof, S. Jacobs, A. Khalimov, and S. Rubin, “Parameterized model checking of token-passing systems,” in Verification, Model Checking, and Abstract Interpretation, San Diego, CA, United States, 2014, vol. 8318, pp. 262–281.","apa":"Aminof, B., Jacobs, S., Khalimov, A., & Rubin, S. (2014). Parameterized model checking of token-passing systems. In Verification, Model Checking, and Abstract Interpretation (Vol. 8318, pp. 262–281). San Diego, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-642-54013-4_15","ama":"Aminof B, Jacobs S, Khalimov A, Rubin S. Parameterized model checking of token-passing systems. In: Verification, Model Checking, and Abstract Interpretation. Vol 8318. Springer Nature; 2014:262-281. doi:10.1007/978-3-642-54013-4_15","ista":"Aminof B, Jacobs S, Khalimov A, Rubin S. 2014. Parameterized model checking of token-passing systems. Verification, Model Checking, and Abstract Interpretation. VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318, 262–281."},"acknowledgement":"This work was supported by the Austrian Science Fund through grant P23499-N23\r\nand through the RiSE network (S11403, S11405, S11406, S11407-N23); ERC Starting Grant (279307: Graph Games); Vienna Science and Technology Fund (WWTF)\r\ngrants PROSEED, ICT12-059, and VRG11-005.","year":"2014","publisher":"Springer Nature","arxiv":1,"day":"30","intvolume":" 8318","external_id":{"arxiv":["1311.4425"]},"scopus_import":"1","conference":{"location":"San Diego, CA, United States","name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","end_date":"2014-01-21","start_date":"2014-01-19"},"author":[{"full_name":"Aminof, Benjamin","last_name":"Aminof","id":"4A55BD00-F248-11E8-B48F-1D18A9856A87","first_name":"Benjamin"},{"last_name":"Jacobs","full_name":"Jacobs, Swen","first_name":"Swen"},{"full_name":"Khalimov, Ayrat","last_name":"Khalimov","first_name":"Ayrat"},{"first_name":"Sasha","last_name":"Rubin","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","full_name":"Rubin, Sasha"}],"publication":"Verification, Model Checking, and Abstract Interpretation","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.1311.4425"}],"doi":"10.1007/978-3-642-54013-4_15","type":"conference","publication_identifier":{"issn":["0302-9743"],"eisbn":["9783642540134"],"eissn":["1611-3349"],"isbn":["9783642540127"]},"oa":1,"title":"Parameterized model checking of token-passing systems","volume":8318,"department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"publication_status":"published","page":"262-281","month":"01","date_created":"2022-03-18T13:01:22Z","article_processing_charge":"No","quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23"},{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"}]},{"external_id":{"arxiv":["1311.3238"]},"intvolume":" 8318","_id":"10885","status":"public","oa_version":"Preprint","arxiv":1,"day":"30","acknowledgement":" Supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No\r\nS11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.","citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, Emmanuel Filiot, and Jean-François Raskin. “Doomsday Equilibria for Omega-Regular Games.” In VMCAI 2014: Verification, Model Checking, and Abstract Interpretation, 8318:78–97. Springer Nature, 2014. https://doi.org/10.1007/978-3-642-54013-4_5.","mla":"Chatterjee, Krishnendu, et al. “Doomsday Equilibria for Omega-Regular Games.” VMCAI 2014: Verification, Model Checking, and Abstract Interpretation, vol. 8318, Springer Nature, 2014, pp. 78–97, doi:10.1007/978-3-642-54013-4_5.","short":"K. Chatterjee, L. Doyen, E. Filiot, J.-F. Raskin, in:, VMCAI 2014: Verification, Model Checking, and Abstract Interpretation, Springer Nature, 2014, pp. 78–97.","ista":"Chatterjee K, Doyen L, Filiot E, Raskin J-F. 2014. Doomsday equilibria for omega-regular games. VMCAI 2014: Verification, Model Checking, and Abstract Interpretation. VMCAI: Verifcation, Model Checking, and Abstract Interpretation, LNCS, vol. 8318, 78–97.","ama":"Chatterjee K, Doyen L, Filiot E, Raskin J-F. Doomsday equilibria for omega-regular games. In: VMCAI 2014: Verification, Model Checking, and Abstract Interpretation. Vol 8318. Springer Nature; 2014:78-97. doi:10.1007/978-3-642-54013-4_5","ieee":"K. Chatterjee, L. Doyen, E. Filiot, and J.-F. Raskin, “Doomsday equilibria for omega-regular games,” in VMCAI 2014: Verification, Model Checking, and Abstract Interpretation, San Diego, CA, United States, 2014, vol. 8318, pp. 78–97.","apa":"Chatterjee, K., Doyen, L., Filiot, E., & Raskin, J.-F. (2014). Doomsday equilibria for omega-regular games. In VMCAI 2014: Verification, Model Checking, and Abstract Interpretation (Vol. 8318, pp. 78–97). San Diego, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-642-54013-4_5"},"year":"2014","publisher":"Springer Nature","OA_type":"green","date_published":"2014-01-30T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-642-54013-4_5","OA_place":"repository","date_updated":"2026-04-16T10:00:03Z","alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"abstract":[{"lang":"eng","text":"Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information games.\r\nIn this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile such that all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players objective, then the objective of every player is violated.\r\nWe present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω-regular objectives, both for imperfect-information games, and for perfect-information games.We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games."}],"date_created":"2022-03-18T13:03:15Z","article_processing_charge":"No","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","grant_number":"P 23499-N23"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"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"}],"related_material":{"record":[{"status":"public","id":"681","relation":"later_version"}]},"quality_controlled":"1","page":"78-97","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"volume":8318,"publication_status":"published","month":"01","publication_identifier":{"issn":["0302-9743"],"isbn":["9783642540127"],"eisbn":["9783642540134"],"eissn":["1611-3349"]},"oa":1,"title":"Doomsday equilibria for omega-regular games","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1311.3238","open_access":"1"}],"doi":"10.1007/978-3-642-54013-4_5","type":"conference","conference":{"end_date":"2014-01-21","name":"VMCAI: Verifcation, Model Checking, and Abstract Interpretation","location":"San Diego, CA, United States","start_date":"2014-01-19"},"scopus_import":"1","publication":"VMCAI 2014: Verification, Model Checking, and Abstract Interpretation","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"first_name":"Laurent","last_name":"Doyen","full_name":"Doyen, Laurent"},{"first_name":"Emmanuel","last_name":"Filiot","full_name":"Filiot, Emmanuel"},{"first_name":"Jean-François","full_name":"Raskin, Jean-François","last_name":"Raskin"}]},{"date_published":"2014-04-01T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-642-54830-7_14","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"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). We present an algorithm running in time O(d·n2d·MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2 1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective). "}],"publist_id":"4758","alternative_title":["LNCS"],"date_updated":"2023-02-23T12:24:50Z","intvolume":" 8412","day":"01","publisher":"Springer","year":"2014","citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. “Perfect-Information Stochastic Mean-Payoff Parity Games,” 8412:210–25. Springer, 2014. https://doi.org/10.1007/978-3-642-54830-7_14.","short":"K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, in:, Springer, 2014, pp. 210–225.","mla":"Chatterjee, Krishnendu, et al. Perfect-Information Stochastic Mean-Payoff Parity Games. Vol. 8412, Springer, 2014, pp. 210–25, doi:10.1007/978-3-642-54830-7_14.","ama":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. Perfect-information stochastic mean-payoff parity games. In: Vol 8412. Springer; 2014:210-225. doi:10.1007/978-3-642-54830-7_14","ista":"Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2014. Perfect-information stochastic mean-payoff parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 8412, 210–225.","ieee":"K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, “Perfect-information stochastic mean-payoff parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France, 2014, vol. 8412, pp. 210–225.","apa":"Chatterjee, K., Doyen, L., Gimbert, H., & Oualhadj, Y. (2014). Perfect-information stochastic mean-payoff parity games (Vol. 8412, pp. 210–225). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France: Springer. https://doi.org/10.1007/978-3-642-54830-7_14"},"acknowledgement":"This research was supported by European project Cassting (FP7-601148).\r\nA Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/128.","status":"public","_id":"2212","oa_version":"None","title":"Perfect-information stochastic mean-payoff parity games","type":"conference","doi":"10.1007/978-3-642-54830-7_14","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"first_name":"Laurent","full_name":"Doyen, Laurent","last_name":"Doyen"},{"last_name":"Gimbert","full_name":"Gimbert, Hugo","first_name":"Hugo"},{"first_name":"Youssouf","full_name":"Oualhadj, Youssouf","last_name":"Oualhadj"}],"conference":{"name":"FoSSaCS: Foundations of Software Science and Computation Structures","end_date":"2014-04-13","location":"Grenoble, France","start_date":"2014-04-05"},"scopus_import":1,"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"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"related_material":{"record":[{"id":"5405","relation":"earlier_version","status":"public"}]},"quality_controlled":"1","date_created":"2018-12-11T11:56:21Z","month":"04","page":"210 - 225","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"volume":8412},{"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5408"}]},"quality_controlled":"1","project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S11407"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"date_created":"2018-12-11T11:56:21Z","month":"04","publication_status":"published","volume":8412,"language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"page":"242 - 257","type":"conference","main_file_link":[{"url":"http://arxiv.org/abs/1401.3289","open_access":"1"}],"doi":"10.1007/978-3-642-54830-7_16","oa":1,"title":"The complexity of partial-observation stochastic parity games with finite-memory strategies","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"},{"first_name":"Sumit","full_name":"Nain, Sumit","last_name":"Nain"},{"first_name":"Moshe","full_name":"Vardi, Moshe","last_name":"Vardi"}],"scopus_import":1,"conference":{"location":"Grenoble, France","end_date":"2014-04-13","name":"FoSSaCS: Foundations of Software Science and Computation Structures","start_date":"2014-04-05"},"intvolume":" 8412","external_id":{"arxiv":["1401.3289"]},"publisher":"Springer","acknowledgement":"This research was supported by European project Cassting (FP7-601148), NSF grants CNS 1049862 and CCF-1139011, by NSF Expe ditions in Computing project “ExCAPE: Expeditions in Computer Augmented Program Engineering”, by BSF grant 9800096, and by gift from Intel.","year":"2014","citation":{"short":"K. Chatterjee, L. Doyen, S. Nain, M. Vardi, in:, Springer, 2014, pp. 242–257.","mla":"Chatterjee, Krishnendu, et al. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. Vol. 8412, Springer, 2014, pp. 242–57, doi:10.1007/978-3-642-54830-7_16.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. “The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies,” 8412:242–57. Springer, 2014. https://doi.org/10.1007/978-3-642-54830-7_16.","apa":"Chatterjee, K., Doyen, L., Nain, S., & Vardi, M. (2014). The complexity of partial-observation stochastic parity games with finite-memory strategies (Vol. 8412, pp. 242–257). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France: Springer. https://doi.org/10.1007/978-3-642-54830-7_16","ieee":"K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, “The complexity of partial-observation stochastic parity games with finite-memory strategies,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Grenoble, France, 2014, vol. 8412, pp. 242–257.","ista":"Chatterjee K, Doyen L, Nain S, Vardi M. 2014. The complexity of partial-observation stochastic parity games with finite-memory strategies. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 8412, 242–257.","ama":"Chatterjee K, Doyen L, Nain S, Vardi M. The complexity of partial-observation stochastic parity games with finite-memory strategies. In: Vol 8412. Springer; 2014:242-257. doi:10.1007/978-3-642-54830-7_16"},"day":"01","arxiv":1,"oa_version":"Preprint","status":"public","_id":"2213","fulldoi":"https://doi.org/10.1007/978-3-642-54830-7_16","date_published":"2014-04-01T00:00:00Z","ec_funded":1,"abstract":[{"lang":"eng","text":"We consider two-player partial-observation stochastic games on finitestate graphs where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are ε-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). These qualitative-analysis problems are known to be undecidable. However in many applications the relevant question is the existence of finite-memory strategies, and the qualitative-analysis problems under finite-memory strategies was recently shown to be decidable in 2EXPTIME.We improve the complexity and show that the qualitative-analysis problems for partial-observation stochastic parity games under finite-memory strategies are EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"date_updated":"2023-02-23T12:24:58Z","publist_id":"4757"},{"quality_controlled":"1","related_material":{"record":[{"id":"5409","relation":"earlier_version","status":"public"}]},"date_created":"2018-12-11T11:56:22Z","day":"01","month":"01","year":"2014","citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Majumdar R. Edit distance for timed automata. In: Springer; 2014:303-312. doi:10.1145/2562059.2562141","ista":"Chatterjee K, Ibsen-Jensen R, Majumdar R. 2014. Edit distance for timed automata. HSCC: Hybrid Systems - Computation and Control, 303–312.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, “Edit distance for timed automata,” presented at the HSCC: Hybrid Systems - Computation and Control, Berlin, Germany, 2014, pp. 303–312.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Majumdar, R. (2014). Edit distance for timed automata (pp. 303–312). Presented at the HSCC: Hybrid Systems - Computation and Control, Berlin, Germany: Springer. https://doi.org/10.1145/2562059.2562141","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Ritankar Majumdar. “Edit Distance for Timed Automata,” 303–12. Springer, 2014. https://doi.org/10.1145/2562059.2562141.","short":"K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, in:, Springer, 2014, pp. 303–312.","mla":"Chatterjee, Krishnendu, et al. Edit Distance for Timed Automata. Springer, 2014, pp. 303–12, doi:10.1145/2562059.2562141."},"publisher":"Springer","status":"public","_id":"2216","page":"303 - 312","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"publication_status":"published","oa_version":"Submitted Version","date_published":"2014-01-01T00:00:00Z","oa":1,"title":"Edit distance for timed automata","doi":"10.1145/2562059.2562141","fulldoi":"https://doi.org/10.1145/2562059.2562141","main_file_link":[{"open_access":"1","url":"https://dl.acm.org/citation.cfm?doid=2562059.2562141"}],"type":"conference","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","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. In 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 time stamps. 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 δ away from the parameter, for δ > 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 analogous decidability results hold for rectangular automata."}],"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus"},{"full_name":"Majumdar, Ritankar","last_name":"Majumdar","first_name":"Ritankar"}],"date_updated":"2024-10-21T06:02:53Z","publist_id":"4752","conference":{"start_date":"2017-04-15","name":"HSCC: Hybrid Systems - Computation and Control","end_date":"2017-04-17","location":"Berlin, Germany"},"scopus_import":"1"},{"quality_controlled":"1","date_created":"2018-12-11T11:56:33Z","article_processing_charge":"No","month":"02","volume":521,"department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"publication_status":"published","page":"73 - 91","doi":"10.1016/j.tcs.2013.11.032","main_file_link":[{"url":"http://arxiv.org/abs/1303.3777","open_access":"1"}],"type":"journal_article","publication_identifier":{"issn":["0304-3975"]},"oa":1,"title":"Alternating traps in Muller and parity games","author":[{"first_name":"Andrey","full_name":"Grinshpun, Andrey","last_name":"Grinshpun"},{"first_name":"Pakawat","full_name":"Phalitnonkiat, Pakawat","last_name":"Phalitnonkiat"},{"full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","last_name":"Rubin","first_name":"Sasha"},{"last_name":"Tarfulea","full_name":"Tarfulea, Andrei","first_name":"Andrei"}],"publication":"Theoretical Computer Science","scopus_import":"1","corr_author":"1","intvolume":" 521","external_id":{"isi":["000331433100007"],"arxiv":["1303.3777"]},"year":"2014","citation":{"chicago":"Grinshpun, Andrey, Pakawat Phalitnonkiat, Sasha Rubin, and Andrei Tarfulea. “Alternating Traps in Muller and Parity Games.” Theoretical Computer Science. Elsevier, 2014. https://doi.org/10.1016/j.tcs.2013.11.032.","mla":"Grinshpun, Andrey, et al. “Alternating Traps in Muller and Parity Games.” Theoretical Computer Science, vol. 521, Elsevier, 2014, pp. 73–91, doi:10.1016/j.tcs.2013.11.032.","short":"A. Grinshpun, P. Phalitnonkiat, S. Rubin, A. Tarfulea, Theoretical Computer Science 521 (2014) 73–91.","ama":"Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. Alternating traps in Muller and parity games. Theoretical Computer Science. 2014;521:73-91. doi:10.1016/j.tcs.2013.11.032","ista":"Grinshpun A, Phalitnonkiat P, Rubin S, Tarfulea A. 2014. Alternating traps in Muller and parity games. Theoretical Computer Science. 521, 73–91.","apa":"Grinshpun, A., Phalitnonkiat, P., Rubin, S., & Tarfulea, A. (2014). Alternating traps in Muller and parity games. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2013.11.032","ieee":"A. Grinshpun, P. Phalitnonkiat, S. Rubin, and A. Tarfulea, “Alternating traps in Muller and parity games,” Theoretical Computer Science, vol. 521. Elsevier, pp. 73–91, 2014."},"publisher":"Elsevier","day":"13","arxiv":1,"isi":1,"oa_version":"Submitted Version","status":"public","_id":"2246","fulldoi":"https://doi.org/10.1016/j.tcs.2013.11.032","date_published":"2014-02-13T00:00:00Z","abstract":[{"lang":"eng","text":"Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth. "}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","date_updated":"2026-04-16T10:08:15Z","publist_id":"4703"},{"intvolume":" 61","issue":"3","external_id":{"isi":["000337201400001"]},"oa_version":"Submitted Version","_id":"2141","status":"public","publisher":"ACM","year":"2014","citation":{"chicago":"Chatterjee, Krishnendu, and Monika Henzinger. “Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.” Journal of the ACM. ACM, 2014. https://doi.org/10.1145/2597631.","short":"K. Chatterjee, M. Henzinger, Journal of the ACM 61 (2014).","mla":"Chatterjee, Krishnendu, and Monika Henzinger. “Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition.” Journal of the ACM, vol. 61, no. 3, a15, ACM, 2014, doi:10.1145/2597631.","ama":"Chatterjee K, Henzinger M. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. 2014;61(3). doi:10.1145/2597631","ista":"Chatterjee K, Henzinger M. 2014. Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. 61(3), a15.","ieee":"K. Chatterjee and M. Henzinger, “Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition,” Journal of the ACM, vol. 61, no. 3. ACM, 2014.","apa":"Chatterjee, K., & Henzinger, M. (2014). Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. Journal of the ACM. ACM. https://doi.org/10.1145/2597631"},"isi":1,"day":"01","fulldoi":"https://doi.org/10.1145/2597631","date_published":"2014-05-01T00:00:00Z","date_updated":"2025-09-29T11:45:13Z","publist_id":"4883","abstract":[{"lang":"eng","text":"The computation of the winning set for Büchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound for solving the problem is Õ(n ⋅ m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n ⋅ m) boundary by presenting a new technique that reduces the running time to O(n2). This bound also leads to O(n2)-time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n ⋅ m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m>n4/3 an earlier bound of O(m ⋅ √m)). We then show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. Our algorithms are the first dynamic algorithms for this problem. We then consider another core graph theoretic problem in verification of probabilistic systems, namely computing the maximal end-component decomposition of a graph. We present two improved static algorithms for the maximal end-component decomposition problem. Our first algorithm is an O(m ⋅ √m)-time algorithm, and our second algorithm is an O(n2)-time algorithm which is obtained using the same technique as for alternating Büchi games. Thus, we obtain an O(min &lcu;m ⋅ √m,n2})-time algorithm improving the long-standing O(n ⋅ m) time bound. Finally, we show how to maintain the maximal end-component decomposition of a graph under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time per edge insertion. Again, our algorithms are the first dynamic algorithms for this problem."}],"ec_funded":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","date_created":"2018-12-11T11:55:57Z","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"3165"}]},"quality_controlled":"1","project":[{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"call_identifier":"FWF","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"volume":61,"month":"05","type":"journal_article","doi":"10.1145/2597631","main_file_link":[{"open_access":"1","url":"https://eprints.cs.univie.ac.at/3933/"}],"oa":1,"title":"Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition","article_number":"a15","scopus_import":"1","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H"}],"publication":"Journal of the ACM"},{"month":"01","volume":8573,"language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"publication_status":"published","page":"122 - 133","quality_controlled":"1","related_material":{"record":[{"status":"public","id":"5404","relation":"earlier_version"}]},"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"call_identifier":"FWF","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"date_created":"2018-12-11T11:56:04Z","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","first_name":"Rasmus"}],"scopus_import":"1","corr_author":"1","conference":{"location":"Copenhagen, Denmark","end_date":"2014-07-11","name":"ICST: International Conference on Software Testing, Verification and Validation","start_date":"2014-07-08"},"doi":"10.1007/978-3-662-43951-7_11","main_file_link":[{"url":"http://arxiv.org/abs/1404.5734","open_access":"1"}],"type":"conference","oa":1,"title":"The complexity of ergodic mean payoff games","citation":{"chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “The Complexity of Ergodic Mean Payoff Games,” 8573:122–33. Springer, 2014. https://doi.org/10.1007/978-3-662-43951-7_11.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Mean Payoff Games. Vol. 8573, no. Part 2, Springer, 2014, pp. 122–33, doi:10.1007/978-3-662-43951-7_11.","short":"K. Chatterjee, R. Ibsen-Jensen, in:, Springer, 2014, pp. 122–133.","ista":"Chatterjee K, Ibsen-Jensen R. 2014. The complexity of ergodic mean payoff games. ICST: International Conference on Software Testing, Verification and Validation, LNCS, vol. 8573, 122–133.","ama":"Chatterjee K, Ibsen-Jensen R. The complexity of ergodic mean payoff games. In: Vol 8573. Springer; 2014:122-133. doi:10.1007/978-3-662-43951-7_11","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2014). The complexity of ergodic mean payoff games (Vol. 8573, pp. 122–133). Presented at the ICST: International Conference on Software Testing, Verification and Validation, Copenhagen, Denmark: Springer. https://doi.org/10.1007/978-3-662-43951-7_11","ieee":"K. Chatterjee and R. Ibsen-Jensen, “The complexity of ergodic mean payoff games,” presented at the ICST: International Conference on Software Testing, Verification and Validation, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 122–133."},"year":"2014","publisher":"Springer","day":"01","arxiv":1,"oa_version":"Preprint","status":"public","_id":"2162","intvolume":" 8573","external_id":{"arxiv":["1404.5734"]},"issue":"Part 2","abstract":[{"lang":"eng","text":"We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state 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 lies in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP ∩ coNP is the long-standing best known bound). We present a variant of the strategy-iteration algorithm by Hoffman and Karp; show that both our algorithm and the classical value-iteration algorithm can approximate the value in exponential time; and identify a subclass where the value-iteration algorithm is a FPTAS. We also show that the exact value can be expressed in the existential theory of the reals, and establish square-root sum hardness for a related class of games."}],"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"4822","alternative_title":["LNCS"],"date_updated":"2024-10-21T06:02:53Z","fulldoi":"https://doi.org/10.1007/978-3-662-43951-7_11","date_published":"2014-01-01T00:00:00Z"},{"issue":"Part 2","external_id":{"arxiv":["1404.5453"]},"intvolume":" 8573","_id":"2163","status":"public","oa_version":"Preprint","arxiv":1,"day":"01","publisher":"Springer","year":"2014","acknowledgement":"This research was partly supported by European project Cassting (FP7-601148).\r\nTechnical Report under https://research-explorer.app.ist.ac.at/record/5418\r\n","citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” In Lecture Notes in Computer Science, 8573:110–21. Springer, 2014. https://doi.org/10.1007/978-3-662-43951-7_10.","short":"K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer, 2014, pp. 110–121.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” Lecture Notes in Computer Science, vol. 8573, no. Part 2, Springer, 2014, pp. 110–21, doi:10.1007/978-3-662-43951-7_10.","ista":"Chatterjee K, Doyen L. 2014. Games with a weak adversary. Lecture Notes in Computer Science. ICALP: Automata, Languages and Programming, LNCS, vol. 8573, 110–121.","ama":"Chatterjee K, Doyen L. Games with a weak adversary. In: Lecture Notes in Computer Science. Vol 8573. Springer; 2014:110-121. doi:10.1007/978-3-662-43951-7_10","apa":"Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary. In Lecture Notes in Computer Science (Vol. 8573, pp. 110–121). Copenhagen, Denmark: Springer. https://doi.org/10.1007/978-3-662-43951-7_10","ieee":"K. Chatterjee and L. Doyen, “Games with a weak adversary,” in Lecture Notes in Computer Science, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 110–121."},"date_published":"2014-01-01T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-662-43951-7_10","alternative_title":["LNCS"],"publist_id":"4821","date_updated":"2024-10-21T06:02:54Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"abstract":[{"text":"We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable in general, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. From our results we derive new complexity results for partial-observation stochastic games.","lang":"eng"}],"date_created":"2018-12-11T11:56:04Z","project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"grant_number":"S11407","call_identifier":"FWF","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5418"}]},"page":"110 - 121","publication_status":"published","department":[{"_id":"KrCh"}],"volume":8573,"language":[{"iso":"eng"}],"month":"01","oa":1,"title":"Games with a weak adversary","type":"conference","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1404.5453"}],"doi":"10.1007/978-3-662-43951-7_10","conference":{"name":"ICALP: Automata, Languages and Programming","end_date":"2014-07-11","location":"Copenhagen, Denmark","start_date":"2014-07-08"},"scopus_import":"1","publication":"Lecture Notes in Computer Science","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"last_name":"Doyen","full_name":"Doyen, Laurent","first_name":"Laurent"}]},{"month":"06","page":"193 - 220","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"volume":51,"language":[{"iso":"eng"}],"pubrep_id":"71","publication_status":"published","project":[{"call_identifier":"FWF","_id":"25F5A88A-B435-11E9-9278-68D0E5697425","name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23"},{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"},{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","call_identifier":"FP7"}],"quality_controlled":"1","date_created":"2018-12-11T11:56:13Z","article_processing_charge":"No","publication":"Acta Informatica","author":[{"last_name":"Bloem","full_name":"Bloem, Roderick","first_name":"Roderick"},{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Greimel, Karin","last_name":"Greimel","first_name":"Karin"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724"},{"first_name":"Georg","last_name":"Hofferek","full_name":"Hofferek, Georg"},{"full_name":"Jobstmann, Barbara","last_name":"Jobstmann","first_name":"Barbara"},{"last_name":"Könighofer","full_name":"Könighofer, Bettina","first_name":"Bettina"},{"last_name":"Könighofer","full_name":"Könighofer, Robert","first_name":"Robert"}],"scopus_import":"1","title":"Synthesizing robust systems","oa":1,"doi":"10.1007/s00236-013-0191-5","type":"journal_article","day":"01","isi":1,"citation":{"ieee":"R. Bloem et al., “Synthesizing robust systems,” Acta Informatica, vol. 51, no. 3–4. Springer, pp. 193–220, 2014.","apa":"Bloem, R., Chatterjee, K., Greimel, K., Henzinger, T. A., Hofferek, G., Jobstmann, B., … Könighofer, R. (2014). Synthesizing robust systems. Acta Informatica. Springer. https://doi.org/10.1007/s00236-013-0191-5","ama":"Bloem R, Chatterjee K, Greimel K, et al. Synthesizing robust systems. Acta Informatica. 2014;51(3-4):193-220. doi:10.1007/s00236-013-0191-5","ista":"Bloem R, Chatterjee K, Greimel K, Henzinger TA, Hofferek G, Jobstmann B, Könighofer B, Könighofer R. 2014. Synthesizing robust systems. Acta Informatica. 51(3–4), 193–220.","mla":"Bloem, Roderick, et al. “Synthesizing Robust Systems.” Acta Informatica, vol. 51, no. 3–4, Springer, 2014, pp. 193–220, doi:10.1007/s00236-013-0191-5.","short":"R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, G. Hofferek, B. Jobstmann, B. Könighofer, R. Könighofer, Acta Informatica 51 (2014) 193–220.","chicago":"Bloem, Roderick, Krishnendu Chatterjee, Karin Greimel, Thomas A Henzinger, Georg Hofferek, Barbara Jobstmann, Bettina Könighofer, and Robert Könighofer. “Synthesizing Robust Systems.” Acta Informatica. Springer, 2014. https://doi.org/10.1007/s00236-013-0191-5."},"year":"2014","publisher":"Springer","status":"public","_id":"2187","oa_version":"Submitted Version","external_id":{"isi":["000335981500004"]},"issue":"3-4","file":[{"file_size":169523,"date_created":"2018-12-12T10:16:44Z","file_name":"IST-2012-71-v1+1_Synthesizing_robust_systems.pdf","file_id":"5234","creator":"system","date_updated":"2020-07-14T12:45:31Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"d7f560f3d923f0f00aa10a0652f83273"}],"intvolume":" 51","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file_date_updated":"2020-07-14T12:45:31Z","ec_funded":1,"abstract":[{"text":"Systems should not only be correct but also robust in the sense that they behave reasonably in unexpected situations. This article addresses synthesis of robust reactive systems from temporal specifications. Existing methods allow arbitrary behavior if assumptions in the specification are violated. To overcome this, we define two robustness notions, combine them, and show how to enforce them in synthesis. The first notion applies to safety properties: If safety assumptions are violated temporarily, we require that the system recovers to normal operation with as few errors as possible. The second notion requires that, if liveness assumptions are violated, as many guarantees as possible should be fulfilled nevertheless. We present a synthesis procedure achieving this for the important class of GR(1) specifications, and establish complexity bounds. We also present an implementation of a special case of robustness, and show experimental results.","lang":"eng"}],"publist_id":"4787","date_updated":"2025-09-29T11:32:51Z","ddc":["621"],"has_accepted_license":"1","date_published":"2014-06-01T00:00:00Z","article_type":"original","fulldoi":"https://doi.org/10.1007/s00236-013-0191-5"},{"external_id":{"arxiv":["1402.3388"]},"intvolume":" 8559","status":"public","_id":"2190","oa_version":"Submitted Version","day":"01","arxiv":1,"acknowledgement":"The author is on leave from Faculty of Informatics, Masaryk University, Czech Republic, and partially supported by the Czech Science Foundation, grant No. P202/12/G061.","year":"2014","citation":{"ieee":"J. Esparza and J. Kretinsky, “From LTL to deterministic automata: A safraless compositional approach,” presented at the CAV: Computer Aided Verification, 2014, vol. 8559, pp. 192–208.","apa":"Esparza, J., & Kretinsky, J. (2014). From LTL to deterministic automata: A safraless compositional approach (Vol. 8559, pp. 192–208). Presented at the CAV: Computer Aided Verification, Springer. https://doi.org/10.1007/978-3-319-08867-9_13","ista":"Esparza J, Kretinsky J. 2014. From LTL to deterministic automata: A safraless compositional approach. CAV: Computer Aided Verification, LNCS, vol. 8559, 192–208.","ama":"Esparza J, Kretinsky J. From LTL to deterministic automata: A safraless compositional approach. In: Vol 8559. Springer; 2014:192-208. doi:10.1007/978-3-319-08867-9_13","mla":"Esparza, Javier, and Jan Kretinsky. From LTL to Deterministic Automata: A Safraless Compositional Approach. Vol. 8559, Springer, 2014, pp. 192–208, doi:10.1007/978-3-319-08867-9_13.","short":"J. Esparza, J. Kretinsky, in:, Springer, 2014, pp. 192–208.","chicago":"Esparza, Javier, and Jan Kretinsky. “From LTL to Deterministic Automata: A Safraless Compositional Approach,” 8559:192–208. Springer, 2014. https://doi.org/10.1007/978-3-319-08867-9_13."},"publisher":"Springer","date_published":"2014-01-01T00:00:00Z","fulldoi":"https://doi.org/10.1007/978-3-319-08867-9_13","date_updated":"2025-06-11T08:01:04Z","publist_id":"4784","alternative_title":["LNCS"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We present a new algorithm to construct a (generalized) deterministic Rabin automaton for an LTL formula φ. The automaton is the product of a master automaton and an array of slave automata, one for each G-subformula of φ. The slave automaton for G ψ is in charge of recognizing whether FG ψ holds. As opposed to standard determinization procedures, the states of all our automata have a clear logical structure, which allows for various optimizations. Our construction subsumes former algorithms for fragments of LTL. Experimental results show improvement in the sizes of the resulting automata compared to existing methods."}],"ec_funded":1,"date_created":"2018-12-11T11:56:14Z","article_processing_charge":"No","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"grant_number":"S11402-N23","call_identifier":"FWF","name":"Moderne Concurrency Paradigms","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","page":"192 - 208","language":[{"iso":"eng"}],"volume":8559,"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"publication_status":"published","month":"01","oa":1,"title":"From LTL to deterministic automata: A safraless compositional approach","main_file_link":[{"url":"http://arxiv.org/abs/1402.3388","open_access":"1"}],"doi":"10.1007/978-3-319-08867-9_13","type":"conference","corr_author":"1","conference":{"name":"CAV: Computer Aided Verification"},"scopus_import":"1","author":[{"first_name":"Javier","full_name":"Esparza, Javier","last_name":"Esparza"},{"last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan","orcid":"0000-0002-8122-2881","first_name":"Jan"}]}]