[{"quality_controlled":"1","date_published":"2014-10-01T00:00:00Z","doi":"10.1016/j.conb.2014.06.006","publication_status":"published","publication_identifier":{"issn":["0959-4388"]},"citation":{"ieee":"L. B. Sweeney and D. B. Kelley, “Harnessing vocal patterns for social communication,” <i>Current Opinion in Neurobiology</i>, vol. 28, no. 10. Elsevier, pp. 34–41, 2014.","chicago":"Sweeney, Lora B., and Darcy B Kelley. “Harnessing Vocal Patterns for Social Communication.” <i>Current Opinion in Neurobiology</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.conb.2014.06.006\">https://doi.org/10.1016/j.conb.2014.06.006</a>.","short":"L.B. Sweeney, D.B. Kelley, Current Opinion in Neurobiology 28 (2014) 34–41.","ama":"Sweeney LB, Kelley DB. Harnessing vocal patterns for social communication. <i>Current Opinion in Neurobiology</i>. 2014;28(10):34-41. doi:<a href=\"https://doi.org/10.1016/j.conb.2014.06.006\">10.1016/j.conb.2014.06.006</a>","ista":"Sweeney LB, Kelley DB. 2014. Harnessing vocal patterns for social communication. Current Opinion in Neurobiology. 28(10), 34–41.","mla":"Sweeney, Lora B., and Darcy B. Kelley. “Harnessing Vocal Patterns for Social Communication.” <i>Current Opinion in Neurobiology</i>, vol. 28, no. 10, Elsevier, 2014, pp. 34–41, doi:<a href=\"https://doi.org/10.1016/j.conb.2014.06.006\">10.1016/j.conb.2014.06.006</a>.","apa":"Sweeney, L. B., &#38; Kelley, D. B. (2014). Harnessing vocal patterns for social communication. <i>Current Opinion in Neurobiology</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.conb.2014.06.006\">https://doi.org/10.1016/j.conb.2014.06.006</a>"},"language":[{"iso":"eng"}],"issue":"10","extern":"1","intvolume":"        28","status":"public","date_created":"2020-04-30T10:35:39Z","volume":28,"title":"Harnessing vocal patterns for social communication","date_updated":"2024-01-31T10:14:08Z","day":"01","oa_version":"None","type":"journal_article","month":"10","author":[{"first_name":"Lora Beatrice Jaeger","last_name":"Sweeney","orcid":"0000-0001-9242-5601","id":"56BE8254-C4F0-11E9-8E45-0B23E6697425","full_name":"Sweeney, Lora Beatrice Jaeger"},{"full_name":"Kelley, Darcy B","first_name":"Darcy B","last_name":"Kelley"}],"page":"34-41","article_processing_charge":"No","article_type":"original","publication":"Current Opinion in Neurobiology","_id":"7699","year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Elsevier"},{"language":[{"iso":"eng"}],"citation":{"ieee":"D.-A. Alistarh, P. Eugster, M. Herlihy, A. Matveev, and N. Shavit, “StackTrack: An automated transactional approach to concurrent memory reclamation,” presented at the EuroSys: European Conference on Computer Systems, 2014.","chicago":"Alistarh, Dan-Adrian, Patrick Eugster, Maurice Herlihy, Alexander Matveev, and Nir Shavit. “StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation.” ACM, 2014. <a href=\"https://doi.org/10.1145/2592798.2592808\">https://doi.org/10.1145/2592798.2592808</a>.","short":"D.-A. Alistarh, P. Eugster, M. Herlihy, A. Matveev, N. Shavit, in:, ACM, 2014.","ama":"Alistarh D-A, Eugster P, Herlihy M, Matveev A, Shavit N. StackTrack: An automated transactional approach to concurrent memory reclamation. In: ACM; 2014. doi:<a href=\"https://doi.org/10.1145/2592798.2592808\">10.1145/2592798.2592808</a>","ista":"Alistarh D-A, Eugster P, Herlihy M, Matveev A, Shavit N. 2014. StackTrack: An automated transactional approach to concurrent memory reclamation. EuroSys: European Conference on Computer Systems.","mla":"Alistarh, Dan-Adrian, et al. <i>StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation</i>. ACM, 2014, doi:<a href=\"https://doi.org/10.1145/2592798.2592808\">10.1145/2592798.2592808</a>.","apa":"Alistarh, D.-A., Eugster, P., Herlihy, M., Matveev, A., &#38; Shavit, N. (2014). StackTrack: An automated transactional approach to concurrent memory reclamation. Presented at the EuroSys: European Conference on Computer Systems, ACM. <a href=\"https://doi.org/10.1145/2592798.2592808\">https://doi.org/10.1145/2592798.2592808</a>"},"conference":{"name":"EuroSys: European Conference on Computer Systems"},"extern":"1","status":"public","doi":"10.1145/2592798.2592808","date_published":"2014-01-01T00:00:00Z","publication_status":"published","article_processing_charge":"No","_id":"770","year":"2014","acknowledgement":"Dan Alistarh - Part  of  this  work  was  performed  while  the  author  was  a  Postdoctoral\r\nAssociate a MIT CSAIL, supported in part by NSF grant CCF-1217921,\r\nDoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle\r\nand Intel corporations.\r\nPatrick Eugester - Supported in part by DARPA grant N11AP20014 and NSF grant CNS-\r\n1117065.\r\nMaurice Herlihy - Supported by NSF grant 1301924.\r\nNir Shavit - Supported in part by NSF grants CCF-1217921 and CCF-1301926, DoE\r\nASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and\r\nIntel corporations.","publisher":"ACM","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"6888","date_created":"2018-12-11T11:48:24Z","title":"StackTrack: An automated transactional approach to concurrent memory reclamation","oa_version":"None","type":"conference","month":"01","date_updated":"2023-02-23T13:14:25Z","day":"01","abstract":[{"lang":"eng","text":"Dynamic memory reclamation is arguably the biggest open problem in concurrent data structure design: All known solutions induce high overhead, or must be customized to the specific data structure by the programmer, or both. This paper presents StackTrack, the first concurrent memory reclamation scheme that can be applied automatically by a compiler, while maintaining efficiency. StackTrack eliminates most of the expensive bookkeeping required for memory reclamation by leveraging the power of hardware transactional memory (HTM) in a new way: it tracks thread variables dynamically, and in an atomic fashion. This effectively makes all memory references visible without having threads pay the overhead of writing out this information. Our empirical results show that this new approach matches or outperforms prior, non-automated, techniques."}],"author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"last_name":"Eugster","first_name":"Patrick","full_name":"Eugster, Patrick"},{"last_name":"Herlihy","first_name":"Maurice","full_name":"Herlihy, Maurice"},{"last_name":"Matveev","first_name":"Alexander","full_name":"Matveev, Alexander"},{"full_name":"Shavit, Nir","first_name":"Nir","last_name":"Shavit"}]},{"date_published":"2014-01-01T00:00:00Z","doi":"10.1145/2611462.2611499","publication_status":"published","language":[{"iso":"eng"}],"citation":{"ama":"Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems. In: ACM; 2014:232-241. doi:<a href=\"https://doi.org/10.1145/2611462.2611499\">10.1145/2611462.2611499</a>","mla":"Alistarh, Dan-Adrian, et al. <i>Balls-into-Leaves: Sub-Logarithmic Renaming in Synchronous Message-Passing Systems</i>. ACM, 2014, pp. 232–41, doi:<a href=\"https://doi.org/10.1145/2611462.2611499\">10.1145/2611462.2611499</a>.","ista":"Alistarh D-A, Denysyuk O, Rodrígues L, Shavit N. 2014. Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems. PODC: Principles of Distributed Computing, 232–241.","apa":"Alistarh, D.-A., Denysyuk, O., Rodrígues, L., &#38; Shavit, N. (2014). Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems (pp. 232–241). Presented at the PODC: Principles of Distributed Computing, ACM. <a href=\"https://doi.org/10.1145/2611462.2611499\">https://doi.org/10.1145/2611462.2611499</a>","ieee":"D.-A. Alistarh, O. Denysyuk, L. Rodrígues, and N. Shavit, “Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems,” presented at the PODC: Principles of Distributed Computing, 2014, pp. 232–241.","chicago":"Alistarh, Dan-Adrian, Oksana Denysyuk, Luís Rodrígues, and Nir Shavit. “Balls-into-Leaves: Sub-Logarithmic Renaming in Synchronous Message-Passing Systems,” 232–41. ACM, 2014. <a href=\"https://doi.org/10.1145/2611462.2611499\">https://doi.org/10.1145/2611462.2611499</a>.","short":"D.-A. Alistarh, O. Denysyuk, L. Rodrígues, N. Shavit, in:, ACM, 2014, pp. 232–241."},"conference":{"name":"PODC: Principles of Distributed Computing"},"extern":"1","status":"public","date_created":"2018-12-11T11:48:25Z","publist_id":"6884","title":"Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems","type":"conference","oa_version":"None","month":"01","abstract":[{"text":"We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of ©(logn) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sublogarithmic solutions exist for this apparently simple but intriguing problem. In this paper, we combine the two approaches to provide a new randomized solution for tight renaming, which terminates in O (log log n) communication rounds with high probability, against a strong adaptive adversary. Our solution, called Balls-into-Leaves, combines the deterministic approach with a new randomized scheme to obtain perfectly balanced allocations. The algorithm arranges the items as leaves of a tree, and participants repeatedly perform random choices among the leaves. The algorithm exchanges information in each round to split the participants into progressively smaller groups whose random choices do not conflict. We then extend the algorithm to terminate early in O(log log) rounds w.h.p., where is the actual number of failures. These results imply an exponential separation between deterministic and randomized algorithms for the tight renaming problem in message-passing systems.","lang":"eng"}],"date_updated":"2023-02-23T13:14:49Z","day":"01","page":"232 - 241","author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"},{"full_name":"Denysyuk, Oksana","last_name":"Denysyuk","first_name":"Oksana"},{"last_name":"Rodrígues","first_name":"Luís","full_name":"Rodrígues, Luís"},{"full_name":"Shavit, Nir","first_name":"Nir","last_name":"Shavit"}],"article_processing_charge":"No","_id":"771","year":"2014","acknowledgement":"Dan Alistarh was partially supported by the SNF Post-\r\ndoctoral Fellows Program, NSF grant CCF-1217921, DoE\r\nASCR grant ER26116/DE-SC0008923, and by grants from\r\nthe Oracle and Intel corporations.\r\nOksana Denysyuk and Lu ́ıs Rodrigues were partially supported by Funda ̧c ̃ao para a Ciˆencia e Tecnologia (FCT) via\r\nthe project PEPITA (PTDC/EEI-SCR/2776/2012) and via\r\nthe INESC-ID multi-annual funding through the PIDDAC\r\nProgram fund grant, under project PEst-OE/EEI/LA0021/\r\n2013.\r\nNir Shavit was supported in part by NSF grants CCF-1217921 and CCF-1301926, DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"ACM"},{"day":"01","abstract":[{"lang":"eng","text":"Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior."}],"date_updated":"2023-02-23T13:15:13Z","oa_version":"Preprint","month":"01","type":"conference","author":[{"full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian"},{"last_name":"Censor Hillel","first_name":"Keren","full_name":"Censor Hillel, Keren"},{"last_name":"Shavit","first_name":"Nir","full_name":"Shavit, Nir"}],"page":"714 - 723","date_created":"2018-12-11T11:48:25Z","publist_id":"6885","arxiv":1,"title":"Are lock-free concurrent algorithms practically wait-free?","year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"ACM","acknowledgement":"Dan Alistarh - Part of this work was performed while the author was a Postdoctoral Associate at MIT CSAIL, where he was supported by SNF\r\nPostdoctoral Fellows Program, NSF grant CCF-1217921, DoE\r\nASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations.\r\nKeron Censor-Hillel - Shalon Fellow\r\nNir Shavit - This work was supported in part by NSF grants CCF-1217921 and\r\nCCF-1301926, DoE ASCR grant ER26116/DE-SC0008923, and\r\nby grants from the Oracle and Intel corporations.","article_processing_charge":"No","_id":"772","publication_status":"published","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1311.3200","open_access":"1"}],"date_published":"2014-01-01T00:00:00Z","doi":"10.1145/2591796.2591836","external_id":{"arxiv":["1311.3200"]},"status":"public","citation":{"ista":"Alistarh D-A, Censor Hillel K, Shavit N. 2014. Are lock-free concurrent algorithms practically wait-free? STOC: Symposium on Theory of Computing, 714–723.","mla":"Alistarh, Dan-Adrian, et al. <i>Are Lock-Free Concurrent Algorithms Practically Wait-Free?</i> ACM, 2014, pp. 714–23, doi:<a href=\"https://doi.org/10.1145/2591796.2591836\">10.1145/2591796.2591836</a>.","apa":"Alistarh, D.-A., Censor Hillel, K., &#38; Shavit, N. (2014). Are lock-free concurrent algorithms practically wait-free? (pp. 714–723). Presented at the STOC: Symposium on Theory of Computing, ACM. <a href=\"https://doi.org/10.1145/2591796.2591836\">https://doi.org/10.1145/2591796.2591836</a>","ama":"Alistarh D-A, Censor Hillel K, Shavit N. Are lock-free concurrent algorithms practically wait-free? In: ACM; 2014:714-723. doi:<a href=\"https://doi.org/10.1145/2591796.2591836\">10.1145/2591796.2591836</a>","short":"D.-A. Alistarh, K. Censor Hillel, N. Shavit, in:, ACM, 2014, pp. 714–723.","ieee":"D.-A. Alistarh, K. Censor Hillel, and N. Shavit, “Are lock-free concurrent algorithms practically wait-free?,” presented at the STOC: Symposium on Theory of Computing, 2014, pp. 714–723.","chicago":"Alistarh, Dan-Adrian, Keren Censor Hillel, and Nir Shavit. “Are Lock-Free Concurrent Algorithms Practically Wait-Free?,” 714–23. ACM, 2014. <a href=\"https://doi.org/10.1145/2591796.2591836\">https://doi.org/10.1145/2591796.2591836</a>."},"language":[{"iso":"eng"}],"extern":"1","conference":{"name":"STOC: Symposium on Theory of Computing"}},{"alternative_title":["LNCS"],"editor":[{"last_name":"Kuhn","first_name":"Fabian","full_name":"Kuhn, Fabian"}],"status":"public","extern":"1","intvolume":"      8784","conference":{"location":"Austin, USA","name":"DISC: Distributed Computing","start_date":"2014-10-12","end_date":"2014-10-15"},"citation":{"short":"D.-A. Alistarh, J. Aspnes, V. King, J. Saia, in:, F. Kuhn (Ed.), Springer, 2014, pp. 61–75.","chicago":"Alistarh, Dan-Adrian, James Aspnes, Valerie King, and Jared Saia. “Communication-Efficient Randomized Consensus.” edited by Fabian Kuhn, 8784:61–75. Springer, 2014. <a href=\"https://doi.org/10.1007/978-3-662-45174-8_5\">https://doi.org/10.1007/978-3-662-45174-8_5</a>.","ieee":"D.-A. Alistarh, J. Aspnes, V. King, and J. Saia, “Communication-efficient randomized consensus,” presented at the DISC: Distributed Computing, Austin, USA, 2014, vol. 8784, pp. 61–75.","apa":"Alistarh, D.-A., Aspnes, J., King, V., &#38; Saia, J. (2014). Communication-efficient randomized consensus. In F. Kuhn (Ed.) (Vol. 8784, pp. 61–75). Presented at the DISC: Distributed Computing, Austin, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-662-45174-8_5\">https://doi.org/10.1007/978-3-662-45174-8_5</a>","ista":"Alistarh D-A, Aspnes J, King V, Saia J. 2014. Communication-efficient randomized consensus. DISC: Distributed Computing, LNCS, vol. 8784, 61–75.","mla":"Alistarh, Dan-Adrian, et al. <i>Communication-Efficient Randomized Consensus</i>. Edited by Fabian Kuhn, vol. 8784, Springer, 2014, pp. 61–75, doi:<a href=\"https://doi.org/10.1007/978-3-662-45174-8_5\">10.1007/978-3-662-45174-8_5</a>.","ama":"Alistarh D-A, Aspnes J, King V, Saia J. Communication-efficient randomized consensus. In: Kuhn F, ed. Vol 8784. Springer; 2014:61-75. doi:<a href=\"https://doi.org/10.1007/978-3-662-45174-8_5\">10.1007/978-3-662-45174-8_5</a>"},"language":[{"iso":"eng"}],"publication_status":"published","date_published":"2014-01-01T00:00:00Z","doi":"10.1007/978-3-662-45174-8_5","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2014","_id":"773","article_processing_charge":"No","author":[{"last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Aspnes, James","last_name":"Aspnes","first_name":"James"},{"full_name":"King, Valerie","first_name":"Valerie","last_name":"King"},{"full_name":"Saia, Jared","last_name":"Saia","first_name":"Jared"}],"page":"61 - 75","date_updated":"2023-02-23T13:15:36Z","day":"01","abstract":[{"lang":"eng","text":"We describe a new randomized consensus protocol with expected message complexity O(n2log2n) when fewer than n/2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n2) message lower bound. The protocol further ensures that no process sends more than O(n log3n) messages in expectation, which is again within logarithmic factors of optimal.We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt + t2log2t) total messages. Our protocol uses messages of size O(log n), and can therefore scale to large networks.\r\n\r\nWe consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary.\r\n\r\nOur approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model."}],"month":"01","type":"conference","oa_version":"None","volume":8784,"title":"Communication-efficient randomized consensus","date_created":"2018-12-11T11:48:25Z","publist_id":"6881"},{"status":"public","extern":"1","conference":{"name":"PODC: Principles of Distributed Computing"},"citation":{"ama":"Alistarh D-A, Censor Hille K, Shavit N. Brief announcement: Are lock-free concurrent algorithms practically wait-free? In: ACM; 2014:50-52. doi:<a href=\"https://doi.org/10.1145/2611462.2611502\">10.1145/2611462.2611502</a>","apa":"Alistarh, D.-A., Censor Hille, K., &#38; Shavit, N. (2014). Brief announcement: Are lock-free concurrent algorithms practically wait-free? (pp. 50–52). Presented at the PODC: Principles of Distributed Computing, ACM. <a href=\"https://doi.org/10.1145/2611462.2611502\">https://doi.org/10.1145/2611462.2611502</a>","ista":"Alistarh D-A, Censor Hille K, Shavit N. 2014. Brief announcement: Are lock-free concurrent algorithms practically wait-free? PODC: Principles of Distributed Computing, 50–52.","mla":"Alistarh, Dan-Adrian, et al. <i>Brief Announcement: Are Lock-Free Concurrent Algorithms Practically Wait-Free?</i> ACM, 2014, pp. 50–52, doi:<a href=\"https://doi.org/10.1145/2611462.2611502\">10.1145/2611462.2611502</a>.","chicago":"Alistarh, Dan-Adrian, Keren Censor Hille, and Nir Shavit. “Brief Announcement: Are Lock-Free Concurrent Algorithms Practically Wait-Free?,” 50–52. ACM, 2014. <a href=\"https://doi.org/10.1145/2611462.2611502\">https://doi.org/10.1145/2611462.2611502</a>.","ieee":"D.-A. Alistarh, K. Censor Hille, and N. Shavit, “Brief announcement: Are lock-free concurrent algorithms practically wait-free?,” presented at the PODC: Principles of Distributed Computing, 2014, pp. 50–52.","short":"D.-A. Alistarh, K. Censor Hille, N. Shavit, in:, ACM, 2014, pp. 50–52."},"language":[{"iso":"eng"}],"publication_status":"published","date_published":"2014-01-01T00:00:00Z","doi":"10.1145/2611462.2611502","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"ACM","acknowledgement":"Dan Alistarh - Part  of  this  work  was  performed  while  the  author  was  a\r\nPostdoctoral Associate at MIT CSAIL, where he was supported  by  SNF  Postdoctoral  Fellows  Program,  NSF  grant\r\nCCF-1217921, DoE ASCR grant ER26116/DE-SC0008923,\r\nand by grants from the Oracle and Intel corporations.\r\nKeren Censor-Hille - Shalon Fellow\r\nNir Shavit - This  work  was  supported  in  part  by  NSF  grants  CCF-1217921 and CCF-1301926, DoE ASCR grant ER26116/DE-\r\nSC0008923, and by grants from the Oracle and Intel corporations.","year":"2014","_id":"774","article_processing_charge":"No","page":"50 - 52","author":[{"orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh"},{"last_name":"Censor Hille","first_name":"Keren","full_name":"Censor Hille, Keren"},{"full_name":"Shavit, Nir","last_name":"Shavit","first_name":"Nir"}],"date_updated":"2023-02-23T13:15:54Z","day":"01","abstract":[{"text":"Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers would prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is in general a complex undertaking, and the resulting algorithms are not always efficient, so most non-blocking commercial code is only lock-free, and the design of efficient wait-free algorithms has been left to the academic community. In [2], we suggest a solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a broad subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes.","lang":"eng"}],"type":"conference","oa_version":"None","month":"01","title":"Brief announcement: Are lock-free concurrent algorithms practically wait-free?","publist_id":"6882","date_created":"2018-12-11T11:48:26Z"},{"publisher":"Wiley","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2014","place":"Chichester, UK","_id":"7743","publication":"Genotype-by-Environment Interactions and Sexual Selection","article_processing_charge":"No","author":[{"first_name":"Matthew Richard","last_name":"Robinson","id":"E5D42276-F5DA-11E9-8E24-6303E6697425","orcid":"0000-0001-8982-8813","full_name":"Robinson, Matthew Richard"},{"first_name":"Anna","last_name":"Qvarnström","full_name":"Qvarnström, Anna"}],"page":"137-168","oa_version":"None","month":"08","type":"book_chapter","day":"29","abstract":[{"text":"Experimental studies have demonstrated that environmental variation can create genotype‐environment interactions (GEIs) in the traits involved in sexual selection. Understanding the genetic architecture of phenotype across environments will require statistical tests that can describe both changes in genetic variance and covariance across environments. This chapter outlines the theoretical framework for the processes of sexual selection in the wild, identifying key parameters in wild systems, and highlighting the potential effects of the environment. It describes the proposed approaches for the estimation of these key parameters in a quantitative genetic framework within naturally occurring pedigreed populations. The chapter provides a worked example for a range of analysis methods. It aims to provide an overview of the analytical methods that can be used to model GEIs for traits involved in sexual selection in naturally occurring pedigreed populations.","lang":"eng"}],"date_updated":"2021-01-12T08:15:13Z","title":"Influence of the environment on the genetic architecture of traits involved in sexual selection within wild populations","date_created":"2020-04-30T10:58:39Z","status":"public","editor":[{"full_name":"Hunt, John","last_name":"Hunt","first_name":"John"},{"full_name":"Hosken, David","first_name":"David","last_name":"Hosken"}],"extern":"1","citation":{"chicago":"Robinson, Matthew Richard, and Anna Qvarnström. “Influence of the Environment on the Genetic Architecture of Traits Involved in Sexual Selection within Wild Populations.” In <i>Genotype-by-Environment Interactions and Sexual Selection</i>, edited by John Hunt and David Hosken, 137–68. Chichester, UK: Wiley, 2014. <a href=\"https://doi.org/10.1002/9781118912591.ch6\">https://doi.org/10.1002/9781118912591.ch6</a>.","ieee":"M. R. Robinson and A. Qvarnström, “Influence of the environment on the genetic architecture of traits involved in sexual selection within wild populations,” in <i>Genotype-by-Environment Interactions and Sexual Selection</i>, J. Hunt and D. Hosken, Eds. Chichester, UK: Wiley, 2014, pp. 137–168.","short":"M.R. Robinson, A. Qvarnström, in:, J. Hunt, D. Hosken (Eds.), Genotype-by-Environment Interactions and Sexual Selection, Wiley, Chichester, UK, 2014, pp. 137–168.","ama":"Robinson MR, Qvarnström A. Influence of the environment on the genetic architecture of traits involved in sexual selection within wild populations. In: Hunt J, Hosken D, eds. <i>Genotype-by-Environment Interactions and Sexual Selection</i>. Chichester, UK: Wiley; 2014:137-168. doi:<a href=\"https://doi.org/10.1002/9781118912591.ch6\">10.1002/9781118912591.ch6</a>","apa":"Robinson, M. R., &#38; Qvarnström, A. (2014). Influence of the environment on the genetic architecture of traits involved in sexual selection within wild populations. In J. Hunt &#38; D. Hosken (Eds.), <i>Genotype-by-Environment Interactions and Sexual Selection</i> (pp. 137–168). Chichester, UK: Wiley. <a href=\"https://doi.org/10.1002/9781118912591.ch6\">https://doi.org/10.1002/9781118912591.ch6</a>","mla":"Robinson, Matthew Richard, and Anna Qvarnström. “Influence of the Environment on the Genetic Architecture of Traits Involved in Sexual Selection within Wild Populations.” <i>Genotype-by-Environment Interactions and Sexual Selection</i>, edited by John Hunt and David Hosken, Wiley, 2014, pp. 137–68, doi:<a href=\"https://doi.org/10.1002/9781118912591.ch6\">10.1002/9781118912591.ch6</a>.","ista":"Robinson MR, Qvarnström A. 2014.Influence of the environment on the genetic architecture of traits involved in sexual selection within wild populations. In: Genotype-by-Environment Interactions and Sexual Selection. , 137–168."},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9780470671795"],"eisbn":["9781118912591"]},"publication_status":"published","doi":"10.1002/9781118912591.ch6","date_published":"2014-08-29T00:00:00Z","quality_controlled":"1"},{"date_updated":"2021-01-12T08:15:14Z","day":"01","oa_version":"None","type":"journal_article","month":"04","page":"124-132","author":[{"first_name":"Matthew Richard","last_name":"Robinson","orcid":"0000-0001-8982-8813","id":"E5D42276-F5DA-11E9-8E24-6303E6697425","full_name":"Robinson, Matthew Richard"},{"full_name":"Wray, Naomi R.","first_name":"Naomi R.","last_name":"Wray"},{"full_name":"Visscher, Peter M.","first_name":"Peter M.","last_name":"Visscher"}],"date_created":"2020-04-30T10:58:58Z","volume":30,"title":"Explaining additional genetic variation in complex traits","year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Elsevier","article_processing_charge":"No","article_type":"original","publication":"Trends in Genetics","_id":"7744","publication_status":"published","publication_identifier":{"issn":["0168-9525"]},"quality_controlled":"1","date_published":"2014-04-01T00:00:00Z","doi":"10.1016/j.tig.2014.02.003","status":"public","language":[{"iso":"eng"}],"citation":{"ieee":"M. R. Robinson, N. R. Wray, and P. M. Visscher, “Explaining additional genetic variation in complex traits,” <i>Trends in Genetics</i>, vol. 30, no. 4. Elsevier, pp. 124–132, 2014.","chicago":"Robinson, Matthew Richard, Naomi R. Wray, and Peter M. Visscher. “Explaining Additional Genetic Variation in Complex Traits.” <i>Trends in Genetics</i>. Elsevier, 2014. <a href=\"https://doi.org/10.1016/j.tig.2014.02.003\">https://doi.org/10.1016/j.tig.2014.02.003</a>.","short":"M.R. Robinson, N.R. Wray, P.M. Visscher, Trends in Genetics 30 (2014) 124–132.","ama":"Robinson MR, Wray NR, Visscher PM. Explaining additional genetic variation in complex traits. <i>Trends in Genetics</i>. 2014;30(4):124-132. doi:<a href=\"https://doi.org/10.1016/j.tig.2014.02.003\">10.1016/j.tig.2014.02.003</a>","ista":"Robinson MR, Wray NR, Visscher PM. 2014. Explaining additional genetic variation in complex traits. Trends in Genetics. 30(4), 124–132.","mla":"Robinson, Matthew Richard, et al. “Explaining Additional Genetic Variation in Complex Traits.” <i>Trends in Genetics</i>, vol. 30, no. 4, Elsevier, 2014, pp. 124–32, doi:<a href=\"https://doi.org/10.1016/j.tig.2014.02.003\">10.1016/j.tig.2014.02.003</a>.","apa":"Robinson, M. R., Wray, N. R., &#38; Visscher, P. M. (2014). Explaining additional genetic variation in complex traits. <i>Trends in Genetics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tig.2014.02.003\">https://doi.org/10.1016/j.tig.2014.02.003</a>"},"issue":"4","intvolume":"        30","extern":"1"},{"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1405.5461"}],"doi":"10.1109/ICDCS.2014.43","date_published":"2014-08-29T00:00:00Z","publication_status":"published","oa":1,"language":[{"iso":"eng"}],"citation":{"ista":"Alistarh D-A, Kopinsky J, Matveev A, Shavit N. 2014. The levelarray: A fast, practical long-lived renaming algorithm. ICDCS: International Conference on Distributed Computing Systems, 348–357.","mla":"Alistarh, Dan-Adrian, et al. <i>The Levelarray: A Fast, Practical Long-Lived Renaming Algorithm</i>. IEEE, 2014, pp. 348–57, doi:<a href=\"https://doi.org/10.1109/ICDCS.2014.43\">10.1109/ICDCS.2014.43</a>.","apa":"Alistarh, D.-A., Kopinsky, J., Matveev, A., &#38; Shavit, N. (2014). The levelarray: A fast, practical long-lived renaming algorithm (pp. 348–357). Presented at the ICDCS: International Conference on Distributed Computing Systems, IEEE. <a href=\"https://doi.org/10.1109/ICDCS.2014.43\">https://doi.org/10.1109/ICDCS.2014.43</a>","ama":"Alistarh D-A, Kopinsky J, Matveev A, Shavit N. The levelarray: A fast, practical long-lived renaming algorithm. In: IEEE; 2014:348-357. doi:<a href=\"https://doi.org/10.1109/ICDCS.2014.43\">10.1109/ICDCS.2014.43</a>","short":"D.-A. Alistarh, J. Kopinsky, A. Matveev, N. Shavit, in:, IEEE, 2014, pp. 348–357.","ieee":"D.-A. Alistarh, J. Kopinsky, A. Matveev, and N. Shavit, “The levelarray: A fast, practical long-lived renaming algorithm,” presented at the ICDCS: International Conference on Distributed Computing Systems, 2014, pp. 348–357.","chicago":"Alistarh, Dan-Adrian, Justin Kopinsky, Alexander Matveev, and Nir Shavit. “The Levelarray: A Fast, Practical Long-Lived Renaming Algorithm,” 348–57. IEEE, 2014. <a href=\"https://doi.org/10.1109/ICDCS.2014.43\">https://doi.org/10.1109/ICDCS.2014.43</a>."},"conference":{"name":"ICDCS: International Conference on Distributed Computing Systems"},"extern":"1","external_id":{"arxiv":["1405.5461"]},"status":"public","date_created":"2018-12-11T11:48:26Z","publist_id":"6883","arxiv":1,"title":"The levelarray: A fast, practical long-lived renaming algorithm","month":"08","type":"conference","oa_version":"Preprint","abstract":[{"text":"The long-lived renaming problem appears in shared-memory systems where a set of threads need to register and deregister frequently from the computation, while concurrent operations scan the set of currently registered threads. Instances of this problem show up in concurrent implementations of transactional memory, flat combining, thread barriers, and memory reclamation schemes for lock-free data structures. In this paper, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the Level Array, has previously been used for hashing and one-shot (single-use) renaming. Our main contribution is to prove that, in long-lived executions, where processes may register and deregister polynomially many times, the technique guarantees constant steps on average and O (log log n) steps with high probability for registering, unit cost for deregistering, and O (n) steps for collect queries, where n is an upper bound on the number of processes that may be active at any point in time. We also show that the algorithm has the surprising property that it is self-healing: under reasonable assumptions on the schedule, operations running while the data structure is in a degraded state implicitly help the data structure re-balance itself. This subtle mechanism obviates the need for expensive periodic rebuilding procedures. Our benchmarks validate this approach, showing that, for typical use parameters, the average number of steps a process takes to register is less than two and the worst-case number of steps is bounded by six, even in executions with billions of operations. We contrast this with other randomized implementations, whose worst-case behavior we show to be unreliable, and with deterministic implementations, whose cost is linear in n.","lang":"eng"}],"day":"29","date_updated":"2023-02-23T13:16:18Z","author":[{"first_name":"Dan-Adrian","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Justin","last_name":"Kopinsky","full_name":"Kopinsky, Justin"},{"full_name":"Matveev, Alexander","first_name":"Alexander","last_name":"Matveev"},{"last_name":"Shavit","first_name":"Nir","full_name":"Shavit, Nir"}],"page":"348 - 357","article_processing_charge":"No","_id":"775","year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IEEE"},{"citation":{"apa":"Cimadom, A., Ulloa, A., Meidl, P., Zöttl, M., Zöttl, E., Fessl, B., … Tebbich, S. (2014). Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin’s finches. <i>PLoS One</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0107518\">https://doi.org/10.1371/journal.pone.0107518</a>","mla":"Cimadom, Arno, et al. “Invasive Parasites Habitat Change and Heavy Rainfall Reduce Breeding Success in Darwin’s Finches.” <i>PLoS One</i>, vol. 9, no. 9, 0107518, Public Library of Science, 2014, doi:<a href=\"https://doi.org/10.1371/journal.pone.0107518\">10.1371/journal.pone.0107518</a>.","ista":"Cimadom A, Ulloa A, Meidl P, Zöttl M, Zöttl E, Fessl B, Nemeth E, Dvorak M, Cunninghame F, Tebbich S. 2014. Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin’s finches. PLoS One. 9(9), 0107518.","ama":"Cimadom A, Ulloa A, Meidl P, et al. Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin’s finches. <i>PLoS One</i>. 2014;9(9). doi:<a href=\"https://doi.org/10.1371/journal.pone.0107518\">10.1371/journal.pone.0107518</a>","short":"A. Cimadom, A. Ulloa, P. Meidl, M. Zöttl, E. Zöttl, B. Fessl, E. Nemeth, M. Dvorak, F. Cunninghame, S. Tebbich, PLoS One 9 (2014).","chicago":"Cimadom, Arno, Angel Ulloa, Patrick Meidl, Markus Zöttl, Elisabet Zöttl, Birgit Fessl, Erwin Nemeth, Michael Dvorak, Francesca Cunninghame, and Sabine Tebbich. “Invasive Parasites Habitat Change and Heavy Rainfall Reduce Breeding Success in Darwin’s Finches.” <i>PLoS One</i>. Public Library of Science, 2014. <a href=\"https://doi.org/10.1371/journal.pone.0107518\">https://doi.org/10.1371/journal.pone.0107518</a>.","ieee":"A. Cimadom <i>et al.</i>, “Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin’s finches,” <i>PLoS One</i>, vol. 9, no. 9. Public Library of Science, 2014."},"intvolume":"         9","status":"public","ddc":["576"],"date_published":"2014-09-23T00:00:00Z","has_accepted_license":"1","publication_status":"published","oa":1,"_id":"468","year":"2014","acknowledgement":"The study was funded by the University of Vienna (Focus of Excellence grant), the Galápagos Conservation Trust, and the Ethologische Gesellschaft e.V.","file_date_updated":"2020-07-14T12:46:34Z","date_created":"2018-12-11T11:46:38Z","volume":9,"oa_version":"Published Version","type":"journal_article","month":"09","date_updated":"2021-01-12T08:00:48Z","abstract":[{"text":"Invasive alien parasites and pathogens are a growing threat to biodiversity worldwide, which can contribute to the extinction of endemic species. On the Galápagos Islands, the invasive parasitic fly Philornis downsi poses a major threat to the endemic avifauna. Here, we investigated the influence of this parasite on the breeding success of two Darwin's finch species, the warbler finch (Certhidea olivacea) and the sympatric small tree finch (Camarhynchus parvulus), on Santa Cruz Island in 2010 and 2012. While the population of the small tree finch appeared to be stable, the warbler finch has experienced a dramatic decline in population size on Santa Cruz Island since 1997. We aimed to identify whether warbler finches are particularly vulnerable during different stages of the breeding cycle. Contrary to our prediction, breeding success was lower in the small tree finch than in the warbler finch. In both species P. downsi had a strong negative impact on breeding success and our data suggest that heavy rain events also lowered the fledging success. On the one hand parents might be less efficient in compensating their chicks' energy loss due to parasitism as they might be less efficient in foraging on days of heavy rain. On the other hand, intense rainfalls might lead to increased humidity and more rapid cooling of the nests. In the case of the warbler finch we found that the control of invasive plant species with herbicides had a significant additive negative impact on the breeding success. It is very likely that the availability of insects (i.e. food abundance) is lower in such controlled areas, as herbicide usage led to the removal of the entire understory. Predation seems to be a minor factor in brood loss.","lang":"eng"}],"issue":"9","language":[{"iso":"eng"}],"quality_controlled":"1","doi":"10.1371/journal.pone.0107518","pubrep_id":"954","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"scopus_import":1,"publication":"PLoS One","department":[{"_id":"CampIT"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Public Library of Science","publist_id":"7352","article_number":"0107518","title":"Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin's finches","file":[{"access_level":"open_access","date_created":"2018-12-12T10:14:48Z","checksum":"b24e7518ccd41effed0d7d9e2498f67f","date_updated":"2020-07-14T12:46:34Z","file_id":"5103","creator":"system","relation":"main_file","content_type":"application/pdf","file_size":489387,"file_name":"IST-2018-954-v1+1_2014_Meidl_Invasive_parasites.PDF"}],"license":"https://creativecommons.org/licenses/by/4.0/","day":"23","author":[{"last_name":"Cimadom","first_name":"Arno","full_name":"Cimadom, Arno"},{"last_name":"Ulloa","first_name":"Angel","full_name":"Ulloa, Angel"},{"id":"4709BCE6-F248-11E8-B48F-1D18A9856A87","full_name":"Meidl, Patrick","first_name":"Patrick","last_name":"Meidl"},{"last_name":"Zöttl","first_name":"Markus","full_name":"Zöttl, Markus"},{"full_name":"Zöttl, Elisabet","last_name":"Zöttl","first_name":"Elisabet"},{"first_name":"Birgit","last_name":"Fessl","full_name":"Fessl, Birgit"},{"full_name":"Nemeth, Erwin","last_name":"Nemeth","first_name":"Erwin"},{"full_name":"Dvorak, Michael","last_name":"Dvorak","first_name":"Michael"},{"last_name":"Cunninghame","first_name":"Francesca","full_name":"Cunninghame, Francesca"},{"first_name":"Sabine","last_name":"Tebbich","full_name":"Tebbich, Sabine"}]},{"doi":"10.4204/EPTCS.146.11","quality_controlled":"1","pubrep_id":"952","conference":{"start_date":"2014-04-05","name":"SR: Strategic Reasoning","location":"Grenoble, France","end_date":"2014-04-06"},"language":[{"iso":"eng"}],"project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23"},{"_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23"},{"grant_number":"S11407","name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"}],"title":"First cycle games","publist_id":"7345","author":[{"full_name":"Aminof, Benjamin","id":"4A55BD00-F248-11E8-B48F-1D18A9856A87","first_name":"Benjamin","last_name":"Aminof"},{"last_name":"Rubin","first_name":"Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","full_name":"Rubin, Sasha"}],"file":[{"date_updated":"2020-07-14T12:46:35Z","file_id":"5260","checksum":"4d7b4ab82980cca2b96ac7703992a8c8","date_created":"2018-12-12T10:17:08Z","access_level":"open_access","file_name":"IST-2018-952-v1+1_2014_Rubin_First_cycle.pdf","content_type":"application/pdf","relation":"main_file","file_size":100115,"creator":"system"}],"day":"01","publication":"Electronic Proceedings in Theoretical Computer Science, EPTCS","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"scopus_import":1,"ec_funded":1,"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Open Publishing Association","department":[{"_id":"KrCh"}],"ddc":["004"],"date_published":"2014-04-01T00:00:00Z","publication_status":"published","oa":1,"has_accepted_license":"1","intvolume":"       146","citation":{"short":"B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer Science, EPTCS, Open Publishing Association, 2014, pp. 83–90.","chicago":"Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” In <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, 146:83–90. Open Publishing Association, 2014. <a href=\"https://doi.org/10.4204/EPTCS.146.11\">https://doi.org/10.4204/EPTCS.146.11</a>.","ieee":"B. Aminof and S. Rubin, “First cycle games,” in <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, Grenoble, France, 2014, vol. 146, pp. 83–90.","apa":"Aminof, B., &#38; Rubin, S. (2014). First cycle games. In <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i> (Vol. 146, pp. 83–90). Grenoble, France: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.146.11\">https://doi.org/10.4204/EPTCS.146.11</a>","ista":"Aminof B, Rubin S. 2014. First cycle games. Electronic Proceedings in Theoretical Computer Science, EPTCS. SR: Strategic Reasoning, EPTCS, vol. 146, 83–90.","mla":"Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>, vol. 146, Open Publishing Association, 2014, pp. 83–90, doi:<a href=\"https://doi.org/10.4204/EPTCS.146.11\">10.4204/EPTCS.146.11</a>.","ama":"Aminof B, Rubin S. First cycle games. In: <i>Electronic Proceedings in Theoretical Computer Science, EPTCS</i>. Vol 146. Open Publishing Association; 2014:83-90. doi:<a href=\"https://doi.org/10.4204/EPTCS.146.11\">10.4204/EPTCS.146.11</a>"},"alternative_title":["EPTCS"],"status":"public","volume":146,"file_date_updated":"2020-07-14T12:46:35Z","date_created":"2018-12-11T11:46:41Z","page":"83 - 90","month":"04","type":"conference","oa_version":"Published Version","date_updated":"2021-01-12T08:00:53Z","abstract":[{"text":"First cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity and mean-payoff games. We study the memory requirements for winning strategies of FCGs and certain associated infinite duration games. We exhibit a simple FCG that is not memoryless determined (this corrects a mistake in Memoryless determinacy of parity and mean payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims that FCGs for which Y is closed under cyclic permutations are memoryless determined). We show that θ (n)! memory (where n is the number of nodes in the graph), which is always sufficient, may be necessary to win some FCGs. On the other hand, we identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations, and both Y and its complement are closed under concatenation) that are sufficient to ensure that the corresponding FCGs and their associated infinite duration games are memoryless determined. We demonstrate that many games considered in the literature, such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE, solving some families of FCGs is PSPACE-hard. ","lang":"eng"}],"_id":"475","year":"2014"},{"arxiv":1,"title":"Polynomial-time algorithms for energy games with special weight structures","publist_id":"7282","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"day":"01","publication":"Algorithmica","ec_funded":1,"article_processing_charge":"No","scopus_import":"1","article_type":"original","user_id":"72615eeb-f1f3-11ec-aa25-d4573ddc34fd","publisher":"Springer","department":[{"_id":"KrCh"}],"doi":"10.1007/s00453-013-9843-7","quality_controlled":"1","language":[{"iso":"eng"}],"issue":"3","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"volume":70,"date_created":"2018-12-11T11:47:01Z","page":"457 - 492","date_updated":"2023-09-05T14:09:29Z","abstract":[{"text":"Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.","lang":"eng"}],"month":"11","oa_version":"Preprint","type":"journal_article","_id":"535","year":"2014","date_published":"2014-11-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1604.08234","open_access":"1"}],"oa":1,"publication_status":"published","intvolume":"        70","related_material":{"record":[{"relation":"earlier_version","id":"10905","status":"public"}]},"citation":{"chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>Algorithmica</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00453-013-9843-7\">https://doi.org/10.1007/s00453-013-9843-7</a>.","ieee":"K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time algorithms for energy games with special weight structures,” <i>Algorithmica</i>, vol. 70, no. 3. Springer, pp. 457–492, 2014.","short":"K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, Algorithmica 70 (2014) 457–492.","ama":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms for energy games with special weight structures. <i>Algorithmica</i>. 2014;70(3):457-492. doi:<a href=\"https://doi.org/10.1007/s00453-013-9843-7\">10.1007/s00453-013-9843-7</a>","apa":"Chatterjee, K., Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2014). Polynomial-time algorithms for energy games with special weight structures. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-013-9843-7\">https://doi.org/10.1007/s00453-013-9843-7</a>","mla":"Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.” <i>Algorithmica</i>, vol. 70, no. 3, Springer, 2014, pp. 457–92, doi:<a href=\"https://doi.org/10.1007/s00453-013-9843-7\">10.1007/s00453-013-9843-7</a>.","ista":"Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2014. Polynomial-time algorithms for energy games with special weight structures. Algorithmica. 70(3), 457–492."},"external_id":{"arxiv":["1604.08234"]},"status":"public"},{"scopus_import":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication":"Ecology and Evolution","department":[{"_id":"NiBa"},{"_id":"GaTk"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Wiley-Blackwell","publist_id":"7280","title":"Fitness consequences of maternal and grandmaternal effects","day":"19","file":[{"date_updated":"2020-07-14T12:46:38Z","file_id":"4886","checksum":"e32abf75a248e7a11811fd7f60858769","date_created":"2018-12-12T10:11:31Z","access_level":"open_access","file_name":"IST-2018-934-v1+1_Prizak_et_al-2014-Ecology_and_Evolution.pdf","content_type":"application/pdf","relation":"main_file","file_size":621582,"creator":"system"}],"author":[{"id":"4456104E-F248-11E8-B48F-1D18A9856A87","full_name":"Prizak, Roshan","first_name":"Roshan","last_name":"Prizak"},{"full_name":"Ezard, Thomas","last_name":"Ezard","first_name":"Thomas"},{"full_name":"Hoyle, Rebecca","last_name":"Hoyle","first_name":"Rebecca"}],"language":[{"iso":"eng"}],"issue":"15","doi":"10.1002/ece3.1150","pubrep_id":"934","_id":"537","year":"2014","file_date_updated":"2020-07-14T12:46:38Z","date_created":"2018-12-11T11:47:02Z","volume":4,"abstract":[{"lang":"eng","text":"Transgenerational effects are broader than only parental relationships. Despite mounting evidence that multigenerational effects alter phenotypic and life-history traits, our understanding of how they combine to determine fitness is not well developed because of the added complexity necessary to study them. Here, we derive a quantitative genetic model of adaptation to an extraordinary new environment by an additive genetic component, phenotypic plasticity, maternal and grandmaternal effects. We show how, at equilibrium, negative maternal and negative grandmaternal effects maximize expected population mean fitness. We define negative transgenerational effects as those that have a negative effect on trait expression in the subsequent generation, that is, they slow, or potentially reverse, the expected evolutionary dynamic. When maternal effects are positive, negative grandmaternal effects are preferred. As expected under Mendelian inheritance, the grandmaternal effects have a lower impact on fitness than the maternal effects, but this dual inheritance model predicts a more complex relationship between maternal and grandmaternal effects to constrain phenotypic variance and so maximize expected population mean fitness in the offspring."}],"date_updated":"2021-01-12T08:01:30Z","month":"07","oa_version":"Published Version","type":"journal_article","page":"3139 - 3145","citation":{"short":"R. Prizak, T. Ezard, R. Hoyle, Ecology and Evolution 4 (2014) 3139–3145.","ieee":"R. Prizak, T. Ezard, and R. Hoyle, “Fitness consequences of maternal and grandmaternal effects,” <i>Ecology and Evolution</i>, vol. 4, no. 15. Wiley-Blackwell, pp. 3139–3145, 2014.","chicago":"Prizak, Roshan, Thomas Ezard, and Rebecca Hoyle. “Fitness Consequences of Maternal and Grandmaternal Effects.” <i>Ecology and Evolution</i>. Wiley-Blackwell, 2014. <a href=\"https://doi.org/10.1002/ece3.1150\">https://doi.org/10.1002/ece3.1150</a>.","mla":"Prizak, Roshan, et al. “Fitness Consequences of Maternal and Grandmaternal Effects.” <i>Ecology and Evolution</i>, vol. 4, no. 15, Wiley-Blackwell, 2014, pp. 3139–45, doi:<a href=\"https://doi.org/10.1002/ece3.1150\">10.1002/ece3.1150</a>.","ista":"Prizak R, Ezard T, Hoyle R. 2014. Fitness consequences of maternal and grandmaternal effects. Ecology and Evolution. 4(15), 3139–3145.","apa":"Prizak, R., Ezard, T., &#38; Hoyle, R. (2014). Fitness consequences of maternal and grandmaternal effects. <i>Ecology and Evolution</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1002/ece3.1150\">https://doi.org/10.1002/ece3.1150</a>","ama":"Prizak R, Ezard T, Hoyle R. Fitness consequences of maternal and grandmaternal effects. <i>Ecology and Evolution</i>. 2014;4(15):3139-3145. doi:<a href=\"https://doi.org/10.1002/ece3.1150\">10.1002/ece3.1150</a>"},"intvolume":"         4","status":"public","ddc":["530","571"],"date_published":"2014-07-19T00:00:00Z","has_accepted_license":"1","oa":1,"publication_status":"published"},{"date_updated":"2023-02-23T10:31:07Z","day":"28","abstract":[{"text":"Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to their complexity, testing presents a considerable portion of the effort and cost in the design process. Exploiting the compositional structure of system specifications can considerably reduce the effort in model-based testing. Moreover, inferring properties about the system from testing its individual components allows the designer to reduce the amount of integration testing.\r\nIn this paper, we study compositional properties of the IOCO-testing theory. We propose a new approach to composition and hiding operations, inspired by contract-based design and interface theories. These operations preserve behaviors that are compatible under composition and hiding, and prune away incompatible ones. The resulting specification characterizes the input sequences for which the unit testing of components is sufficient to infer the correctness of component integration without the need for further tests. We provide a methodology that uses these results to minimize integration testing effort, but also to detect potential weaknesses in specifications. While we focus on asynchronous models and the IOCO conformance relation, the resulting methodology can be applied to a broader class of systems.","lang":"eng"}],"file":[{"date_created":"2018-12-12T11:54:21Z","access_level":"open_access","date_updated":"2020-07-14T12:46:46Z","file_id":"5543","checksum":"0e03aba625cc334141a3148432aa5760","content_type":"application/pdf","relation":"main_file","file_size":534732,"creator":"system","file_name":"IST-2014-148-v2+1_main_tr.pdf"}],"oa_version":"Published Version","type":"technical_report","month":"01","page":"20","author":[{"last_name":"Daca","first_name":"Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw"},{"last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"last_name":"Krenn","first_name":"Willibald","full_name":"Krenn, Willibald"},{"full_name":"Nickovic, Dejan","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","first_name":"Dejan","last_name":"Nickovic"}],"file_date_updated":"2020-07-14T12:46:46Z","date_created":"2018-12-12T11:39:11Z","title":"Compositional specifications for IOCO testing","department":[{"_id":"ToHe"}],"year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","_id":"5411","pubrep_id":"152","has_accepted_license":"1","oa":1,"publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"ddc":["000"],"date_published":"2014-01-28T00:00:00Z","doi":"10.15479/AT:IST-2014-148-v2-1","status":"public","alternative_title":["IST Austria Technical Report"],"citation":{"ieee":"P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, <i>Compositional specifications for IOCO testing</i>. IST Austria, 2014.","chicago":"Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic. <i>Compositional Specifications for IOCO Testing</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">https://doi.org/10.15479/AT:IST-2014-148-v2-1</a>.","short":"P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, Compositional Specifications for IOCO Testing, IST Austria, 2014.","ama":"Daca P, Henzinger TA, Krenn W, Nickovic D. <i>Compositional Specifications for IOCO Testing</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">10.15479/AT:IST-2014-148-v2-1</a>","ista":"Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications for IOCO testing, IST Austria, 20p.","mla":"Daca, Przemyslaw, et al. <i>Compositional Specifications for IOCO Testing</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">10.15479/AT:IST-2014-148-v2-1</a>.","apa":"Daca, P., Henzinger, T. A., Krenn, W., &#38; Nickovic, D. (2014). <i>Compositional specifications for IOCO testing</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-148-v2-1\">https://doi.org/10.15479/AT:IST-2014-148-v2-1</a>"},"language":[{"iso":"eng"}],"related_material":{"record":[{"id":"2167","status":"public","relation":"later_version"}]}},{"year":"2014","department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","_id":"5412","date_updated":"2023-02-23T12:25:18Z","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"day":"29","file":[{"file_name":"IST-2014-153-v1+1_main.pdf","file_size":423322,"relation":"main_file","content_type":"application/pdf","creator":"system","file_id":"5500","date_updated":"2020-07-14T12:46:47Z","checksum":"4d6cda4bebed970926403ad6ad8c745f","date_created":"2018-12-12T11:53:39Z","access_level":"open_access"}],"oa_version":"Published Version","type":"technical_report","month":"01","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","first_name":"Przemyslaw","last_name":"Daca"},{"id":"3624234E-F248-11E8-B48F-1D18A9856A87","full_name":"Chmelik, Martin","first_name":"Martin","last_name":"Chmelik"}],"page":"31","date_created":"2018-12-12T11:39:11Z","file_date_updated":"2020-07-14T12:46:47Z","title":"CEGAR for qualitative analysis of probabilistic systems","status":"public","alternative_title":["IST Austria Technical Report"],"citation":{"chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">https://doi.org/10.15479/AT:IST-2014-153-v1-1</a>","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 31p.","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v1-1\">10.15479/AT:IST-2014-153-v1-1</a>."},"language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","id":"2063","relation":"later_version"},{"status":"public","id":"5413","relation":"later_version"},{"status":"public","id":"5414","relation":"later_version"}]},"pubrep_id":"153","has_accepted_license":"1","oa":1,"publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2014-153-v1-1","ddc":["000"],"date_published":"2014-01-29T00:00:00Z"},{"_id":"5413","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","year":"2014","department":[{"_id":"KrCh"}],"title":"CEGAR for qualitative analysis of probabilistic systems","file_date_updated":"2020-07-14T12:46:47Z","date_created":"2018-12-12T11:39:11Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"49351290-F248-11E8-B48F-1D18A9856A87","full_name":"Daca, Przemyslaw","last_name":"Daca","first_name":"Przemyslaw"},{"first_name":"Martin","last_name":"Chmelik","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"page":"33","oa_version":"Published Version","type":"technical_report","month":"02","file":[{"date_created":"2018-12-12T11:54:17Z","access_level":"open_access","date_updated":"2020-07-14T12:46:47Z","file_id":"5539","checksum":"ce4967a184d84863eec76c66cbac1614","content_type":"application/pdf","relation":"main_file","file_size":606049,"creator":"system","file_name":"IST-2014-153-v2+2_main.pdf"}],"date_updated":"2023-02-23T12:25:18Z","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"day":"06","related_material":{"record":[{"status":"public","id":"2063","relation":"later_version"},{"status":"public","id":"5412","relation":"earlier_version"},{"status":"public","id":"5414","relation":"later_version"}]},"language":[{"iso":"eng"}],"citation":{"ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>","mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">10.15479/AT:IST-2014-153-v2-2</a>.","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v2-2\">https://doi.org/10.15479/AT:IST-2014-153-v2-2</a>.","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014."},"alternative_title":["IST Austria Technical Report"],"status":"public","date_published":"2014-02-06T00:00:00Z","ddc":["000"],"doi":"10.15479/AT:IST-2014-153-v2-2","publication_identifier":{"issn":["2664-1690"]},"oa":1,"publication_status":"published","has_accepted_license":"1","pubrep_id":"164"},{"oa":1,"publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"has_accepted_license":"1","pubrep_id":"165","ddc":["000"],"date_published":"2014-02-07T00:00:00Z","doi":"10.15479/AT:IST-2014-153-v3-1","alternative_title":["IST Austria Technical Report"],"status":"public","related_material":{"record":[{"relation":"later_version","id":"2063","status":"public"},{"relation":"earlier_version","id":"5412","status":"public"},{"relation":"earlier_version","id":"5413","status":"public"}]},"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>.","ista":"Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic systems, IST Austria, 33p.","apa":"Chatterjee, K., Daca, P., &#38; Chmelik, M. (2014). <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>","ama":"Chatterjee K, Daca P, Chmelik M. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">10.15479/AT:IST-2014-153-v3-1</a>","short":"K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic Systems, IST Austria, 2014.","ieee":"K. Chatterjee, P. Daca, and M. Chmelik, <i>CEGAR for qualitative analysis of probabilistic systems</i>. IST Austria, 2014.","chicago":"Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. <i>CEGAR for Qualitative Analysis of Probabilistic Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-153-v3-1\">https://doi.org/10.15479/AT:IST-2014-153-v3-1</a>."},"language":[{"iso":"eng"}],"page":"33","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Chmelik","first_name":"Martin","full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2023-02-23T12:25:15Z","day":"07","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability.\r\nWe introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation.\r\nWe present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. \r\nWe have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"file":[{"file_name":"IST-2014-153-v3+1_main.pdf","content_type":"application/pdf","relation":"main_file","file_size":606227,"creator":"system","date_updated":"2020-07-14T12:46:48Z","file_id":"5464","checksum":"87b93fe9af71fc5c94b0eb6151537e11","date_created":"2018-12-12T11:53:03Z","access_level":"open_access"}],"oa_version":"Published Version","month":"02","type":"technical_report","title":"CEGAR for qualitative analysis of probabilistic systems","date_created":"2018-12-12T11:39:12Z","file_date_updated":"2020-07-14T12:46:48Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","department":[{"_id":"KrCh"}],"year":"2014","_id":"5414"},{"year":"2014","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","_id":"5415","date_updated":"2023-02-23T12:26:19Z","file":[{"file_id":"5497","date_updated":"2020-07-14T12:46:48Z","checksum":"31f90dcf2cf899c3f8c6427cfcc2b3c7","date_created":"2018-12-12T11:53:36Z","access_level":"open_access","file_name":"IST-2014-170-v1+1_main.pdf","file_size":573457,"content_type":"application/pdf","relation":"main_file","creator":"system"}],"day":"19","abstract":[{"lang":"eng","text":"Recently there has been a significant effort to add 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, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains.  "}],"month":"02","type":"technical_report","oa_version":"Published Version","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"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"}],"page":"27","file_date_updated":"2020-07-14T12:46:48Z","date_created":"2018-12-12T11:39:12Z","title":"Nested weighted automata","status":"public","alternative_title":["IST Austria Technical Report"],"language":[{"iso":"eng"}],"citation":{"chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. <i>Nested Weighted Automata</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2014.","short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2014.","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2014). <i>Nested weighted automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">https://doi.org/10.15479/AT:IST-2014-170-v1-1</a>","mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Automata</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-170-v1-1\">10.15479/AT:IST-2014-170-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria, 27p."},"related_material":{"record":[{"status":"public","id":"1656","relation":"later_version"},{"status":"public","id":"467","relation":"later_version"},{"status":"public","id":"5436","relation":"later_version"}]},"pubrep_id":"170","has_accepted_license":"1","oa":1,"publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2014-170-v1-1","date_published":"2014-02-19T00:00:00Z","ddc":["004"]},{"date_created":"2018-12-12T11:39:12Z","file_date_updated":"2020-07-14T12:46:49Z","title":"Model measuring for hybrid systems","abstract":[{"lang":"eng","text":"As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem."}],"file":[{"checksum":"445456d22371e4e49aad2b9a0c13bf80","date_updated":"2020-07-14T12:46:49Z","file_id":"5492","access_level":"open_access","date_created":"2018-12-12T11:53:32Z","file_name":"IST-2014-171-v1+1_report.pdf","creator":"system","relation":"main_file","content_type":"application/pdf","file_size":712077}],"day":"19","date_updated":"2023-02-23T10:33:21Z","type":"technical_report","oa_version":"Published Version","month":"02","page":"22","author":[{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"_id":"5416","department":[{"_id":"ToHe"}],"year":"2014","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","doi":"10.15479/AT:IST-2014-171-v1-1","date_published":"2014-02-19T00:00:00Z","ddc":["005"],"has_accepted_license":"1","pubrep_id":"171","oa":1,"publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"citation":{"ieee":"T. A. Henzinger and J. Otop, <i>Model measuring for hybrid systems</i>. IST Austria, 2014.","chicago":"Henzinger, Thomas A, and Jan Otop. <i>Model Measuring for Hybrid Systems</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">https://doi.org/10.15479/AT:IST-2014-171-v1-1</a>.","short":"T.A. Henzinger, J. Otop, Model Measuring for Hybrid Systems, IST Austria, 2014.","ama":"Henzinger TA, Otop J. <i>Model Measuring for Hybrid Systems</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>","ista":"Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria, 22p.","mla":"Henzinger, Thomas A., and Jan Otop. <i>Model Measuring for Hybrid Systems</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">10.15479/AT:IST-2014-171-v1-1</a>.","apa":"Henzinger, T. A., &#38; Otop, J. (2014). <i>Model measuring for hybrid systems</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-171-v1-1\">https://doi.org/10.15479/AT:IST-2014-171-v1-1</a>"},"language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"2217"}]},"status":"public","alternative_title":["IST Austria Technical Report"]},{"publication_identifier":{"issn":["2664-1690"]},"oa":1,"publication_status":"published","has_accepted_license":"1","pubrep_id":"175","ddc":["000"],"doi":"10.15479/AT:IST-2014-172-v1-1","date_published":"2014-02-19T00:00:00Z","alternative_title":["IST Austria Technical Report"],"status":"public","related_material":{"record":[{"relation":"later_version","id":"2327","status":"public"}]},"language":[{"iso":"eng"}],"citation":{"short":"T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria, 2014.","ieee":"T. A. Henzinger and J. Otop, <i>From model checking to model measuring</i>. IST Austria, 2014.","chicago":"Henzinger, Thomas A, and Jan Otop. <i>From Model Checking to Model Measuring</i>. IST Austria, 2014. <a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">https://doi.org/10.15479/AT:IST-2014-172-v1-1</a>.","mla":"Henzinger, Thomas A., and Jan Otop. <i>From Model Checking to Model Measuring</i>. IST Austria, 2014, doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>.","ista":"Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria, 14p.","apa":"Henzinger, T. A., &#38; Otop, J. (2014). <i>From model checking to model measuring</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">https://doi.org/10.15479/AT:IST-2014-172-v1-1</a>","ama":"Henzinger TA, Otop J. <i>From Model Checking to Model Measuring</i>. IST Austria; 2014. doi:<a href=\"https://doi.org/10.15479/AT:IST-2014-172-v1-1\">10.15479/AT:IST-2014-172-v1-1</a>"},"page":"14","author":[{"orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A"},{"first_name":"Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan"}],"oa_version":"Published Version","month":"02","type":"technical_report","day":"19","abstract":[{"text":"We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata.\r\nThe model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification.\r\nWe show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved.\r\nWe use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. \r\nWe give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications.","lang":"eng"}],"date_updated":"2023-02-23T10:38:10Z","file":[{"file_name":"IST-2014-172-v1+1_report.pdf","file_size":383052,"relation":"main_file","content_type":"application/pdf","creator":"system","file_id":"5481","date_updated":"2020-07-14T12:46:49Z","checksum":"fcc3eab903cfcd3778b338d2d0d44d18","date_created":"2018-12-12T11:53:20Z","access_level":"open_access"}],"title":"From model checking to model measuring","date_created":"2018-12-12T11:39:13Z","file_date_updated":"2020-07-14T12:46:49Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","department":[{"_id":"ToHe"}],"year":"2014","_id":"5417"}]