[{"_id":"3771","type":"journal_article","date_created":"2018-12-11T12:05:05Z","year":"2011","page":"527 - 539","doi":"10.1111/j.1095-8312.2010.01601.x","status":"public","day":"10","scopus_import":1,"publication":"Biological Journal of the Linnean Society","publist_id":"2456","intvolume":"       102","citation":{"ieee":"A. Pavan, F. Martins, F. Santos, A. Ditchfield, and R. A. Fernandes Redondo, “Patterns of diversification in two species of short-tailed bats (Carollia Gray, 1838): the effects of historical fragmentation of Brazilian rainforests.,” <i>Biological Journal of the Linnean Society</i>, vol. 102, no. 3. Wiley-Blackwell, pp. 527–539, 2011.","ama":"Pavan A, Martins F, Santos F, Ditchfield A, Fernandes Redondo RA. Patterns of diversification in two species of short-tailed bats (Carollia Gray, 1838): the effects of historical fragmentation of Brazilian rainforests. <i>Biological Journal of the Linnean Society</i>. 2011;102(3):527-539. doi:<a href=\"https://doi.org/10.1111/j.1095-8312.2010.01601.x\">10.1111/j.1095-8312.2010.01601.x</a>","chicago":"Pavan, Ana, Felipe Martins, Fabrício Santos, Albert Ditchfield, and Rodrigo A Fernandes Redondo. “Patterns of Diversification in Two Species of Short-Tailed Bats (Carollia Gray, 1838): The Effects of Historical Fragmentation of Brazilian Rainforests.” <i>Biological Journal of the Linnean Society</i>. Wiley-Blackwell, 2011. <a href=\"https://doi.org/10.1111/j.1095-8312.2010.01601.x\">https://doi.org/10.1111/j.1095-8312.2010.01601.x</a>.","ista":"Pavan A, Martins F, Santos F, Ditchfield A, Fernandes Redondo RA. 2011. Patterns of diversification in two species of short-tailed bats (Carollia Gray, 1838): the effects of historical fragmentation of Brazilian rainforests. Biological Journal of the Linnean Society. 102(3), 527–539.","apa":"Pavan, A., Martins, F., Santos, F., Ditchfield, A., &#38; Fernandes Redondo, R. A. (2011). Patterns of diversification in two species of short-tailed bats (Carollia Gray, 1838): the effects of historical fragmentation of Brazilian rainforests. <i>Biological Journal of the Linnean Society</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/j.1095-8312.2010.01601.x\">https://doi.org/10.1111/j.1095-8312.2010.01601.x</a>","mla":"Pavan, Ana, et al. “Patterns of Diversification in Two Species of Short-Tailed Bats (Carollia Gray, 1838): The Effects of Historical Fragmentation of Brazilian Rainforests.” <i>Biological Journal of the Linnean Society</i>, vol. 102, no. 3, Wiley-Blackwell, 2011, pp. 527–39, doi:<a href=\"https://doi.org/10.1111/j.1095-8312.2010.01601.x\">10.1111/j.1095-8312.2010.01601.x</a>.","short":"A. Pavan, F. Martins, F. Santos, A. Ditchfield, R.A. Fernandes Redondo, Biological Journal of the Linnean Society 102 (2011) 527–539."},"oa_version":"None","department":[{"_id":"FyKo"}],"quality_controlled":"1","date_updated":"2021-01-12T07:52:05Z","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Ana","last_name":"Pavan","full_name":"Pavan, Ana"},{"last_name":"Martins","first_name":"Felipe","full_name":"Martins, Felipe"},{"full_name":"Santos, Fabrício","last_name":"Santos","first_name":"Fabrício"},{"full_name":"Ditchfield, Albert","first_name":"Albert","last_name":"Ditchfield"},{"id":"409D5C96-F248-11E8-B48F-1D18A9856A87","full_name":"Fernandes Redondo, Rodrigo A","first_name":"Rodrigo A","last_name":"Fernandes Redondo","orcid":"0000-0002-5837-2793"}],"issue":"3","publication_status":"published","month":"02","abstract":[{"text":"The small-sized frugivorous bat Carollia perspicillata is an understory specialist and occurs in a wide range of lowland habitats, tending to be more common in tropical dry or moist forests of South and Central America. Its sister species, Carollia brevicauda, occurs almost exclusively in the Amazon rainforest. A recent phylogeographic study proposed a hypothesis of origin and subsequent diversification for C. perspicillata along the Atlantic coastal forest of Brazil. Additionally, it also found two allopatric clades for C. brevicauda separated by the Amazon Basin. We used cytochrome b gene sequences and a more extensive sampling to test hypotheses related to the origin and diversification of C. perspicillata plus C. brevicauda clade in South America. The results obtained indicate that there are two sympatric evolutionary lineages within each species. In C. perspicillata, one lineage is limited to the Southern Atlantic Forest, whereas the other is widely distributed. Coalescent analysis points to a simultaneous origin for C. perspicillata and C. brevicauda, although no place for the diversification of each species can be firmly suggested. The phylogeographic pattern shown by C. perspicillata is also congruent with the Pleistocene refugia hypothesis as a likely vicariant phenomenon shaping the present distribution of its intraspecific lineages.","lang":"eng"}],"title":"Patterns of diversification in two species of short-tailed bats (Carollia Gray, 1838): the effects of historical fragmentation of Brazilian rainforests.","volume":102,"publisher":"Wiley-Blackwell","language":[{"iso":"eng"}],"date_published":"2011-02-10T00:00:00Z"},{"publist_id":"2449","intvolume":"       106","publication":"Heredity","scopus_import":1,"status":"public","year":"2011","day":"01","page":"205 - 206","doi":"10.1038/hdy.2010.67","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3183869/"}],"date_created":"2018-12-11T12:05:07Z","oa":1,"type":"journal_article","_id":"3778","pmid":1,"date_published":"2011-02-01T00:00:00Z","publisher":"Nature Publishing Group","language":[{"iso":"eng"}],"volume":106,"title":"Estimating linkage disequilibria","publication_status":"published","month":"02","issue":"2","author":[{"orcid":"0000-0002-8548-5240","first_name":"Nicholas H","last_name":"Barton","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"pmid":["20502479"]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"NiBa"}],"date_updated":"2021-01-12T07:52:08Z","oa_version":"Submitted Version","citation":{"mla":"Barton, Nicholas H. “Estimating Linkage Disequilibria.” <i>Heredity</i>, vol. 106, no. 2, Nature Publishing Group, 2011, pp. 205–06, doi:<a href=\"https://doi.org/10.1038/hdy.2010.67\">10.1038/hdy.2010.67</a>.","short":"N.H. Barton, Heredity 106 (2011) 205–206.","ieee":"N. H. Barton, “Estimating linkage disequilibria,” <i>Heredity</i>, vol. 106, no. 2. Nature Publishing Group, pp. 205–206, 2011.","ama":"Barton NH. Estimating linkage disequilibria. <i>Heredity</i>. 2011;106(2):205-206. doi:<a href=\"https://doi.org/10.1038/hdy.2010.67\">10.1038/hdy.2010.67</a>","ista":"Barton NH. 2011. Estimating linkage disequilibria. Heredity. 106(2), 205–206.","chicago":"Barton, Nicholas H. “Estimating Linkage Disequilibria.” <i>Heredity</i>. Nature Publishing Group, 2011. <a href=\"https://doi.org/10.1038/hdy.2010.67\">https://doi.org/10.1038/hdy.2010.67</a>.","apa":"Barton, N. H. (2011). Estimating linkage disequilibria. <i>Heredity</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/hdy.2010.67\">https://doi.org/10.1038/hdy.2010.67</a>"}},{"oa_version":"None","citation":{"mla":"Fasy, Brittany Terese. “The Difference in Length of Curves in R^n.” <i>Acta Sci. Math. (Szeged)</i>, vol. 77, no. 1–2, Szegedi Tudományegyetem, 2011, pp. 359–67.","short":"B.T. Fasy, Acta Sci. Math. (Szeged) 77 (2011) 359–367.","ieee":"B. T. Fasy, “The difference in length of curves in R^n,” <i>Acta Sci. Math. (Szeged)</i>, vol. 77, no. 1–2. Szegedi Tudományegyetem, pp. 359–367, 2011.","apa":"Fasy, B. T. (2011). The difference in length of curves in R^n. <i>Acta Sci. Math. (Szeged)</i>. Szegedi Tudományegyetem.","chicago":"Fasy, Brittany Terese. “The Difference in Length of Curves in R^n.” <i>Acta Sci. Math. (Szeged)</i>. Szegedi Tudományegyetem, 2011.","ama":"Fasy BT. The difference in length of curves in R^n. <i>Acta Sci Math (Szeged)</i>. 2011;77(1-2):359-367.","ista":"Fasy BT. 2011. The difference in length of curves in R^n. Acta Sci. Math. (Szeged). 77(1–2), 359–367."},"department":[{"_id":"HeEd"}],"quality_controlled":"1","date_updated":"2021-01-12T07:52:09Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"F65D502E-E68D-11E9-9252-C644099818F6","full_name":"Fasy, Brittany Terese","last_name":"Fasy","first_name":"Brittany Terese"}],"issue":"1-2","month":"01","publication_status":"published","abstract":[{"lang":"eng","text":"We bound the difference in length of two curves in terms of their total curvatures and the Fréchet distance. The bound is independent of the dimension of the ambient Euclidean space, it improves upon a bound by Cohen-Steiner and Edelsbrunner, and it generalizes a result by Fáry and Chakerian."}],"title":"The difference in length of curves in R^n","volume":77,"date_published":"2011-01-01T00:00:00Z","publisher":"Szegedi Tudományegyetem","language":[{"iso":"eng"}],"type":"journal_article","_id":"3781","date_created":"2018-12-11T12:05:08Z","page":"359 - 367","day":"01","year":"2011","status":"public","acknowledgement":"Funded by Graduate Aid in Areas of National Need (GAANN) Fellowship.","publication":"Acta Sci. Math. (Szeged)","publist_id":"2446","intvolume":"        77"},{"date_updated":"2021-01-12T07:52:10Z","department":[{"_id":"NiBa"}],"citation":{"ieee":"F. Palero, G. Guerao, P. Clark, and P. Abello, “Scyllarus arctus (Crustacea: Decapoda: Scyllaridae) final stage phyllosoma identified by DNA analysis, with morphological description,” <i>Journal of the Marine Biological Association of the United Kingdom</i>, vol. 91, no. 2. Cambridge University Press, pp. 485–492, 2011.","ama":"Palero F, Guerao G, Clark P, Abello P. Scyllarus arctus (Crustacea: Decapoda: Scyllaridae) final stage phyllosoma identified by DNA analysis, with morphological description. <i>Journal of the Marine Biological Association of the United Kingdom</i>. 2011;91(2):485-492. doi:<a href=\"https://doi.org/10.1017/S0025315410000287\">10.1017/S0025315410000287</a>","chicago":"Palero, Ferran, Guillermo Guerao, Paul Clark, and Pere Abello. “Scyllarus Arctus (Crustacea: Decapoda: Scyllaridae) Final Stage Phyllosoma Identified by DNA Analysis, with Morphological Description.” <i>Journal of the Marine Biological Association of the United Kingdom</i>. Cambridge University Press, 2011. <a href=\"https://doi.org/10.1017/S0025315410000287\">https://doi.org/10.1017/S0025315410000287</a>.","ista":"Palero F, Guerao G, Clark P, Abello P. 2011. Scyllarus arctus (Crustacea: Decapoda: Scyllaridae) final stage phyllosoma identified by DNA analysis, with morphological description. Journal of the Marine Biological Association of the United Kingdom. 91(2), 485–492.","apa":"Palero, F., Guerao, G., Clark, P., &#38; Abello, P. (2011). Scyllarus arctus (Crustacea: Decapoda: Scyllaridae) final stage phyllosoma identified by DNA analysis, with morphological description. <i>Journal of the Marine Biological Association of the United Kingdom</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/S0025315410000287\">https://doi.org/10.1017/S0025315410000287</a>","short":"F. Palero, G. Guerao, P. Clark, P. Abello, Journal of the Marine Biological Association of the United Kingdom 91 (2011) 485–492.","mla":"Palero, Ferran, et al. “Scyllarus Arctus (Crustacea: Decapoda: Scyllaridae) Final Stage Phyllosoma Identified by DNA Analysis, with Morphological Description.” <i>Journal of the Marine Biological Association of the United Kingdom</i>, vol. 91, no. 2, Cambridge University Press, 2011, pp. 485–92, doi:<a href=\"https://doi.org/10.1017/S0025315410000287\">10.1017/S0025315410000287</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"Advanced stages of Scyllarus phyllosoma larvae were collected by demersal trawling during fishery research surveys in the western Mediterranean Sea in 2003–2005. Nucleotide sequence analysis of the mitochondrial 16S rDNA gene allowed the final-stage phyllosoma of Scyllarus arctus to be identified among these larvae. Its morphology is described and illustrated. This constitutes the second complete description of a Scyllaridae phyllosoma with its specific identity being validated by molecular techniques (the first was S. pygmaeus). These results also solved a long lasting taxonomic anomaly of several species assigned to the ancient genus Phyllosoma Leach, 1814. Detailed examination indicated that the final-stage phyllosoma of S. arctus shows closer affinities with the American scyllarid Scyllarus depressus or with the Australian Scyllarus sp. b (sensu Phillips et al., 1981) than to its sympatric species S. pygmaeus.","lang":"eng"}],"publication_status":"published","date_published":"2011-03-01T00:00:00Z","publisher":"Cambridge University Press","title":"Scyllarus arctus (Crustacea: Decapoda: Scyllaridae) final stage phyllosoma identified by DNA analysis, with morphological description","oa":1,"page":"485 - 492","day":"01","year":"2011","doi":"10.1017/S0025315410000287","scopus_import":1,"intvolume":"        91","publist_id":"2443","publication":"Journal of the Marine Biological Association of the United Kingdom","quality_controlled":"1","oa_version":"Published Version","author":[{"full_name":"Palero, Ferran","id":"3F0E2A22-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0343-8329","last_name":"Palero","first_name":"Ferran"},{"full_name":"Guerao, Guillermo","last_name":"Guerao","first_name":"Guillermo"},{"full_name":"Clark, Paul","last_name":"Clark","first_name":"Paul"},{"first_name":"Pere","last_name":"Abello","full_name":"Abello, Pere"}],"month":"03","issue":"2","language":[{"iso":"eng"}],"article_processing_charge":"No","volume":91,"date_created":"2018-12-11T12:05:09Z","type":"journal_article","_id":"3784","article_type":"original","status":"public","main_file_link":[{"open_access":"1","url":"https://digital.csic.es/bitstream/10261/32783/3/Palero_et_al_2011.pdf"}]},{"oa_version":"None","citation":{"apa":"Krens, G., &#38; Heisenberg, C.-P. J. (2011). Cell sorting in development. In M. Labouesse (Ed.), <i>Forces and Tension in Development</i> (Vol. 95, pp. 189–213). Elsevier. <a href=\"https://doi.org/10.1016/B978-0-12-385065-2.00006-2\">https://doi.org/10.1016/B978-0-12-385065-2.00006-2</a>","ama":"Krens G, Heisenberg C-PJ. Cell sorting in development. In: Labouesse M, ed. <i>Forces and Tension in Development</i>. Vol 95. Elsevier; 2011:189-213. doi:<a href=\"https://doi.org/10.1016/B978-0-12-385065-2.00006-2\">10.1016/B978-0-12-385065-2.00006-2</a>","chicago":"Krens, Gabriel, and Carl-Philipp J Heisenberg. “Cell Sorting in Development.” In <i>Forces and Tension in Development</i>, edited by Michel Labouesse, 95:189–213. Elsevier, 2011. <a href=\"https://doi.org/10.1016/B978-0-12-385065-2.00006-2\">https://doi.org/10.1016/B978-0-12-385065-2.00006-2</a>.","ista":"Krens G, Heisenberg C-PJ. 2011.Cell sorting in development. In: Forces and Tension in Development. Current Topics in Developmental Biology, vol. 95, 189–213.","ieee":"G. Krens and C.-P. J. Heisenberg, “Cell sorting in development,” in <i>Forces and Tension in Development</i>, vol. 95, M. Labouesse, Ed. Elsevier, 2011, pp. 189–213.","mla":"Krens, Gabriel, and Carl-Philipp J. Heisenberg. “Cell Sorting in Development.” <i>Forces and Tension in Development</i>, edited by Michel Labouesse, vol. 95, Elsevier, 2011, pp. 189–213, doi:<a href=\"https://doi.org/10.1016/B978-0-12-385065-2.00006-2\">10.1016/B978-0-12-385065-2.00006-2</a>.","short":"G. Krens, C.-P.J. Heisenberg, in:, M. Labouesse (Ed.), Forces and Tension in Development, Elsevier, 2011, pp. 189–213."},"department":[{"_id":"CaHe"}],"quality_controlled":"1","date_updated":"2021-01-12T07:52:13Z","alternative_title":["Current Topics in Developmental Biology"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2B819732-F248-11E8-B48F-1D18A9856A87","full_name":"Krens, Gabriel","last_name":"Krens","first_name":"Gabriel","orcid":"0000-0003-4761-5996"},{"full_name":"Heisenberg, Carl-Philipp J","id":"39427864-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-0912-4566","first_name":"Carl-Philipp J","last_name":"Heisenberg"}],"month":"01","publication_status":"published","abstract":[{"lang":"eng","text":"During the development of multicellular organisms, cell fate specification is followed by the sorting of different cell types into distinct domains from where the different tissues and organs are formed. Cell sorting involves both the segregation of a mixed population of cells with different fates and properties into distinct domains, and the active maintenance of their segregated state. Because of its biological importance and apparent resemblance to fluid segregation in physics, cell sorting was extensively studied by both biologists and physicists over the last decades. Different theories were developed that try to explain cell sorting on the basis of the physical properties of the constituent cells. However, only recently the molecular and cellular mechanisms that control the physical properties driving cell sorting, have begun to be unraveled. In this review, we will provide an overview of different cell-sorting processes in development and discuss how these processes can be explained by the different sorting theories, and how these theories in turn can be connected to the molecular and cellular mechanisms driving these processes."}],"title":"Cell sorting in development","volume":95,"article_processing_charge":"No","publisher":"Elsevier","date_published":"2011-01-01T00:00:00Z","language":[{"iso":"eng"}],"type":"book_chapter","_id":"3791","date_created":"2018-12-11T12:05:11Z","status":"public","day":"01","year":"2011","doi":"10.1016/B978-0-12-385065-2.00006-2","page":"189 - 213","editor":[{"first_name":"Michel","last_name":"Labouesse","full_name":"Labouesse, Michel"}],"scopus_import":"1","publication":"Forces and Tension in Development","publist_id":"2436","intvolume":"        95"},{"volume":6570,"language":[{"iso":"eng"}],"file":[{"file_name":"IST-2016-539-v1+1_2011-B-01-CoveringPacking.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:07:42Z","date_updated":"2020-07-14T12:46:16Z","checksum":"aaf22b4d7bd4277ffe8db532119cf474","file_id":"4640","creator":"system","access_level":"open_access","file_size":436875,"relation":"main_file"}],"has_accepted_license":"1","month":"05","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Kerber, Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299","first_name":"Michael","last_name":"Kerber"}],"oa_version":"Submitted Version","quality_controlled":"1","pubrep_id":"539","status":"public","_id":"3796","type":"book_chapter","date_created":"2018-12-11T12:05:13Z","title":"Covering and packing with spheres by diagonal distortion in R^n","date_published":"2011-05-03T00:00:00Z","file_date_updated":"2020-07-14T12:46:16Z","publisher":"Springer","ddc":["000"],"series_title":"Dedicated to Hermann Maurer on the Occasion of His 70th Birthday","publication_status":"published","abstract":[{"lang":"eng","text":"We address the problem of covering ℝ n with congruent balls, while minimizing the number of balls that contain an average point. Considering the 1-parameter family of lattices defined by stretching or compressing the integer grid in diagonal direction, we give a closed formula for the covering density that depends on the distortion parameter. We observe that our family contains the thinnest lattice coverings in dimensions 2 to 5. We also consider the problem of packing congruent balls in ℝ n , for which we give a closed formula for the packing density as well. Again we observe that our family contains optimal configurations, this time densest packings in dimensions 2 and 3."}],"alternative_title":["LNCS"],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","citation":{"short":"H. Edelsbrunner, M. Kerber, in:, C. Calude, G. Rozenberg, A. Salomaa (Eds.), Rainbow of Computer Science, Springer, 2011, pp. 20–35.","mla":"Edelsbrunner, Herbert, and Michael Kerber. “Covering and Packing with Spheres by Diagonal Distortion in R^n.” <i>Rainbow of Computer Science</i>, edited by Cristian Calude et al., vol. 6570, Springer, 2011, pp. 20–35, doi:<a href=\"https://doi.org/10.1007/978-3-642-19391-0_2\">10.1007/978-3-642-19391-0_2</a>.","ieee":"H. Edelsbrunner and M. Kerber, “Covering and packing with spheres by diagonal distortion in R^n,” in <i>Rainbow of Computer Science</i>, vol. 6570, C. Calude, G. Rozenberg, and A. Salomaa, Eds. Springer, 2011, pp. 20–35.","ama":"Edelsbrunner H, Kerber M. Covering and packing with spheres by diagonal distortion in R^n. In: Calude C, Rozenberg G, Salomaa A, eds. <i>Rainbow of Computer Science</i>. Vol 6570. Dedicated to Hermann Maurer on the Occasion of His 70th Birthday. Springer; 2011:20-35. doi:<a href=\"https://doi.org/10.1007/978-3-642-19391-0_2\">10.1007/978-3-642-19391-0_2</a>","ista":"Edelsbrunner H, Kerber M. 2011.Covering and packing with spheres by diagonal distortion in R^n. In: Rainbow of Computer Science. LNCS, vol. 6570, 20–35.","chicago":"Edelsbrunner, Herbert, and Michael Kerber. “Covering and Packing with Spheres by Diagonal Distortion in R^n.” In <i>Rainbow of Computer Science</i>, edited by Cristian Calude, Grzegorz Rozenberg, and Arto Salomaa, 6570:20–35. Dedicated to Hermann Maurer on the Occasion of His 70th Birthday. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-19391-0_2\">https://doi.org/10.1007/978-3-642-19391-0_2</a>.","apa":"Edelsbrunner, H., &#38; Kerber, M. (2011). Covering and packing with spheres by diagonal distortion in R^n. In C. Calude, G. Rozenberg, &#38; A. Salomaa (Eds.), <i>Rainbow of Computer Science</i> (Vol. 6570, pp. 20–35). Springer. <a href=\"https://doi.org/10.1007/978-3-642-19391-0_2\">https://doi.org/10.1007/978-3-642-19391-0_2</a>"},"department":[{"_id":"HeEd"}],"date_updated":"2021-01-12T07:52:15Z","publication":"Rainbow of Computer Science","publist_id":"2427","intvolume":"      6570","editor":[{"full_name":"Calude, Cristian","first_name":"Cristian","last_name":"Calude"},{"full_name":"Rozenberg, Grzegorz","first_name":"Grzegorz","last_name":"Rozenberg"},{"full_name":"Salomaa, Arto","first_name":"Arto","last_name":"Salomaa"}],"day":"03","year":"2011","page":"20 - 35","doi":"10.1007/978-3-642-19391-0_2","oa":1},{"author":[{"full_name":"Wang, Bei","first_name":"Bei","last_name":"Wang"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"last_name":"Morozov","first_name":"Dmitriy","full_name":"Morozov, Dmitriy"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","department":[{"_id":"HeEd"}],"date_updated":"2021-01-12T07:53:31Z","citation":{"ieee":"B. Wang, H. Edelsbrunner, and D. Morozov, “Computing elevation maxima by searching the Gauss sphere,” <i>Journal of Experimental Algorithmics</i>, vol. 16, no. 2.2. ACM, pp. 1–13, 2011.","apa":"Wang, B., Edelsbrunner, H., &#38; Morozov, D. (2011). Computing elevation maxima by searching the Gauss sphere. <i>Journal of Experimental Algorithmics</i>. ACM. <a href=\"https://doi.org/10.1145/1963190.1970375\">https://doi.org/10.1145/1963190.1970375</a>","chicago":"Wang, Bei, Herbert Edelsbrunner, and Dmitriy Morozov. “Computing Elevation Maxima by Searching the Gauss Sphere.” <i>Journal of Experimental Algorithmics</i>. ACM, 2011. <a href=\"https://doi.org/10.1145/1963190.1970375\">https://doi.org/10.1145/1963190.1970375</a>.","ama":"Wang B, Edelsbrunner H, Morozov D. Computing elevation maxima by searching the Gauss sphere. <i>Journal of Experimental Algorithmics</i>. 2011;16(2.2):1-13. doi:<a href=\"https://doi.org/10.1145/1963190.1970375\">10.1145/1963190.1970375</a>","ista":"Wang B, Edelsbrunner H, Morozov D. 2011. Computing elevation maxima by searching the Gauss sphere. Journal of Experimental Algorithmics. 16(2.2), 1–13.","short":"B. Wang, H. Edelsbrunner, D. Morozov, Journal of Experimental Algorithmics 16 (2011) 1–13.","mla":"Wang, Bei, et al. “Computing Elevation Maxima by Searching the Gauss Sphere.” <i>Journal of Experimental Algorithmics</i>, vol. 16, no. 2.2, ACM, 2011, pp. 1–13, doi:<a href=\"https://doi.org/10.1145/1963190.1970375\">10.1145/1963190.1970375</a>."},"oa_version":"None","language":[{"iso":"eng"}],"date_published":"2011-05-01T00:00:00Z","publisher":"ACM","title":"Computing elevation maxima by searching the Gauss sphere","volume":16,"publication_status":"published","month":"05","abstract":[{"lang":"eng","text":"The elevation function on a smoothly embedded 2-manifold in R-3 reflects the multiscale topography of cavities and protrusions as local maxima. The function has been useful in identifying coarse docking configurations for protein pairs. Transporting the concept from the smooth to the piecewise linear category, this paper describes an algorithm for finding all local maxima. While its worst-case running time is the same as of the algorithm used in prior work, its performance in practice is orders of magnitudes superior. We cast light on this improvement by relating the running time to the total absolute Gaussian curvature of the 2-manifold."}],"issue":"2.2","page":"1 - 13","status":"public","doi":"10.1145/1963190.1970375","year":"2011","day":"01","date_created":"2018-12-11T12:06:09Z","type":"journal_article","_id":"3965","publist_id":"2161","intvolume":"        16","publication":"Journal of Experimental Algorithmics","scopus_import":1},{"issue":"4","month":"12","volume":186,"language":[{"iso":"eng"}],"oa_version":"Submitted Version","quality_controlled":"1","project":[{"name":"Limits to selection in biology and in evolutionary computation","grant_number":"250152","_id":"25B07788-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"author":[{"first_name":"Daniel","last_name":"Weissman","id":"2D0CE020-F248-11E8-B48F-1D18A9856A87","full_name":"Weissman, Daniel"},{"last_name":"Feldman","first_name":"Marcus","full_name":"Feldman, Marcus"},{"first_name":"Daniel","last_name":"Fisher","full_name":"Fisher, Daniel"}],"ec_funded":1,"_id":"3303","type":"journal_article","date_created":"2018-12-11T12:02:33Z","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2998319/"}],"status":"public","publication_status":"published","abstract":[{"lang":"eng","text":"Biological traits result in part from interactions between different genetic loci. This can lead to sign epistasis, in which a beneficial adaptation involves a combination of individually deleterious or neutral mutations; in this case, a population must cross a “fitness valley” to adapt. Recombination can assist this process by combining mutations from different individuals or retard it by breaking up the adaptive combination. Here, we analyze the simplest fitness valley, in which an adaptation requires one mutation at each of two loci to provide a fitness benefit. We present a theoretical analysis of the effect of recombination on the valley-crossing process across the full spectrum of possible parameter regimes. We find that low recombination rates can speed up valley crossing relative to the asexual case, while higher recombination rates slow down valley crossing, with the transition between the two regimes occurring when the recombination rate between the loci is approximately equal to the selective advantage provided by the adaptation. In large populations, if the recombination rate is high and selection against single mutants is substantial, the time to cross the valley grows exponentially with population size, effectively meaning that the population cannot acquire the adaptation. Recombination at the optimal (low) rate can reduce the valley-crossing time by up to several orders of magnitude relative to that in an asexual population. "}],"title":"The rate of fitness-valley crossing in sexual populations","date_published":"2010-12-01T00:00:00Z","publisher":"Genetics Society of America","citation":{"ieee":"D. Weissman, M. Feldman, and D. Fisher, “The rate of fitness-valley crossing in sexual populations,” <i>Genetics</i>, vol. 186, no. 4. Genetics Society of America, pp. 1389–1410, 2010.","ama":"Weissman D, Feldman M, Fisher D. The rate of fitness-valley crossing in sexual populations. <i>Genetics</i>. 2010;186(4):1389-1410. doi:<a href=\"https://doi.org/10.1534/genetics.110.123240\">10.1534/genetics.110.123240</a>","ista":"Weissman D, Feldman M, Fisher D. 2010. The rate of fitness-valley crossing in sexual populations. Genetics. 186(4), 1389–1410.","chicago":"Weissman, Daniel, Marcus Feldman, and Daniel Fisher. “The Rate of Fitness-Valley Crossing in Sexual Populations.” <i>Genetics</i>. Genetics Society of America, 2010. <a href=\"https://doi.org/10.1534/genetics.110.123240\">https://doi.org/10.1534/genetics.110.123240</a>.","apa":"Weissman, D., Feldman, M., &#38; Fisher, D. (2010). The rate of fitness-valley crossing in sexual populations. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1534/genetics.110.123240\">https://doi.org/10.1534/genetics.110.123240</a>","mla":"Weissman, Daniel, et al. “The Rate of Fitness-Valley Crossing in Sexual Populations.” <i>Genetics</i>, vol. 186, no. 4, Genetics Society of America, 2010, pp. 1389–410, doi:<a href=\"https://doi.org/10.1534/genetics.110.123240\">10.1534/genetics.110.123240</a>.","short":"D. Weissman, M. Feldman, D. Fisher, Genetics 186 (2010) 1389–1410."},"department":[{"_id":"NiBa"}],"date_updated":"2021-01-12T07:42:31Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"publication":"Genetics","publist_id":"3337","intvolume":"       186","oa":1,"year":"2010","page":"1389 - 1410","doi":"10.1534/genetics.110.123240","day":"01","acknowledgement":"This work was supported in part by a Robert N. Noyce Stanford Graduate Fellowship and European Research Council grant 250152 (to D.B.W.) and by National Institutes of Health grant GM 28016 (to M.W.F.).\r\nWe thank Michael Desai for many ideas and discussions and are grateful to Joanna Masel and an anonymous reviewer for their helpful suggestions. "},{"editor":[{"full_name":"Clarke, Edmund M","first_name":"Edmund M","last_name":"Clarke"},{"last_name":"Voronkov","first_name":"Andrei","full_name":"Voronkov, Andrei"}],"scopus_import":"1","publication":"Logic for Programming, Artificial Intelligence, and Reasoning","intvolume":"      6355","oa":1,"page":"103-118","doi":"10.1007/978-3-642-17511-4_7","day":"01","year":"2010","acknowledgement":"This work was supported in part by the Swiss NSF. The fourth author is supported by an FWF Hertha Firnberg Research grant (T425-N23).","series_title":"LNCS","abstract":[{"text":"We present ABC, a software tool for automatically computing symbolic upper bounds on the number of iterations of nested program loops. The system combines static analysis of programs with symbolic summation techniques to derive loop invariant relations between program variables. Iteration bounds are obtained from the inferred invariants, by replacing variables with bounds on their greatest values. We have successfully applied ABC to a large number of examples. The derived symbolic bounds express non-trivial polynomial relations over loop variables. We also report on results to automatically infer symbolic expressions over harmonic numbers as upper bounds on loop iteration counts.","lang":"eng"}],"publication_status":"published","title":"ABC: Algebraic Bound Computation for loops","date_published":"2010-05-01T00:00:00Z","publisher":"Springer Nature","citation":{"mla":"Blanc, Régis, et al. “ABC: Algebraic Bound Computation for Loops.” <i>Logic for Programming, Artificial Intelligence, and Reasoning</i>, edited by Edmund M Clarke and Andrei Voronkov, vol. 6355, Springer Nature, 2010, pp. 103–18, doi:<a href=\"https://doi.org/10.1007/978-3-642-17511-4_7\">10.1007/978-3-642-17511-4_7</a>.","short":"R. Blanc, T.A. Henzinger, T. Hottelier, L. Kovács, in:, E.M. Clarke, A. Voronkov (Eds.), Logic for Programming, Artificial Intelligence, and Reasoning, Springer Nature, Berlin, Heidelberg, 2010, pp. 103–118.","ieee":"R. Blanc, T. A. Henzinger, T. Hottelier, and L. Kovács, “ABC: Algebraic Bound Computation for loops,” in <i>Logic for Programming, Artificial Intelligence, and Reasoning</i>, Dakar, Senegal, 2010, vol. 6355, pp. 103–118.","apa":"Blanc, R., Henzinger, T. A., Hottelier, T., &#38; Kovács, L. (2010). ABC: Algebraic Bound Computation for loops. In E. M. Clarke &#38; A. Voronkov (Eds.), <i>Logic for Programming, Artificial Intelligence, and Reasoning</i> (Vol. 6355, pp. 103–118). Berlin, Heidelberg: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-17511-4_7\">https://doi.org/10.1007/978-3-642-17511-4_7</a>","ama":"Blanc R, Henzinger TA, Hottelier T, Kovács L. ABC: Algebraic Bound Computation for loops. In: Clarke EM, Voronkov A, eds. <i>Logic for Programming, Artificial Intelligence, and Reasoning</i>. Vol 6355. LNCS. Berlin, Heidelberg: Springer Nature; 2010:103-118. doi:<a href=\"https://doi.org/10.1007/978-3-642-17511-4_7\">10.1007/978-3-642-17511-4_7</a>","ista":"Blanc R, Henzinger TA, Hottelier T, Kovács L. 2010. ABC: Algebraic Bound Computation for loops. Logic for Programming, Artificial Intelligence, and Reasoning. LPAR: Conference on Logic for Programming, Artificial Intelligence and ReasoningLNCS vol. 6355, 103–118.","chicago":"Blanc, Régis, Thomas A Henzinger, Thibaud Hottelier, and Laura Kovács. “ABC: Algebraic Bound Computation for Loops.” In <i>Logic for Programming, Artificial Intelligence, and Reasoning</i>, edited by Edmund M Clarke and Andrei Voronkov, 6355:103–18. LNCS. Berlin, Heidelberg: Springer Nature, 2010. <a href=\"https://doi.org/10.1007/978-3-642-17511-4_7\">https://doi.org/10.1007/978-3-642-17511-4_7</a>."},"date_updated":"2022-06-13T07:44:21Z","department":[{"_id":"ToHe"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Dakar, Senegal","name":"LPAR: Conference on Logic for Programming, Artificial Intelligence and Reasoning","end_date":"2010-05-01","start_date":"2010-04-25"},"_id":"10908","type":"conference","date_created":"2022-03-21T08:14:35Z","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783642175114"],"isbn":["9783642175107"]},"status":"public","main_file_link":[{"url":"https://infoscience.epfl.ch/record/186096","open_access":"1"}],"month":"05","article_processing_charge":"No","volume":6355,"language":[{"iso":"eng"}],"oa_version":"Submitted Version","quality_controlled":"1","place":"Berlin, Heidelberg","author":[{"full_name":"Blanc, Régis","last_name":"Blanc","first_name":"Régis"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000-0002-2985-7724"},{"full_name":"Hottelier, Thibaud","last_name":"Hottelier","first_name":"Thibaud"},{"full_name":"Kovács, Laura","last_name":"Kovács","first_name":"Laura"}]},{"date_created":"2022-03-21T08:24:07Z","_id":"10909","type":"conference","acknowledgement":"Partially supported by the Austrian Science Fund under grantFSP-S9103-N04 and P20134-N13.","day":"01","year":"2010","publication_identifier":{"eisbn":["9781611973075"]},"status":"public","page":"1594-1604","doi":"10.1137/1.9781611973075.129","related_material":{"record":[{"id":"3267","relation":"later_version","status":"public"}]},"scopus_import":"1","conference":{"end_date":"2010-01-19","start_date":"2010-01-17","name":"SODA: Symposium on Discrete Algorithms","location":"Austin, TX, United States"},"publication":"Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms","date_updated":"2023-02-23T11:19:46Z","department":[{"_id":"HeEd"}],"quality_controlled":"1","oa_version":"None","citation":{"short":"C. Chen, D. Freedman, in:, Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2010, pp. 1594–1604.","mla":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2010, pp. 1594–604, doi:<a href=\"https://doi.org/10.1137/1.9781611973075.129\">10.1137/1.9781611973075.129</a>.","ieee":"C. Chen and D. Freedman, “Hardness results for homology localization,” in <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Austin, TX, United States, 2010, pp. 1594–1604.","apa":"Chen, C., &#38; Freedman, D. (2010). Hardness results for homology localization. In <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1594–1604). Austin, TX, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611973075.129\">https://doi.org/10.1137/1.9781611973075.129</a>","ista":"Chen C, Freedman D. 2010. Hardness results for homology localization. Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1594–1604.","ama":"Chen C, Freedman D. Hardness results for homology localization. In: <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2010:1594-1604. doi:<a href=\"https://doi.org/10.1137/1.9781611973075.129\">10.1137/1.9781611973075.129</a>","chicago":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” In <i>Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1594–1604. Society for Industrial and Applied Mathematics, 2010. <a href=\"https://doi.org/10.1137/1.9781611973075.129\">https://doi.org/10.1137/1.9781611973075.129</a>."},"author":[{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","full_name":"Chen, Chao","last_name":"Chen","first_name":"Chao"},{"full_name":"Freedman, Daniel","last_name":"Freedman","first_name":"Daniel"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We focus on the volume measure, that is, the 1-norm of a cycle. Two main results are presented. First, we prove the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). A side effect is the inapproximability of the problem of computing the nonbounding cycle with the smallest volume, and computing cycles representing a homology basis with the minimal total volume. We also discuss other geometric measures (diameter and radius) and show their disadvantages in homology localization. Our work is restricted to homology over the ℤ2 field."}],"month":"02","publication_status":"published","language":[{"iso":"eng"}],"date_published":"2010-02-01T00:00:00Z","publisher":"Society for Industrial and Applied Mathematics","article_processing_charge":"No","title":"Hardness results for homology localization"},{"ddc":["576"],"abstract":[{"text":"Background: The availability of many gene alignments with overlapping taxon sets raises the question of which strategy is the best to infer species phylogenies from multiple gene information. Methods and programs abound that use the gene alignment in different ways to reconstruct the species tree. In particular, different methods combine the original data at different points along the way from the underlying sequences to the final tree. Accordingly, they are classified into superalignment, supertree and medium-level approaches. Here, we present a simulation study to compare different methods from each of these three approaches.\r\n\r\nResults: We observe that superalignment methods usually outperform the other approaches over a wide range of parameters including sparse data and gene-specific evolutionary parameters. In the presence of high incongruency among gene trees, however, other combination methods show better performance than the superalignment approach. Surprisingly, some supertree and medium-level methods exhibit, on average, worse results than a single gene phylogeny with complete taxon information.\r\n\r\nConclusions: For some methods, using the reconstructed gene tree as an estimation of the species tree is superior to the combination of incomplete information. Superalignment usually performs best since it is less susceptible to stochastic error. Supertree methods can outperform superalignment in the presence of gene-tree conflict.","lang":"eng"}],"publication_status":"published","title":"Accuracy of phylogeny reconstruction methods combining overlapping gene data sets ","date_published":"2010-12-06T00:00:00Z","publisher":"BioMed Central","file_date_updated":"2020-07-14T12:45:40Z","citation":{"mla":"Kupczok, Anne, et al. “Accuracy of Phylogeny Reconstruction Methods Combining Overlapping Gene Data Sets .” <i>Algorithms for Molecular Biology</i>, vol. 5, no. 1, 37, BioMed Central, 2010, doi:<a href=\"https://doi.org/10.1186/1748-7188-5-37\">10.1186/1748-7188-5-37</a>.","short":"A. Kupczok, H. Schmidt, A. Von Haeseler, Algorithms for Molecular Biology 5 (2010).","apa":"Kupczok, A., Schmidt, H., &#38; Von Haeseler, A. (2010). Accuracy of phylogeny reconstruction methods combining overlapping gene data sets . <i>Algorithms for Molecular Biology</i>. BioMed Central. <a href=\"https://doi.org/10.1186/1748-7188-5-37\">https://doi.org/10.1186/1748-7188-5-37</a>","ama":"Kupczok A, Schmidt H, Von Haeseler A. Accuracy of phylogeny reconstruction methods combining overlapping gene data sets . <i>Algorithms for Molecular Biology</i>. 2010;5(1). doi:<a href=\"https://doi.org/10.1186/1748-7188-5-37\">10.1186/1748-7188-5-37</a>","ista":"Kupczok A, Schmidt H, Von Haeseler A. 2010. Accuracy of phylogeny reconstruction methods combining overlapping gene data sets . Algorithms for Molecular Biology. 5(1), 37.","chicago":"Kupczok, Anne, Heiko Schmidt, and Arndt Von Haeseler. “Accuracy of Phylogeny Reconstruction Methods Combining Overlapping Gene Data Sets .” <i>Algorithms for Molecular Biology</i>. BioMed Central, 2010. <a href=\"https://doi.org/10.1186/1748-7188-5-37\">https://doi.org/10.1186/1748-7188-5-37</a>.","ieee":"A. Kupczok, H. Schmidt, and A. Von Haeseler, “Accuracy of phylogeny reconstruction methods combining overlapping gene data sets ,” <i>Algorithms for Molecular Biology</i>, vol. 5, no. 1. BioMed Central, 2010."},"date_updated":"2021-01-12T06:57:18Z","department":[{"_id":"JoBo"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"publication":"Algorithms for Molecular Biology","intvolume":"         5","publist_id":"4517","oa":1,"doi":"10.1186/1748-7188-5-37","day":"06","year":"2010","acknowledgement":"Financial support from the Wiener Wissenschafts-, Forschungs- and Technologiefonds (WWTF) is greatly appreciated. A.v.H. acknowledges support from the German Research Foundation (DFG, SPP-1174).","issue":"1","file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:45:40Z","date_created":"2018-12-12T10:09:16Z","file_name":"IST-2018-939-v1+1_2010_Kupczok_Accuracy_of.pdf","relation":"main_file","creator":"system","checksum":"e2497285388bc4da629bafb46662eb43","file_id":"4739","file_size":723929,"access_level":"open_access"}],"article_number":"37","month":"12","has_accepted_license":"1","volume":5,"language":[{"iso":"eng"}],"oa_version":"Published Version","quality_controlled":"1","author":[{"last_name":"Kupczok","first_name":"Anne","id":"2BB22BC2-F248-11E8-B48F-1D18A9856A87","full_name":"Kupczok, Anne"},{"last_name":"Schmidt","first_name":"Heiko","full_name":"Schmidt, Heiko"},{"full_name":"Von Haeseler, Arndt","last_name":"Von Haeseler","first_name":"Arndt"}],"pubrep_id":"939","type":"journal_article","_id":"2409","date_created":"2018-12-11T11:57:30Z","status":"public"},{"abstract":[{"text":"Classical models of gene flow fail in three ways: they cannot explain large-scale patterns; they predict much more genetic diversity than is observed; and they assume that loosely linked genetic loci evolve independently. We propose a new model that deals with these problems. Extinction events kill some fraction of individuals in a region. These are replaced by offspring from a small number of parents, drawn from the preexisting population. This model of evolution forwards in time corresponds to a backwards model, in which ancestral lineages jump to a new location if they are hit by an event, and may coalesce with other lineages that are hit by the same event. We derive an expression for the identity in allelic state, and show that, over scales much larger than the largest event, this converges to the classical value derived by Wright and Malécot. However, rare events that cover large areas cause low genetic diversity, large-scale patterns, and correlations in ancestry between unlinked loci.","lang":"eng"}],"month":"09","publication_status":"published","issue":"9","publisher":"Wiley-Blackwell","language":[{"iso":"eng"}],"date_published":"2010-09-01T00:00:00Z","title":"A new model for extinction and recolonization in two dimensions: Quantifying phylogeography","volume":64,"date_updated":"2021-01-12T08:00:52Z","department":[{"_id":"NiBa"}],"quality_controlled":"1","oa_version":"None","citation":{"short":"N.H. Barton, J. Kelleher, A. Etheridge, Evolution 64 (2010) 2701–2715.","mla":"Barton, Nicholas H., et al. “A New Model for Extinction and Recolonization in Two Dimensions: Quantifying Phylogeography.” <i>Evolution</i>, vol. 64, no. 9, Wiley-Blackwell, 2010, pp. 2701–15, doi:<a href=\"https://doi.org/10.1111/j.1558-5646.2010.01019.x\">10.1111/j.1558-5646.2010.01019.x</a>.","ieee":"N. H. Barton, J. Kelleher, and A. Etheridge, “A new model for extinction and recolonization in two dimensions: Quantifying phylogeography,” <i>Evolution</i>, vol. 64, no. 9. Wiley-Blackwell, pp. 2701–2715, 2010.","apa":"Barton, N. H., Kelleher, J., &#38; Etheridge, A. (2010). A new model for extinction and recolonization in two dimensions: Quantifying phylogeography. <i>Evolution</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/j.1558-5646.2010.01019.x\">https://doi.org/10.1111/j.1558-5646.2010.01019.x</a>","ama":"Barton NH, Kelleher J, Etheridge A. A new model for extinction and recolonization in two dimensions: Quantifying phylogeography. <i>Evolution</i>. 2010;64(9):2701-2715. doi:<a href=\"https://doi.org/10.1111/j.1558-5646.2010.01019.x\">10.1111/j.1558-5646.2010.01019.x</a>","ista":"Barton NH, Kelleher J, Etheridge A. 2010. A new model for extinction and recolonization in two dimensions: Quantifying phylogeography. Evolution. 64(9), 2701–2715.","chicago":"Barton, Nicholas H, Jerome Kelleher, and Alison Etheridge. “A New Model for Extinction and Recolonization in Two Dimensions: Quantifying Phylogeography.” <i>Evolution</i>. Wiley-Blackwell, 2010. <a href=\"https://doi.org/10.1111/j.1558-5646.2010.01019.x\">https://doi.org/10.1111/j.1558-5646.2010.01019.x</a>."},"author":[{"full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8548-5240","last_name":"Barton","first_name":"Nicholas H"},{"full_name":"Kelleher, Jerome","first_name":"Jerome","last_name":"Kelleher"},{"full_name":"Etheridge, Alison","last_name":"Etheridge","first_name":"Alison"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"intvolume":"        64","publist_id":"2780","publication":"Evolution","date_created":"2018-12-11T11:46:40Z","_id":"474","type":"journal_article","acknowledgement":"This work has made use of the resources provided by the Edinburgh Compute and Data Facility (ECDF). The ECDF is partially supported by the eDIKT initiative. NHB is supported in part by EPSRC Grant EP/E066070/1; JK is supported by EPSRC Grant EP/E066070/1; and AME is supported in part by EPSRC Grant EP/E065945/1.","status":"public","doi":"10.1111/j.1558-5646.2010.01019.x","day":"01","year":"2010","page":"2701 - 2715"},{"publist_id":"7331","intvolume":"         8","scopus_import":1,"page":"1 - 12","year":"2010","day":"01","doi":"10.4230/LIPIcs.FSTTCS.2010.1","oa":1,"file_date_updated":"2020-07-14T12:46:35Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2010-01-01T00:00:00Z","title":"Expressiveness of streaming string transducers","publication_status":"published","abstract":[{"text":"Streaming string transducers [1] define (partial) functions from input strings to output strings. A streaming string transducer makes a single pass through the input string and uses a finite set of variables that range over strings from the output alphabet. At every step, the transducer processes an input symbol, and updates all the variables in parallel using assignments whose right-hand-sides are concatenations of output symbols and variables with the restriction that a variable can be used at most once in a right-hand-side expression. It has been shown that streaming string transducers operating on strings over infinite data domains are of interest in algorithmic verification of list-processing programs, as they lead to PSPACE decision procedures for checking pre/post conditions and for checking semantic equivalence, for a well-defined class of heap-manipulating programs. In order to understand the theoretical expressiveness of streaming transducers, we focus on streaming transducers processing strings over finite alphabets, given the existence of a robust and well-studied class of &quot;regular&quot; transductions for this case. Such regular transductions can be defined either by two-way deterministic finite-state transducers, or using a logical MSO-based characterization. Our main result is that the expressiveness of streaming string transducers coincides exactly with this class of regular transductions. ","lang":"eng"}],"ddc":["005"],"alternative_title":["LIPIcs"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)"},"department":[{"_id":"ToHe"}],"date_updated":"2021-01-12T08:01:00Z","citation":{"mla":"Alur, Rajeev, and Pavol Cerny. <i>Expressiveness of Streaming String Transducers</i>. Vol. 8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 1–12, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1\">10.4230/LIPIcs.FSTTCS.2010.1</a>.","short":"R. Alur, P. Cerny, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 1–12.","ieee":"R. Alur and P. Cerny, “Expressiveness of streaming string transducers,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Chennai, India, 2010, vol. 8, pp. 1–12.","chicago":"Alur, Rajeev, and Pavol Cerny. “Expressiveness of Streaming String Transducers,” 8:1–12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1\">https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1</a>.","ista":"Alur R, Cerny P. 2010. Expressiveness of streaming string transducers. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 8, 1–12.","ama":"Alur R, Cerny P. Expressiveness of streaming string transducers. In: Vol 8. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2010:1-12. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1\">10.4230/LIPIcs.FSTTCS.2010.1</a>","apa":"Alur, R., &#38; Cerny, P. (2010). Expressiveness of streaming string transducers (Vol. 8, pp. 1–12). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Chennai, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1\">https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1</a>"},"conference":{"location":"Chennai, India","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","start_date":"2010-12-15","end_date":"2010-12-18"},"pubrep_id":"948","status":"public","date_created":"2018-12-11T11:46:45Z","_id":"488","type":"conference","language":[{"iso":"eng"}],"volume":8,"has_accepted_license":"1","month":"01","file":[{"date_updated":"2020-07-14T12:46:35Z","date_created":"2018-12-12T10:08:29Z","content_type":"application/pdf","file_name":"IST-2018-948-v1+1_2011_Cerny_Expressiveness_of.pdf","relation":"main_file","file_size":492344,"access_level":"open_access","creator":"system","file_id":"4690","checksum":"5845be5aa19791830f7407d8853f2df0"}],"author":[{"full_name":"Alur, Rajeev","last_name":"Alur","first_name":"Rajeev"},{"last_name":"Cerny","first_name":"Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Cerny, Pavol"}],"quality_controlled":"1","oa_version":"Published Version"},{"conference":{"location":"Minori, Amalfi Coast, Italy","name":"GandALF: Games, Automata, Logic, and Formal Verification","end_date":"2010-06-18","start_date":"2010-06-17"},"status":"public","main_file_link":[{"url":"https://arxiv.org/abs/1006.1404v1","open_access":"1"}],"date_created":"2018-12-11T11:46:45Z","type":"conference","_id":"489","language":[{"iso":"eng"}],"volume":25,"month":"06","author":[{"full_name":"Cristau, Julien","first_name":"Julien","last_name":"Cristau"},{"full_name":"David, Claire","last_name":"David","first_name":"Claire"},{"full_name":"Horn, Florian","id":"37327ACE-F248-11E8-B48F-1D18A9856A87","last_name":"Horn","first_name":"Florian"}],"quality_controlled":"1","oa_version":"Published Version","publist_id":"7332","intvolume":"        25","publication":"Proceedings of GandALF 2010","scopus_import":1,"doi":"10.4204/EPTCS.25.7","day":"09","page":"30 - 39","year":"2010","oa":1,"date_published":"2010-06-09T00:00:00Z","publisher":"Open Publishing Association","title":"How do we remember the past in randomised strategies? ","publication_status":"published","abstract":[{"lang":"eng","text":"Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance. In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies."}],"alternative_title":["EPTCS"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"date_updated":"2021-01-12T08:01:01Z","citation":{"short":"J. Cristau, C. David, F. Horn, in:, Proceedings of GandALF 2010, Open Publishing Association, 2010, pp. 30–39.","mla":"Cristau, Julien, et al. “How Do We Remember the Past in Randomised Strategies? .” <i>Proceedings of GandALF 2010</i>, vol. 25, Open Publishing Association, 2010, pp. 30–39, doi:<a href=\"https://doi.org/10.4204/EPTCS.25.7\">10.4204/EPTCS.25.7</a>.","ieee":"J. Cristau, C. David, and F. Horn, “How do we remember the past in randomised strategies? ,” in <i>Proceedings of GandALF 2010</i>, Minori, Amalfi Coast, Italy, 2010, vol. 25, pp. 30–39.","ama":"Cristau J, David C, Horn F. How do we remember the past in randomised strategies? . In: <i>Proceedings of GandALF 2010</i>. Vol 25. Open Publishing Association; 2010:30-39. doi:<a href=\"https://doi.org/10.4204/EPTCS.25.7\">10.4204/EPTCS.25.7</a>","ista":"Cristau J, David C, Horn F. 2010. How do we remember the past in randomised strategies? . Proceedings of GandALF 2010. GandALF: Games, Automata, Logic, and Formal Verification, EPTCS, vol. 25, 30–39.","chicago":"Cristau, Julien, Claire David, and Florian Horn. “How Do We Remember the Past in Randomised Strategies? .” In <i>Proceedings of GandALF 2010</i>, 25:30–39. Open Publishing Association, 2010. <a href=\"https://doi.org/10.4204/EPTCS.25.7\">https://doi.org/10.4204/EPTCS.25.7</a>.","apa":"Cristau, J., David, C., &#38; Horn, F. (2010). How do we remember the past in randomised strategies? . In <i>Proceedings of GandALF 2010</i> (Vol. 25, pp. 30–39). Minori, Amalfi Coast, Italy: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.25.7\">https://doi.org/10.4204/EPTCS.25.7</a>"}},{"citation":{"ieee":"J. Hoenicke, K. Leino, A. Podelski, M. Schäf, and T. Wies, “Doomed program points,” <i>Formal Methods in System Design</i>, vol. 37, no. 2–3. Springer, pp. 171–199, 2010.","ama":"Hoenicke J, Leino K, Podelski A, Schäf M, Wies T. Doomed program points. <i>Formal Methods in System Design</i>. 2010;37(2-3):171-199. doi:<a href=\"https://doi.org/10.1007/s10703-010-0102-0\">10.1007/s10703-010-0102-0</a>","ista":"Hoenicke J, Leino K, Podelski A, Schäf M, Wies T. 2010. Doomed program points. Formal Methods in System Design. 37(2–3), 171–199.","chicago":"Hoenicke, Jochen, Kari Leino, Andreas Podelski, Martin Schäf, and Thomas Wies. “Doomed Program Points.” <i>Formal Methods in System Design</i>. Springer, 2010. <a href=\"https://doi.org/10.1007/s10703-010-0102-0\">https://doi.org/10.1007/s10703-010-0102-0</a>.","apa":"Hoenicke, J., Leino, K., Podelski, A., Schäf, M., &#38; Wies, T. (2010). Doomed program points. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-010-0102-0\">https://doi.org/10.1007/s10703-010-0102-0</a>","mla":"Hoenicke, Jochen, et al. “Doomed Program Points.” <i>Formal Methods in System Design</i>, vol. 37, no. 2–3, Springer, 2010, pp. 171–99, doi:<a href=\"https://doi.org/10.1007/s10703-010-0102-0\">10.1007/s10703-010-0102-0</a>.","short":"J. Hoenicke, K. Leino, A. Podelski, M. Schäf, T. Wies, Formal Methods in System Design 37 (2010) 171–199."},"oa_version":"None","date_updated":"2021-01-12T08:01:28Z","department":[{"_id":"ToHe"}],"quality_controlled":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Jochen","last_name":"Hoenicke","full_name":"Hoenicke, Jochen"},{"full_name":"Leino, Kari","first_name":"Kari","last_name":"Leino"},{"last_name":"Podelski","first_name":"Andreas","full_name":"Podelski, Andreas"},{"full_name":"Schäf, Martin","last_name":"Schäf","first_name":"Martin"},{"id":"447BFB88-F248-11E8-B48F-1D18A9856A87","full_name":"Wies, Thomas","last_name":"Wies","first_name":"Thomas"}],"issue":"2-3","abstract":[{"lang":"eng","text":"Any programming error that can be revealed before compiling a program saves precious time for the programmer. While integrated development environments already do a good job by detecting, e.g., data-flow abnormalities, current static analysis tools suffer from false positives (&quot;noise&quot;) or require strong user interaction. We propose to avoid this deficiency by defining a new class of errors. A program fragment is doomed if its execution will inevitably fail, regardless of which state it is started in. We use a formal verification method to identify such errors fully automatically and, most significantly, without producing noise. We report on experiments with a prototype tool."}],"publication_status":"published","month":"12","volume":37,"title":"Doomed program points","language":[{"iso":"eng"}],"date_published":"2010-12-01T00:00:00Z","publisher":"Springer","type":"journal_article","_id":"533","date_created":"2018-12-11T11:47:01Z","year":"2010","day":"01","doi":"10.1007/s10703-010-0102-0","status":"public","page":"171 - 199","scopus_import":1,"publication":"Formal Methods in System Design","intvolume":"        37","publist_id":"7284"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["IST Austria Technical Report"],"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Cerny, Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","last_name":"Cerny","first_name":"Pavol"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A"},{"last_name":"Radhakrishna","first_name":"Arjun","full_name":"Radhakrishna, Arjun","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Rohit","last_name":"Singh","full_name":"Singh, Rohit"}],"citation":{"ama":"Chatterjee K, Cerny P, Henzinger TA, Radhakrishna A, Singh R. <i>Quantitative Synthesis for Concurrent Programs</i>. IST Austria; 2010. doi:<a href=\"https://doi.org/10.15479/AT:IST-2010-0004\">10.15479/AT:IST-2010-0004</a>","ista":"Chatterjee K, Cerny P, Henzinger TA, Radhakrishna A, Singh R. 2010. Quantitative synthesis for concurrent programs, IST Austria, 17p.","chicago":"Chatterjee, Krishnendu, Pavol Cerny, Thomas A Henzinger, Arjun Radhakrishna, and Rohit Singh. <i>Quantitative Synthesis for Concurrent Programs</i>. IST Austria, 2010. <a href=\"https://doi.org/10.15479/AT:IST-2010-0004\">https://doi.org/10.15479/AT:IST-2010-0004</a>.","apa":"Chatterjee, K., Cerny, P., Henzinger, T. A., Radhakrishna, A., &#38; Singh, R. (2010). <i>Quantitative synthesis for concurrent programs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2010-0004\">https://doi.org/10.15479/AT:IST-2010-0004</a>","ieee":"K. Chatterjee, P. Cerny, T. A. Henzinger, A. Radhakrishna, and R. Singh, <i>Quantitative synthesis for concurrent programs</i>. IST Austria, 2010.","short":"K. Chatterjee, P. Cerny, T.A. Henzinger, A. Radhakrishna, R. Singh, Quantitative Synthesis for Concurrent Programs, IST Austria, 2010.","mla":"Chatterjee, Krishnendu, et al. <i>Quantitative Synthesis for Concurrent Programs</i>. IST Austria, 2010, doi:<a href=\"https://doi.org/10.15479/AT:IST-2010-0004\">10.15479/AT:IST-2010-0004</a>."},"oa_version":"Published Version","date_updated":"2023-02-23T11:24:08Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"title":"Quantitative synthesis for concurrent programs","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:42Z","language":[{"iso":"eng"}],"date_published":"2010-10-07T00:00:00Z","file":[{"file_name":"IST-2010-0004_IST-2010-0004.pdf","date_updated":"2020-07-14T12:46:42Z","date_created":"2018-12-12T11:53:53Z","content_type":"application/pdf","file_size":429101,"access_level":"open_access","creator":"system","file_id":"5515","checksum":"da38782d2388a6fa32109d10bb9bad67","relation":"main_file"}],"ddc":["000","005"],"abstract":[{"text":"We present an algorithmic method for the synthesis of concurrent programs that are optimal with respect to quantitative performance measures. The input consists of a sequential sketch, that is, a program that does not contain synchronization constructs, and of a parametric performance model that assigns costs to actions such as locking, context switching, and idling. The quantitative synthesis problem is to automatically introduce synchronization constructs into the sequential sketch so that both correctness is guaranteed and worst-case (or average-case) performance is optimized. Correctness is formalized as race freedom or linearizability.\r\n\r\nWe show that for worst-case performance, the problem can be modeled\r\nas a 2-player graph game with quantitative (limit-average) objectives, and\r\nfor average-case performance, as a 2 1/2 -player graph game (with probabilistic transitions). In both cases, the optimal correct program is derived from an optimal strategy in the corresponding quantitative game. We prove that the respective game problems are computationally expensive (NP-complete), and present several techniques that overcome the theoretical difficulty in cases of concurrent programs of practical interest.\r\n\r\nWe have implemented a prototype tool and used it for the automatic syn- thesis of programs that access a concurrent list. For certain parameter val- ues, our method automatically synthesizes various classical synchronization schemes for implementing a concurrent list, such as fine-grained locking or a lazy algorithm. For other parameter values, a new, hybrid synchronization style is synthesized, which uses both the lazy approach and coarse-grained locks (instead of standard fine-grained locks). The trade-off occurs because while fine-grained locking tends to decrease the cost that is due to waiting for locks, it increases cache size requirements.","lang":"eng"}],"publication_status":"published","has_accepted_license":"1","month":"10","day":"07","year":"2010","publication_identifier":{"issn":["2664-1690"]},"status":"public","page":"17","doi":"10.15479/AT:IST-2010-0004","_id":"5388","type":"technical_report","date_created":"2018-12-12T11:39:03Z","oa":1,"pubrep_id":"24","related_material":{"record":[{"status":"public","relation":"later_version","id":"3366"}]}},{"date_created":"2018-12-12T11:39:03Z","oa":1,"_id":"5389","type":"technical_report","year":"2010","day":"04","publication_identifier":{"issn":["2664-1690"]},"status":"public","page":"24","doi":"10.15479/AT:IST-2010-0003","pubrep_id":"25","related_material":{"record":[{"status":"public","id":"3249","relation":"later_version"},{"id":"4393","relation":"later_version","status":"public"}]},"department":[{"_id":"ToHe"}],"date_updated":"2023-02-23T12:09:16Z","oa_version":"Published Version","citation":{"apa":"Cerny, P., Henzinger, T. A., &#38; Radhakrishna, A. (2010). <i>Simulation distances</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2010-0003\">https://doi.org/10.15479/AT:IST-2010-0003</a>","ama":"Cerny P, Henzinger TA, Radhakrishna A. <i>Simulation Distances</i>. IST Austria; 2010. doi:<a href=\"https://doi.org/10.15479/AT:IST-2010-0003\">10.15479/AT:IST-2010-0003</a>","chicago":"Cerny, Pavol, Thomas A Henzinger, and Arjun Radhakrishna. <i>Simulation Distances</i>. IST Austria, 2010. <a href=\"https://doi.org/10.15479/AT:IST-2010-0003\">https://doi.org/10.15479/AT:IST-2010-0003</a>.","ista":"Cerny P, Henzinger TA, Radhakrishna A. 2010. Simulation distances, IST Austria, 24p.","ieee":"P. Cerny, T. A. Henzinger, and A. Radhakrishna, <i>Simulation distances</i>. IST Austria, 2010.","short":"P. Cerny, T.A. Henzinger, A. Radhakrishna, Simulation Distances, IST Austria, 2010.","mla":"Cerny, Pavol, et al. <i>Simulation Distances</i>. IST Austria, 2010, doi:<a href=\"https://doi.org/10.15479/AT:IST-2010-0003\">10.15479/AT:IST-2010-0003</a>."},"author":[{"last_name":"Cerny","first_name":"Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Cerny, Pavol"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"last_name":"Radhakrishna","first_name":"Arjun","full_name":"Radhakrishna, Arjun","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87"}],"alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","has_accepted_license":"1","month":"06","abstract":[{"text":"Boolean notions of correctness are formalized by preorders on systems. Quantitative measures of correctness can be formalized by real-valued distance functions between systems, where the distance between implementation and specification provides a measure of “fit” or “desirability.” We extend the simulation preorder to the quantitative setting, by making each player of a simulation game pay a certain price for her choices. We use the resulting games with quantitative objectives to define three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the im- plementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. We consider these distances for safety as well as liveness specifications. The distances can be computed in polynomial time for safety specifications, and for liveness specifications given by weak fairness constraints. We show that the distance functions satisfy the triangle inequality, that the distance between two systems does not increase under parallel composition with a third system, and that the distance between two systems can be bounded from above and below by distances between abstractions of the two systems. These properties suggest that our simulation distances provide an appropriate basis for a quantitative theory of discrete systems. We also demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes.","lang":"eng"}],"file":[{"content_type":"application/pdf","date_created":"2018-12-12T11:54:25Z","date_updated":"2020-07-14T12:46:42Z","file_name":"IST-2010-0003_IST-2010-0003.pdf","relation":"main_file","checksum":"284ded99764e32a583a8ea83fcea254b","file_id":"5547","creator":"system","access_level":"open_access","file_size":367246}],"ddc":["005"],"file_date_updated":"2020-07-14T12:46:42Z","publisher":"IST Austria","language":[{"iso":"eng"}],"date_published":"2010-06-04T00:00:00Z","title":"Simulation distances"},{"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Fijalkow, Nathanaël","last_name":"Fijalkow","first_name":"Nathanaël"}],"alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"date_updated":"2020-07-14T23:04:41Z","citation":{"short":"K. Chatterjee, N. Fijalkow, Topological, Automata-Theoretic and Logical Characterization of Finitary Languages, IST Austria, 2010.","mla":"Chatterjee, Krishnendu, and Nathanaël Fijalkow. <i>Topological, Automata-Theoretic and Logical Characterization of Finitary Languages</i>. IST Austria, 2010, doi:<a href=\"https://doi.org/10.15479/AT:IST-2010-0002\">10.15479/AT:IST-2010-0002</a>.","ieee":"K. Chatterjee and N. Fijalkow, <i>Topological, automata-theoretic and logical characterization of finitary languages</i>. IST Austria, 2010.","apa":"Chatterjee, K., &#38; Fijalkow, N. (2010). <i>Topological, automata-theoretic and logical characterization of finitary languages</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2010-0002\">https://doi.org/10.15479/AT:IST-2010-0002</a>","ama":"Chatterjee K, Fijalkow N. <i>Topological, Automata-Theoretic and Logical Characterization of Finitary Languages</i>. IST Austria; 2010. doi:<a href=\"https://doi.org/10.15479/AT:IST-2010-0002\">10.15479/AT:IST-2010-0002</a>","ista":"Chatterjee K, Fijalkow N. 2010. Topological, automata-theoretic and logical characterization of finitary languages, IST Austria, 21p.","chicago":"Chatterjee, Krishnendu, and Nathanaël Fijalkow. <i>Topological, Automata-Theoretic and Logical Characterization of Finitary Languages</i>. IST Austria, 2010. <a href=\"https://doi.org/10.15479/AT:IST-2010-0002\">https://doi.org/10.15479/AT:IST-2010-0002</a>."},"oa_version":"Published Version","file_date_updated":"2020-07-14T12:46:43Z","language":[{"iso":"eng"}],"publisher":"IST Austria","date_published":"2010-06-04T00:00:00Z","title":"Topological, automata-theoretic and logical characterization of finitary languages","month":"06","publication_status":"published","has_accepted_license":"1","abstract":[{"text":"The class of ω regular languages provide a robust specification language in verification. Every ω-regular condition can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens “eventually.” Two main strengths of the classical, infinite-limit formulation of liveness are robustness (independence from the granularity of transitions) and simplicity (abstraction of complicated time bounds). However, the classical liveness formulation suffers from the drawback that the time until something good happens may be unbounded. A stronger formulation of liveness, so-called finitary liveness, overcomes this drawback, while still retaining robustness and simplicity. Finitary liveness requires that there exists an unknown, fixed bound b such that something good happens within b transitions. In this work we consider the finitary parity and Streett (fairness) conditions. We present the topological, automata-theoretic and logical characterization of finitary languages defined by finitary parity and Streett conditions. We (a) show that the finitary parity and Streett languages are Σ2-complete; (b) present a complete characterization of the expressive power of various classes of automata with finitary and infinitary conditions (in particular we show that non-deterministic finitary parity and Streett automata cannot be determinized to deterministic finitary parity or Streett automata); and (c) show that the languages defined by non-deterministic finitary parity automata exactly characterize the star-free fragment of ωB-regular languages.","lang":"eng"}],"ddc":["000"],"file":[{"file_size":395662,"access_level":"open_access","creator":"system","file_id":"5532","checksum":"283d3604d76dd4d5161585d4c8625fbe","relation":"main_file","file_name":"IST-2010-0002_IST-2010-0002.pdf","date_updated":"2020-07-14T12:46:43Z","date_created":"2018-12-12T11:54:10Z","content_type":"application/pdf"}],"year":"2010","status":"public","day":"04","doi":"10.15479/AT:IST-2010-0002","page":"21","publication_identifier":{"issn":["2664-1690"]},"oa":1,"date_created":"2018-12-12T11:39:03Z","type":"technical_report","_id":"5390","pubrep_id":"26"},{"oa":1,"date_created":"2018-12-12T11:39:04Z","_id":"5391","type":"technical_report","page":"27","doi":"10.15479/AT:IST-2010-0001","day":"19","publication_identifier":{"issn":["2664-1690"]},"year":"2010","status":"public","related_material":{"record":[{"id":"4390","relation":"later_version","status":"public"}]},"pubrep_id":"27","date_updated":"2023-02-23T12:09:09Z","department":[{"_id":"ToHe"}],"citation":{"chicago":"Cerny, Pavol, Arjun Radhakrishna, Damien Zufferey, Swarat Chaudhuri, and Rajeev Alur. <i>Model Checking of Linearizability of Concurrent List Implementations</i>. IST Austria, 2010. <a href=\"https://doi.org/10.15479/AT:IST-2010-0001\">https://doi.org/10.15479/AT:IST-2010-0001</a>.","ista":"Cerny P, Radhakrishna A, Zufferey D, Chaudhuri S, Alur R. 2010. Model checking of linearizability of concurrent list implementations, IST Austria, 27p.","ama":"Cerny P, Radhakrishna A, Zufferey D, Chaudhuri S, Alur R. <i>Model Checking of Linearizability of Concurrent List Implementations</i>. IST Austria; 2010. doi:<a href=\"https://doi.org/10.15479/AT:IST-2010-0001\">10.15479/AT:IST-2010-0001</a>","apa":"Cerny, P., Radhakrishna, A., Zufferey, D., Chaudhuri, S., &#38; Alur, R. (2010). <i>Model checking of linearizability of concurrent list implementations</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2010-0001\">https://doi.org/10.15479/AT:IST-2010-0001</a>","ieee":"P. Cerny, A. Radhakrishna, D. Zufferey, S. Chaudhuri, and R. Alur, <i>Model checking of linearizability of concurrent list implementations</i>. IST Austria, 2010.","mla":"Cerny, Pavol, et al. <i>Model Checking of Linearizability of Concurrent List Implementations</i>. IST Austria, 2010, doi:<a href=\"https://doi.org/10.15479/AT:IST-2010-0001\">10.15479/AT:IST-2010-0001</a>.","short":"P. Cerny, A. Radhakrishna, D. Zufferey, S. Chaudhuri, R. Alur, Model Checking of Linearizability of Concurrent List Implementations, IST Austria, 2010."},"oa_version":"Published Version","author":[{"first_name":"Pavol","last_name":"Cerny","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Cerny, Pavol"},{"last_name":"Radhakrishna","first_name":"Arjun","id":"3B51CAC4-F248-11E8-B48F-1D18A9856A87","full_name":"Radhakrishna, Arjun"},{"id":"4397AC76-F248-11E8-B48F-1D18A9856A87","full_name":"Zufferey, Damien","last_name":"Zufferey","first_name":"Damien","orcid":"0000-0002-3197-8736"},{"first_name":"Swarat","last_name":"Chaudhuri","full_name":"Chaudhuri, Swarat"},{"full_name":"Alur, Rajeev","first_name":"Rajeev","last_name":"Alur"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["IST Austria Technical Report"],"abstract":[{"lang":"eng","text":"Concurrent data structures with fine-grained synchronization are notoriously difficult to implement correctly. The difficulty of reasoning about these implementations does not stem from the number of variables or the program size, but rather from the large number of possible interleavings. These implementations are therefore prime candidates for model checking. We introduce an algorithm for verifying linearizability of singly-linked heap-based concurrent data structures. We consider a model consisting of an unbounded heap where each node consists an element from an unbounded data domain, with a restricted set of operations for testing and updating pointers and data elements. Our main result is that linearizability is decidable for programs that invoke a fixed number of methods, possibly in parallel. This decidable fragment covers many of the common implementation techniques — fine-grained locking, lazy synchronization, and lock-free synchronization. We also show how the technique can be used to verify optimistic implementations with the help of programmer annotations. We developed a verification tool CoLT and evaluated it on a representative sample of Java implementations of the concurrent set data structure. The tool verified linearizability of a number of implementations, found a known error in a lock-free imple- mentation and proved that the corrected version is linearizable."}],"month":"04","has_accepted_license":"1","publication_status":"published","ddc":["004"],"file":[{"creator":"system","checksum":"986645caad7dd85a6a091488f6c646dc","file_id":"5505","file_size":372286,"access_level":"open_access","relation":"main_file","file_name":"IST-2010-0001_IST-2010-0001.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:43Z","date_created":"2018-12-12T11:53:44Z"}],"date_published":"2010-04-19T00:00:00Z","file_date_updated":"2020-07-14T12:46:43Z","publisher":"IST Austria","language":[{"iso":"eng"}],"title":"Model checking of linearizability of concurrent list implementations"},{"editor":[{"first_name":"Bernhard","last_name":"Graimann","full_name":"Graimann, Bernhard"},{"full_name":"Pfurtscheller, Gert","first_name":"Gert","last_name":"Pfurtscheller"},{"first_name":"Brendan","last_name":"Allison","full_name":"Allison, Brendan"}],"publication":"Brain-Computer Interfaces","year":"2010","doi":"10.1007/978-3-642-02091-9_18","page":"331-355","day":"06","acknowledgement":"This work was supported by the EU grants “BrainCom” (FP6-2004-Mobility-5 Grant No 024259) and “Multi-adaptive BCI” (MEIF-CT-2006 Grant No 040666). Furthermore, we thank Matthias Krauledat for fruitful discussions and tools for generating Fig. 5.","series_title":"FRONTCOLL","abstract":[{"lang":"eng","text":"This chapter tackles a difficult challenge: presenting signal processing material to non-experts. This chapter is meant to be comprehensible to people who have some math background, including a course in linear algebra and basic statistics, but do not specialize in mathematics, engineering, or related fields. Some formulas assume the reader is familiar with matrices and basic matrix operations, but not more advanced material. Furthermore, we tried to make the chapter readable even if you skip the formulas. Nevertheless, we include some simple methods to demonstrate the basics of adaptive data processing, then we proceed with some advanced methods that are fundamental in adaptive signal processing, and are likely to be useful in a variety of applications. The advanced algorithms are also online available [30]. In the second part, these techniques are applied to some real-world BCI data."}],"publication_status":"published","title":"Adaptive Methods in BCI Research - An Introductory Tutorial","date_published":"2010-09-06T00:00:00Z","publisher":"Springer","citation":{"short":"A. Schlögl, C. Vidaurre, K.-R. Müller, in:, B. Graimann, G. Pfurtscheller, B. Allison (Eds.), Brain-Computer Interfaces, 1st ed., Springer, Berlin, Heidelberg, 2010, pp. 331–355.","mla":"Schlögl, Alois, et al. “Adaptive Methods in BCI Research - An Introductory Tutorial.” <i>Brain-Computer Interfaces</i>, edited by Bernhard Graimann et al., 1st ed., Springer, 2010, pp. 331–55, doi:<a href=\"https://doi.org/10.1007/978-3-642-02091-9_18\">10.1007/978-3-642-02091-9_18</a>.","apa":"Schlögl, A., Vidaurre, C., &#38; Müller, K.-R. (2010). Adaptive Methods in BCI Research - An Introductory Tutorial. In B. Graimann, G. Pfurtscheller, &#38; B. Allison (Eds.), <i>Brain-Computer Interfaces</i> (1st ed., pp. 331–355). Berlin, Heidelberg: Springer. <a href=\"https://doi.org/10.1007/978-3-642-02091-9_18\">https://doi.org/10.1007/978-3-642-02091-9_18</a>","ista":"Schlögl A, Vidaurre C, Müller K-R. 2010.Adaptive Methods in BCI Research - An Introductory Tutorial. In: Brain-Computer Interfaces. The Frontiers Collection, , 331–355.","chicago":"Schlögl, Alois, Carmen Vidaurre, and Klaus-Robert Müller. “Adaptive Methods in BCI Research - An Introductory Tutorial.” In <i>Brain-Computer Interfaces</i>, edited by Bernhard Graimann, Gert Pfurtscheller, and Brendan Allison, 1st ed., 331–55. FRONTCOLL. Berlin, Heidelberg: Springer, 2010. <a href=\"https://doi.org/10.1007/978-3-642-02091-9_18\">https://doi.org/10.1007/978-3-642-02091-9_18</a>.","ama":"Schlögl A, Vidaurre C, Müller K-R. Adaptive Methods in BCI Research - An Introductory Tutorial. In: Graimann B, Pfurtscheller G, Allison B, eds. <i>Brain-Computer Interfaces</i>. 1st ed. FRONTCOLL. Berlin, Heidelberg: Springer; 2010:331-355. doi:<a href=\"https://doi.org/10.1007/978-3-642-02091-9_18\">10.1007/978-3-642-02091-9_18</a>","ieee":"A. Schlögl, C. Vidaurre, and K.-R. Müller, “Adaptive Methods in BCI Research - An Introductory Tutorial,” in <i>Brain-Computer Interfaces</i>, 1st ed., B. Graimann, G. Pfurtscheller, and B. Allison, Eds. Berlin, Heidelberg: Springer, 2010, pp. 331–355."},"date_updated":"2024-02-19T09:47:25Z","department":[{"_id":"ScienComp"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["The Frontiers Collection"],"edition":"1","type":"book_chapter","_id":"14983","date_created":"2024-02-14T09:56:00Z","publication_identifier":{"issn":["1612-3018"],"isbn":["9783642020902"],"eisbn":["9783642020919"]},"status":"public","month":"09","article_processing_charge":"No","language":[{"iso":"eng"}],"oa_version":"None","quality_controlled":"1","place":"Berlin, Heidelberg","author":[{"orcid":"0000-0002-5621-8100","first_name":"Alois","last_name":"Schlögl","full_name":"Schlögl, Alois","id":"45BF87EE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Vidaurre, Carmen","last_name":"Vidaurre","first_name":"Carmen"},{"first_name":"Klaus-Robert","last_name":"Müller","full_name":"Müller, Klaus-Robert"}]}]