[{"has_accepted_license":"1","related_material":{"record":[{"id":"1729","relation":"earlier_version","status":"public"}]},"ec_funded":1,"year":"2017","oa":1,"article_processing_charge":"No","title":"From non-preemptive to preemptive scheduling using synchronization synthesis","doi":"10.1007/s10703-016-0256-5","isi":1,"external_id":{"isi":["000399888900001"]},"day":"01","date_updated":"2023-09-20T11:13:51Z","page":"97 - 139","issue":"2-3","language":[{"iso":"eng"}],"_id":"1338","pubrep_id":"656","file_date_updated":"2020-07-14T12:44:44Z","month":"06","file":[{"content_type":"application/pdf","creator":"system","checksum":"1163dfd997e8212c789525d4178b1653","file_name":"IST-2016-656-v1+1_s10703-016-0256-5.pdf","relation":"main_file","file_id":"4985","file_size":1416170,"date_created":"2018-12-12T10:13:05Z","date_updated":"2020-07-14T12:44:44Z","access_level":"open_access"}],"author":[{"full_name":"Cerny, Pavol","last_name":"Cerny","first_name":"Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Clarke, Edmund","last_name":"Clarke","first_name":"Edmund"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","first_name":"Arjun","last_name":"Radhakrishna","full_name":"Radhakrishna, Arjun"},{"first_name":"Leonid","last_name":"Ryzhyk","full_name":"Ryzhyk, Leonid"},{"full_name":"Samanta, Roopsha","id":"3D2AAC08-F248-11E8-B48F-1D18A9856A87","first_name":"Roopsha","last_name":"Samanta"},{"orcid":"0000-0003-4409-8487","full_name":"Tarrach, Thorsten","first_name":"Thorsten","last_name":"Tarrach","id":"3D6E8F2C-F248-11E8-B48F-1D18A9856A87"}],"citation":{"apa":"Cerny, P., Clarke, E., Henzinger, T. A., Radhakrishna, A., Ryzhyk, L., Samanta, R., &#38; Tarrach, T. (2017). From non-preemptive to preemptive scheduling using synchronization synthesis. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-016-0256-5\">https://doi.org/10.1007/s10703-016-0256-5</a>","ista":"Cerny P, Clarke E, Henzinger TA, Radhakrishna A, Ryzhyk L, Samanta R, Tarrach T. 2017. From non-preemptive to preemptive scheduling using synchronization synthesis. Formal Methods in System Design. 50(2–3), 97–139.","ama":"Cerny P, Clarke E, Henzinger TA, et al. From non-preemptive to preemptive scheduling using synchronization synthesis. <i>Formal Methods in System Design</i>. 2017;50(2-3):97-139. doi:<a href=\"https://doi.org/10.1007/s10703-016-0256-5\">10.1007/s10703-016-0256-5</a>","short":"P. Cerny, E. Clarke, T.A. Henzinger, A. Radhakrishna, L. Ryzhyk, R. Samanta, T. Tarrach, Formal Methods in System Design 50 (2017) 97–139.","mla":"Cerny, Pavol, et al. “From Non-Preemptive to Preemptive Scheduling Using Synchronization Synthesis.” <i>Formal Methods in System Design</i>, vol. 50, no. 2–3, Springer, 2017, pp. 97–139, doi:<a href=\"https://doi.org/10.1007/s10703-016-0256-5\">10.1007/s10703-016-0256-5</a>.","ieee":"P. Cerny <i>et al.</i>, “From non-preemptive to preemptive scheduling using synchronization synthesis,” <i>Formal Methods in System Design</i>, vol. 50, no. 2–3. Springer, pp. 97–139, 2017.","chicago":"Cerny, Pavol, Edmund Clarke, Thomas A Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, Roopsha Samanta, and Thorsten Tarrach. “From Non-Preemptive to Preemptive Scheduling Using Synchronization Synthesis.” <i>Formal Methods in System Design</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s10703-016-0256-5\">https://doi.org/10.1007/s10703-016-0256-5</a>."},"ddc":["000"],"volume":50,"type":"journal_article","department":[{"_id":"ToHe"}],"project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"},{"grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","call_identifier":"FWF"},{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"quality_controlled":"1","publication_status":"published","publisher":"Springer","abstract":[{"lang":"eng","text":"We present a computer-aided programming approach to concurrency. The approach allows programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior. Let us consider sequences of calls that the program makes to an external interface. The specification requires that any such sequence produced under a preemptive scheduler should be included in the set of sequences produced under a non-preemptive scheduler. We guarantee that our synthesis does not introduce deadlocks and that the synchronization inserted is optimal w.r.t. a given objective function. The solution is based on a finitary abstraction, an algorithm for bounded language inclusion modulo an independence relation, and generation of a set of global constraints over synchronization placements. Each model of the global constraints set corresponds to a correctness-ensuring synchronization placement. The placement that is optimal w.r.t. the given objective function is chosen as the synchronization solution. We apply the approach to device-driver programming, where the driver threads call the software interface of the device and the API provided by the operating system. Our experiments demonstrate that our synthesis method is precise and efficient. The implicit specification helped us find one concurrency bug previously missed when model-checking using an explicit, user-provided specification. We implemented objective functions for coarse-grained and fine-grained locking and observed that different synchronization placements are produced for our experiments, favoring a minimal number of synchronization operations or maximum concurrency, respectively."}],"date_published":"2017-06-01T00:00:00Z","status":"public","publication":"Formal Methods in System Design","publist_id":"5929","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":"        50","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","scopus_import":"1","date_created":"2018-12-11T11:51:27Z"},{"type":"journal_article","volume":54,"quality_controlled":"1","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF"},{"grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","grant_number":"618091"},{"_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7"},{"_id":"25B07788-B435-11E9-9278-68D0E5697425","name":"Limits to selection in biology and in evolutionary computation","grant_number":"250152","call_identifier":"FP7"}],"department":[{"_id":"ToHe"},{"_id":"CaGu"},{"_id":"NiBa"}],"publisher":"Springer","publication_status":"published","publist_id":"5898","publication":"Acta Informatica","date_published":"2017-12-01T00:00:00Z","status":"public","abstract":[{"lang":"eng","text":"The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs—an important problem of interest in evolutionary biology—more efficiently than the classical simulation method. We specify the property in linear temporal logic. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":"        54","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Published Version","date_created":"2018-12-11T11:51:32Z","scopus_import":"1","year":"2017","ec_funded":1,"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1835"}]},"has_accepted_license":"1","article_processing_charge":"No","oa":1,"external_id":{"isi":["000414343200003"]},"isi":1,"doi":"10.1007/s00236-016-0278-x","title":"Model checking the evolution of gene regulatory networks","date_updated":"2025-05-28T11:57:04Z","day":"01","publication_identifier":{"issn":["00015903"]},"issue":"8","page":"765 - 787","pubrep_id":"649","_id":"1351","language":[{"iso":"eng"}],"file":[{"file_id":"5841","file_size":755241,"date_updated":"2020-07-14T12:44:46Z","date_created":"2019-01-17T15:57:29Z","access_level":"open_access","content_type":"application/pdf","checksum":"4e661d9135d7f8c342e8e258dee76f3e","creator":"dernst","relation":"main_file","file_name":"2017_ActaInformatica_Giacobbe.pdf"}],"author":[{"first_name":"Mirco","last_name":"Giacobbe","id":"3444EA5E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8180-0904","full_name":"Giacobbe, Mirco"},{"last_name":"Guet","first_name":"Calin C","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6220-2052","full_name":"Guet, Calin C"},{"first_name":"Ashutosh","last_name":"Gupta","id":"335E5684-F248-11E8-B48F-1D18A9856A87","full_name":"Gupta, Ashutosh"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","first_name":"Tiago","last_name":"Paixao","full_name":"Paixao, Tiago","orcid":"0000-0003-2361-3953"},{"last_name":"Petrov","first_name":"Tatjana","id":"3D5811FC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9041-0905","full_name":"Petrov, Tatjana"}],"month":"12","file_date_updated":"2020-07-14T12:44:46Z","ddc":["006","576"],"citation":{"ista":"Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. 2017. Model checking the evolution of gene regulatory networks. Acta Informatica. 54(8), 765–787.","apa":"Giacobbe, M., Guet, C. C., Gupta, A., Henzinger, T. A., Paixao, T., &#38; Petrov, T. (2017). Model checking the evolution of gene regulatory networks. <i>Acta Informatica</i>. Springer. <a href=\"https://doi.org/10.1007/s00236-016-0278-x\">https://doi.org/10.1007/s00236-016-0278-x</a>","ama":"Giacobbe M, Guet CC, Gupta A, Henzinger TA, Paixao T, Petrov T. Model checking the evolution of gene regulatory networks. <i>Acta Informatica</i>. 2017;54(8):765-787. doi:<a href=\"https://doi.org/10.1007/s00236-016-0278-x\">10.1007/s00236-016-0278-x</a>","short":"M. Giacobbe, C.C. Guet, A. Gupta, T.A. Henzinger, T. Paixao, T. Petrov, Acta Informatica 54 (2017) 765–787.","mla":"Giacobbe, Mirco, et al. “Model Checking the Evolution of Gene Regulatory Networks.” <i>Acta Informatica</i>, vol. 54, no. 8, Springer, 2017, pp. 765–87, doi:<a href=\"https://doi.org/10.1007/s00236-016-0278-x\">10.1007/s00236-016-0278-x</a>.","chicago":"Giacobbe, Mirco, Calin C Guet, Ashutosh Gupta, Thomas A Henzinger, Tiago Paixao, and Tatjana Petrov. “Model Checking the Evolution of Gene Regulatory Networks.” <i>Acta Informatica</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00236-016-0278-x\">https://doi.org/10.1007/s00236-016-0278-x</a>.","ieee":"M. Giacobbe, C. C. Guet, A. Gupta, T. A. Henzinger, T. Paixao, and T. Petrov, “Model checking the evolution of gene regulatory networks,” <i>Acta Informatica</i>, vol. 54, no. 8. Springer, pp. 765–787, 2017."}},{"type":"journal_article","volume":36,"department":[{"_id":"ChWo"}],"quality_controlled":"1","publication_status":"published","publisher":"Wiley-Blackwell","abstract":[{"lang":"eng","text":"One of the major challenges in physically based modelling is making simulations efficient. Adaptive models provide an essential solution to these efficiency goals. These models are able to self-adapt in space and time, attempting to provide the best possible compromise between accuracy and speed. This survey reviews the adaptive solutions proposed so far in computer graphics. Models are classified according to the strategy they use for adaptation, from time-stepping and freezing techniques to geometric adaptivity in the form of structured grids, meshes and particles. Applications range from fluids, through deformable bodies, to articulated solids."}],"publication":"Computer Graphics Forum","publist_id":"5873","status":"public","date_published":"2017-09-01T00:00:00Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":"        36","oa_version":"Submitted Version","scopus_import":"1","date_created":"2018-12-11T11:51:37Z","has_accepted_license":"1","year":"2017","article_processing_charge":"No","oa":1,"doi":"10.1111/cgf.12941","title":"Adaptive physically based models in computer graphics","external_id":{"isi":["000408634200019"]},"isi":1,"day":"01","publication_identifier":{"issn":["01677055"]},"date_updated":"2023-09-20T11:05:36Z","page":"312 - 337","issue":"6","_id":"1367","language":[{"iso":"eng"}],"pubrep_id":"634","acknowledgement":"This work was partly supported by the starting grants ADAPT and BigSplash, as well as the advanced grant EXPRESSIVE from the European Research Council (ERC-2012-StG_20111012, ERC-2014-StG_638176 and ERC-2011-ADG_20110209).","file":[{"date_updated":"2020-07-14T12:44:47Z","date_created":"2018-12-12T10:16:21Z","access_level":"open_access","file_id":"5208","file_size":1434439,"checksum":"7676e9a9ead6d58c3000988c97deb2ef","creator":"system","relation":"main_file","file_name":"IST-2016-634-v1+1_starAdaptivity-cgf.pdf","content_type":"application/pdf"}],"author":[{"last_name":"Manteaux","first_name":"Pierre","full_name":"Manteaux, Pierre"},{"first_name":"Christopher J","last_name":"Wojtan","id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6646-5546","full_name":"Wojtan, Christopher J"},{"first_name":"Rahul","last_name":"Narain","full_name":"Narain, Rahul"},{"full_name":"Redon, Stéphane","last_name":"Redon","first_name":"Stéphane"},{"first_name":"François","last_name":"Faure","full_name":"Faure, François"},{"first_name":"Marie","last_name":"Cani","full_name":"Cani, Marie"}],"month":"09","file_date_updated":"2020-07-14T12:44:47Z","ddc":["000"],"citation":{"chicago":"Manteaux, Pierre, Chris Wojtan, Rahul Narain, Stéphane Redon, François Faure, and Marie Cani. “Adaptive Physically Based Models in Computer Graphics.” <i>Computer Graphics Forum</i>. Wiley-Blackwell, 2017. <a href=\"https://doi.org/10.1111/cgf.12941\">https://doi.org/10.1111/cgf.12941</a>.","ieee":"P. Manteaux, C. Wojtan, R. Narain, S. Redon, F. Faure, and M. Cani, “Adaptive physically based models in computer graphics,” <i>Computer Graphics Forum</i>, vol. 36, no. 6. Wiley-Blackwell, pp. 312–337, 2017.","mla":"Manteaux, Pierre, et al. “Adaptive Physically Based Models in Computer Graphics.” <i>Computer Graphics Forum</i>, vol. 36, no. 6, Wiley-Blackwell, 2017, pp. 312–37, doi:<a href=\"https://doi.org/10.1111/cgf.12941\">10.1111/cgf.12941</a>.","short":"P. Manteaux, C. Wojtan, R. Narain, S. Redon, F. Faure, M. Cani, Computer Graphics Forum 36 (2017) 312–337.","ama":"Manteaux P, Wojtan C, Narain R, Redon S, Faure F, Cani M. Adaptive physically based models in computer graphics. <i>Computer Graphics Forum</i>. 2017;36(6):312-337. doi:<a href=\"https://doi.org/10.1111/cgf.12941\">10.1111/cgf.12941</a>","ista":"Manteaux P, Wojtan C, Narain R, Redon S, Faure F, Cani M. 2017. Adaptive physically based models in computer graphics. Computer Graphics Forum. 36(6), 312–337.","apa":"Manteaux, P., Wojtan, C., Narain, R., Redon, S., Faure, F., &#38; Cani, M. (2017). Adaptive physically based models in computer graphics. <i>Computer Graphics Forum</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/cgf.12941\">https://doi.org/10.1111/cgf.12941</a>"}},{"project":[{"call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering"},{"call_identifier":"FWF","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407","call_identifier":"FWF"}],"quality_controlled":"1","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"publisher":"Elsevier","publication_status":"published","main_file_link":[{"url":"http://arxiv.org/abs/1410.5387","open_access":"1"}],"volume":23,"type":"journal_article","oa_version":"Preprint","date_created":"2018-12-11T11:51:50Z","scopus_import":"1","date_published":"2017-02-01T00:00:00Z","status":"public","publication":"Nonlinear Analysis: Hybrid Systems","publist_id":"5800","abstract":[{"lang":"eng","text":"We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of all satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. While the proposed algorithm guarantees progress and soundness in every iteration, it is computationally demanding. We offer an alternative, more efficient solution for the reachability properties that decomposes the problem into a series of smaller problems of the same type. All algorithms are demonstrated on an illustrative case study."}],"intvolume":"        23","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","isi":1,"external_id":{"arxiv":["1410.5387"],"isi":["000390637000014"]},"title":"Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games","doi":"10.1016/j.nahs.2016.04.006","date_updated":"2023-09-20T09:43:09Z","day":"01","year":"2017","ec_funded":1,"related_material":{"record":[{"status":"public","id":"1689","relation":"earlier_version"}]},"oa":1,"article_processing_charge":"No","month":"02","author":[{"last_name":"Svoreňová","first_name":"Mária","full_name":"Svoreňová, Mária"},{"orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","first_name":"Jan","last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chmelik, Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Chmelik"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Ivana","last_name":"Cěrná","full_name":"Cěrná, Ivana"},{"full_name":"Belta, Cǎlin","first_name":"Cǎlin","last_name":"Belta"}],"arxiv":1,"citation":{"ieee":"M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, and C. Belta, “Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games,” <i>Nonlinear Analysis: Hybrid Systems</i>, vol. 23, no. 2. Elsevier, pp. 230–253, 2017.","chicago":"Svoreňová, Mária, Jan Kretinsky, Martin Chmelik, Krishnendu Chatterjee, Ivana Cěrná, and Cǎlin Belta. “Temporal Logic Control for Stochastic Linear Systems Using Abstraction Refinement of Probabilistic Games.” <i>Nonlinear Analysis: Hybrid Systems</i>. Elsevier, 2017. <a href=\"https://doi.org/10.1016/j.nahs.2016.04.006\">https://doi.org/10.1016/j.nahs.2016.04.006</a>.","short":"M. Svoreňová, J. Kretinsky, M. Chmelik, K. Chatterjee, I. Cěrná, C. Belta, Nonlinear Analysis: Hybrid Systems 23 (2017) 230–253.","mla":"Svoreňová, Mária, et al. “Temporal Logic Control for Stochastic Linear Systems Using Abstraction Refinement of Probabilistic Games.” <i>Nonlinear Analysis: Hybrid Systems</i>, vol. 23, no. 2, Elsevier, 2017, pp. 230–53, doi:<a href=\"https://doi.org/10.1016/j.nahs.2016.04.006\">10.1016/j.nahs.2016.04.006</a>.","ama":"Svoreňová M, Kretinsky J, Chmelik M, Chatterjee K, Cěrná I, Belta C. Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games. <i>Nonlinear Analysis: Hybrid Systems</i>. 2017;23(2):230-253. doi:<a href=\"https://doi.org/10.1016/j.nahs.2016.04.006\">10.1016/j.nahs.2016.04.006</a>","apa":"Svoreňová, M., Kretinsky, J., Chmelik, M., Chatterjee, K., Cěrná, I., &#38; Belta, C. (2017). Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games. <i>Nonlinear Analysis: Hybrid Systems</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.nahs.2016.04.006\">https://doi.org/10.1016/j.nahs.2016.04.006</a>","ista":"Svoreňová M, Kretinsky J, Chmelik M, Chatterjee K, Cěrná I, Belta C. 2017. Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games. Nonlinear Analysis: Hybrid Systems. 23(2), 230–253."},"issue":"2","page":"230 - 253","language":[{"iso":"eng"}],"_id":"1407"},{"oa_version":"Preprint","date_created":"2023-08-22T14:17:19Z","extern":"1","status":"public","date_published":"2017-02-21T00:00:00Z","publication":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics","abstract":[{"text":"Two of the most fundamental prototypes of greedy optimization are the matching pursuit and Frank-Wolfe algorithms. In this paper, we take a unified view on both classes of methods, leading to the first explicit convergence rates of matching pursuit methods in an optimization sense, for general sets of atoms. We derive sublinear (1/t) convergence for both classes on general smooth objectives, and linear convergence on strongly convex objectives, as well as a clear correspondence of algorithm variants. Our presented algorithms and rates are affine invariant, and do not need any incoherence or sparsity assumptions.","lang":"eng"}],"intvolume":"        54","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","quality_controlled":"1","department":[{"_id":"FrLo"}],"publisher":"ML Research Press","publication_status":"published","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1702.06457","open_access":"1"}],"volume":54,"type":"conference","month":"02","author":[{"orcid":"0000-0002-4850-0683","full_name":"Locatello, Francesco","last_name":"Locatello","first_name":"Francesco","id":"26cfd52f-2483-11ee-8040-88983bcc06d4"},{"full_name":"Khanna, Rajiv","first_name":"Rajiv","last_name":"Khanna"},{"last_name":"Tschannen","first_name":"Michael","full_name":"Tschannen, Michael"},{"full_name":"Jaggi, Martin","first_name":"Martin","last_name":"Jaggi"}],"arxiv":1,"citation":{"short":"F. Locatello, R. Khanna, M. Tschannen, M. Jaggi, in:, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2017, pp. 860–868.","mla":"Locatello, Francesco, et al. “A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe.” <i>Proceedings of the 20th International Conference on Artificial Intelligence and Statistics</i>, vol. 54, ML Research Press, 2017, pp. 860–68.","ieee":"F. Locatello, R. Khanna, M. Tschannen, and M. Jaggi, “A unified optimization view on generalized matching pursuit and Frank-Wolfe,” in <i>Proceedings of the 20th International Conference on Artificial Intelligence and Statistics</i>, Fort Lauderdale, FL, United States, 2017, vol. 54, pp. 860–868.","chicago":"Locatello, Francesco, Rajiv Khanna, Michael Tschannen, and Martin Jaggi. “A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe.” In <i>Proceedings of the 20th International Conference on Artificial Intelligence and Statistics</i>, 54:860–68. ML Research Press, 2017.","apa":"Locatello, F., Khanna, R., Tschannen, M., &#38; Jaggi, M. (2017). A unified optimization view on generalized matching pursuit and Frank-Wolfe. In <i>Proceedings of the 20th International Conference on Artificial Intelligence and Statistics</i> (Vol. 54, pp. 860–868). Fort Lauderdale, FL, United States: ML Research Press.","ista":"Locatello F, Khanna R, Tschannen M, Jaggi M. 2017. A unified optimization view on generalized matching pursuit and Frank-Wolfe. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics vol. 54, 860–868.","ama":"Locatello F, Khanna R, Tschannen M, Jaggi M. A unified optimization view on generalized matching pursuit and Frank-Wolfe. In: <i>Proceedings of the 20th International Conference on Artificial Intelligence and Statistics</i>. Vol 54. ML Research Press; 2017:860-868."},"page":"860-868","language":[{"iso":"eng"}],"_id":"14205","external_id":{"arxiv":["1702.06457"]},"title":"A unified optimization view on generalized matching pursuit and Frank-Wolfe","date_updated":"2023-09-13T09:49:10Z","day":"21","year":"2017","conference":{"location":"Fort Lauderdale, FL, United States","name":"AISTATS: Conference on Artificial Intelligence and Statistics","start_date":"2017-04-20","end_date":"2017-04-22"},"article_processing_charge":"No","oa":1},{"publication_status":"published","publication_identifier":{"isbn":["9781510860964"]},"day":"31","date_updated":"2023-09-13T08:32:23Z","title":"Greedy algorithms for cone constrained optimization with convergence guarantees","department":[{"_id":"FrLo"}],"quality_controlled":"1","external_id":{"arxiv":["1705.11041"]},"type":"conference","oa":1,"article_processing_charge":"No","conference":{"start_date":"2017-12-04","end_date":"2017-12-09","location":"Long Beach, CA, United States","name":"NeurIPS: Neural Information Processing Systems"},"main_file_link":[{"url":"https://arxiv.org/abs/1705.11041","open_access":"1"}],"year":"2017","extern":"1","date_created":"2023-08-22T14:17:38Z","citation":{"ama":"Locatello F, Tschannen M, Rätsch G, Jaggi M. Greedy algorithms for cone constrained optimization with convergence guarantees. In: <i>Advances in Neural Information Processing Systems</i>. ; 2017.","apa":"Locatello, F., Tschannen, M., Rätsch, G., &#38; Jaggi, M. (2017). Greedy algorithms for cone constrained optimization with convergence guarantees. In <i>Advances in Neural Information Processing Systems</i>. Long Beach, CA, United States.","ista":"Locatello F, Tschannen M, Rätsch G, Jaggi M. 2017. Greedy algorithms for cone constrained optimization with convergence guarantees. Advances in Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems.","ieee":"F. Locatello, M. Tschannen, G. Rätsch, and M. Jaggi, “Greedy algorithms for cone constrained optimization with convergence guarantees,” in <i>Advances in Neural Information Processing Systems</i>, Long Beach, CA, United States, 2017.","chicago":"Locatello, Francesco, Michael Tschannen, Gunnar Rätsch, and Martin Jaggi. “Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees.” In <i>Advances in Neural Information Processing Systems</i>, 2017.","short":"F. Locatello, M. Tschannen, G. Rätsch, M. Jaggi, in:, Advances in Neural Information Processing Systems, 2017.","mla":"Locatello, Francesco, et al. “Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees.” <i>Advances in Neural Information Processing Systems</i>, 2017."},"arxiv":1,"month":"05","oa_version":"Preprint","author":[{"orcid":"0000-0002-4850-0683","full_name":"Locatello, Francesco","last_name":"Locatello","first_name":"Francesco","id":"26cfd52f-2483-11ee-8040-88983bcc06d4"},{"first_name":"Michael","last_name":"Tschannen","full_name":"Tschannen, Michael"},{"last_name":"Rätsch","first_name":"Gunnar","full_name":"Rätsch, Gunnar"},{"full_name":"Jaggi, Martin","first_name":"Martin","last_name":"Jaggi"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"14206","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe (FW) algorithms regained popularity in recent years due to their simplicity, effectiveness and theoretical guarantees. MP and FW address optimization over the linear span and the convex hull of a set of atoms, respectively. In this paper, we consider the intermediate case of optimization over the convex cone, parametrized as the conic hull of a generic atom set, leading to the first principled definitions of non-negative MP algorithms for which we give explicit convergence rates and demonstrate excellent empirical performance. In particular, we derive sublinear (O(1/t)) convergence on general smooth and convex objectives, and linear convergence (O(e−t)) on strongly convex objectives, in both cases for general sets of atoms. Furthermore, we establish a clear correspondence of our algorithms to known algorithms from the MP and FW literature. Our novel algorithms and analyses target general atom sets and general objective functions, and hence are directly applicable to a large variety of learning settings."}],"date_published":"2017-05-31T00:00:00Z","status":"public","publication":"Advances in Neural Information Processing Systems"},{"scopus_import":"1","date_created":"2018-12-11T11:51:59Z","oa_version":"Published Version","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":"        78","abstract":[{"lang":"eng","text":"Phat is an open-source C. ++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. We provide numerous different reduction strategies as well as data types to store and manipulate the boundary matrix. We compare the different combinations through extensive experimental evaluation and identify optimization techniques that work well in practical situations. We also compare our software with various other publicly available libraries for persistent homology."}],"publication":"Journal of Symbolic Computation","publist_id":"5765","date_published":"2017-01-01T00:00:00Z","status":"public","publication_status":"published","publisher":"Academic Press","department":[{"_id":"HeEd"}],"quality_controlled":"1","project":[{"call_identifier":"FP7","name":"Topological Complex Systems","_id":"255D761E-B435-11E9-9278-68D0E5697425","grant_number":"318493"}],"type":"journal_article","volume":78,"main_file_link":[{"url":"https://doi.org/10.1016/j.jsc.2016.03.008","open_access":"1"}],"article_type":"original","citation":{"mla":"Bauer, Ulrich, et al. “Phat - Persistent Homology Algorithms Toolbox.” <i>Journal of Symbolic Computation</i>, vol. 78, Academic Press, 2017, pp. 76–90, doi:<a href=\"https://doi.org/10.1016/j.jsc.2016.03.008\">10.1016/j.jsc.2016.03.008</a>.","short":"U. Bauer, M. Kerber, J. Reininghaus, H. Wagner, Journal of Symbolic Computation 78 (2017) 76–90.","ieee":"U. Bauer, M. Kerber, J. Reininghaus, and H. Wagner, “Phat - Persistent homology algorithms toolbox,” <i>Journal of Symbolic Computation</i>, vol. 78. Academic Press, pp. 76–90, 2017.","chicago":"Bauer, Ulrich, Michael Kerber, Jan Reininghaus, and Hubert Wagner. “Phat - Persistent Homology Algorithms Toolbox.” <i>Journal of Symbolic Computation</i>. Academic Press, 2017. <a href=\"https://doi.org/10.1016/j.jsc.2016.03.008\">https://doi.org/10.1016/j.jsc.2016.03.008</a>.","apa":"Bauer, U., Kerber, M., Reininghaus, J., &#38; Wagner, H. (2017). Phat - Persistent homology algorithms toolbox. <i>Journal of Symbolic Computation</i>. Academic Press. <a href=\"https://doi.org/10.1016/j.jsc.2016.03.008\">https://doi.org/10.1016/j.jsc.2016.03.008</a>","ista":"Bauer U, Kerber M, Reininghaus J, Wagner H. 2017. Phat - Persistent homology algorithms toolbox. Journal of Symbolic Computation. 78, 76–90.","ama":"Bauer U, Kerber M, Reininghaus J, Wagner H. Phat - Persistent homology algorithms toolbox. <i>Journal of Symbolic Computation</i>. 2017;78:76-90. doi:<a href=\"https://doi.org/10.1016/j.jsc.2016.03.008\">10.1016/j.jsc.2016.03.008</a>"},"author":[{"full_name":"Bauer, Ulrich","first_name":"Ulrich","last_name":"Bauer"},{"last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael"},{"full_name":"Reininghaus, Jan","first_name":"Jan","last_name":"Reininghaus"},{"id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Hubert","full_name":"Wagner, Hubert"}],"month":"01","language":[{"iso":"eng"}],"_id":"1433","page":"76 - 90","day":"01","publication_identifier":{"issn":[" 07477171"]},"date_updated":"2023-09-20T09:42:40Z","doi":"10.1016/j.jsc.2016.03.008","title":"Phat - Persistent homology algorithms toolbox","external_id":{"isi":["000384396000005"]},"isi":1,"article_processing_charge":"No","oa":1,"related_material":{"record":[{"relation":"earlier_version","id":"10894","status":"public"}]},"year":"2017","ec_funded":1},{"date_updated":"2021-01-12T08:01:48Z","day":"01","publication_identifier":{"issn":["15537366"]},"doi":"10.1371/journal.ppat.1006758","title":"Characterization of host proteins interacting with the lymphocytic choriomeningitis virus L protein","oa":1,"year":"2017","has_accepted_license":"1","ddc":["576","616"],"citation":{"ista":"Khamina K, Lercher A, Caldera M, Schliehe C, Vilagos B, Sahin M, Kosack L, Bhattacharya A, Májek P, Stukalov A, Sacco R, James L, Pinschewer D, Bennett K, Menche J, Bergthaler A. 2017. Characterization of host proteins interacting with the lymphocytic choriomeningitis virus L protein. PLoS Pathogens. 13(12), e1006758.","apa":"Khamina, K., Lercher, A., Caldera, M., Schliehe, C., Vilagos, B., Sahin, M., … Bergthaler, A. (2017). Characterization of host proteins interacting with the lymphocytic choriomeningitis virus L protein. <i>PLoS Pathogens</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.ppat.1006758\">https://doi.org/10.1371/journal.ppat.1006758</a>","ama":"Khamina K, Lercher A, Caldera M, et al. Characterization of host proteins interacting with the lymphocytic choriomeningitis virus L protein. <i>PLoS Pathogens</i>. 2017;13(12). doi:<a href=\"https://doi.org/10.1371/journal.ppat.1006758\">10.1371/journal.ppat.1006758</a>","short":"K. Khamina, A. Lercher, M. Caldera, C. Schliehe, B. Vilagos, M. Sahin, L. Kosack, A. Bhattacharya, P. Májek, A. Stukalov, R. Sacco, L. James, D. Pinschewer, K. Bennett, J. Menche, A. Bergthaler, PLoS Pathogens 13 (2017).","mla":"Khamina, Kseniya, et al. “Characterization of Host Proteins Interacting with the Lymphocytic Choriomeningitis Virus L Protein.” <i>PLoS Pathogens</i>, vol. 13, no. 12, e1006758, Public Library of Science, 2017, doi:<a href=\"https://doi.org/10.1371/journal.ppat.1006758\">10.1371/journal.ppat.1006758</a>.","chicago":"Khamina, Kseniya, Alexander Lercher, Michael Caldera, Christopher Schliehe, Bojan Vilagos, Mehmet Sahin, Lindsay Kosack, et al. “Characterization of Host Proteins Interacting with the Lymphocytic Choriomeningitis Virus L Protein.” <i>PLoS Pathogens</i>. Public Library of Science, 2017. <a href=\"https://doi.org/10.1371/journal.ppat.1006758\">https://doi.org/10.1371/journal.ppat.1006758</a>.","ieee":"K. Khamina <i>et al.</i>, “Characterization of host proteins interacting with the lymphocytic choriomeningitis virus L protein,” <i>PLoS Pathogens</i>, vol. 13, no. 12. Public Library of Science, 2017."},"author":[{"last_name":"Khamina","first_name":"Kseniya","full_name":"Khamina, Kseniya"},{"first_name":"Alexander","last_name":"Lercher","full_name":"Lercher, Alexander"},{"last_name":"Caldera","first_name":"Michael","full_name":"Caldera, Michael"},{"full_name":"Schliehe, Christopher","last_name":"Schliehe","first_name":"Christopher"},{"first_name":"Bojan","last_name":"Vilagos","full_name":"Vilagos, Bojan"},{"last_name":"Sahin","first_name":"Mehmet","full_name":"Sahin, Mehmet"},{"full_name":"Kosack, Lindsay","first_name":"Lindsay","last_name":"Kosack"},{"full_name":"Bhattacharya, Anannya","last_name":"Bhattacharya","first_name":"Anannya"},{"last_name":"Májek","first_name":"Peter","full_name":"Májek, Peter"},{"last_name":"Stukalov","first_name":"Alexey","full_name":"Stukalov, Alexey"},{"last_name":"Sacco","first_name":"Roberto","id":"42C9F57E-F248-11E8-B48F-1D18A9856A87","full_name":"Sacco, Roberto"},{"first_name":"Leo","last_name":"James","full_name":"James, Leo"},{"first_name":"Daniel","last_name":"Pinschewer","full_name":"Pinschewer, Daniel"},{"last_name":"Bennett","first_name":"Keiryn","full_name":"Bennett, Keiryn"},{"first_name":"Jörg","last_name":"Menche","full_name":"Menche, Jörg"},{"first_name":"Andreas","last_name":"Bergthaler","full_name":"Bergthaler, Andreas"}],"file":[{"file_name":"IST-2018-931-v1+1_journal.ppat.1006758.pdf","relation":"main_file","creator":"system","checksum":"1aa20f19a1e90664fadce6e7d5284fdc","content_type":"application/pdf","access_level":"open_access","date_created":"2018-12-12T10:12:26Z","date_updated":"2020-07-14T12:46:44Z","file_size":4106772,"file_id":"4944"}],"article_number":"e1006758","file_date_updated":"2020-07-14T12:46:44Z","month":"12","_id":"540","language":[{"iso":"eng"}],"pubrep_id":"931","issue":"12","publisher":"Public Library of Science","publication_status":"published","quality_controlled":"1","department":[{"_id":"GaNo"}],"type":"journal_article","volume":13,"date_created":"2018-12-11T11:47:03Z","scopus_import":1,"oa_version":"Published Version","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":"        13","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"7276","publication":"PLoS Pathogens","status":"public","date_published":"2017-12-01T00:00:00Z","abstract":[{"lang":"eng","text":"RNA-dependent RNA polymerases (RdRps) play a key role in the life cycle of RNA viruses and impact their immunobiology. The arenavirus lymphocytic choriomeningitis virus (LCMV) strain Clone 13 provides a benchmark model for studying chronic infection. A major genetic determinant for its ability to persist maps to a single amino acid exchange in the viral L protein, which exhibits RdRp activity, yet its functional consequences remain elusive. To unravel the L protein interactions with the host proteome, we engineered infectious L protein-tagged LCMV virions by reverse genetics. A subsequent mass-spectrometric analysis of L protein pulldowns from infected human cells revealed a comprehensive network of interacting host proteins. The obtained LCMV L protein interactome was bioinformatically integrated with known host protein interactors of RdRps from other RNA viruses, emphasizing interconnected modules of human proteins. Functional characterization of selected interactors highlighted proviral (DDX3X) as well as antiviral (NKRF, TRIM21) host factors. To corroborate these findings, we infected Trim21-/-mice with LCMV and found impaired virus control in chronic infection. These results provide insights into the complex interactions of the arenavirus LCMV and other viral RdRps with the host proteome and contribute to a better molecular understanding of how chronic viruses interact with their host."}]},{"publication_status":"published","publisher":"Public Library of Science","department":[{"_id":"CaGu"}],"project":[{"name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7"}],"quality_controlled":"1","volume":13,"type":"journal_article","scopus_import":1,"date_created":"2018-12-11T11:47:04Z","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":"        13","abstract":[{"lang":"eng","text":"While we have good understanding of bacterial metabolism at the population level, we know little about the metabolic behavior of individual cells: do single cells in clonal populations sometimes specialize on different metabolic pathways? Such metabolic specialization could be driven by stochastic gene expression and could provide individual cells with growth benefits of specialization. We measured the degree of phenotypic specialization in two parallel metabolic pathways, the assimilation of glucose and arabinose. We grew Escherichia coli in chemostats, and used isotope-labeled sugars in combination with nanometer-scale secondary ion mass spectrometry and mathematical modeling to quantify sugar assimilation at the single-cell level. We found large variation in metabolic activities between single cells, both in absolute assimilation and in the degree to which individual cells specialize in the assimilation of different sugars. Analysis of transcriptional reporters indicated that this variation was at least partially based on cell-to-cell variation in gene expression. Metabolic differences between cells in clonal populations could potentially reduce metabolic incompatibilities between different pathways, and increase the rate at which parallel reactions can be performed."}],"date_published":"2017-12-18T00:00:00Z","status":"public","publist_id":"7275","publication":"PLoS Genetics","publication_identifier":{"issn":["15537390"]},"day":"18","date_updated":"2023-02-23T14:10:34Z","title":"Cell-to-cell variation and specialization in sugar metabolism in clonal bacterial populations","doi":"10.1371/journal.pgen.1007122","oa":1,"related_material":{"record":[{"relation":"research_data","id":"9844","status":"public"},{"id":"9845","relation":"research_data","status":"public"},{"status":"public","relation":"research_data","id":"9846"}]},"has_accepted_license":"1","year":"2017","ec_funded":1,"citation":{"apa":"Nikolic, N., Schreiber, F., Dal Co, A., Kiviet, D., Bergmiller, T., Littmann, S., … Ackermann, M. (2017). Cell-to-cell variation and specialization in sugar metabolism in clonal bacterial populations. <i>PLoS Genetics</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pgen.1007122\">https://doi.org/10.1371/journal.pgen.1007122</a>","ista":"Nikolic N, Schreiber F, Dal Co A, Kiviet D, Bergmiller T, Littmann S, Kuypers M, Ackermann M. 2017. Cell-to-cell variation and specialization in sugar metabolism in clonal bacterial populations. PLoS Genetics. 13(12), e1007122.","ama":"Nikolic N, Schreiber F, Dal Co A, et al. Cell-to-cell variation and specialization in sugar metabolism in clonal bacterial populations. <i>PLoS Genetics</i>. 2017;13(12). doi:<a href=\"https://doi.org/10.1371/journal.pgen.1007122\">10.1371/journal.pgen.1007122</a>","short":"N. Nikolic, F. Schreiber, A. Dal Co, D. Kiviet, T. Bergmiller, S. Littmann, M. Kuypers, M. Ackermann, PLoS Genetics 13 (2017).","mla":"Nikolic, Nela, et al. “Cell-to-Cell Variation and Specialization in Sugar Metabolism in Clonal Bacterial Populations.” <i>PLoS Genetics</i>, vol. 13, no. 12, e1007122, Public Library of Science, 2017, doi:<a href=\"https://doi.org/10.1371/journal.pgen.1007122\">10.1371/journal.pgen.1007122</a>.","ieee":"N. Nikolic <i>et al.</i>, “Cell-to-cell variation and specialization in sugar metabolism in clonal bacterial populations,” <i>PLoS Genetics</i>, vol. 13, no. 12. Public Library of Science, 2017.","chicago":"Nikolic, Nela, Frank Schreiber, Alma Dal Co, Daniel Kiviet, Tobias Bergmiller, Sten Littmann, Marcel Kuypers, and Martin Ackermann. “Cell-to-Cell Variation and Specialization in Sugar Metabolism in Clonal Bacterial Populations.” <i>PLoS Genetics</i>. Public Library of Science, 2017. <a href=\"https://doi.org/10.1371/journal.pgen.1007122\">https://doi.org/10.1371/journal.pgen.1007122</a>."},"ddc":["576","579"],"month":"12","article_number":"e1007122","file_date_updated":"2020-07-14T12:46:46Z","file":[{"file_size":1308475,"file_id":"5088","access_level":"open_access","date_created":"2018-12-12T10:14:35Z","date_updated":"2020-07-14T12:46:46Z","content_type":"application/pdf","relation":"main_file","file_name":"IST-2018-959-v1+1_2017_Nikolic_Cell-to-cell.pdf","checksum":"22426d9382f21554bad5fa5967afcfd0","creator":"system"}],"author":[{"last_name":"Nikolic","first_name":"Nela","id":"42D9CABC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-9068-6090","full_name":"Nikolic, Nela"},{"last_name":"Schreiber","first_name":"Frank","full_name":"Schreiber, Frank"},{"full_name":"Dal Co, Alma","last_name":"Dal Co","first_name":"Alma"},{"full_name":"Kiviet, Daniel","first_name":"Daniel","last_name":"Kiviet"},{"last_name":"Bergmiller","first_name":"Tobias","id":"2C471CFA-F248-11E8-B48F-1D18A9856A87","full_name":"Bergmiller, Tobias","orcid":"0000-0001-5396-4346"},{"last_name":"Littmann","first_name":"Sten","full_name":"Littmann, Sten"},{"last_name":"Kuypers","first_name":"Marcel","full_name":"Kuypers, Marcel"},{"first_name":"Martin","last_name":"Ackermann","full_name":"Ackermann, Martin"}],"pubrep_id":"959","_id":"541","language":[{"iso":"eng"}],"issue":"12"},{"month":"11","file_date_updated":"2020-07-14T12:46:58Z","author":[{"first_name":"Ewa","last_name":"Mazur","full_name":"Mazur, Ewa"},{"orcid":"0000-0002-8302-7596","full_name":"Friml, Jirí","first_name":"Jirí","last_name":"Friml","id":"4159519E-F248-11E8-B48F-1D18A9856A87"}],"file":[{"file_id":"4969","file_size":7443683,"date_created":"2018-12-12T10:12:49Z","date_updated":"2020-07-14T12:46:58Z","access_level":"open_access","content_type":"application/pdf","creator":"system","checksum":"e1f05e5850dfd9f9434d2d373ca61941","file_name":"IST-2018-929-v1+1_56106.pdf","relation":"main_file"}],"citation":{"ama":"Mazur E, Friml J. Vascular tissue development and regeneration in the model plant arabidopsis. In: Jurić S, ed. <i>Plant Engineering</i>. Plant Engineering. InTech; 2017:113-140. doi:<a href=\"https://doi.org/10.5772/intechopen.69712\">10.5772/intechopen.69712</a>","ista":"Mazur E, Friml J. 2017.Vascular tissue development and regeneration in the model plant arabidopsis. In: Plant Engineering. Agricultural and Biological Sciences, , 113–140.","apa":"Mazur, E., &#38; Friml, J. (2017). Vascular tissue development and regeneration in the model plant arabidopsis. In S. Jurić (Ed.), <i>Plant Engineering</i> (pp. 113–140). InTech. <a href=\"https://doi.org/10.5772/intechopen.69712\">https://doi.org/10.5772/intechopen.69712</a>","chicago":"Mazur, Ewa, and Jiří Friml. “Vascular Tissue Development and Regeneration in the Model Plant Arabidopsis.” In <i>Plant Engineering</i>, edited by Snježana Jurić, 113–40. Plant Engineering. InTech, 2017. <a href=\"https://doi.org/10.5772/intechopen.69712\">https://doi.org/10.5772/intechopen.69712</a>.","ieee":"E. Mazur and J. Friml, “Vascular tissue development and regeneration in the model plant arabidopsis,” in <i>Plant Engineering</i>, S. Jurić, Ed. InTech, 2017, pp. 113–140.","mla":"Mazur, Ewa, and Jiří Friml. “Vascular Tissue Development and Regeneration in the Model Plant Arabidopsis.” <i>Plant Engineering</i>, edited by Snježana Jurić, InTech, 2017, pp. 113–40, doi:<a href=\"https://doi.org/10.5772/intechopen.69712\">10.5772/intechopen.69712</a>.","short":"E. Mazur, J. Friml, in:, S. Jurić (Ed.), Plant Engineering, InTech, 2017, pp. 113–140."},"ddc":["581"],"page":"113 - 140","language":[{"iso":"eng"}],"_id":"545","pubrep_id":"929","title":"Vascular tissue development and regeneration in the model plant arabidopsis","doi":"10.5772/intechopen.69712","day":"17","date_updated":"2024-02-12T12:03:42Z","series_title":"Plant Engineering","has_accepted_license":"1","related_material":{"record":[{"relation":"earlier_version","id":"1274","status":"public"}]},"ec_funded":1,"year":"2017","oa":1,"oa_version":"Published Version","alternative_title":["Agricultural and Biological Sciences"],"date_created":"2018-12-11T11:47:05Z","abstract":[{"text":"Development of vascular tissue is a remarkable example of intercellular communication and coordinated development involving hormonal signaling and tissue polarity. Thus far, studies on vascular patterning and regeneration have been conducted mainly in trees—woody plants—with a well-developed layer of vascular cambium and secondary tissues. Trees are difficult to use as genetic models, i.e., due to long generation time, unstable environmental conditions, and lack of available mutants and transgenic lines. Therefore, the use of the main genetic model plant Arabidopsis thaliana (L.) Heynh., with a wealth of available marker and transgenic lines, provides a unique opportunity to address molecular mechanism of vascular tissue formation and regeneration. With specific treatments, the tiny weed Arabidopsis can serve as a model to understand the growth of mighty trees and interconnect a tree physiology with molecular genetics and cell biology of Arabidopsis.","lang":"eng"}],"date_published":"2017-11-17T00:00:00Z","status":"public","publist_id":"7269","publication":"Plant Engineering","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"department":[{"_id":"JiFr"}],"editor":[{"first_name":"Snježana","last_name":"Jurić","full_name":"Jurić, Snježana"}],"project":[{"call_identifier":"FP7","grant_number":"282300","_id":"25716A02-B435-11E9-9278-68D0E5697425","name":"Polarity and subcellular dynamics in plants"}],"quality_controlled":"1","publication_status":"published","publisher":"InTech","type":"book_chapter"},{"status":"public","date_published":"2017-06-26T00:00:00Z","abstract":[{"text":"In this report the implementation of the institutional data repository IST DataRep at IST Austria will be covered: Starting with the research phase when requirements for a repository were established, the procedure of choosing a repository-software and its customization based on the results of user-testings will be discussed. Followed by reflections on the marketing strategies in regard of impact, and at the end sharing some experiences of one year operating IST DataRep.","lang":"eng"}],"pubrep_id":"724","_id":"5450","author":[{"id":"406048EC-F248-11E8-B48F-1D18A9856A87","first_name":"Barbara","last_name":"Petritsch","orcid":"0000-0003-2724-4614","full_name":"Barbara Petritsch"}],"file":[{"date_created":"2018-12-12T11:53:22Z","date_updated":"2020-07-14T12:46:59Z","access_level":"open_access","file_id":"5483","file_size":3460985,"checksum":"6321792dcfa82bf490f17615a9b22355","creator":"system","file_name":"IST-2017-724-v1+1_DataRep_Project_Report_2017.pdf","relation":"main_file","content_type":"application/pdf"}],"file_date_updated":"2020-07-14T12:46:59Z","month":"06","publication_date":"2017-06-26","date_created":"2018-12-12T11:39:24Z","citation":{"chicago":"Petritsch, Barbara. <i>Implementing the Institutional Data Repository IST DataRep</i>. IST Austria, 2017.","ieee":"B. Petritsch, <i>Implementing the institutional data repository IST DataRep</i>. IST Austria, 2017.","short":"B. Petritsch, Implementing the Institutional Data Repository IST DataRep, IST Austria, 2017.","mla":"Petritsch, Barbara. <i>Implementing the Institutional Data Repository IST DataRep</i>. IST Austria, 2017.","ama":"Petritsch B. <i>Implementing the Institutional Data Repository IST DataRep</i>. IST Austria; 2017.","ista":"Petritsch B. 2017. Implementing the institutional data repository IST DataRep, IST Austria,p.","apa":"Petritsch, B. (2017). <i>Implementing the institutional data repository IST DataRep</i>. IST Austria."},"extern":0,"year":"2017","main_file_link":[{"url":"https://repository.ist.ac.at/id/eprint/724.","open_access":"1"}],"oa":1,"type":"report","department":[{"_id":"E-Lib"}],"title":"Implementing the institutional data repository IST DataRep","date_updated":"2020-07-14T23:05:03Z","publisher":"IST Austria","day":"26"},{"department":[{"_id":"KrCh"}],"publication_status":"published","publisher":"IST Austria","type":"technical_report","oa_version":"Published Version","alternative_title":["IST Austria Technical Report"],"date_created":"2018-12-12T11:39:26Z","abstract":[{"text":"A fundamental algorithmic problem at the heart of static analysis is Dyck reachability. The input is a graphwhere the edges are labeled with different types of opening and closing parentheses, and the reachabilityinformation is computed via paths whose parentheses are properly matched. We present new results for Dyckreachability problems with applications to alias analysis and data-dependence analysis. Our main contributions,that include improved upper bounds as well as lower bounds that establish optimality guarantees, are asfollows:First, we consider Dyck reachability on bidirected graphs, which is the standard way of performing field-sensitive points-to analysis. Given a bidirected graph withnnodes andmedges, we present: (i) an algorithmwith worst-case running timeO(m+n·α(n)), whereα(n)is the inverse Ackermann function, improving thepreviously knownO(n2)time bound; (ii) a matching lower bound that shows that our algorithm is optimalwrt to worst-case complexity; and (iii) an optimal average-case upper bound ofO(m)time, improving thepreviously knownO(m·logn)bound.Second, we consider the problem of context-sensitive data-dependence analysis, where the task is to obtainanalysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almostlinear time, after which the contribution of the library in the complexity of the client analysis is only linear,and only wrt the number of call sites.Third, we prove that combinatorial algorithms for Dyck reachability on general graphs with truly sub-cubic bounds cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean MatrixMultiplication, which is a long-standing open problem. Thus we establish that the existing combinatorialalgorithms for Dyck reachability are (conditionally) optimal for general graphs. We also show that the samehardness holds for graphs of constant treewidth.Finally, we provide a prototype implementation of our algorithms for both alias analysis and data-dependenceanalysis. Our experimental evaluation demonstrates that the new algorithms significantly outperform allexisting methods on the two problems, over real-world benchmarks.","lang":"eng"}],"status":"public","date_published":"2017-10-23T00:00:00Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","doi":"10.15479/AT:IST-2017-870-v1-1","title":"Optimal Dyck reachability for data-dependence and alias analysis","day":"23","publication_identifier":{"issn":["2664-1690"]},"date_updated":"2023-02-21T15:54:10Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"10416"}]},"has_accepted_license":"1","year":"2017","oa":1,"article_processing_charge":"No","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"first_name":"Bhavya","last_name":"Choudhary","full_name":"Choudhary, Bhavya"},{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas"}],"file":[{"content_type":"application/pdf","checksum":"177a84a46e3ac17e87b31534ad16a4c9","creator":"system","file_name":"IST-2017-870-v1+1_main.pdf","relation":"main_file","file_id":"5524","file_size":960491,"date_created":"2018-12-12T11:54:02Z","date_updated":"2020-07-14T12:46:59Z","access_level":"open_access"}],"month":"10","file_date_updated":"2020-07-14T12:46:59Z","ddc":["000"],"citation":{"ama":"Chatterjee K, Choudhary B, Pavlogiannis A. <i>Optimal Dyck Reachability for Data-Dependence and Alias Analysis</i>. IST Austria; 2017. doi:<a href=\"https://doi.org/10.15479/AT:IST-2017-870-v1-1\">10.15479/AT:IST-2017-870-v1-1</a>","apa":"Chatterjee, K., Choudhary, B., &#38; Pavlogiannis, A. (2017). <i>Optimal Dyck reachability for data-dependence and alias analysis</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2017-870-v1-1\">https://doi.org/10.15479/AT:IST-2017-870-v1-1</a>","ista":"Chatterjee K, Choudhary B, Pavlogiannis A. 2017. Optimal Dyck reachability for data-dependence and alias analysis, IST Austria, 37p.","ieee":"K. Chatterjee, B. Choudhary, and A. Pavlogiannis, <i>Optimal Dyck reachability for data-dependence and alias analysis</i>. IST Austria, 2017.","chicago":"Chatterjee, Krishnendu, Bhavya Choudhary, and Andreas Pavlogiannis. <i>Optimal Dyck Reachability for Data-Dependence and Alias Analysis</i>. IST Austria, 2017. <a href=\"https://doi.org/10.15479/AT:IST-2017-870-v1-1\">https://doi.org/10.15479/AT:IST-2017-870-v1-1</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Optimal Dyck Reachability for Data-Dependence and Alias Analysis</i>. IST Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:IST-2017-870-v1-1\">10.15479/AT:IST-2017-870-v1-1</a>.","short":"K. Chatterjee, B. Choudhary, A. Pavlogiannis, Optimal Dyck Reachability for Data-Dependence and Alias Analysis, IST Austria, 2017."},"page":"37","pubrep_id":"870","language":[{"iso":"eng"}],"_id":"5455"},{"author":[{"first_name":"Marek","last_name":"Chalupa","full_name":"Chalupa, Marek"},{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","first_name":"Andreas","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"},{"full_name":"Sinha, Nishant","last_name":"Sinha","first_name":"Nishant"},{"full_name":"Vaidya, Kapil","first_name":"Kapil","last_name":"Vaidya"}],"oa_version":"Published Version","file":[{"file_id":"5487","file_size":910347,"date_created":"2018-12-12T11:53:26Z","date_updated":"2020-07-14T12:46:59Z","access_level":"open_access","content_type":"application/pdf","creator":"system","checksum":"d2635c4cf013000f0a1b09e80f9e4ab7","file_name":"IST-2017-872-v1+1_main.pdf","relation":"main_file"}],"month":"10","file_date_updated":"2020-07-14T12:46:59Z","alternative_title":["IST Austria Technical Report"],"ddc":["000"],"date_created":"2018-12-12T11:39:26Z","citation":{"mla":"Chalupa, Marek, et al. <i>Data-Centric Dynamic Partial Order Reduction</i>. IST Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:IST-2017-872-v1-1\">10.15479/AT:IST-2017-872-v1-1</a>.","short":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, K. Vaidya, Data-Centric Dynamic Partial Order Reduction, IST Austria, 2017.","ieee":"M. Chalupa, K. Chatterjee, A. Pavlogiannis, N. Sinha, and K. Vaidya, <i>Data-centric dynamic partial order reduction</i>. IST Austria, 2017.","chicago":"Chalupa, Marek, Krishnendu Chatterjee, Andreas Pavlogiannis, Nishant Sinha, and Kapil Vaidya. <i>Data-Centric Dynamic Partial Order Reduction</i>. IST Austria, 2017. <a href=\"https://doi.org/10.15479/AT:IST-2017-872-v1-1\">https://doi.org/10.15479/AT:IST-2017-872-v1-1</a>.","apa":"Chalupa, M., Chatterjee, K., Pavlogiannis, A., Sinha, N., &#38; Vaidya, K. (2017). <i>Data-centric dynamic partial order reduction</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2017-872-v1-1\">https://doi.org/10.15479/AT:IST-2017-872-v1-1</a>","ista":"Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. 2017. Data-centric dynamic partial order reduction, IST Austria, 36p.","ama":"Chalupa M, Chatterjee K, Pavlogiannis A, Sinha N, Vaidya K. <i>Data-Centric Dynamic Partial Order Reduction</i>. IST Austria; 2017. doi:<a href=\"https://doi.org/10.15479/AT:IST-2017-872-v1-1\">10.15479/AT:IST-2017-872-v1-1</a>"},"page":"36","abstract":[{"lang":"eng","text":"We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class.\r\nWe introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence.\r\n1. For acyclic architectures, our algorithm is guaranteed to explore exactly one representative trace from each observation class, while spending polynomial time per class. Hence, our algorithm is optimal wrt the observation equivalence, and in several cases explores exponentially fewer traces than any enumerative method based on the Mazurkiewicz equivalence.\r\n2. For cyclic architectures, we consider an equivalence between traces which is finer than the observation equivalence; but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence. \r\nFinally, we perform a basic experimental comparison between the existing Mazurkiewicz-based DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show a significant reduction in both running time and the number of explored equivalence classes."}],"status":"public","date_published":"2017-10-23T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5456","language":[{"iso":"eng"}],"pubrep_id":"872","doi":"10.15479/AT:IST-2017-872-v1-1","title":"Data-centric dynamic partial order reduction","department":[{"_id":"KrCh"}],"day":"23","publication_status":"published","publication_identifier":{"issn":["2664-1690"]},"date_updated":"2023-02-23T12:26:54Z","publisher":"IST Austria","related_material":{"record":[{"status":"public","id":"10417","relation":"later_version"},{"status":"public","id":"5448","relation":"earlier_version"}]},"has_accepted_license":"1","year":"2017","type":"technical_report","oa":1},{"doi":"10.1103/PhysRevE.96.060401","title":"Maximum entropy modeling of metabolic networks by constraining growth-rate moments predicts coexistence of phenotypes","day":"21","publication_identifier":{"issn":["2470-0045"]},"date_updated":"2023-10-10T13:29:38Z","year":"2017","ec_funded":1,"article_processing_charge":"No","oa":1,"author":[{"id":"3FF5848A-F248-11E8-B48F-1D18A9856A87","last_name":"De Martino","first_name":"Daniele","full_name":"De Martino, Daniele","orcid":"0000-0002-5214-4706"}],"article_number":"060401","month":"12","citation":{"mla":"De Martino, Daniele. “Maximum Entropy Modeling of Metabolic Networks by Constraining Growth-Rate Moments Predicts Coexistence of Phenotypes.” <i>Physical Review E</i>, vol. 96, no. 6, 060401, American Physical Society, 2017, doi:<a href=\"https://doi.org/10.1103/PhysRevE.96.060401\">10.1103/PhysRevE.96.060401</a>.","short":"D. De Martino, Physical Review E 96 (2017).","chicago":"De Martino, Daniele. “Maximum Entropy Modeling of Metabolic Networks by Constraining Growth-Rate Moments Predicts Coexistence of Phenotypes.” <i>Physical Review E</i>. American Physical Society, 2017. <a href=\"https://doi.org/10.1103/PhysRevE.96.060401\">https://doi.org/10.1103/PhysRevE.96.060401</a>.","ieee":"D. De Martino, “Maximum entropy modeling of metabolic networks by constraining growth-rate moments predicts coexistence of phenotypes,” <i>Physical Review E</i>, vol. 96, no. 6. American Physical Society, 2017.","ista":"De Martino D. 2017. Maximum entropy modeling of metabolic networks by constraining growth-rate moments predicts coexistence of phenotypes. Physical Review E. 96(6), 060401.","apa":"De Martino, D. (2017). Maximum entropy modeling of metabolic networks by constraining growth-rate moments predicts coexistence of phenotypes. <i>Physical Review E</i>. American Physical Society. <a href=\"https://doi.org/10.1103/PhysRevE.96.060401\">https://doi.org/10.1103/PhysRevE.96.060401</a>","ama":"De Martino D. Maximum entropy modeling of metabolic networks by constraining growth-rate moments predicts coexistence of phenotypes. <i>Physical Review E</i>. 2017;96(6). doi:<a href=\"https://doi.org/10.1103/PhysRevE.96.060401\">10.1103/PhysRevE.96.060401</a>"},"issue":"6","language":[{"iso":"eng"}],"_id":"548","department":[{"_id":"GaTk"}],"quality_controlled":"1","project":[{"call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","publisher":"American Physical Society","main_file_link":[{"url":"https://arxiv.org/abs/1707.00320","open_access":"1"}],"type":"journal_article","volume":96,"oa_version":"Submitted Version","scopus_import":"1","alternative_title":["Rapid Communications"],"date_created":"2018-12-11T11:47:06Z","abstract":[{"text":"In this work maximum entropy distributions in the space of steady states of metabolic networks are considered upon constraining the first and second moments of the growth rate. Coexistence of fast and slow phenotypes, with bimodal flux distributions, emerges upon considering control on the average growth (optimization) and its fluctuations (heterogeneity). This is applied to the carbon catabolic core of Escherichia coli where it quantifies the metabolic activity of slow growing phenotypes and it provides a quantitative map with metabolic fluxes, opening the possibility to detect coexistence from flux data. A preliminary analysis on data for E. coli cultures in standard conditions shows degeneracy for the inferred parameters that extend in the coexistence region.","lang":"eng"}],"publication":"Physical Review E","publist_id":"7266","date_published":"2017-12-21T00:00:00Z","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"        96"},{"date_updated":"2023-10-17T12:02:46Z","publication_identifier":{"issn":["2075-2180"]},"day":"10","title":"Causality-based model checking","doi":"10.4204/EPTCS.259.3","oa":1,"article_processing_charge":"No","year":"2017","has_accepted_license":"1","conference":{"start_date":"2017-04-29","end_date":"2017-04-29","location":"Uppsala, Sweden","name":"CREST: Causal Reasoning for Embedded and Safety-Critical Systems Technologies"},"citation":{"short":"B. Finkbeiner, A. Kupriyanov, in:, Electronic Proceedings in Theoretical Computer Science, Open Publishing Association, 2017, pp. 31–38.","mla":"Finkbeiner, Bernd, and Andrey Kupriyanov. “Causality-Based Model Checking.” <i>Electronic Proceedings in Theoretical Computer Science</i>, vol. 259, Open Publishing Association, 2017, pp. 31–38, doi:<a href=\"https://doi.org/10.4204/EPTCS.259.3\">10.4204/EPTCS.259.3</a>.","chicago":"Finkbeiner, Bernd, and Andrey Kupriyanov. “Causality-Based Model Checking.” In <i>Electronic Proceedings in Theoretical Computer Science</i>, 259:31–38. Open Publishing Association, 2017. <a href=\"https://doi.org/10.4204/EPTCS.259.3\">https://doi.org/10.4204/EPTCS.259.3</a>.","ieee":"B. Finkbeiner and A. Kupriyanov, “Causality-based model checking,” in <i>Electronic Proceedings in Theoretical Computer Science</i>, Uppsala, Sweden, 2017, vol. 259, pp. 31–38.","ista":"Finkbeiner B, Kupriyanov A. 2017. Causality-based model checking. Electronic Proceedings in Theoretical Computer Science. CREST: Causal Reasoning for Embedded and Safety-Critical Systems Technologies, EPTCS, vol. 259, 31–38.","apa":"Finkbeiner, B., &#38; Kupriyanov, A. (2017). Causality-based model checking. In <i>Electronic Proceedings in Theoretical Computer Science</i> (Vol. 259, pp. 31–38). Uppsala, Sweden: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.259.3\">https://doi.org/10.4204/EPTCS.259.3</a>","ama":"Finkbeiner B, Kupriyanov A. Causality-based model checking. In: <i>Electronic Proceedings in Theoretical Computer Science</i>. Vol 259. Open Publishing Association; 2017:31-38. doi:<a href=\"https://doi.org/10.4204/EPTCS.259.3\">10.4204/EPTCS.259.3</a>"},"ddc":["004"],"month":"10","file_date_updated":"2020-07-14T12:47:00Z","author":[{"first_name":"Bernd","last_name":"Finkbeiner","full_name":"Finkbeiner, Bernd"},{"first_name":"Andrey","last_name":"Kupriyanov","id":"2C311BF8-F248-11E8-B48F-1D18A9856A87","full_name":"Kupriyanov, Andrey"}],"file":[{"access_level":"open_access","date_created":"2018-12-12T10:12:21Z","date_updated":"2020-07-14T12:47:00Z","file_size":209294,"file_id":"4939","relation":"main_file","file_name":"IST-2018-925-v1+1_1710.03391v1.pdf","creator":"system","checksum":"6274f6c0da3376a7b079180d81568518","content_type":"application/pdf"}],"_id":"549","language":[{"iso":"eng"}],"pubrep_id":"925","page":"31 - 38","publisher":"Open Publishing Association","publication_status":"published","project":[{"call_identifier":"FWF","grant_number":"S11402-N23","name":"Moderne Concurrency Paradigms","_id":"25F5A88A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"quality_controlled":"1","department":[{"_id":"ToHe"}],"volume":259,"type":"conference","main_file_link":[{"url":"https://arxiv.org/abs/1710.03391v1","open_access":"1"}],"date_created":"2018-12-11T11:47:07Z","alternative_title":["EPTCS"],"scopus_import":"1","oa_version":"Submitted Version","intvolume":"       259","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2017-10-10T00:00:00Z","status":"public","publication":"Electronic Proceedings in Theoretical Computer Science","publist_id":"7264","abstract":[{"lang":"eng","text":"Model checking is usually based on a comprehensive traversal of the state space. Causality-based model checking is a radically different approach that instead analyzes the cause-effect relationships in a program. We give an overview on a new class of model checking algorithms that capture the causal relationships in a special data structure called concurrent traces. Concurrent traces identify key events in an execution history and link them through their cause-effect relationships. The model checker builds a tableau of concurrent traces, where the case splits represent different causal explanations of a hypothetical error. Causality-based model checking has been implemented in the ARCTOR tool, and applied to previously intractable multi-threaded benchmarks."}]},{"day":"21","publication_identifier":{"issn":["1083589X"]},"date_updated":"2023-09-07T12:38:08Z","doi":"10.1214/17-ECP97","title":"Singularities of the density of states of random Gram matrices","oa":1,"has_accepted_license":"1","related_material":{"record":[{"id":"149","relation":"dissertation_contains","status":"public"}]},"ec_funded":1,"year":"2017","ddc":["539"],"citation":{"ista":"Alt J. 2017. Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. 22, 63.","apa":"Alt, J. (2017). Singularities of the density of states of random Gram matrices. <i>Electronic Communications in Probability</i>. Institute of Mathematical Statistics. <a href=\"https://doi.org/10.1214/17-ECP97\">https://doi.org/10.1214/17-ECP97</a>","ama":"Alt J. Singularities of the density of states of random Gram matrices. <i>Electronic Communications in Probability</i>. 2017;22. doi:<a href=\"https://doi.org/10.1214/17-ECP97\">10.1214/17-ECP97</a>","short":"J. Alt, Electronic Communications in Probability 22 (2017).","mla":"Alt, Johannes. “Singularities of the Density of States of Random Gram Matrices.” <i>Electronic Communications in Probability</i>, vol. 22, 63, Institute of Mathematical Statistics, 2017, doi:<a href=\"https://doi.org/10.1214/17-ECP97\">10.1214/17-ECP97</a>.","chicago":"Alt, Johannes. “Singularities of the Density of States of Random Gram Matrices.” <i>Electronic Communications in Probability</i>. Institute of Mathematical Statistics, 2017. <a href=\"https://doi.org/10.1214/17-ECP97\">https://doi.org/10.1214/17-ECP97</a>.","ieee":"J. Alt, “Singularities of the density of states of random Gram matrices,” <i>Electronic Communications in Probability</i>, vol. 22. Institute of Mathematical Statistics, 2017."},"author":[{"full_name":"Alt, Johannes","id":"36D3D8B6-F248-11E8-B48F-1D18A9856A87","last_name":"Alt","first_name":"Johannes"}],"file":[{"access_level":"open_access","date_created":"2018-12-12T10:08:04Z","date_updated":"2020-07-14T12:47:00Z","file_size":470876,"file_id":"4663","relation":"main_file","file_name":"IST-2018-926-v1+1_euclid.ecp.1511233247.pdf","checksum":"0ec05303a0de190de145654237984c79","creator":"system","content_type":"application/pdf"}],"file_date_updated":"2020-07-14T12:47:00Z","month":"11","article_number":"63","language":[{"iso":"eng"}],"_id":"550","pubrep_id":"926","publication_status":"published","publisher":"Institute of Mathematical Statistics","department":[{"_id":"LaEr"}],"quality_controlled":"1","project":[{"grant_number":"338804","name":"Random matrices, universality and disordered quantum systems","_id":"258DCDE6-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"type":"journal_article","volume":22,"scopus_import":1,"date_created":"2018-12-11T11:47:07Z","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":"        22","abstract":[{"text":"For large random matrices X with independent, centered entries but not necessarily identical variances, the eigenvalue density of XX* is well-approximated by a deterministic measure on ℝ. We show that the density of this measure has only square and cubic-root singularities away from zero. We also extend the bulk local law in [5] to the vicinity of these singularities.","lang":"eng"}],"publication":"Electronic Communications in Probability","publist_id":"7265","date_published":"2017-11-21T00:00:00Z","status":"public"},{"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"},{"full_name":"Nowak, Martin","first_name":"Martin","last_name":"Nowak"}],"file":[{"relation":"main_file","file_name":"IST-2018-924-v1+1_LIPIcs-MFCS-2017-61.pdf","checksum":"2eed5224c0e4e259484a1d71acb8ba6a","creator":"system","content_type":"application/pdf","access_level":"open_access","date_created":"2018-12-12T10:18:04Z","date_updated":"2020-07-14T12:47:00Z","file_size":535077,"file_id":"5322"}],"article_number":"61","file_date_updated":"2020-07-14T12:47:00Z","month":"11","ddc":["004"],"citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs. In: <i>Leibniz International Proceedings in Informatics</i>. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.61\">10.4230/LIPIcs.MFCS.2017.61</a>","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2017). Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs. In <i>Leibniz International Proceedings in Informatics</i> (Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.61\">https://doi.org/10.4230/LIPIcs.MFCS.2017.61</a>","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2017. Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 61.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, “Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs,” in <i>Leibniz International Proceedings in Informatics</i>, Aalborg, Denmark, 2017, vol. 83.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. “Faster Monte Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs.” In <i>Leibniz International Proceedings in Informatics</i>, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.61\">https://doi.org/10.4230/LIPIcs.MFCS.2017.61</a>.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Chatterjee, Krishnendu, et al. “Faster Monte Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs.” <i>Leibniz International Proceedings in Informatics</i>, vol. 83, 61, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.61\">10.4230/LIPIcs.MFCS.2017.61</a>."},"_id":"551","language":[{"iso":"eng"}],"pubrep_id":"924","doi":"10.4230/LIPIcs.MFCS.2017.61","title":"Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs","day":"01","publication_identifier":{"isbn":["978-395977046-0"]},"date_updated":"2021-01-12T08:02:34Z","conference":{"start_date":"2017-08-21","end_date":"2017-08-25","location":"Aalborg, Denmark","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"has_accepted_license":"1","year":"2017","oa":1,"oa_version":"Published Version","scopus_import":1,"alternative_title":["LIPIcs"],"date_created":"2018-12-11T11:47:08Z","abstract":[{"lang":"eng","text":"Evolutionary graph theory studies the evolutionary dynamics in a population structure given as a connected graph. Each node of the graph represents an individual of the population, and edges determine how offspring are placed. We consider the classical birth-death Moran process where there are two types of individuals, namely, the residents with fitness 1 and mutants with fitness r. The fitness indicates the reproductive strength. The evolutionary dynamics happens as follows: in the initial step, in a population of all resident individuals a mutant is introduced, and then at each step, an individual is chosen proportional to the fitness of its type to reproduce, and the offspring replaces a neighbor uniformly at random. The process stops when all individuals are either residents or mutants. The probability that all individuals in the end are mutants is called the fixation probability, which is a key factor in the rate of evolution. We consider the problem of approximating the fixation probability. The class of algorithms that is extremely relevant for approximation of the fixation probabilities is the Monte-Carlo simulation of the process. Previous results present a polynomial-time Monte-Carlo algorithm for undirected graphs when r is given in unary. First, we present a simple modification: instead of simulating each step, we discard ineffective steps, where no node changes type (i.e., either residents replace residents, or mutants replace mutants). Using the above simple modification and our result that the number of effective steps is concentrated around the expected number of effective steps, we present faster polynomial-time Monte-Carlo algorithms for undirected graphs. Our algorithms are always at least a factor O(n2/ log n) faster as compared to the previous algorithms, where n is the number of nodes, and is polynomial even if r is given in binary. We also present lower bounds showing that the upper bound on the expected number of effective steps we present is asymptotically tight for undirected graphs. "}],"publist_id":"7263","publication":"Leibniz International Proceedings in Informatics","status":"public","date_published":"2017-11-01T00:00:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":"        83","department":[{"_id":"KrCh"}],"quality_controlled":"1","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","type":"conference","volume":83},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","license":"https://creativecommons.org/licenses/by/3.0/","tmp":{"short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png"},"intvolume":"        83","abstract":[{"lang":"eng","text":"Graph games provide the foundation for modeling and synthesis of reactive processes. Such games are played over graphs where the vertices are controlled by two adversarial players. We consider graph games where the objective of the first player is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a meanpayoff condition). There are two variants of the problem, namely, the threshold problem where the quantitative goal is to ensure that the mean-payoff value is above a threshold, and the value problem where the quantitative goal is to ensure the optimal mean-payoff value; in both cases ensuring the qualitative parity objective. The previous best-known algorithms for game graphs with n vertices, m edges, parity objectives with d priorities, and maximal absolute reward value W for mean-payoff objectives, are as follows: O(nd+1 . m . w) for the threshold problem, and O(nd+2 · m · W) for the value problem. Our main contributions are faster algorithms, and the running times of our algorithms are as follows: O(nd-1 · m ·W) for the threshold problem, and O(nd · m · W · log(n · W)) for the value problem. For mean-payoff parity objectives with two priorities, our algorithms match the best-known bounds of the algorithms for mean-payoff games (without conjunction with parity objectives). Our results are relevant in synthesis of reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective)."}],"status":"public","date_published":"2017-11-01T00:00:00Z","publication":"Leibniz International Proceedings in Informatics","publist_id":"7262","alternative_title":["LIPIcs"],"scopus_import":"1","date_created":"2018-12-11T11:47:08Z","oa_version":"Published Version","volume":83,"type":"conference","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"}],"project":[{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"},{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","language":[{"iso":"eng"}],"_id":"552","pubrep_id":"923","citation":{"apa":"Chatterjee, K., Henzinger, M. H., &#38; Svozil, A. (2017). Faster algorithms for mean-payoff parity games. In <i>Leibniz International Proceedings in Informatics</i> (Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.39\">https://doi.org/10.4230/LIPIcs.MFCS.2017.39</a>","ista":"Chatterjee K, Henzinger MH, Svozil A. 2017. Faster algorithms for mean-payoff parity games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 39.","ama":"Chatterjee K, Henzinger MH, Svozil A. Faster algorithms for mean-payoff parity games. In: <i>Leibniz International Proceedings in Informatics</i>. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.39\">10.4230/LIPIcs.MFCS.2017.39</a>","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithms for Mean-Payoff Parity Games.” <i>Leibniz International Proceedings in Informatics</i>, vol. 83, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.39\">10.4230/LIPIcs.MFCS.2017.39</a>.","short":"K. Chatterjee, M.H. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","ieee":"K. Chatterjee, M. H. Henzinger, and A. Svozil, “Faster algorithms for mean-payoff parity games,” in <i>Leibniz International Proceedings in Informatics</i>, Aalborg, Denmark, 2017, vol. 83.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, and Alexander Svozil. “Faster Algorithms for Mean-Payoff Parity Games.” In <i>Leibniz International Proceedings in Informatics</i>, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.39\">https://doi.org/10.4230/LIPIcs.MFCS.2017.39</a>."},"ddc":["004"],"article_number":"39","month":"11","file_date_updated":"2020-07-14T12:47:00Z","file":[{"access_level":"open_access","date_created":"2018-12-12T10:16:57Z","date_updated":"2020-07-14T12:47:00Z","file_size":610339,"file_id":"5248","file_name":"IST-2018-923-v1+1_LIPIcs-MFCS-2017-39.pdf","relation":"main_file","creator":"system","checksum":"c67f4866ddbfd555afef1f63ae9a8fc7","content_type":"application/pdf"}],"author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"first_name":"Alexander","last_name":"Svozil","full_name":"Svozil, Alexander"}],"oa":1,"article_processing_charge":"No","has_accepted_license":"1","conference":{"start_date":"2017-08-21","end_date":"2017-08-25","location":"Aalborg, Denmark","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"year":"2017","ec_funded":1,"publication_identifier":{"isbn":["978-395977046-0"]},"day":"01","date_updated":"2023-02-14T10:06:46Z","title":"Faster algorithms for mean-payoff parity games","doi":"10.4230/LIPIcs.MFCS.2017.39"},{"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Hansen","first_name":"Kristofer","full_name":"Hansen, Kristofer"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389"}],"file":[{"creator":"system","checksum":"7101facb56ade363205c695d72dbd173","file_name":"IST-2018-922-v1+1_LIPIcs-MFCS-2017-55.pdf","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:09:29Z","date_updated":"2020-07-14T12:47:00Z","access_level":"open_access","file_id":"4753","file_size":549967}],"month":"11","file_date_updated":"2020-07-14T12:47:00Z","article_number":"55","ddc":["004"],"citation":{"ama":"Chatterjee K, Hansen K, Ibsen-Jensen R. Strategy complexity of concurrent safety games. In: <i>Leibniz International Proceedings in Informatics</i>. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.55\">10.4230/LIPIcs.MFCS.2017.55</a>","apa":"Chatterjee, K., Hansen, K., &#38; Ibsen-Jensen, R. (2017). Strategy complexity of concurrent safety games. In <i>Leibniz International Proceedings in Informatics</i> (Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.55\">https://doi.org/10.4230/LIPIcs.MFCS.2017.55</a>","ista":"Chatterjee K, Hansen K, Ibsen-Jensen R. 2017. Strategy complexity of concurrent safety games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83, 55.","ieee":"K. Chatterjee, K. Hansen, and R. Ibsen-Jensen, “Strategy complexity of concurrent safety games,” in <i>Leibniz International Proceedings in Informatics</i>, Aalborg, Denmark, 2017, vol. 83.","chicago":"Chatterjee, Krishnendu, Kristofer Hansen, and Rasmus Ibsen-Jensen. “Strategy Complexity of Concurrent Safety Games.” In <i>Leibniz International Proceedings in Informatics</i>, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.55\">https://doi.org/10.4230/LIPIcs.MFCS.2017.55</a>.","short":"K. Chatterjee, K. Hansen, R. Ibsen-Jensen, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Chatterjee, Krishnendu, et al. “Strategy Complexity of Concurrent Safety Games.” <i>Leibniz International Proceedings in Informatics</i>, vol. 83, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2017.55\">10.4230/LIPIcs.MFCS.2017.55</a>."},"language":[{"iso":"eng"}],"_id":"553","pubrep_id":"922","doi":"10.4230/LIPIcs.MFCS.2017.55","title":"Strategy complexity of concurrent safety games","day":"01","publication_identifier":{"isbn":["978-395977046-0"]},"date_updated":"2021-01-12T08:02:35Z","conference":{"location":"Aalborg, Denmark","name":"MFCS: Mathematical Foundations of Computer Science (SG)","start_date":"2017-08-21","end_date":"2017-08-25"},"has_accepted_license":"1","year":"2017","oa":1,"oa_version":"Published Version","scopus_import":1,"alternative_title":["LIPIcs"],"date_created":"2018-12-11T11:47:08Z","abstract":[{"lang":"eng","text":"We consider two player, zero-sum, finite-state concurrent reachability games, played for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. Player 1 wins iff a designated goal state is eventually visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed. Our main results are as follows: We show that: (i) the optimal bound on the patience of optimal and -optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. "}],"publication":"Leibniz International Proceedings in Informatics","publist_id":"7261","date_published":"2017-11-01T00:00:00Z","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":"        83","department":[{"_id":"KrCh"}],"quality_controlled":"1","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","main_file_link":[{"url":"https://arxiv.org/abs/1506.02434","open_access":"1"}],"type":"conference","volume":83},{"ddc":["519"],"keyword":["natural selection"],"citation":{"short":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak , (2017).","mla":"Pavlogiannis, Andreas, et al. <i>Strong Amplifiers of Natural Selection</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:51\">10.15479/AT:ISTA:51</a>.","ieee":"A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak , “Strong amplifiers of natural selection.” Institute of Science and Technology Austria, 2017.","chicago":"Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin Nowak . “Strong Amplifiers of Natural Selection.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:51\">https://doi.org/10.15479/AT:ISTA:51</a>.","apa":"Pavlogiannis, A., Tkadlec, J., Chatterjee, K., &#38; Nowak , M. (2017). Strong amplifiers of natural selection. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:51\">https://doi.org/10.15479/AT:ISTA:51</a>","ista":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak  M. 2017. Strong amplifiers of natural selection, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:51\">10.15479/AT:ISTA:51</a>.","ama":"Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak  M. Strong amplifiers of natural selection. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:51\">10.15479/AT:ISTA:51</a>"},"date_created":"2018-12-12T12:31:32Z","file":[{"relation":"main_file","file_name":"IST-2017-51-v1+2_illustration.mp4","creator":"system","checksum":"b427dd46a30096a1911b245640c47af8","content_type":"video/mp4","access_level":"open_access","date_created":"2018-12-12T13:05:18Z","date_updated":"2020-07-14T12:47:02Z","file_size":32987015,"file_id":"5644"}],"author":[{"last_name":"Pavlogiannis","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"},{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","first_name":"Josef","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684"},{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Nowak ","first_name":"Martin","full_name":"Nowak , Martin"}],"oa_version":"Published Version","month":"01","file_date_updated":"2020-07-14T12:47:02Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"5559","abstract":[{"text":"Strong amplifiers of natural selection","lang":"eng"}],"status":"public","date_published":"2017-01-02T00:00:00Z","day":"02","date_updated":"2024-02-21T13:48:42Z","publisher":"Institute of Science and Technology Austria","doi":"10.15479/AT:ISTA:51","department":[{"_id":"KrCh"}],"title":"Strong amplifiers of natural selection","project":[{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"type":"research_data","article_processing_charge":"No","oa":1,"datarep_id":"51","related_material":{"record":[{"id":"5452","relation":"research_paper","status":"public"},{"status":"public","relation":"research_paper","id":"5751"}]},"has_accepted_license":"1","year":"2017","ec_funded":1}]