[{"ec_funded":1,"publist_id":"5489","article_number":"7174888","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Loitzenbauer, Veronika","first_name":"Veronika","last_name":"Loitzenbauer"}],"related_material":{"record":[{"id":"464","status":"public","relation":"later_version"}]},"date_updated":"2023-02-23T12:20:05Z","date_created":"2018-12-11T11:53:19Z","volume":"2015-July","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.","publication_status":"published","publisher":"IEEE","department":[{"_id":"KrCh"}],"month":"07","conference":{"name":"LICS: Logic in Computer Science","location":"Kyoto, Japan","start_date":"2015-07-06","end_date":"2015-07-10"},"doi":"10.1109/LICS.2015.34","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://eprints.cs.univie.ac.at/4368/","open_access":"1"}],"quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"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"}],"type":"conference","oa_version":"Submitted Version","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","_id":"1661","status":"public","title":"Improved algorithms for one-pair and k-pair Streett objectives","day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2015-07-01T00:00:00Z","publication":"Proceedings - Symposium on Logic in Computer Science","citation":{"short":"K. Chatterjee, M.H. Henzinger, V. Loitzenbauer, in:, Proceedings - Symposium on Logic in Computer Science, IEEE, 2015.","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.","chicago":"Chatterjee, Krishnendu, Monika H 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.","ama":"Chatterjee K, Henzinger MH, 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","apa":"Chatterjee, K., Henzinger, M. H., & 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. H. 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 MH, 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."}},{"publisher":"Ecole Polytechnique","department":[{"_id":"RoSe"}],"publication_status":"published","year":"2015","volume":2,"date_updated":"2021-01-12T08:00:52Z","date_created":"2018-12-11T11:46:40Z","author":[{"full_name":"Lewin, Mathieu","first_name":"Mathieu","last_name":"Lewin"},{"id":"404092F4-F248-11E8-B48F-1D18A9856A87","last_name":"Phan Thanh","first_name":"Nam","full_name":"Phan Thanh, Nam"},{"full_name":"Rougerie, Nicolas","first_name":"Nicolas","last_name":"Rougerie"}],"license":"https://creativecommons.org/licenses/by-nd/4.0/","ec_funded":1,"publist_id":"7344","file_date_updated":"2020-07-14T12:46:35Z","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"quality_controlled":"1","tmp":{"short":"CC BY-ND (4.0)","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.5802/jep.18","month":"01","intvolume":" 2","ddc":["539"],"title":"Derivation of nonlinear gibbs measures from many-body quantum mechanics","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"473","oa_version":"Published Version","file":[{"creator":"system","file_size":1084254,"content_type":"application/pdf","file_name":"IST-2018-951-v1+1_2015_Thanh-Nam_Derivation_of.pdf","access_level":"open_access","date_created":"2018-12-12T10:12:53Z","date_updated":"2020-07-14T12:46:35Z","checksum":"a40eb4016717ddc9927154798a4c164a","file_id":"4974","relation":"main_file"}],"pubrep_id":"951","type":"journal_article","abstract":[{"text":"We prove that nonlinear Gibbs measures can be obtained from the corresponding many-body, grand-canonical, quantum Gibbs states, in a mean-field limit where the temperature T diverges and the interaction strength behaves as 1/T. We proceed by characterizing the interacting Gibbs state as minimizing a functional counting the free-energy relatively to the non-interacting case. We then perform an infinite-dimensional analogue of phase-space semiclassical analysis, using fine properties of the quantum relative entropy, the link between quantum de Finetti measures and upper/lower symbols in a coherent state basis, as well as Berezin-Lieb type inequalities. Our results cover the measure built on the defocusing nonlinear Schrödinger functional on a finite interval, as well as smoother interactions in dimensions d 2.","lang":"eng"}],"page":"65 - 115","citation":{"chicago":"Lewin, Mathieu, Phan Nam, and Nicolas Rougerie. “Derivation of Nonlinear Gibbs Measures from Many-Body Quantum Mechanics.” Journal de l’Ecole Polytechnique - Mathematiques. Ecole Polytechnique, 2015. https://doi.org/10.5802/jep.18.","short":"M. Lewin, P. Nam, N. Rougerie, Journal de l’Ecole Polytechnique - Mathematiques 2 (2015) 65–115.","mla":"Lewin, Mathieu, et al. “Derivation of Nonlinear Gibbs Measures from Many-Body Quantum Mechanics.” Journal de l’Ecole Polytechnique - Mathematiques, vol. 2, Ecole Polytechnique, 2015, pp. 65–115, doi:10.5802/jep.18.","ieee":"M. Lewin, P. Nam, and N. Rougerie, “Derivation of nonlinear gibbs measures from many-body quantum mechanics,” Journal de l’Ecole Polytechnique - Mathematiques, vol. 2. Ecole Polytechnique, pp. 65–115, 2015.","apa":"Lewin, M., Nam, P., & Rougerie, N. (2015). Derivation of nonlinear gibbs measures from many-body quantum mechanics. Journal de l’Ecole Polytechnique - Mathematiques. Ecole Polytechnique. https://doi.org/10.5802/jep.18","ista":"Lewin M, Nam P, Rougerie N. 2015. Derivation of nonlinear gibbs measures from many-body quantum mechanics. Journal de l’Ecole Polytechnique - Mathematiques. 2, 65–115.","ama":"Lewin M, Nam P, Rougerie N. Derivation of nonlinear gibbs measures from many-body quantum mechanics. Journal de l’Ecole Polytechnique - Mathematiques. 2015;2:65-115. doi:10.5802/jep.18"},"publication":"Journal de l'Ecole Polytechnique - Mathematiques","date_published":"2015-01-01T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"01"},{"abstract":[{"lang":"eng","text":"Dendritic cells are potent antigen-presenting cells endowed with the unique ability to initiate adaptive immune responses upon inflammation. Inflammatory processes are often associated with an increased production of serotonin, which operates by activating specific receptors. However, the functional role of serotonin receptors in regulation of dendritic cell functions is poorly understood. Here, we demonstrate that expression of serotonin receptor 5-HT7 (5-HT7TR) as well as its downstream effector Cdc42 is upregulated in dendritic cells upon maturation. Although dendritic cell maturation was independent of 5-HT7TR, receptor stimulation affected dendritic cell morphology through Cdc42-mediated signaling. In addition, basal activity of 5-HT7TR was required for the proper expression of the chemokine receptor CCR7, which is a key factor that controls dendritic cell migration. Consistent with this, we observed that 5-HT7TR enhances chemotactic motility of dendritic cells in vitro by modulating their directionality and migration velocity. Accordingly, migration of dendritic cells in murine colon explants was abolished after pharmacological receptor inhibition. Our results indicate that there is a crucial role for 5-HT7TR-Cdc42-mediated signaling in the regulation of dendritic cell morphology and motility, suggesting that 5-HT7TR could be a new target for treatment of a variety of inflammatory and immune disorders."}],"publist_id":"7343","issue":"15","type":"journal_article","author":[{"full_name":"Holst, Katrin","last_name":"Holst","first_name":"Katrin"},{"full_name":"Guseva, Daria","first_name":"Daria","last_name":"Guseva"},{"first_name":"Susann","last_name":"Schindler","full_name":"Schindler, Susann"},{"first_name":"Michael K","last_name":"Sixt","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6620-9179","full_name":"Sixt, Michael K"},{"full_name":"Braun, Armin","first_name":"Armin","last_name":"Braun"},{"last_name":"Chopra","first_name":"Himpriya","full_name":"Chopra, Himpriya"},{"full_name":"Pabst, Oliver","last_name":"Pabst","first_name":"Oliver"},{"full_name":"Ponimaskin, Evgeni","first_name":"Evgeni","last_name":"Ponimaskin"}],"date_updated":"2021-01-12T08:00:54Z","date_created":"2018-12-11T11:46:41Z","oa_version":"None","volume":128,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"477","year":"2015","status":"public","title":"The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells","publication_status":"published","department":[{"_id":"MiSi"}],"publisher":"Company of Biologists","intvolume":" 128","month":"06","day":"15","scopus_import":1,"doi":"10.1242/jcs.167999","date_published":"2015-06-15T00:00:00Z","language":[{"iso":"eng"}],"publication":"Journal of Cell Science","citation":{"mla":"Holst, Katrin, et al. “The Serotonin Receptor 5-HT7R Regulates the Morphology and Migratory Properties of Dendritic Cells.” Journal of Cell Science, vol. 128, no. 15, Company of Biologists, 2015, pp. 2866–80, doi:10.1242/jcs.167999.","short":"K. Holst, D. Guseva, S. Schindler, M.K. Sixt, A. Braun, H. Chopra, O. Pabst, E. Ponimaskin, Journal of Cell Science 128 (2015) 2866–2880.","chicago":"Holst, Katrin, Daria Guseva, Susann Schindler, Michael K Sixt, Armin Braun, Himpriya Chopra, Oliver Pabst, and Evgeni Ponimaskin. “The Serotonin Receptor 5-HT7R Regulates the Morphology and Migratory Properties of Dendritic Cells.” Journal of Cell Science. Company of Biologists, 2015. https://doi.org/10.1242/jcs.167999.","ama":"Holst K, Guseva D, Schindler S, et al. The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. Journal of Cell Science. 2015;128(15):2866-2880. doi:10.1242/jcs.167999","ista":"Holst K, Guseva D, Schindler S, Sixt MK, Braun A, Chopra H, Pabst O, Ponimaskin E. 2015. The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. Journal of Cell Science. 128(15), 2866–2880.","apa":"Holst, K., Guseva, D., Schindler, S., Sixt, M. K., Braun, A., Chopra, H., … Ponimaskin, E. (2015). The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells. Journal of Cell Science. Company of Biologists. https://doi.org/10.1242/jcs.167999","ieee":"K. Holst et al., “The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells,” Journal of Cell Science, vol. 128, no. 15. Company of Biologists, pp. 2866–2880, 2015."},"quality_controlled":"1","page":"2866 - 2880"},{"oa_version":"Preprint","_id":"523","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 242","status":"public","title":"Looking at mean-payoff and total-payoff through windows","issue":"6","abstract":[{"text":"We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.","lang":"eng"}],"type":"journal_article","date_published":"2015-03-24T00:00:00Z","citation":{"ama":"Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff through windows. Information and Computation. 2015;242(6):25-52. doi:10.1016/j.ic.2015.03.010","ista":"Chatterjee K, Doyen L, Randour M, Raskin J. 2015. Looking at mean-payoff and total-payoff through windows. Information and Computation. 242(6), 25–52.","ieee":"K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff and total-payoff through windows,” Information and Computation, vol. 242, no. 6. Elsevier, pp. 25–52, 2015.","apa":"Chatterjee, K., Doyen, L., Randour, M., & Raskin, J. (2015). Looking at mean-payoff and total-payoff through windows. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2015.03.010","mla":"Chatterjee, Krishnendu, et al. “Looking at Mean-Payoff and Total-Payoff through Windows.” Information and Computation, vol. 242, no. 6, Elsevier, 2015, pp. 25–52, doi:10.1016/j.ic.2015.03.010.","short":"K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin. “Looking at Mean-Payoff and Total-Payoff through Windows.” Information and Computation. Elsevier, 2015. https://doi.org/10.1016/j.ic.2015.03.010."},"publication":"Information and Computation","page":"25 - 52","day":"24","scopus_import":1,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"2279"}]},"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"},{"first_name":"Mickael","last_name":"Randour","full_name":"Randour, Mickael"},{"full_name":"Raskin, Jean","last_name":"Raskin","first_name":"Jean"}],"volume":242,"date_created":"2018-12-11T11:46:57Z","date_updated":"2023-02-23T10:36:02Z","year":"2015","publisher":"Elsevier","department":[{"_id":"KrCh"}],"publication_status":"published","publist_id":"7296","ec_funded":1,"doi":"10.1016/j.ic.2015.03.010","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1302.4248"}],"project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_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"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","month":"03"},{"day":"22","month":"10","scopus_import":1,"doi":"10.1016/j.cell.2015.09.037","date_published":"2015-10-22T00:00:00Z","language":[{"iso":"eng"}],"publication":"Cell","citation":{"ieee":"W. Li et al., “EIN2-directed translational regulation of ethylene signaling in arabidopsis,” Cell, vol. 163, no. 3. Cell Press, pp. 670–683, 2015.","apa":"Li, W., Ma, M., Feng, Y., Li, H., Wang, Y., Ma, Y., … Guo, H. (2015). EIN2-directed translational regulation of ethylene signaling in arabidopsis. Cell. Cell Press. https://doi.org/10.1016/j.cell.2015.09.037","ista":"Li W, Ma M, Feng Y, Li H, Wang Y, Ma Y, Li M, An F, Guo H. 2015. EIN2-directed translational regulation of ethylene signaling in arabidopsis. Cell. 163(3), 670–683.","ama":"Li W, Ma M, Feng Y, et al. EIN2-directed translational regulation of ethylene signaling in arabidopsis. Cell. 2015;163(3):670-683. doi:10.1016/j.cell.2015.09.037","chicago":"Li, Wenyang, Mengdi Ma, Ying Feng, Hongjiang Li, Yichuan Wang, Yutong Ma, Mingzhe Li, Fengying An, and Hongwei Guo. “EIN2-Directed Translational Regulation of Ethylene Signaling in Arabidopsis.” Cell. Cell Press, 2015. https://doi.org/10.1016/j.cell.2015.09.037.","short":"W. Li, M. Ma, Y. Feng, H. Li, Y. Wang, Y. Ma, M. Li, F. An, H. Guo, Cell 163 (2015) 670–683.","mla":"Li, Wenyang, et al. “EIN2-Directed Translational Regulation of Ethylene Signaling in Arabidopsis.” Cell, vol. 163, no. 3, Cell Press, 2015, pp. 670–83, doi:10.1016/j.cell.2015.09.037."},"quality_controlled":"1","page":"670 - 683","abstract":[{"text":"Ethylene is a gaseous phytohormone that plays vital roles in plant growth and development. Previous studies uncovered EIN2 as an essential signal transducer linking ethylene perception on ER to transcriptional regulation in the nucleus through a “cleave and shuttle” model. In this study, we report another mechanism of EIN2-mediated ethylene signaling, whereby EIN2 imposes the translational repression of EBF1 and EBF2 mRNA. We find that the EBF1/2 3′ UTRs mediate EIN2-directed translational repression and identify multiple poly-uridylates (PolyU) motifs as functional cis elements of 3′ UTRs. Furthermore, we demonstrate that ethylene induces EIN2 to associate with 3′ UTRs and target EBF1/2 mRNA to cytoplasmic processing-body (P-body) through interacting with multiple P-body factors, including EIN5 and PABs. Our study illustrates translational regulation as a key step in ethylene signaling and presents mRNA 3′ UTR functioning as a “signal transducer” to sense and relay cellular signaling in plants.","lang":"eng"}],"issue":"3","publist_id":"7285","type":"journal_article","author":[{"full_name":"Li, Wenyang","first_name":"Wenyang","last_name":"Li"},{"first_name":"Mengdi","last_name":"Ma","full_name":"Ma, Mengdi"},{"first_name":"Ying","last_name":"Feng","full_name":"Feng, Ying"},{"full_name":"Li, Hongjiang","orcid":"0000-0001-5039-9660","id":"33CA54A6-F248-11E8-B48F-1D18A9856A87","last_name":"Li","first_name":"Hongjiang"},{"full_name":"Wang, Yichuan","first_name":"Yichuan","last_name":"Wang"},{"full_name":"Ma, Yutong","last_name":"Ma","first_name":"Yutong"},{"full_name":"Li, Mingzhe","first_name":"Mingzhe","last_name":"Li"},{"full_name":"An, Fengying","last_name":"An","first_name":"Fengying"},{"full_name":"Guo, Hongwei","first_name":"Hongwei","last_name":"Guo"}],"date_updated":"2021-01-12T08:01:27Z","date_created":"2018-12-11T11:47:00Z","oa_version":"None","volume":163,"year":"2015","_id":"532","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"EIN2-directed translational regulation of ethylene signaling in arabidopsis","publication_status":"published","intvolume":" 163","publisher":"Cell Press","department":[{"_id":"JiFr"}]},{"issue":"6","abstract":[{"text":"We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"524","intvolume":" 242","title":"Qualitative analysis of concurrent mean payoff games","status":"public","day":"11","scopus_import":1,"date_published":"2015-10-11T00:00:00Z","citation":{"chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” Information and Computation. Elsevier, 2015. https://doi.org/10.1016/j.ic.2015.03.009.","short":"K. Chatterjee, R. Ibsen-Jensen, Information and Computation 242 (2015) 2–24.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” Information and Computation, vol. 242, no. 6, Elsevier, 2015, pp. 2–24, doi:10.1016/j.ic.2015.03.009.","ieee":"K. Chatterjee and R. Ibsen-Jensen, “Qualitative analysis of concurrent mean payoff games,” Information and Computation, vol. 242, no. 6. Elsevier, pp. 2–24, 2015.","apa":"Chatterjee, K., & Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean payoff games. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2015.03.009","ista":"Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean payoff games. Information and Computation. 242(6), 2–24.","ama":"Chatterjee K, Ibsen-Jensen R. Qualitative analysis of concurrent mean payoff games. Information and Computation. 2015;242(6):2-24. doi:10.1016/j.ic.2015.03.009"},"publication":"Information and Computation","page":"2 - 24","publist_id":"7295","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5403"}]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","first_name":"Rasmus","last_name":"Ibsen-Jensen"}],"volume":242,"date_created":"2018-12-11T11:46:57Z","date_updated":"2023-02-23T12:24:45Z","year":"2015","publisher":"Elsevier","department":[{"_id":"KrCh"}],"publication_status":"published","month":"10","doi":"10.1016/j.ic.2015.03.009","language":[{"iso":"eng"}],"external_id":{"arxiv":["1409.5306"]},"main_file_link":[{"url":"https://arxiv.org/abs/1409.5306","open_access":"1"}],"oa":1,"quality_controlled":"1"},{"ec_funded":1,"publist_id":"5713","year":"2015","acknowledgement":"A Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/146.\r\n","publisher":"AAAI Press","department":[{"_id":"KrCh"}],"publication_status":"published","related_material":{"record":[{"id":"5410","relation":"earlier_version","status":"public"}]},"author":[{"first_name":"Umair","last_name":"Ahmed","full_name":"Ahmed, Umair"},{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Gulwani, Sumit","first_name":"Sumit","last_name":"Gulwani"}],"volume":2,"date_created":"2018-12-11T11:52:16Z","date_updated":"2023-02-23T12:25:07Z","month":"01","oa":1,"main_file_link":[{"open_access":"1","url":"https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9523/9300"}],"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","conference":{"location":"Austin, TX, USA","start_date":"2015-01-25","end_date":"2015-01-30","name":"AAAI: Conference on Artificial Intelligence"},"language":[{"iso":"eng"}],"type":"conference","abstract":[{"text":"Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. We present an approach that generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. The presence of such states for standard game variants like 4×4 Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased. ","lang":"eng"}],"_id":"1481","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 2","title":"Automatic generation of alternative starting positions for simple traditional board games","status":"public","oa_version":"None","scopus_import":1,"article_processing_charge":"No","day":"01","citation":{"ama":"Ahmed U, Chatterjee K, Gulwani S. Automatic generation of alternative starting positions for simple traditional board games. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Vol 2. AAAI Press; 2015:745-752.","ista":"Ahmed U, Chatterjee K, Gulwani S. 2015. Automatic generation of alternative starting positions for simple traditional board games. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 2, 745–752.","ieee":"U. Ahmed, K. Chatterjee, and S. Gulwani, “Automatic generation of alternative starting positions for simple traditional board games,” in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, TX, USA, 2015, vol. 2, pp. 745–752.","apa":"Ahmed, U., Chatterjee, K., & Gulwani, S. (2015). Automatic generation of alternative starting positions for simple traditional board games. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (Vol. 2, pp. 745–752). Austin, TX, USA: AAAI Press.","mla":"Ahmed, Umair, et al. “Automatic Generation of Alternative Starting Positions for Simple Traditional Board Games.” Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, vol. 2, AAAI Press, 2015, pp. 745–52.","short":"U. Ahmed, K. Chatterjee, S. Gulwani, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015, pp. 745–752.","chicago":"Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. “Automatic Generation of Alternative Starting Positions for Simple Traditional Board Games.” In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2:745–52. AAAI Press, 2015."},"publication":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence","page":"745 - 752","date_published":"2015-01-01T00:00:00Z"},{"page":"325 - 330","citation":{"chicago":"Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications,” 325–30. IEEE, 2015. https://doi.org/10.1109/ICRA.2015.7139019.","mla":"Chatterjee, Krishnendu, et al. Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications. IEEE, 2015, pp. 325–30, doi:10.1109/ICRA.2015.7139019.","short":"K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, IEEE, 2015, pp. 325–330.","ista":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. ICRA: International Conference on Robotics and Automation, 325–330.","apa":"Chatterjee, K., Chmelik, M., Gupta, R., & Kanodia, A. (2015). Qualitative analysis of POMDPs with temporal logic specifications for robotics applications (pp. 325–330). Presented at the ICRA: International Conference on Robotics and Automation, Seattle, WA, United States: IEEE. https://doi.org/10.1109/ICRA.2015.7139019","ieee":"K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Qualitative analysis of POMDPs with temporal logic specifications for robotics applications,” presented at the ICRA: International Conference on Robotics and Automation, Seattle, WA, United States, 2015, pp. 325–330.","ama":"Chatterjee K, Chmelik M, Gupta R, Kanodia A. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. In: IEEE; 2015:325-330. doi:10.1109/ICRA.2015.7139019"},"date_published":"2015-01-01T00:00:00Z","scopus_import":1,"day":"01","status":"public","title":"Qualitative analysis of POMDPs with temporal logic specifications for robotics applications","_id":"1732","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","type":"conference","abstract":[{"lang":"eng","text":"We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty."}],"quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Game Theory"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1409.3360"}],"external_id":{"arxiv":["1409.3360"]},"oa":1,"language":[{"iso":"eng"}],"conference":{"end_date":"2015-05-30","location":"Seattle, WA, United States","start_date":"2015-05-26","name":"ICRA: International Conference on Robotics and Automation"},"doi":"10.1109/ICRA.2015.7139019","month":"01","publication_status":"published","department":[{"_id":"KrCh"}],"publisher":"IEEE","year":"2015","date_created":"2018-12-11T11:53:43Z","date_updated":"2023-02-23T12:25:52Z","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Chmelik","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin"},{"full_name":"Gupta, Raghav","last_name":"Gupta","first_name":"Raghav"},{"full_name":"Kanodia, Ayush","last_name":"Kanodia","first_name":"Ayush"}],"related_material":{"record":[{"id":"5424","status":"public","relation":"earlier_version"},{"id":"5426","relation":"earlier_version","status":"public"}]},"publist_id":"5394","ec_funded":1},{"day":"19","month":"02","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","page":"25","oa":1,"citation":{"mla":"Chatterjee, Krishnendu, et al. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria, 2015, doi:10.15479/AT:IST-2015-322-v1-1.","short":"K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives, IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Kristoffer Hansen. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-322-v1-1.","ama":"Chatterjee K, Ibsen-Jensen R, Hansen K. The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives. IST Austria; 2015. doi:10.15479/AT:IST-2015-322-v1-1","ista":"Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and K. Hansen, The patience of concurrent stochastic games with safety and reachability objectives. IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Hansen, K. (2015). The patience of concurrent stochastic games with safety and reachability objectives. IST Austria. https://doi.org/10.15479/AT:IST-2015-322-v1-1"},"language":[{"iso":"eng"}],"date_published":"2015-02-19T00:00:00Z","doi":"10.15479/AT:IST-2015-322-v1-1","alternative_title":["IST Austria Technical Report"],"type":"technical_report","abstract":[{"text":"We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed.\r\n\r\n Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:53Z","ddc":["005","519"],"status":"public","publication_status":"published","title":"The patience of concurrent stochastic games with safety and reachability objectives","publisher":"IST Austria","department":[{"_id":"KrCh"}],"year":"2015","_id":"5431","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:02:13Z","date_created":"2018-12-12T11:39:17Z","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"IST-2015-322-v1+1_safetygames.pdf","creator":"system","content_type":"application/pdf","file_size":661015,"file_id":"5491","relation":"main_file","checksum":"bfb858262c30445b8e472c40069178a2","date_created":"2018-12-12T11:53:31Z","date_updated":"2020-07-14T12:46:53Z"}],"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389","first_name":"Rasmus","last_name":"Ibsen-Jensen","full_name":"Ibsen-Jensen, Rasmus"},{"full_name":"Hansen, Kristoffer","first_name":"Kristoffer","last_name":"Hansen"}],"pubrep_id":"322"},{"citation":{"chicago":"Anonymous, 1, and 2 Anonymous. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria, 2015.","mla":"Anonymous, 1, and 2 Anonymous. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria, 2015.","short":"1 Anonymous, 2 Anonymous, Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs, IST Austria, 2015.","ista":"Anonymous 1, Anonymous 2. 2015. Optimal cost indefinite-horizon reachability in goal DEC-POMDPs, IST Austria, 16p.","apa":"Anonymous, 1, & Anonymous, 2. (2015). Optimal cost indefinite-horizon reachability in goal DEC-POMDPs. IST Austria.","ieee":"1 Anonymous and 2 Anonymous, Optimal cost indefinite-horizon reachability in goal DEC-POMDPs. IST Austria, 2015.","ama":"Anonymous 1, Anonymous 2. Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs. IST Austria; 2015."},"oa":1,"page":"16","date_published":"2015-02-19T00:00:00Z","language":[{"iso":"eng"}],"has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"month":"02","day":"19","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5434","year":"2015","publisher":"IST Austria","ddc":["000"],"status":"public","publication_status":"published","title":"Optimal cost indefinite-horizon reachability in goal DEC-POMDPs","pubrep_id":"326","author":[{"last_name":"Anonymous","first_name":"1","full_name":"Anonymous, 1"},{"first_name":"2","last_name":"Anonymous","full_name":"Anonymous, 2"}],"oa_version":"Published Version","file":[{"file_name":"IST-2015-326-v1+1_main.pdf","access_level":"open_access","content_type":"application/pdf","file_size":378162,"creator":"system","relation":"main_file","file_id":"5475","date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:53:14Z","checksum":"8542fd0b10aed7811cd41077b8ccb632"},{"creator":"dernst","file_size":64,"content_type":"text/plain","file_name":"IST-2015-326-v1+2_authors.txt","access_level":"closed","date_created":"2019-04-16T13:00:33Z","date_updated":"2020-07-14T12:46:53Z","checksum":"84c31c537bdaf7a91909f18d25d640ab","file_id":"6317","relation":"main_file"}],"date_created":"2018-12-12T11:39:18Z","date_updated":"2020-07-14T23:04:59Z","type":"technical_report","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:53Z","abstract":[{"lang":"eng","text":"DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new method to solve the problem that extends methods for finite-horizon DEC- POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show our approach presents promising results."}]},{"month":"07","quality_controlled":"1","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"name":"Quantitative Reactive Modeling","call_identifier":"FP7","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"language":[{"iso":"eng"}],"conference":{"location":"Kyoto, Japan","start_date":"2015-07-06","end_date":"2015-07-10","name":"LICS: Logic in Computer Science"},"doi":"10.1109/LICS.2015.32","publist_id":"5493","ec_funded":1,"publication_status":"published","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"IEEE","acknowledgement":"A Technical Report of this paper is available at: https://repository.ist.ac.at/327\r\n","year":"2015","date_created":"2018-12-11T11:53:18Z","date_updated":"2023-02-23T12:26:16Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Komárková","first_name":"Zuzana","full_name":"Komárková, Zuzana"},{"full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","first_name":"Jan","last_name":"Kretinsky"}],"related_material":{"record":[{"id":"466","relation":"later_version","status":"public"},{"relation":"earlier_version","status":"public","id":"5429"},{"id":"5435","relation":"earlier_version","status":"public"}]},"series_title":"LICS","scopus_import":1,"day":"01","page":"244 - 256","citation":{"short":"K. Chatterjee, Z. Komárková, J. Kretinsky, (2015) 244–256.","mla":"Chatterjee, Krishnendu, et al. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. IEEE, 2015, pp. 244–56, doi:10.1109/LICS.2015.32.","chicago":"Chatterjee, Krishnendu, Zuzana Komárková, and Jan Kretinsky. “Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes.” LICS. IEEE, 2015. https://doi.org/10.1109/LICS.2015.32.","ama":"Chatterjee K, Komárková Z, Kretinsky J. Unifying two views on multiple mean-payoff objectives in Markov decision processes. 2015:244-256. doi:10.1109/LICS.2015.32","ieee":"K. Chatterjee, Z. Komárková, and J. Kretinsky, “Unifying two views on multiple mean-payoff objectives in Markov decision processes.” IEEE, pp. 244–256, 2015.","apa":"Chatterjee, K., Komárková, Z., & Kretinsky, J. (2015). Unifying two views on multiple mean-payoff objectives in Markov decision processes. Presented at the LICS: Logic in Computer Science, Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.32","ista":"Chatterjee K, Komárková Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes. , 244–256."},"date_published":"2015-07-01T00:00:00Z","alternative_title":["LICS"],"type":"conference","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist 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. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., Ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems, 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. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem. "}],"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1657","oa_version":"None"},{"type":"conference","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"}],"status":"public","title":"Nested weighted automata","_id":"1656","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"None","scopus_import":1,"day":"31","citation":{"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.","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.","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.","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","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.","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"},"publication":"Proceedings - Symposium on Logic in Computer Science","date_published":"2015-07-31T00:00:00Z","article_number":"7174926","ec_funded":1,"publist_id":"5494","publisher":"IEEE","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication_status":"published","year":"2015","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","volume":"2015-July","date_created":"2018-12-11T11:53:17Z","date_updated":"2023-02-23T12:26:19Z","related_material":{"record":[{"id":"467","status":"public","relation":"later_version"},{"id":"5415","relation":"earlier_version","status":"public"},{"relation":"earlier_version","status":"public","id":"5436"}]},"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop"}],"month":"07","project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling","call_identifier":"FP7"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"call_identifier":"FWF","name":"The Wittgenstein Prize","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","external_id":{"arxiv":["1606.03598"]},"language":[{"iso":"eng"}],"doi":"10.1109/LICS.2015.72","conference":{"start_date":"2015-07-06","location":"Kyoto, Japan","end_date":"2015-07-10","name":"LICS: Logic in Computer Science"}},{"date_created":"2018-12-12T11:39:17Z","date_updated":"2023-02-23T12:26:16Z","oa_version":"Published Version","file":[{"file_name":"IST-2015-318-v1+1_main.pdf","access_level":"open_access","creator":"system","file_size":689863,"content_type":"application/pdf","file_id":"5533","relation":"main_file","date_created":"2018-12-12T11:54:11Z","date_updated":"2020-07-14T12:46:52Z","checksum":"e4869a584567c506349abda9c8ec7db3"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Komarkova, Zuzana","last_name":"Komarkova","first_name":"Zuzana"},{"last_name":"Kretinsky","first_name":"Jan","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"}],"pubrep_id":"318","related_material":{"record":[{"id":"1657","relation":"later_version","status":"public"},{"status":"public","relation":"later_version","id":"466"},{"relation":"later_version","status":"public","id":"5435"}]},"status":"public","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","publication_status":"published","ddc":["004"],"publisher":"IST Austria","department":[{"_id":"KrCh"}],"_id":"5429","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2015","abstract":[{"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.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:52Z","alternative_title":["IST Austria Technical Report"],"type":"technical_report","language":[{"iso":"eng"}],"date_published":"2015-01-12T00:00:00Z","doi":"10.15479/AT:IST-2015-318-v1-1","page":"41","oa":1,"citation":{"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","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","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.","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."},"day":"12","month":"01","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]}},{"page":"51","citation":{"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-v2-1","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 51p.","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-v2-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-v2-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-v2-1."},"oa":1,"language":[{"iso":"eng"}],"doi":"10.15479/AT:IST-2015-318-v2-1","date_published":"2015-02-23T00:00:00Z","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","day":"23","month":"02","department":[{"_id":"KrCh"}],"publisher":"IST Austria","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","ddc":["004"],"status":"public","publication_status":"published","year":"2015","_id":"5435","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"relation":"main_file","file_id":"5525","date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:54:03Z","checksum":"75284adec80baabdfe71ff9ebbc27445","file_name":"IST-2015-318-v2+1_main.pdf","access_level":"open_access","file_size":717630,"content_type":"application/pdf","creator":"system"}],"oa_version":"Published Version","date_updated":"2023-02-23T12:26:00Z","date_created":"2018-12-12T11:39:19Z","pubrep_id":"327","related_material":{"record":[{"id":"1657","status":"public","relation":"later_version"},{"id":"466","status":"public","relation":"later_version"},{"id":"5429","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Zuzana","last_name":"Komarkova","full_name":"Komarkova, Zuzana"},{"last_name":"Kretinsky","first_name":"Jan","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"}],"alternative_title":["IST Austria Technical Report"],"type":"technical_report","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. Our 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.\r\nWe 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. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem."}],"file_date_updated":"2020-07-14T12:46:53Z"},{"year":"2015","_id":"5436","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","status":"public","title":"Nested weighted automata","ddc":["000"],"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"IST Austria","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"},{"full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"pubrep_id":"331","related_material":{"record":[{"id":"1656","status":"public","relation":"later_version"},{"status":"public","relation":"later_version","id":"467"},{"id":"5415","relation":"earlier_version","status":"public"}]},"date_updated":"2023-02-23T12:25:21Z","date_created":"2018-12-12T11:39:19Z","oa_version":"Published Version","file":[{"file_size":569991,"content_type":"application/pdf","creator":"system","access_level":"open_access","file_name":"IST-2015-170-v2+2_report.pdf","checksum":"3c402f47d3669c28d04d1af405a08e3f","date_created":"2018-12-12T11:54:19Z","date_updated":"2020-07-14T12:46:54Z","relation":"main_file","file_id":"5541"}],"type":"technical_report","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:54Z","abstract":[{"lang":"eng","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."}],"oa":1,"citation":{"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.","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.","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","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria, 29p.","ama":"Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria; 2015. doi:10.15479/AT:IST-2015-170-v2-2"},"page":"29","doi":"10.15479/AT:IST-2015-170-v2-2","date_published":"2015-04-24T00:00:00Z","language":[{"iso":"eng"}],"day":"24","month":"04","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]}},{"file_date_updated":"2020-07-14T12:45:10Z","ec_funded":1,"publist_id":"5491","date_updated":"2023-02-23T12:26:27Z","date_created":"2018-12-11T11:53:19Z","author":[{"full_name":"Boker, Udi","last_name":"Boker","first_name":"Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","last_name":"Otop","first_name":"Jan"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"5439"}]},"publication_status":"published","department":[{"_id":"ToHe"}],"publisher":"IEEE","acknowledgement":"A technical report of the article is available at: https://research-explorer.app.ist.ac.at/record/5439","year":"2015","month":"07","publication_identifier":{"issn":["1043-6871 "],"eisbn":["978-1-4799-8875-4 "]},"language":[{"iso":"eng"}],"conference":{"end_date":"2015-07-10","start_date":"2015-007-06","location":"Kyoto, Japan","name":"LICS: Logic in Computer Science"},"doi":"10.1109/LICS.2015.74","quality_controlled":"1","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","call_identifier":"FWF","name":"The Wittgenstein Prize"}],"oa":1,"abstract":[{"lang":"eng","text":"The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata."}],"type":"conference","file":[{"creator":"dernst","file_size":340215,"content_type":"application/pdf","access_level":"open_access","file_name":"2015_LICS_Boker.pdf","checksum":"6abebca9c1a620e9e103a8f9222befac","date_updated":"2020-07-14T12:45:10Z","date_created":"2020-05-15T08:53:29Z","file_id":"7852","relation":"main_file"}],"oa_version":"Submitted Version","title":"The target discounted-sum problem","ddc":["000"],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1659","day":"01","has_accepted_license":"1","article_processing_charge":"No","series_title":"Logic in Computer Science","scopus_import":1,"date_published":"2015-07-01T00:00:00Z","page":"750 - 761","publication":"LICS","citation":{"mla":"Boker, Udi, et al. “The Target Discounted-Sum Problem.” LICS, IEEE, 2015, pp. 750–61, doi:10.1109/LICS.2015.74.","short":"U. Boker, T.A. Henzinger, J. Otop, in:, LICS, IEEE, 2015, pp. 750–761.","chicago":"Boker, Udi, Thomas A Henzinger, and Jan Otop. “The Target Discounted-Sum Problem.” In LICS, 750–61. Logic in Computer Science. IEEE, 2015. https://doi.org/10.1109/LICS.2015.74.","ama":"Boker U, Henzinger TA, Otop J. The target discounted-sum problem. In: LICS. Logic in Computer Science. IEEE; 2015:750-761. doi:10.1109/LICS.2015.74","ista":"Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem. LICS. LICS: Logic in Computer ScienceLogic in Computer Science, 750–761.","apa":"Boker, U., Henzinger, T. A., & Otop, J. (2015). The target discounted-sum problem. In LICS (pp. 750–761). Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.74","ieee":"U. Boker, T. A. Henzinger, and J. Otop, “The target discounted-sum problem,” in LICS, Kyoto, Japan, 2015, pp. 750–761."}},{"type":"conference","alternative_title":["LNCS"],"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. The problem of computing edit distance to pushdown automata 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"}],"issue":"Part II","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","_id":"1610","status":"public","title":"Edit distance for pushdown automata","intvolume":" 9135","pubrep_id":"321","oa_version":"None","scopus_import":"1","day":"01","article_processing_charge":"No","publication":"42nd International Colloquium","citation":{"ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit distance for pushdown automata. In: 42nd International Colloquium. Vol 9135. Springer Nature; 2015:121-133. doi:10.1007/978-3-662-47666-6_10","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit distance for pushdown automata. In 42nd International Colloquium (Vol. 9135, pp. 121–133). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47666-6_10","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, “Edit distance for pushdown automata,” in 42nd International Colloquium, Kyoto, Japan, 2015, vol. 9135, no. Part II, pp. 121–133.","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata. 42nd International Colloquium. ICALP: Automata, Languages and Programming, LNCS, vol. 9135, 121–133.","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, in:, 42nd International Colloquium, Springer Nature, 2015, pp. 121–133.","mla":"Chatterjee, Krishnendu, et al. “Edit Distance for Pushdown Automata.” 42nd International Colloquium, vol. 9135, no. Part II, Springer Nature, 2015, pp. 121–33, doi:10.1007/978-3-662-47666-6_10.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. “Edit Distance for Pushdown Automata.” In 42nd International Colloquium, 9135:121–33. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47666-6_10."},"page":"121 - 133","date_published":"2015-07-01T00:00:00Z","ec_funded":1,"publist_id":"5556","year":"2015","publication_status":"published","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"Springer Nature","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"465"},{"id":"5438","relation":"earlier_version","status":"public"}]},"date_created":"2018-12-11T11:53:01Z","date_updated":"2023-02-23T12:26:24Z","volume":9135,"month":"07","publication_identifier":{"isbn":["978-3-662-47665-9"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1504.08259","open_access":"1"}],"external_id":{"arxiv":["1504.08259"]},"quality_controlled":"1","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"}],"conference":{"end_date":"2015-07-10","start_date":"2015-07-06","location":"Kyoto, Japan","name":"ICALP: Automata, Languages and Programming"},"doi":"10.1007/978-3-662-47666-6_10","language":[{"iso":"eng"}]},{"publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","day":"27","month":"04","language":[{"iso":"eng"}],"date_published":"2015-04-27T00:00:00Z","doi":"10.15479/AT:IST-2015-330-v2-1","page":"27","citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-330-v2-1","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-330-v2-1","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-330-v2-1.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-330-v2-1."},"oa":1,"abstract":[{"lang":"eng","text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. \r\nThe algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights.\r\nOur main theoretical results are as follows.\r\nFirst, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when the output is $\\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$ and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. "}],"file_date_updated":"2020-07-14T12:46:54Z","alternative_title":["IST Austria Technical Report"],"type":"technical_report","file":[{"date_updated":"2020-07-14T12:46:54Z","date_created":"2018-12-12T11:53:12Z","checksum":"f5917c20f84018b362d385c000a2e123","relation":"main_file","file_id":"5473","content_type":"application/pdf","file_size":1072137,"creator":"system","file_name":"IST-2015-330-v2+1_main.pdf","access_level":"open_access"}],"oa_version":"Published Version","date_created":"2018-12-12T11:39:19Z","date_updated":"2023-02-23T12:26:05Z","pubrep_id":"333","related_material":{"record":[{"relation":"later_version","status":"public","id":"1607"},{"relation":"earlier_version","status":"public","id":"5430"}]},"author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus"},{"full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas"}],"department":[{"_id":"KrCh"}],"publisher":"IST Austria","title":"Faster algorithms for quantitative verification in constant treewidth graphs","ddc":["000"],"publication_status":"published","status":"public","_id":"5437","year":"2015","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"type":"technical_report","alternative_title":["IST Austria Technical Report"],"file_date_updated":"2020-07-14T12:46:52Z","abstract":[{"text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.","lang":"eng"}],"_id":"5430","year":"2015","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","department":[{"_id":"KrCh"}],"title":"Faster algorithms for quantitative verification in constant treewidth graphs","ddc":["000"],"status":"public","publication_status":"published","pubrep_id":"319","related_material":{"record":[{"relation":"later_version","status":"public","id":"1607"},{"id":"5437","relation":"later_version","status":"public"}]},"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4783-0389"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas"}],"file":[{"access_level":"open_access","file_name":"IST-2015-319-v1+1_long.pdf","creator":"system","content_type":"application/pdf","file_size":1089651,"file_id":"5482","relation":"main_file","checksum":"62c6ea01e342553dcafb88a070fb1ad5","date_created":"2018-12-12T11:53:21Z","date_updated":"2020-07-14T12:46:52Z"}],"oa_version":"Published Version","date_created":"2018-12-12T11:39:17Z","date_updated":"2023-02-23T12:26:22Z","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"month":"02","day":"10","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2015). Faster algorithms for quantitative verification in constant treewidth graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-319-v1-1","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-319-v1-1","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-319-v1-1.","mla":"Chatterjee, Krishnendu, et al. Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-319-v1-1.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015."},"oa":1,"page":"31","doi":"10.15479/AT:IST-2015-319-v1-1","date_published":"2015-02-10T00:00:00Z","language":[{"iso":"eng"}]},{"related_material":{"record":[{"id":"1659","status":"public","relation":"later_version"}]},"pubrep_id":"335","author":[{"full_name":"Boker, Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","last_name":"Boker","first_name":"Udi"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop","full_name":"Otop, Jan"}],"file":[{"creator":"system","file_size":589619,"content_type":"application/pdf","access_level":"open_access","file_name":"IST-2015-335-v1+1_report.pdf","checksum":"40405907aa012acece1bc26cf0be554d","date_created":"2018-12-12T11:53:55Z","date_updated":"2020-07-14T12:46:55Z","file_id":"5517","relation":"main_file"}],"oa_version":"Published Version","date_created":"2018-12-12T11:39:20Z","date_updated":"2023-02-23T10:08:48Z","year":"2015","_id":"5439","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"ToHe"}],"publisher":"IST Austria","publication_status":"published","status":"public","ddc":["004","512","513"],"title":"The target discounted-sum problem","abstract":[{"lang":"eng","text":"The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata. "}],"file_date_updated":"2020-07-14T12:46:55Z","type":"technical_report","alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2015-335-v1-1","date_published":"2015-05-18T00:00:00Z","language":[{"iso":"eng"}],"oa":1,"citation":{"ama":"Boker U, Henzinger TA, Otop J. The Target Discounted-Sum Problem. IST Austria; 2015. doi:10.15479/AT:IST-2015-335-v1-1","ista":"Boker U, Henzinger TA, Otop J. 2015. The target discounted-sum problem, IST Austria, 20p.","apa":"Boker, U., Henzinger, T. A., & Otop, J. (2015). The target discounted-sum problem. IST Austria. https://doi.org/10.15479/AT:IST-2015-335-v1-1","ieee":"U. Boker, T. A. Henzinger, and J. Otop, The target discounted-sum problem. IST Austria, 2015.","mla":"Boker, Udi, et al. The Target Discounted-Sum Problem. IST Austria, 2015, doi:10.15479/AT:IST-2015-335-v1-1.","short":"U. Boker, T.A. Henzinger, J. Otop, The Target Discounted-Sum Problem, IST Austria, 2015.","chicago":"Boker, Udi, Thomas A Henzinger, and Jan Otop. The Target Discounted-Sum Problem. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-335-v1-1."},"page":"20","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","day":"18","month":"05"}]