[{"status":"public","extern":1,"day":"01","doi":"1557","publist_id":"1079","citation":{"chicago":"Hoenicke, Jochen, K Rustan Leino, Andreas Podelski, Martin Schäf, and Thomas Wies. “It’s Doomed; We Can Prove It,” 338–53. Springer, 2009. <a href=\"https://doi.org/1557\">https://doi.org/1557</a>.","ieee":"J. Hoenicke, K. R. Leino, A. Podelski, M. Schäf, and T. Wies, “It’s Doomed; We Can Prove It,” presented at the FM: Formal Methods, 2009, pp. 338–353.","apa":"Hoenicke, J., Leino, K. R., Podelski, A., Schäf, M., &#38; Wies, T. (2009). It’s Doomed; We Can Prove It (pp. 338–353). Presented at the FM: Formal Methods, Springer. <a href=\"https://doi.org/1557\">https://doi.org/1557</a>","ama":"Hoenicke J, Leino KR, Podelski A, Schäf M, Wies T. It’s Doomed; We Can Prove It. In: Springer; 2009:338-353. doi:<a href=\"https://doi.org/1557\">1557</a>","ista":"Hoenicke J, Leino KR, Podelski A, Schäf M, Wies T. 2009. It’s Doomed; We Can Prove It. FM: Formal Methods, LNCS 5850, , 338–353.","short":"J. Hoenicke, K.R. Leino, A. Podelski, M. Schäf, T. Wies, in:, Springer, 2009, pp. 338–353.","mla":"Hoenicke, Jochen, et al. <i>It’s Doomed; We Can Prove It</i>. Springer, 2009, pp. 338–53, doi:<a href=\"https://doi.org/1557\">1557</a>."},"year":"2009","date_updated":"2021-01-12T07:56:31Z","type":"conference","date_published":"2009-01-01T00:00:00Z","publisher":"Springer","conference":{"name":"FM: Formal Methods"},"quality_controlled":0,"page":"338 - 353","date_created":"2018-12-11T12:08:32Z","publication_status":"published","alternative_title":["LNCS 5850"],"month":"01","title":"It's Doomed; We Can Prove It","_id":"4377","author":[{"first_name":"Jochen","last_name":"Hoenicke","full_name":"Hoenicke,Jochen"},{"full_name":"Leino, K Rustan","last_name":"Leino","first_name":"K Rustan"},{"full_name":"Podelski,Andreas","last_name":"Podelski","first_name":"Andreas"},{"full_name":"Schäf,Martin","last_name":"Schäf","first_name":"Martin"},{"id":"447BFB88-F248-11E8-B48F-1D18A9856A87","last_name":"Wies","first_name":"Thomas","full_name":"Thomas Wies"}]},{"doi":"10.1007/978-3-642-02658-4_26","day":"19","abstract":[{"lang":"eng","text":"Pseudo-code descriptions of STMs assume sequentially consistent program execution and atomicity of high-level STM operations like read, write, and commit. These assumptions are often violated in realistic settings, as STM implementations run on relaxed memory models, with the atomicity of operations as provided by the hardware. This paper presents the first approach to verify STMs under relaxed memory models with atomicity of 32 bit loads and stores, and read-modify-write operations. We present RML, a new high-level language for expressing concurrent algorithms with a hardware-level atomicity of instructions, and whose semantics is parametrized by various relaxed memory models. We then present our tool, FOIL, which takes as input the RML description of an STM algorithm and the description of a memory model, and automatically determines the locations of fences, which if inserted, ensure the correctness of the STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and McRT STM under the memory models of sequential consistency, total store order, partial store order, and relaxed memory order."}],"oa":1,"publist_id":"1074","date_updated":"2021-01-12T07:56:34Z","year":"2009","citation":{"apa":"Guerraoui, R., Henzinger, T. A., &#38; Singh, V. (2009). Software transactional memory on relaxed memory models (Vol. 5643, pp. 321–336). Presented at the CAV: Computer Aided Verification, Springer. <a href=\"https://doi.org/10.1007/978-3-642-02658-4_26\">https://doi.org/10.1007/978-3-642-02658-4_26</a>","ama":"Guerraoui R, Henzinger TA, Singh V. Software transactional memory on relaxed memory models. In: Vol 5643. Springer; 2009:321-336. doi:<a href=\"https://doi.org/10.1007/978-3-642-02658-4_26\">10.1007/978-3-642-02658-4_26</a>","chicago":"Guerraoui, Rachid, Thomas A Henzinger, and Vasu Singh. “Software Transactional Memory on Relaxed Memory Models,” 5643:321–36. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-02658-4_26\">https://doi.org/10.1007/978-3-642-02658-4_26</a>.","ieee":"R. Guerraoui, T. A. Henzinger, and V. Singh, “Software transactional memory on relaxed memory models,” presented at the CAV: Computer Aided Verification, 2009, vol. 5643, pp. 321–336.","mla":"Guerraoui, Rachid, et al. <i>Software Transactional Memory on Relaxed Memory Models</i>. Vol. 5643, Springer, 2009, pp. 321–36, doi:<a href=\"https://doi.org/10.1007/978-3-642-02658-4_26\">10.1007/978-3-642-02658-4_26</a>.","short":"R. Guerraoui, T.A. Henzinger, V. Singh, in:, Springer, 2009, pp. 321–336.","ista":"Guerraoui R, Henzinger TA, Singh V. 2009. Software transactional memory on relaxed memory models. CAV: Computer Aided Verification, LNCS, vol. 5643, 321–336."},"date_published":"2009-06-19T00:00:00Z","type":"conference","acknowledgement":"This research was supported by the Swiss National Science Foundation.","volume":5643,"file":[{"date_updated":"2020-07-14T12:46:28Z","content_type":"application/pdf","file_name":"IST-2012-45-v1+1_Software_transactional_memory_on_relaxed_memory_models.pdf","date_created":"2018-12-12T10:14:50Z","checksum":"df3c3e6306afd3f630a9146f91642f0a","file_size":265763,"file_id":"5105","creator":"system","access_level":"open_access","relation":"main_file"}],"extern":1,"status":"public","publication_status":"published","date_created":"2018-12-11T12:08:34Z","title":"Software transactional memory on relaxed memory models","alternative_title":["LNCS"],"month":"06","pubrep_id":"45","intvolume":"      5643","_id":"4383","author":[{"full_name":"Guerraoui, Rachid","first_name":"Rachid","last_name":"Guerraoui"},{"full_name":"Thomas Henzinger","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Vasu Singh","last_name":"Singh","first_name":"Vasu","id":"4DAE2708-F248-11E8-B48F-1D18A9856A87"}],"publisher":"Springer","conference":{"name":"CAV: Computer Aided Verification"},"page":"321 - 336","quality_controlled":0,"file_date_updated":"2020-07-14T12:46:28Z"},{"publisher":"ACM","conference":{"name":"POPL: Principles of Programming Languages"},"quality_controlled":0,"page":"7 - 16","date_created":"2018-12-11T12:08:35Z","publication_status":"published","month":"01","title":"Preventing versus curing: avoiding conflicts in transactional memories","_id":"4385","author":[{"last_name":"Dragojevic","first_name":"Aleksandar","full_name":"Dragojevic,Aleksandar"},{"full_name":"Guerraoui, Rachid","last_name":"Guerraoui","first_name":"Rachid"},{"last_name":"Singh","first_name":"Anmol","full_name":"Singh, Anmol V"},{"full_name":"Vasu Singh","first_name":"Vasu","last_name":"Singh","id":"4DAE2708-F248-11E8-B48F-1D18A9856A87"}],"status":"public","extern":1,"day":"01","doi":"1533","publist_id":"1070","citation":{"ista":"Dragojevic A, Guerraoui R, Singh A, Singh V. 2009. Preventing versus curing: avoiding conflicts in transactional memories. POPL: Principles of Programming Languages, 7–16.","mla":"Dragojevic, Aleksandar, et al. <i>Preventing versus Curing: Avoiding Conflicts in Transactional Memories</i>. ACM, 2009, pp. 7–16, doi:<a href=\"https://doi.org/1533\">1533</a>.","short":"A. Dragojevic, R. Guerraoui, A. Singh, V. Singh, in:, ACM, 2009, pp. 7–16.","chicago":"Dragojevic, Aleksandar, Rachid Guerraoui, Anmol Singh, and Vasu Singh. “Preventing versus Curing: Avoiding Conflicts in Transactional Memories,” 7–16. ACM, 2009. <a href=\"https://doi.org/1533\">https://doi.org/1533</a>.","ieee":"A. Dragojevic, R. Guerraoui, A. Singh, and V. Singh, “Preventing versus curing: avoiding conflicts in transactional memories,” presented at the POPL: Principles of Programming Languages, 2009, pp. 7–16.","ama":"Dragojevic A, Guerraoui R, Singh A, Singh V. Preventing versus curing: avoiding conflicts in transactional memories. In: ACM; 2009:7-16. doi:<a href=\"https://doi.org/1533\">1533</a>","apa":"Dragojevic, A., Guerraoui, R., Singh, A., &#38; Singh, V. (2009). Preventing versus curing: avoiding conflicts in transactional memories (pp. 7–16). Presented at the POPL: Principles of Programming Languages, ACM. <a href=\"https://doi.org/1533\">https://doi.org/1533</a>"},"year":"2009","date_updated":"2021-01-12T07:56:34Z","type":"conference","date_published":"2009-01-01T00:00:00Z"},{"day":"01","doi":"1548","publist_id":"1067","citation":{"ieee":"P. Cerny and R. Alur, “Automated Analysis of Java Methods for Confidentiality,” presented at the CAV: Computer Aided Verification, 2009, pp. 173–187.","chicago":"Cerny, Pavol, and Rajeev Alur. “Automated Analysis of Java Methods for Confidentiality,” 173–87. Springer, 2009. <a href=\"https://doi.org/1548\">https://doi.org/1548</a>.","ama":"Cerny P, Alur R. Automated Analysis of Java Methods for Confidentiality. In: Springer; 2009:173-187. doi:<a href=\"https://doi.org/1548\">1548</a>","apa":"Cerny, P., &#38; Alur, R. (2009). Automated Analysis of Java Methods for Confidentiality (pp. 173–187). Presented at the CAV: Computer Aided Verification, Springer. <a href=\"https://doi.org/1548\">https://doi.org/1548</a>","ista":"Cerny P, Alur R. 2009. Automated Analysis of Java Methods for Confidentiality. CAV: Computer Aided Verification, LNCS, , 173–187.","mla":"Cerny, Pavol, and Rajeev Alur. <i>Automated Analysis of Java Methods for Confidentiality</i>. Springer, 2009, pp. 173–87, doi:<a href=\"https://doi.org/1548\">1548</a>.","short":"P. Cerny, R. Alur, in:, Springer, 2009, pp. 173–187."},"year":"2009","date_updated":"2021-01-12T07:56:37Z","type":"conference","date_published":"2009-07-01T00:00:00Z","status":"public","extern":1,"date_created":"2018-12-11T12:08:36Z","publication_status":"published","title":"Automated Analysis of Java Methods for Confidentiality","month":"07","alternative_title":["LNCS"],"_id":"4391","author":[{"full_name":"Pavol Cerny","last_name":"Cerny","first_name":"Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Alur, Rajeev","last_name":"Alur","first_name":"Rajeev"}],"publisher":"Springer","conference":{"name":"CAV: Computer Aided Verification"},"quality_controlled":0,"page":"173 - 187"},{"extern":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"status":"public","id":"2967","relation":"later_version"}]},"volume":5771,"main_file_link":[{"url":"http://repository.upenn.edu/cis_reports/894/","open_access":"1"}],"abstract":[{"lang":"eng","text":"For programs whose data variables range over boolean or finite domains, program verification is decidable, and this forms the basis of recent tools for software model checking. In this paper, we consider algorithmic verification of programs that use boolean variables, and in addition, access a single read-only array whose length is potentially unbounded, and whose elements range over a potentially unbounded data domain. We show that the reachability problem, while undecidable in general, is (1) Pspace-complete for programs in which the array-accessing for-loops are not nested, (2) decidable for a restricted class of programs with doubly-nested loops. The second result establishes connections to automata and logics defining languages over data words."}],"publist_id":"1056","oa":1,"doi":"10.1007/978-3-642-04027-6_9","day":"01","date_published":"2009-09-01T00:00:00Z","type":"conference","date_updated":"2023-02-23T11:06:20Z","citation":{"short":"R. Alur, P. Cerny, S. Weinstein, in:, Springer, 2009, pp. 86–101.","mla":"Alur, Rajeev, et al. <i>Algorithmic Analysis of Array-Accessing Programs</i>. Vol. 5771, Springer, 2009, pp. 86–101, doi:<a href=\"https://doi.org/10.1007/978-3-642-04027-6_9\">10.1007/978-3-642-04027-6_9</a>.","ista":"Alur R, Cerny P, Weinstein S. 2009. Algorithmic analysis of array-accessing programs. CSL: Computer Science Logic, LNCS, vol. 5771, 86–101.","apa":"Alur, R., Cerny, P., &#38; Weinstein, S. (2009). Algorithmic analysis of array-accessing programs (Vol. 5771, pp. 86–101). Presented at the CSL: Computer Science Logic, Coimbra, Portugal: Springer. <a href=\"https://doi.org/10.1007/978-3-642-04027-6_9\">https://doi.org/10.1007/978-3-642-04027-6_9</a>","ama":"Alur R, Cerny P, Weinstein S. Algorithmic analysis of array-accessing programs. In: Vol 5771. Springer; 2009:86-101. doi:<a href=\"https://doi.org/10.1007/978-3-642-04027-6_9\">10.1007/978-3-642-04027-6_9</a>","chicago":"Alur, Rajeev, Pavol Cerny, and Scott Weinstein. “Algorithmic Analysis of Array-Accessing Programs,” 5771:86–101. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-04027-6_9\">https://doi.org/10.1007/978-3-642-04027-6_9</a>.","ieee":"R. Alur, P. Cerny, and S. Weinstein, “Algorithmic analysis of array-accessing programs,” presented at the CSL: Computer Science Logic, Coimbra, Portugal, 2009, vol. 5771, pp. 86–101."},"year":"2009","conference":{"name":"CSL: Computer Science Logic","start_date":"2009-09-07","location":"Coimbra, Portugal","end_date":"2009-09-11"},"publisher":"Springer","language":[{"iso":"eng"}],"page":"86 - 101","quality_controlled":"1","title":"Algorithmic analysis of array-accessing programs","month":"09","alternative_title":["LNCS"],"intvolume":"      5771","publication_status":"published","oa_version":"Submitted Version","date_created":"2018-12-11T12:08:40Z","author":[{"first_name":"Rajeev","last_name":"Alur","full_name":"Alur, Rajeev"},{"first_name":"Pavol","last_name":"Cerny","full_name":"Cerny, Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Weinstein, Scott","first_name":"Scott","last_name":"Weinstein"}],"_id":"4403"},{"acknowledgement":"The research has been partially funded by the Swiss National Science Foundation under grant 205321-111840.","volume":5643,"file":[{"relation":"main_file","access_level":"open_access","creator":"system","file_id":"4938","checksum":"36b974111521ea534aae294166e93a63","file_size":804295,"date_created":"2018-12-12T10:12:20Z","file_name":"IST-2012-40-v1+1_Sliding-window_abstraction_for_infinite_markov_chains.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:30Z"}],"main_file_link":[{"open_access":"0","url":"http://pub.ist.ac.at/%7Etah/Publications/sliding-window_abstraction_for_infinite_markov_chains.pdf"}],"extern":1,"status":"public","doi":"10.1007/978-3-642-02658-4_27","day":"01","abstract":[{"lang":"eng","text":"We present an on-the-fly abstraction technique for infinite-state continuous -time Markov chains. We consider Markov chains that are specified by a finite set of transition classes. Such models naturally represent biochemical reactions and therefore play an important role in the stochastic modeling of biological systems. We approximate the transient probability distributions at various time instances by solving a sequence of dynamically constructed abstract models, each depending on the previous one. Each abstract model is a finite Markov chain that represents the behavior of the original, infinite chain during a specific time interval. Our approach provides complete information about probability distributions, not just about individual parameters like the mean. The error of each abstraction can be computed, and the precision of the abstraction refined when desired. We implemented the algorithm and demonstrate its usefulness and efficiency on several case studies from systems biology."}],"publist_id":"278","oa":1,"date_updated":"2021-01-12T07:57:04Z","citation":{"chicago":"Henzinger, Thomas A, Maria Mateescu, and Verena Wolf. “Sliding-Window Abstraction for Infinite Markov Chains,” 5643:337–52. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-02658-4_27\">https://doi.org/10.1007/978-3-642-02658-4_27</a>.","ieee":"T. A. Henzinger, M. Mateescu, and V. Wolf, “Sliding-window abstraction for infinite Markov chains,” presented at the CAV: Computer Aided Verification, 2009, vol. 5643, pp. 337–352.","apa":"Henzinger, T. A., Mateescu, M., &#38; Wolf, V. (2009). Sliding-window abstraction for infinite Markov chains (Vol. 5643, pp. 337–352). Presented at the CAV: Computer Aided Verification, Springer. <a href=\"https://doi.org/10.1007/978-3-642-02658-4_27\">https://doi.org/10.1007/978-3-642-02658-4_27</a>","ama":"Henzinger TA, Mateescu M, Wolf V. Sliding-window abstraction for infinite Markov chains. In: Vol 5643. Springer; 2009:337-352. doi:<a href=\"https://doi.org/10.1007/978-3-642-02658-4_27\">10.1007/978-3-642-02658-4_27</a>","ista":"Henzinger TA, Mateescu M, Wolf V. 2009. Sliding-window abstraction for infinite Markov chains. CAV: Computer Aided Verification, LNCS, vol. 5643, 337–352.","mla":"Henzinger, Thomas A., et al. <i>Sliding-Window Abstraction for Infinite Markov Chains</i>. Vol. 5643, Springer, 2009, pp. 337–52, doi:<a href=\"https://doi.org/10.1007/978-3-642-02658-4_27\">10.1007/978-3-642-02658-4_27</a>.","short":"T.A. Henzinger, M. Mateescu, V. Wolf, in:, Springer, 2009, pp. 337–352."},"year":"2009","date_published":"2009-01-01T00:00:00Z","type":"conference","publisher":"Springer","conference":{"name":"CAV: Computer Aided Verification"},"page":"337 - 352","quality_controlled":0,"file_date_updated":"2020-07-14T12:46:30Z","publication_status":"published","date_created":"2018-12-11T12:08:55Z","month":"01","pubrep_id":"40","title":"Sliding-window abstraction for infinite Markov chains","alternative_title":["LNCS"],"intvolume":"      5643","_id":"4453","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Thomas Henzinger","orcid":"0000−0002−2985−7724"},{"id":"3B43276C-F248-11E8-B48F-1D18A9856A87","last_name":"Mateescu","first_name":"Maria","full_name":"Maria Mateescu"},{"full_name":"Wolf, Verena","first_name":"Verena","last_name":"Wolf"}]},{"date_published":"2009-08-17T00:00:00Z","type":"conference","date_updated":"2023-02-23T11:24:03Z","citation":{"mla":"Didier, Frédéric, et al. <i>Approximation of Event Probabilities in Noisy Cellular Processes</i>. Vol. 5688, Springer, 2009, pp. 173–88, doi:<a href=\"https://doi.org/10.1007/978-3-642-03845-7_12\">10.1007/978-3-642-03845-7_12</a>.","short":"F. Didier, T.A. Henzinger, M. Mateescu, V. Wolf, in:, Springer, 2009, pp. 173–188.","ista":"Didier F, Henzinger TA, Mateescu M, Wolf V. 2009. Approximation of event probabilities in noisy cellular processes. CMSB: Computational Methods in Systems Biology, LNCS, vol. 5688, 173–188.","apa":"Didier, F., Henzinger, T. A., Mateescu, M., &#38; Wolf, V. (2009). Approximation of event probabilities in noisy cellular processes (Vol. 5688, pp. 173–188). Presented at the CMSB: Computational Methods in Systems Biology, Springer. <a href=\"https://doi.org/10.1007/978-3-642-03845-7_12\">https://doi.org/10.1007/978-3-642-03845-7_12</a>","ama":"Didier F, Henzinger TA, Mateescu M, Wolf V. Approximation of event probabilities in noisy cellular processes. In: Vol 5688. Springer; 2009:173-188. doi:<a href=\"https://doi.org/10.1007/978-3-642-03845-7_12\">10.1007/978-3-642-03845-7_12</a>","ieee":"F. Didier, T. A. Henzinger, M. Mateescu, and V. Wolf, “Approximation of event probabilities in noisy cellular processes,” presented at the CMSB: Computational Methods in Systems Biology, 2009, vol. 5688, pp. 173–188.","chicago":"Didier, Frédéric, Thomas A Henzinger, Maria Mateescu, and Verena Wolf. “Approximation of Event Probabilities in Noisy Cellular Processes,” 5688:173–88. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-03845-7_12\">https://doi.org/10.1007/978-3-642-03845-7_12</a>."},"year":"2009","abstract":[{"text":"Molecular noise, which arises from the randomness of the discrete events in the cell, significantly influences fundamental biological processes. Discrete -state continuous-time stochastic models (CTMC) can be used to describe such effects, but the calculation of the probabilities of certain events is computationally expensive.\nWe present a comparison of two analysis approaches for CTMC. On one hand, we estimate the probabilities of interest using repeated Gillespie simulation and determine the statistical accuracy that we obtain. On the other hand, we apply a numerical reachability analysis that approximates the probability distributions of the system at several time instances. We use examples of cellular processes to demonstrate the superiority of the reachability analysis if accurate results are required.","lang":"eng"}],"publist_id":"189","doi":"10.1007/978-3-642-03845-7_12","day":"17","extern":1,"related_material":{"record":[{"relation":"later_version","id":"3364","status":"public"}]},"status":"public","volume":5688,"acknowledgement":"This research was supported in part by the Swiss National Science Foundation under grant 205321-111840 and by the Excellence Cluster on Multimodal Computing and Interaction.","author":[{"full_name":"Didier, Frédéric","last_name":"Didier","first_name":"Frédéric"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Thomas Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"3B43276C-F248-11E8-B48F-1D18A9856A87","full_name":"Maria Mateescu","first_name":"Maria","last_name":"Mateescu"},{"last_name":"Wolf","first_name":"Verena","full_name":"Wolf, Verena"}],"_id":"4535","title":"Approximation of event probabilities in noisy cellular processes","month":"08","alternative_title":["LNCS"],"intvolume":"      5688","publication_status":"published","date_created":"2018-12-11T12:09:21Z","page":"173 - 188","quality_controlled":0,"conference":{"name":"CMSB: Computational Methods in Systems Biology"},"publisher":"Springer"},{"related_material":{"record":[{"relation":"later_version","id":"3867","status":"public"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Expressiveness and Closure Properties for Quantitative Languages</i>. IEEE, 2009, pp. 199–208, doi:<a href=\"https://doi.org/10.1109/LICS.2009.16\">10.1109/LICS.2009.16</a>.","short":"K. Chatterjee, L. Doyen, T.A. Henzinger, in:, IEEE, 2009, pp. 199–208.","ista":"Chatterjee K, Doyen L, Henzinger TA. 2009. Expressiveness and closure properties for quantitative languages. LICS: Logic in Computer Science, 199–208.","ama":"Chatterjee K, Doyen L, Henzinger TA. Expressiveness and closure properties for quantitative languages. In: IEEE; 2009:199-208. doi:<a href=\"https://doi.org/10.1109/LICS.2009.16\">10.1109/LICS.2009.16</a>","apa":"Chatterjee, K., Doyen, L., &#38; Henzinger, T. A. (2009). Expressiveness and closure properties for quantitative languages (pp. 199–208). Presented at the LICS: Logic in Computer Science, IEEE. <a href=\"https://doi.org/10.1109/LICS.2009.16\">https://doi.org/10.1109/LICS.2009.16</a>","ieee":"K. Chatterjee, L. Doyen, and T. A. Henzinger, “Expressiveness and closure properties for quantitative languages,” presented at the LICS: Logic in Computer Science, 2009, pp. 199–208.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Expressiveness and Closure Properties for Quantitative Languages,” 199–208. IEEE, 2009. <a href=\"https://doi.org/10.1109/LICS.2009.16\">https://doi.org/10.1109/LICS.2009.16</a>."},"year":"2009","date_updated":"2023-02-23T11:46:11Z","type":"conference","date_published":"2009-01-01T00:00:00Z","day":"01","doi":"10.1109/LICS.2009.16","publist_id":"181","abstract":[{"lang":"eng","text":"Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the maximum, limsup, liminf, limit average, or discounted sum of the transition weights. We study expressiveness and closure questions about these quantitative languages. We first show that the set of words with value greater than a threshold can be non-w-regular for deterministic limit-average and discounted-sum automata, while this set is always w-regular when the threshold is isolated (i.e., some neighborhood around the threshold contains no word). In the latter case, we prove that the w-regular language is robust against small perturbations of the transition weights. We next consider automata with transition weights 0 or 1 and show that they are as expressive as general weighted automata in the limit-average case, but not in the discounted-sum case. Third, for quantitative languages L-1 and L-2, we consider the operations max(L-1, L-2), min(L-1, L-2), and 1-L-1, which generalize the boolean operations on languages, as well as the sum L-1 + L-2. We establish the closure properties of all classes of quantitative languages with respect to these four operations."}],"quality_controlled":"1","page":"199 - 208","language":[{"iso":"eng"}],"publisher":"IEEE","conference":{"name":"LICS: Logic in Computer Science"},"scopus_import":"1","_id":"4540","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"},{"first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","date_created":"2018-12-11T12:09:23Z","publication_status":"published","oa_version":"None","title":"Expressiveness and closure properties for quantitative languages","month":"01","pubrep_id":"55"},{"date_published":"2009-09-10T00:00:00Z","type":"conference","oa":1,"publist_id":"180","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"checksum":"e8f53abb63579de3f2bff58b2a1188e2","file_size":164428,"date_created":"2018-12-12T10:15:09Z","file_name":"IST-2012-39-v1+1_Alternating_Weighted_Automata.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:31Z","access_level":"open_access","relation":"main_file","creator":"system","file_id":"5126"}],"has_accepted_license":"1","month":"09","oa_version":"Submitted Version","project":[{"_id":"25F1337C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"214373","name":"Design for Embedded Systems"},{"name":"COMponent-Based Embedded Systems design Techniques","grant_number":"215543","call_identifier":"FP7","_id":"25EFB36C-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"conference":{"name":"FCT: Fundamentals of Computation Theory","start_date":"2009-09-02","end_date":"2009-09-04","location":"Wroclaw, Poland"},"date_updated":"2021-01-12T07:59:34Z","year":"2009","citation":{"short":"K. Chatterjee, L. Doyen, T.A. Henzinger, in:, Springer, 2009, pp. 3–13.","mla":"Chatterjee, Krishnendu, et al. <i>Alternating Weighted Automata</i>. Vol. 5699, Springer, 2009, pp. 3–13, doi:<a href=\"https://doi.org/10.1007/978-3-642-03409-1_2\">10.1007/978-3-642-03409-1_2</a>.","ista":"Chatterjee K, Doyen L, Henzinger TA. 2009. Alternating weighted automata. FCT: Fundamentals of Computation Theory, LNCS, vol. 5699, 3–13.","apa":"Chatterjee, K., Doyen, L., &#38; Henzinger, T. A. (2009). Alternating weighted automata (Vol. 5699, pp. 3–13). Presented at the FCT: Fundamentals of Computation Theory, Wroclaw, Poland: Springer. <a href=\"https://doi.org/10.1007/978-3-642-03409-1_2\">https://doi.org/10.1007/978-3-642-03409-1_2</a>","ama":"Chatterjee K, Doyen L, Henzinger TA. Alternating weighted automata. In: Vol 5699. Springer; 2009:3-13. doi:<a href=\"https://doi.org/10.1007/978-3-642-03409-1_2\">10.1007/978-3-642-03409-1_2</a>","ieee":"K. Chatterjee, L. Doyen, and T. A. Henzinger, “Alternating weighted automata,” presented at the FCT: Fundamentals of Computation Theory, Wroclaw, Poland, 2009, vol. 5699, pp. 3–13.","chicago":"Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Alternating Weighted Automata,” 5699:3–13. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-03409-1_2\">https://doi.org/10.1007/978-3-642-03409-1_2</a>."},"abstract":[{"lang":"eng","text":"Weighted automata are finite automata with numerical weights on transitions. Nondeterministic weighted automata define quantitative languages L that assign to each word w a real number L(w) computed as the maximal value of all runs over w, and the value of a run r is a function of the sequence of weights that appear along r. There are several natural functions to consider such as Sup, LimSup, LimInf, limit average, and discounted sum of transition weights.\r\nWe introduce alternating weighted automata in which the transitions of the runs are chosen by two players in a turn-based fashion. Each word is assigned the maximal value of a run that the first player can enforce regardless of the choices made by the second player. We survey the results about closure properties, expressiveness, and decision problems for nondeterministic weighted automata, and we extend these results to alternating weighted automata.\r\nFor quantitative languages L 1 and L 2, we consider the pointwise operations max(L 1,L 2), min(L 1,L 2), 1 − L 1, and the sum L 1 + L 2. We establish the closure properties of all classes of alternating weighted automata with respect to these four operations.\r\nWe next compare the expressive power of the various classes of alternating and nondeterministic weighted automata over infinite words. In particular, for limit average and discounted sum, we show that alternation brings more expressive power than nondeterminism.\r\nFinally, we present decidability results and open questions for the quantitative extension of the classical decision problems in automata theory: emptiness, universality, language inclusion, and language equivalence."}],"doi":"10.1007/978-3-642-03409-1_2","day":"10","ddc":["004"],"acknowledgement":"This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), by the European Combest, Quasimodo, and Gasics projects, by the PAI program Moves funded by the Belgian Federal Government, and by the CFV (Federated Center in Verification) funded by the F.R.S.-FNRS.","volume":5699,"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Doyen, Laurent","first_name":"Laurent","last_name":"Doyen"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"_id":"4542","scopus_import":1,"title":"Alternating weighted automata","pubrep_id":"39","alternative_title":["LNCS"],"intvolume":"      5699","publication_status":"published","department":[{"_id":"KrCh"}],"date_created":"2018-12-11T12:09:23Z","file_date_updated":"2020-07-14T12:46:31Z","page":"3 - 13","quality_controlled":"1","ec_funded":1,"publisher":"Springer"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publist_id":"178","date_published":"2009-08-01T00:00:00Z","type":"conference","conference":{"name":"MFCS: Mathematical Foundations of Computer Science","start_date":"2009-08-24","location":"High Tatras, Slovakia","end_date":"2009-08-28"},"language":[{"iso":"eng"}],"oa_version":"None","project":[{"call_identifier":"FP7","_id":"25EFB36C-B435-11E9-9278-68D0E5697425","grant_number":"215543","name":"COMponent-Based Embedded Systems design Techniques"},{"_id":"25F1337C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Design for Embedded Systems","grant_number":"214373"}],"month":"08","acknowledgement":"This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), and by the European project Combest.","volume":5734,"doi":"10.1007/978-3-642-03816-7_4","day":"01","abstract":[{"text":"The synthesis of a reactive system with respect to all omega-regular specification requires the solution of a graph game. Such games have been extended in two natural ways. First, a game graph can be equipped with probabilistic choices between alternative transitions, thus allowing the, modeling of uncertain behaviour. These are called stochastic games. Second, a liveness specification can he strengthened to require satisfaction within all unknown but bounded amount of time. These are called finitary objectives. We study. for the first time, the, combination of Stochastic games and finitary objectives. We characterize the requirements on optimal strategies and provide algorithms for Computing the maximal achievable probability of winning stochastic games with finitary parity or Street, objectives. Most notably the set of state's from which a player can win with probability . for a finitary parity objective can he computed in polynomial time even though no polynomial-time algorithm is known in the nonfinitary case.","lang":"eng"}],"date_updated":"2021-01-12T07:59:35Z","citation":{"ista":"Chatterjee K, Henzinger TA, Horn F. 2009. Stochastic games with finitary objectives. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 5734, 34–54.","short":"K. Chatterjee, T.A. Henzinger, F. Horn, in:, Springer, 2009, pp. 34–54.","mla":"Chatterjee, Krishnendu, et al. <i>Stochastic Games with Finitary Objectives</i>. Vol. 5734, Springer, 2009, pp. 34–54, doi:<a href=\"https://doi.org/10.1007/978-3-642-03816-7_4\">10.1007/978-3-642-03816-7_4</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and F. Horn, “Stochastic games with finitary objectives,” presented at the MFCS: Mathematical Foundations of Computer Science, High Tatras, Slovakia, 2009, vol. 5734, pp. 34–54.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. “Stochastic Games with Finitary Objectives,” 5734:34–54. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-03816-7_4\">https://doi.org/10.1007/978-3-642-03816-7_4</a>.","ama":"Chatterjee K, Henzinger TA, Horn F. Stochastic games with finitary objectives. In: Vol 5734. Springer; 2009:34-54. doi:<a href=\"https://doi.org/10.1007/978-3-642-03816-7_4\">10.1007/978-3-642-03816-7_4</a>","apa":"Chatterjee, K., Henzinger, T. A., &#38; Horn, F. (2009). Stochastic games with finitary objectives (Vol. 5734, pp. 34–54). Presented at the MFCS: Mathematical Foundations of Computer Science, High Tatras, Slovakia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-03816-7_4\">https://doi.org/10.1007/978-3-642-03816-7_4</a>"},"year":"2009","publisher":"Springer","page":"34 - 54","quality_controlled":"1","ec_funded":1,"publication_status":"published","department":[{"_id":"KrCh"}],"date_created":"2018-12-11T12:09:24Z","alternative_title":["LNCS"],"title":"Stochastic games with finitary objectives","intvolume":"      5734","_id":"4543","scopus_import":1,"author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger"},{"id":"37327ACE-F248-11E8-B48F-1D18A9856A87","last_name":"Horn","first_name":"Florian","full_name":"Horn, Florian"}]},{"extern":1,"status":"public","main_file_link":[{"open_access":"1","url":"https://repository.ist.ac.at/id/eprint/37"}],"file":[{"access_level":"open_access","relation":"main_file","file_id":"4662","creator":"system","date_created":"2018-12-12T10:08:03Z","checksum":"ce7dc1667502e26b23c07a767ac41ae6","file_size":212369,"date_updated":"2020-07-14T12:46:31Z","file_name":"IST-2012-37-v1+1_Termination_criteria_for_solving_concurrent_safety_and_reachability_games.pdf","content_type":"application/pdf"}],"date_published":"2009-01-01T00:00:00Z","type":"conference","date_updated":"2021-01-12T07:59:35Z","citation":{"ama":"Chatterjee K, De Alfaro L, Henzinger TA. Termination criteria for solving concurrent safety and reachability games. In: SIAM; 2009:197-206. doi:<a href=\"https://doi.org/10.1137/1.9781611973068.23\">10.1137/1.9781611973068.23</a>","apa":"Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2009). Termination criteria for solving concurrent safety and reachability games (pp. 197–206). Presented at the SODA: Symposium on Discrete Algorithms, SIAM. <a href=\"https://doi.org/10.1137/1.9781611973068.23\">https://doi.org/10.1137/1.9781611973068.23</a>","ieee":"K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Termination criteria for solving concurrent safety and reachability games,” presented at the SODA: Symposium on Discrete Algorithms, 2009, pp. 197–206.","chicago":"Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Termination Criteria for Solving Concurrent Safety and Reachability Games,” 197–206. SIAM, 2009. <a href=\"https://doi.org/10.1137/1.9781611973068.23\">https://doi.org/10.1137/1.9781611973068.23</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Termination Criteria for Solving Concurrent Safety and Reachability Games</i>. SIAM, 2009, pp. 197–206, doi:<a href=\"https://doi.org/10.1137/1.9781611973068.23\">10.1137/1.9781611973068.23</a>.","short":"K. Chatterjee, L. De Alfaro, T.A. Henzinger, in:, SIAM, 2009, pp. 197–206.","ista":"Chatterjee K, De Alfaro L, Henzinger TA. 2009. Termination criteria for solving concurrent safety and reachability games. SODA: Symposium on Discrete Algorithms, 197–206."},"year":"2009","abstract":[{"text":"We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. We present in this paper a strategy improvement algorithm for computing the value of a concurrent safety game, that is, the maximal probability with which player 1 can enforce the safety objective. The algorithm yields a sequence of player-1 strategies which ensure probabilities of winning that converge monotonically to the value of the safety game. Our result is significant because the strategy improvement algorithm provides, for the first time, a way to approximate the value of a concurrent safety game from below. Since a value iteration algorithm, or a strategy improvement algorithm for reachability games, can be used to approximate the same value from above, the combination of both algorithms yields a method for computing a converging sequence of upper and lower bounds for the values of concurrent reachability and safety games. Previous methods could approximate the values of these games only from one direction, and as no rates of convergence are known, they did not provide a practical way to solve these games.","lang":"eng"}],"publist_id":"176","oa":1,"doi":"10.1137/1.9781611973068.23","day":"01","file_date_updated":"2020-07-14T12:46:31Z","page":"197 - 206","quality_controlled":0,"conference":{"name":"SODA: Symposium on Discrete Algorithms"},"publisher":"SIAM","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Krishnendu Chatterjee"},{"first_name":"Luca","last_name":"De Alfaro","full_name":"de Alfaro, Luca"},{"full_name":"Thomas Henzinger","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"_id":"4544","pubrep_id":"37","title":"Termination criteria for solving concurrent safety and reachability games","month":"01","publication_status":"published","date_created":"2018-12-11T12:09:24Z"},{"publisher":"Springer","page":"1 - 15","quality_controlled":"1","ec_funded":1,"file_date_updated":"2020-07-14T12:46:31Z","publication_status":"published","date_created":"2018-12-11T12:09:24Z","department":[{"_id":"KrCh"}],"pubrep_id":"38","title":"A survey of stochastic games with limsup and liminf objectives","alternative_title":["LNCS"],"intvolume":"      5556","_id":"4545","scopus_import":1,"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"volume":5556,"acknowledgement":"This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), by the European projects COMBEST, Quasimodo, Gasics, by the PAI program Moves funded by the Belgian Federal Government, and by the CFV (Federated Center in Verification) funded by the F.R.S.-FNRS.","ddc":["000","005"],"doi":"10.1007/978-3-642-02930-1_1","day":"24","abstract":[{"lang":"eng","text":"A stochastic game is a two-player game played oil a graph, where in each state the successor is chosen either by One of the players, or according to a probability distribution. We Survey Stochastic games with limsup and liminf objectives. A real-valued re-ward is assigned to each state, and the value of all infinite path is the limsup (resp. liminf) of all rewards along the path. The value of a stochastic game is the maximal expected value of an infinite path that call he achieved by resolving the decisions of the first player. We present the complexity of computing values of Stochastic games and their subclasses, and the complexity, of optimal strategies in such games. "}],"date_updated":"2021-01-12T07:59:35Z","year":"2009","citation":{"chicago":"Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “A Survey of Stochastic Games with Limsup and Liminf Objectives,” 5556:1–15. Springer, 2009. <a href=\"https://doi.org/10.1007/978-3-642-02930-1_1\">https://doi.org/10.1007/978-3-642-02930-1_1</a>.","ieee":"K. Chatterjee, L. Doyen, and T. A. Henzinger, “A survey of stochastic games with limsup and liminf objectives,” presented at the ICALP: Automata, Languages and Programming, Rhodos, Greece, 2009, vol. 5556, pp. 1–15.","ama":"Chatterjee K, Doyen L, Henzinger TA. A survey of stochastic games with limsup and liminf objectives. In: Vol 5556. Springer; 2009:1-15. doi:<a href=\"https://doi.org/10.1007/978-3-642-02930-1_1\">10.1007/978-3-642-02930-1_1</a>","apa":"Chatterjee, K., Doyen, L., &#38; Henzinger, T. A. (2009). A survey of stochastic games with limsup and liminf objectives (Vol. 5556, pp. 1–15). Presented at the ICALP: Automata, Languages and Programming, Rhodos, Greece: Springer. <a href=\"https://doi.org/10.1007/978-3-642-02930-1_1\">https://doi.org/10.1007/978-3-642-02930-1_1</a>","ista":"Chatterjee K, Doyen L, Henzinger TA. 2009. A survey of stochastic games with limsup and liminf objectives. ICALP: Automata, Languages and Programming, LNCS, vol. 5556, 1–15.","mla":"Chatterjee, Krishnendu, et al. <i>A Survey of Stochastic Games with Limsup and Liminf Objectives</i>. Vol. 5556, Springer, 2009, pp. 1–15, doi:<a href=\"https://doi.org/10.1007/978-3-642-02930-1_1\">10.1007/978-3-642-02930-1_1</a>.","short":"K. Chatterjee, L. Doyen, T.A. Henzinger, in:, Springer, 2009, pp. 1–15."},"conference":{"location":"Rhodos, Greece","end_date":"2009-07-12","start_date":"2009-07-05","name":"ICALP: Automata, Languages and Programming"},"language":[{"iso":"eng"}],"oa_version":"Submitted Version","project":[{"name":"COMponent-Based Embedded Systems design Techniques","grant_number":"215543","_id":"25EFB36C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"month":"06","has_accepted_license":"1","file":[{"file_size":187419,"checksum":"dabb6d24428a000254c95493d9c492e6","date_created":"2018-12-12T10:13:11Z","file_name":"IST-2012-38-v1+1_A_survey_of_stochastic_games_with_limsup_and_liminf_objectives.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:31Z","access_level":"open_access","relation":"main_file","creator":"system","file_id":"4992"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"177","oa":1,"date_published":"2009-06-24T00:00:00Z","type":"conference"}]