[{"month":"06","doi":"10.1080/00364827.2000.10414567","year":"2000","date_published":"2000-06-01T00:00:00Z","article_type":"original","title":"A mutational approach to the study of development of the protochordate Ciona intestinalis (Tunicata, Chordata)","publisher":"Taylor & Francis","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:07:13Z","day":"01","citation":{"mla":"Sordino, Paolo, et al. “A Mutational Approach to the Study of Development of the Protochordate Ciona Intestinalis (Tunicata, Chordata).” <i>Sarsia</i>, vol. 85, no. 2, Taylor &#38; Francis, 2000, pp. 173–76, doi:<a href=\"https://doi.org/10.1080/00364827.2000.10414567\">10.1080/00364827.2000.10414567</a>.","ama":"Sordino P, Heisenberg C-PJ, Cirino P, et al. A mutational approach to the study of development of the protochordate Ciona intestinalis (Tunicata, Chordata). <i>Sarsia</i>. 2000;85(2):173-176. doi:<a href=\"https://doi.org/10.1080/00364827.2000.10414567\">10.1080/00364827.2000.10414567</a>","ista":"Sordino P, Heisenberg C-PJ, Cirino P, Toscano A, Giuliano P, Marino R, Pinto M, De Santis R. 2000. A mutational approach to the study of development of the protochordate Ciona intestinalis (Tunicata, Chordata). Sarsia. 85(2), 173–176.","short":"P. Sordino, C.-P.J. Heisenberg, P. Cirino, A. Toscano, P. Giuliano, R. Marino, M. Pinto, R. De Santis, Sarsia 85 (2000) 173–176.","ieee":"P. Sordino <i>et al.</i>, “A mutational approach to the study of development of the protochordate Ciona intestinalis (Tunicata, Chordata),” <i>Sarsia</i>, vol. 85, no. 2. Taylor &#38; Francis, pp. 173–176, 2000.","apa":"Sordino, P., Heisenberg, C.-P. J., Cirino, P., Toscano, A., Giuliano, P., Marino, R., … De Santis, R. (2000). A mutational approach to the study of development of the protochordate Ciona intestinalis (Tunicata, Chordata). <i>Sarsia</i>. Taylor &#38; Francis. <a href=\"https://doi.org/10.1080/00364827.2000.10414567\">https://doi.org/10.1080/00364827.2000.10414567</a>","chicago":"Sordino, Paolo, Carl-Philipp J Heisenberg, Paola Cirino, Alfonso Toscano, Paola Giuliano, Rita Marino, Maria Pinto, and Rosaria De Santis. “A Mutational Approach to the Study of Development of the Protochordate Ciona Intestinalis (Tunicata, Chordata).” <i>Sarsia</i>. Taylor &#38; Francis, 2000. <a href=\"https://doi.org/10.1080/00364827.2000.10414567\">https://doi.org/10.1080/00364827.2000.10414567</a>."},"publication_status":"published","type":"journal_article","abstract":[{"text":"We have developed a protocol to perform a genetic screen for zygotic mutations affecting embryogenesis on the protochordate Ciona intestinalis. The choice of this taxon, whose phylogenetic position places it at the basis of the chordates as one the most primitive vertebrate relatives, could allow to address several evolutionary questions. The protochordates share many morphological features with the vertebrates, in primis the presence of a notochord. Ciona intestinalis shows several ideal features for a mutational analysis, such as external development and larvae made of a limited number of cells and cell types. Detailed cell lineage studies are available. The haploid genome size is comparable to the size of the Drosophila haploid genome. We have optimised conditions for chemical mutagenesis studying the efficiency at which different concentration of N-ethyl-N-nitrosourea (ENU) can induce mutations. Because the adult Ciona are hermaphrodites, we are performing a one-generation screen. The induced mutations are identified by visual inspection of developmental stages. We report the preliminary results from our screen including examples of the different classes of mutant phenotypes found so far.","lang":"eng"}],"intvolume":"        85","author":[{"last_name":"Sordino","full_name":"Sordino, Paolo","first_name":"Paolo"},{"id":"39427864-F248-11E8-B48F-1D18A9856A87","first_name":"Carl-Philipp J","orcid":"0000-0002-0912-4566","full_name":"Heisenberg, Carl-Philipp J","last_name":"Heisenberg"},{"first_name":"Paola","full_name":"Cirino, Paola","last_name":"Cirino"},{"first_name":"Alfonso","full_name":"Toscano, Alfonso","last_name":"Toscano"},{"full_name":"Giuliano, Paola","last_name":"Giuliano","first_name":"Paola"},{"first_name":"Rita","full_name":"Marino, Rita","last_name":"Marino"},{"last_name":"Pinto","full_name":"Pinto, Maria","first_name":"Maria"},{"full_name":"De Santis, Rosaria","last_name":"De Santis","first_name":"Rosaria"}],"status":"public","publication":"Sarsia","issue":"2","page":"173 - 176","article_processing_charge":"No","volume":85,"publist_id":"1972","date_updated":"2023-04-19T14:50:58Z","extern":"1","publication_identifier":{"issn":["0036-4827"]},"_id":"4147","oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"},{"day":"04","type":"journal_article","intvolume":"       405","status":"public","publication":"Nature","issue":"6782","page":"76 - 81","month":"05","date_published":"2000-05-04T00:00:00Z","article_type":"original","scopus_import":"1","publisher":"Nature Publishing Group","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:07:32Z","citation":{"ama":"Heisenberg C-PJ, Tada M, Rauch G, et al. Silberblick/Wnt11 mediates convergent extension movements during zebrafish gastrulation. <i>Nature</i>. 2000;405(6782):76-81. doi:<a href=\"https://doi.org/10.1038/35011068\">10.1038/35011068</a>","mla":"Heisenberg, Carl-Philipp J., et al. “Silberblick/Wnt11 Mediates Convergent Extension Movements during Zebrafish Gastrulation.” <i>Nature</i>, vol. 405, no. 6782, Nature Publishing Group, 2000, pp. 76–81, doi:<a href=\"https://doi.org/10.1038/35011068\">10.1038/35011068</a>.","short":"C.-P.J. Heisenberg, M. Tada, G. Rauch, L. Saúde, M. Concha, R. Geisler, D. Stemple, J. Smith, S. Wilson, Nature 405 (2000) 76–81.","ista":"Heisenberg C-PJ, Tada M, Rauch G, Saúde L, Concha M, Geisler R, Stemple D, Smith J, Wilson S. 2000. Silberblick/Wnt11 mediates convergent extension movements during zebrafish gastrulation. Nature. 405(6782), 76–81.","apa":"Heisenberg, C.-P. J., Tada, M., Rauch, G., Saúde, L., Concha, M., Geisler, R., … Wilson, S. (2000). Silberblick/Wnt11 mediates convergent extension movements during zebrafish gastrulation. <i>Nature</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/35011068\">https://doi.org/10.1038/35011068</a>","ieee":"C.-P. J. Heisenberg <i>et al.</i>, “Silberblick/Wnt11 mediates convergent extension movements during zebrafish gastrulation,” <i>Nature</i>, vol. 405, no. 6782. Nature Publishing Group, pp. 76–81, 2000.","chicago":"Heisenberg, Carl-Philipp J, Masazumi Tada, Gerd Rauch, Leonor Saúde, Miguel Concha, Robert Geisler, Derek Stemple, James Smith, and Stephen Wilson. “Silberblick/Wnt11 Mediates Convergent Extension Movements during Zebrafish Gastrulation.” <i>Nature</i>. Nature Publishing Group, 2000. <a href=\"https://doi.org/10.1038/35011068\">https://doi.org/10.1038/35011068</a>."},"publication_status":"published","abstract":[{"text":"Vertebrate gastrulation involves the specification and coordinated movement of large populations of cells that give rise to the ectodermal, mesodermal and endodermal germ layers. Although many of the genes involved in the specification of cell identity during this process have been identified, little is known of the genes that coordinate cell movement. Here we show that the zebrafish silberblick (slb) locus(1) encodes Wnt11 and that Slb/Wnt11 activity is required for cells to undergo correct convergent extension movements during gastrulation. In the absence of Slb/Wnt11 function, abnormal extension of axial tissue results in cyclopia and other midline defects in the head(2). The requirement for Slb/Wnt11 is cell non-autonomous, and our results indicate that the correct extension of axial tissue is at least partly dependent on medio-lateral cell intercalation in paraxial tissue. We also show that the slb phenotype is rescued by a truncated form of Dishevelled that does not signal through the canonical Wnt pathway(3), suggesting that, as in flies(4), Wnt signalling might mediate morphogenetic events through a divergent signal transduction cascade. Our results provide genetic and experimental evidence that Wnt activity in lateral tissues has a crucial role in driving the convergent extension movements underlying vertebrate gastrulation.","lang":"eng"}],"author":[{"first_name":"Carl-Philipp J","orcid":"0000-0002-0912-4566","last_name":"Heisenberg","full_name":"Heisenberg, Carl-Philipp J","id":"39427864-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Masazumi","last_name":"Tada","full_name":"Tada, Masazumi"},{"first_name":"Gerd","full_name":"Rauch, Gerd","last_name":"Rauch"},{"first_name":"Leonor","last_name":"Saúde","full_name":"Saúde, Leonor"},{"first_name":"Miguel","last_name":"Concha","full_name":"Concha, Miguel"},{"first_name":"Robert","full_name":"Geisler, Robert","last_name":"Geisler"},{"full_name":"Stemple, Derek","last_name":"Stemple","first_name":"Derek"},{"first_name":"James","last_name":"Smith","full_name":"Smith, James"},{"full_name":"Wilson, Stephen","last_name":"Wilson","first_name":"Stephen"}],"article_processing_charge":"No","publist_id":"1921","volume":405,"date_updated":"2023-04-19T14:40:45Z","publication_identifier":{"issn":["0028-0836"]},"extern":"1","_id":"4197","pmid":1,"oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","year":"2000","doi":"10.1038/35011068","title":"Silberblick/Wnt11 mediates convergent extension movements during zebrafish gastrulation","external_id":{"pmid":["10811221 "]}},{"type":"review","citation":{"ama":"Partridge L, Barton NH. Evolving evolvability. <i>Nature</i>. 2000;407(6803):457-458. doi:<a href=\"https://doi.org/10.1038/35035173\">10.1038/35035173</a>","mla":"Partridge, Linda, and Nicholas H. Barton. “Evolving Evolvability.” <i>Nature</i>, vol. 407, no. 6803, Nature Publishing Group, 2000, pp. 457–58, doi:<a href=\"https://doi.org/10.1038/35035173\">10.1038/35035173</a>.","ista":"Partridge L, Barton NH. 2000. Evolving evolvability. Nature. 407(6803), 457–458.","short":"L. Partridge, N.H. Barton, Nature 407 (2000) 457–458.","ieee":"L. Partridge and N. H. Barton, “Evolving evolvability,” <i>Nature</i>, vol. 407, no. 6803. Nature Publishing Group, pp. 457–458, 2000.","apa":"Partridge, L., &#38; Barton, N. H. (2000). Evolving evolvability. <i>Nature</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/35035173\">https://doi.org/10.1038/35035173</a>","chicago":"Partridge, Linda, and Nicholas H Barton. “Evolving Evolvability.” <i>Nature</i>. Nature Publishing Group, 2000. <a href=\"https://doi.org/10.1038/35035173\">https://doi.org/10.1038/35035173</a>."},"day":"01","publication_status":"published","author":[{"last_name":"Partridge","full_name":"Partridge, Linda","first_name":"Linda"},{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","last_name":"Barton"}],"status":"public","intvolume":"       407","page":"457 - 458","article_processing_charge":"No","volume":407,"date_updated":"2023-04-19T14:37:19Z","publist_id":"1823","publication":"Nature","issue":"6803","oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0028-0836"]},"extern":"1","_id":"4268","date_published":"2000-09-01T00:00:00Z","doi":"10.1038/35035173","year":"2000","month":"09","language":[{"iso":"eng"}],"title":"Evolving evolvability","scopus_import":"1","publisher":"Nature Publishing Group","date_created":"2018-12-11T12:07:57Z"},{"author":[{"last_name":"Coyne","full_name":"Coyne, Jerry","first_name":"Jerry"},{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Barton, Nicholas H","last_name":"Barton","orcid":"0000-0002-8548-5240","first_name":"Nicholas H"},{"last_name":"Turelli","full_name":"Turelli, Michael","first_name":"Michael"}],"publication_status":"published","citation":{"mla":"Coyne, Jerry, et al. “Is Wright’s Shifting Balance Process Important in Evolution?” <i>Evolution; International Journal of Organic Evolution</i>, vol. 54, no. 1, Wiley-Blackwell, 2000, pp. 306–17, doi:<a href=\"https://doi.org/10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2\">10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2</a>.","ama":"Coyne J, Barton NH, Turelli M. Is Wright’s shifting balance process important in evolution? <i>Evolution; International Journal of Organic Evolution</i>. 2000;54(1):306-317. doi:<a href=\"https://doi.org/10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2\">10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2</a>","ista":"Coyne J, Barton NH, Turelli M. 2000. Is Wright’s shifting balance process important in evolution? Evolution; International Journal of Organic Evolution. 54(1), 306–317.","short":"J. Coyne, N.H. Barton, M. Turelli, Evolution; International Journal of Organic Evolution 54 (2000) 306–317.","apa":"Coyne, J., Barton, N. H., &#38; Turelli, M. (2000). Is Wright’s shifting balance process important in evolution? <i>Evolution; International Journal of Organic Evolution</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2\">https://doi.org/10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2</a>","ieee":"J. Coyne, N. H. Barton, and M. Turelli, “Is Wright’s shifting balance process important in evolution?,” <i>Evolution; International Journal of Organic Evolution</i>, vol. 54, no. 1. Wiley-Blackwell, pp. 306–317, 2000.","chicago":"Coyne, Jerry, Nicholas H Barton, and Michael Turelli. “Is Wright’s Shifting Balance Process Important in Evolution?” <i>Evolution; International Journal of Organic Evolution</i>. Wiley-Blackwell, 2000. <a href=\"https://doi.org/10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2\">https://doi.org/10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2</a>."},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","quality_controlled":"1","oa_version":"None","pmid":1,"_id":"4269","extern":"1","publication_identifier":{"issn":["0014-3820"]},"publist_id":"1821","date_updated":"2023-04-19T12:48:29Z","volume":54,"article_processing_charge":"No","external_id":{"pmid":["10937209"]},"title":"Is Wright’s shifting balance process important in evolution?","doi":"10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2","year":"2000","status":"public","intvolume":"        54","type":"journal_article","day":"01","page":"306 - 317","issue":"1","publication":"Evolution; International Journal of Organic Evolution","language":[{"iso":"eng"}],"publisher":"Wiley-Blackwell","article_type":"original","date_published":"2000-02-01T00:00:00Z","month":"02","date_created":"2018-12-11T12:07:57Z"},{"date_created":"2018-12-11T12:07:57Z","month":"06","article_type":"original","date_published":"2000-06-01T00:00:00Z","publisher":"Genetics Society of America","language":[{"iso":"eng"}],"issue":"2","publication":"Genetics","page":"981 - 987","day":"01","type":"journal_article","intvolume":"       155","status":"public","main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1461106/"}],"year":"2000","doi":"10.1093/genetics/155.2.981","external_id":{"pmid":["10835415"]},"title":"Detecting bottlenecks and selective sweeps from DNA sequence polymorphism","oa":1,"date_updated":"2023-04-19T14:03:56Z","volume":155,"publist_id":"1822","article_processing_charge":"No","pmid":1,"_id":"4270","extern":"1","publication_identifier":{"issn":["0016-6731"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","publication_status":"published","citation":{"short":"N. Galtier, F. Depaulis, N.H. Barton, Genetics 155 (2000) 981–987.","ista":"Galtier N, Depaulis F, Barton NH. 2000. Detecting bottlenecks and selective sweeps from DNA sequence polymorphism. Genetics. 155(2), 981–987.","ama":"Galtier N, Depaulis F, Barton NH. Detecting bottlenecks and selective sweeps from DNA sequence polymorphism. <i>Genetics</i>. 2000;155(2):981-987. doi:<a href=\"https://doi.org/10.1093/genetics/155.2.981\">10.1093/genetics/155.2.981</a>","mla":"Galtier, Nicolas, et al. “Detecting Bottlenecks and Selective Sweeps from DNA Sequence Polymorphism.” <i>Genetics</i>, vol. 155, no. 2, Genetics Society of America, 2000, pp. 981–87, doi:<a href=\"https://doi.org/10.1093/genetics/155.2.981\">10.1093/genetics/155.2.981</a>.","chicago":"Galtier, Nicolas, Frantz Depaulis, and Nicholas H Barton. “Detecting Bottlenecks and Selective Sweeps from DNA Sequence Polymorphism.” <i>Genetics</i>. Genetics Society of America, 2000. <a href=\"https://doi.org/10.1093/genetics/155.2.981\">https://doi.org/10.1093/genetics/155.2.981</a>.","apa":"Galtier, N., Depaulis, F., &#38; Barton, N. H. (2000). Detecting bottlenecks and selective sweeps from DNA sequence polymorphism. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1093/genetics/155.2.981\">https://doi.org/10.1093/genetics/155.2.981</a>","ieee":"N. Galtier, F. Depaulis, and N. H. Barton, “Detecting bottlenecks and selective sweeps from DNA sequence polymorphism,” <i>Genetics</i>, vol. 155, no. 2. Genetics Society of America, pp. 981–987, 2000."},"abstract":[{"lang":"eng","text":"A coalescence-based maximum-likelihood method is presented that aims to (i) detect diversity-reducing events in the recent history of a population and (ii) distinguish between demographic (e.g., bottlenecks) and selective causes (selective sweep) of a recent reduction of genetic variability. The former goal is achieved by taking account of the distortion in the shape of gene genealogies generated by diversity-reducing events: gene trees tend to be more star-like than under the standard coalescent. The latter issue is addressed by comparing patterns between loci: demographic events apply to the whole genome whereas selective events affect distinct regions of the genome to a varying extent. The maximum-likelihood approach allows one to estimate the time and strength of diversity-reducing events and to choose among competing hypotheses. An application to sequence data from an African population of Drosophila melanogaster shows that the bottleneck hypothesis is unlikely and that one or several selective sweeps probably occurred in the recent history of this population."}],"author":[{"last_name":"Galtier","full_name":"Galtier, Nicolas","first_name":"Nicolas"},{"full_name":"Depaulis, Frantz","last_name":"Depaulis","first_name":"Frantz"},{"first_name":"Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}]},{"issue":"2","publication":"Genetical Research","page":"179 - 198","day":"01","type":"journal_article","intvolume":"        75","status":"public","date_created":"2018-12-11T12:07:58Z","month":"04","article_type":"original","date_published":"2000-04-01T00:00:00Z","publisher":"Cambridge University Press","scopus_import":"1","language":[{"iso":"eng"}],"publist_id":"1819","date_updated":"2023-04-19T09:58:36Z","volume":75,"article_processing_charge":"No","pmid":1,"_id":"4271","publication_identifier":{"issn":["0016-6723"]},"extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"We are grateful to Loeske Kruuk and Michael Turelli for their helpful comments on the manuscript. N.B. was supported by grants GR3/11635 from the NERC and GR/L10048 from the EPSRC, and by the Darwin Trust of Edinburgh. M.S. was supported by a graduate student fellowship from the Yale Institute for Biospheric Studies.","quality_controlled":"1","oa_version":"None","publication_status":"published","citation":{"chicago":"Barton, Nicholas H, and Max Shpak. “The Effects of Epistasis on the Structure of Hybrid Zones.” <i>Genetical Research</i>. Cambridge University Press, 2000. <a href=\"https://doi.org/10.1017/S0016672399004334\">https://doi.org/10.1017/S0016672399004334</a>.","ieee":"N. H. Barton and M. Shpak, “The effects of epistasis on the structure of hybrid zones,” <i>Genetical Research</i>, vol. 75, no. 2. Cambridge University Press, pp. 179–198, 2000.","apa":"Barton, N. H., &#38; Shpak, M. (2000). The effects of epistasis on the structure of hybrid zones. <i>Genetical Research</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/S0016672399004334\">https://doi.org/10.1017/S0016672399004334</a>","short":"N.H. Barton, M. Shpak, Genetical Research 75 (2000) 179–198.","ista":"Barton NH, Shpak M. 2000. The effects of epistasis on the structure of hybrid zones. Genetical Research. 75(2), 179–198.","mla":"Barton, Nicholas H., and Max Shpak. “The Effects of Epistasis on the Structure of Hybrid Zones.” <i>Genetical Research</i>, vol. 75, no. 2, Cambridge University Press, 2000, pp. 179–98, doi:<a href=\"https://doi.org/10.1017/S0016672399004334\">10.1017/S0016672399004334</a>.","ama":"Barton NH, Shpak M. The effects of epistasis on the structure of hybrid zones. <i>Genetical Research</i>. 2000;75(2):179-198. doi:<a href=\"https://doi.org/10.1017/S0016672399004334\">10.1017/S0016672399004334</a>"},"abstract":[{"lang":"eng","text":"Within hybrid zones that are maintained by a balance between selection and dispersal, linkage disequilibrium is generated by the mixing of divergent populations. This linkage disequilibrium causes selection on each locus to act on all other loci, thereby steepening dines, and generating a barrier to gene flow. Diffusion models predict simple relations between the strength of linkage disequilibrium and the dispersal rate, σ, and between the barrier to gene flow, B, and the reduction in mean fitness, W̄. The aim of this paper is to test the accuracy of these predictions by comparison with an exact deterministic model of unlinked loci (r = 0.5). Disruptive selection acts on the proportion of alleles from the parental populations (p, q): W = exp[-S(4pq)(β)], such that the least fit genotype has fitness e(-S). Where β &lt;&lt; 1, fitness is reduced for a wide range of intermediate genotypes; where β &gt;&gt; 1, fitness is only reduced for those genotypes close to p = 0.5. Even with strong epistasis, linkage disequilibria are close to σ2p'(i)p'(j)/r(ij), where p'(i), p'(j) are the gradients in allele frequency at loci i, j. The barrier to gene flow, which is reflected in the steepening of neutral dines, is given by B = ∫(-∞)(∞) (W̄(1/r̄)-1) dx, where r̄, the harmonic mean recombination rate between the neural and selected loci, is here 0.5. This is a close approximation for weak selection, but underestimates B for strong selection. The barrier is stronger for small β, because hybrid fitness is then reduced over a wider range of p. The widths of the selected dines are harder to predict: though simple approximations are accurate for β = 1, they become inaccurate for extreme β because, then, fitness changes sharply with p. Estimates of gene number, made from neutral dines on the assumption that selection acts against heterozygotes, are accurate for weak selection when β = 1; however, for strong selection, gene number is overestimated. For β &gt; 1, gene number is systematically overestimated and, conversely, when β &lt; 1, it is underestimated.\r\n"}],"author":[{"orcid":"0000-0002-8548-5240","last_name":"Barton","full_name":"Barton, Nicholas H","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Shpak","full_name":"Shpak, Max","first_name":"Max"}],"doi":"10.1017/S0016672399004334","year":"2000","title":"The effects of epistasis on the structure of hybrid zones","external_id":{"pmid":["10816975"]}},{"oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0040-5809"]},"extern":"1","_id":"4272","pmid":1,"article_processing_charge":"No","date_updated":"2023-04-19T12:36:39Z","volume":57,"publist_id":"1820","author":[{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","last_name":"Barton"},{"first_name":"Max","last_name":"Shpak","full_name":"Shpak, Max"}],"abstract":[{"lang":"eng","text":"Analysis of multilocus evolution is usually intractable for more than n ~ 10 genes, because the frequencies of very large numbers of genotypes must be followed. An exact analysis of up to n ~ 100 loci is feasible for a symmetrical model, in which a set of unlinked loci segregate for two alleles (labeled '0' and '1') with interchangeable effects on fitness. All haploid genotypes with the same number of 1 alleles can then remain equally frequent. However, such a symmetrical solution may be unstable: for example, under stabilizing selection, populations tend to fix any one genotype which approaches the optimum. Here, we show how the 2' x 2' stability matrix can be decomposed into a set of matrices, each no larger than n x n. This allows the stability of symmetrical solutions to be determined. We apply the method to stabilizing and disruptive selection in a single deme and to selection against heterozygotes in a linear cline. (C) 2000 Academic Press."}],"citation":{"ieee":"N. H. Barton and M. Shpak, “The stability of symmetrical solutions to polygenic models,” <i>Theoretical Population Biology</i>, vol. 57, no. 3. Academic Press, pp. 249–263, 2000.","apa":"Barton, N. H., &#38; Shpak, M. (2000). The stability of symmetrical solutions to polygenic models. <i>Theoretical Population Biology</i>. Academic Press. <a href=\"https://doi.org/10.1006/tpbi.2000.1455\">https://doi.org/10.1006/tpbi.2000.1455</a>","chicago":"Barton, Nicholas H, and Max Shpak. “The Stability of Symmetrical Solutions to Polygenic Models.” <i>Theoretical Population Biology</i>. Academic Press, 2000. <a href=\"https://doi.org/10.1006/tpbi.2000.1455\">https://doi.org/10.1006/tpbi.2000.1455</a>.","ama":"Barton NH, Shpak M. The stability of symmetrical solutions to polygenic models. <i>Theoretical Population Biology</i>. 2000;57(3):249-263. doi:<a href=\"https://doi.org/10.1006/tpbi.2000.1455\">10.1006/tpbi.2000.1455</a>","mla":"Barton, Nicholas H., and Max Shpak. “The Stability of Symmetrical Solutions to Polygenic Models.” <i>Theoretical Population Biology</i>, vol. 57, no. 3, Academic Press, 2000, pp. 249–63, doi:<a href=\"https://doi.org/10.1006/tpbi.2000.1455\">10.1006/tpbi.2000.1455</a>.","ista":"Barton NH, Shpak M. 2000. The stability of symmetrical solutions to polygenic models. Theoretical Population Biology. 57(3), 249–263.","short":"N.H. Barton, M. Shpak, Theoretical Population Biology 57 (2000) 249–263."},"publication_status":"published","external_id":{"pmid":["10828217"]},"title":"The stability of symmetrical solutions to polygenic models","year":"2000","doi":"10.1006/tpbi.2000.1455","page":"249 - 263","publication":"Theoretical Population Biology","issue":"3","status":"public","intvolume":"        57","type":"journal_article","day":"01","date_created":"2018-12-11T12:07:58Z","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Academic Press","article_type":"original","date_published":"2000-05-01T00:00:00Z","month":"05"},{"external_id":{"pmid":["11084623"]},"title":"Limits to natural selection","year":"2000","doi":"10.1002/1521-1878(200012)22:12&lt;1075::AID-BIES5&gt;3.0.CO;2-M","abstract":[{"lang":"eng","text":"We review the various factors that limit adaptation by natural selection. Recent discussion of constraints on selection and, conversely, of the factors that enhance 'evolvability', have concentrated on the kinds of variation that can be produced. Here, we emphasise that adaptation depends on how the various evolutionary processes shape variation in populations. We survey the limits that population genetics places on adaptive evolution, and discuss the relationship between disparate literatures. BioEssays 22:1075-1084, 2000. (C) 2000 John Wiley and Sons, Inc."}],"author":[{"first_name":"Nicholas H","last_name":"Barton","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Linda","full_name":"Partridge, Linda","last_name":"Partridge"}],"publication_status":"published","citation":{"ista":"Barton NH, Partridge L. 2000. Limits to natural selection. BioEssays. 22(12), 1075–1084.","short":"N.H. Barton, L. Partridge, BioEssays 22 (2000) 1075–1084.","mla":"Barton, Nicholas H., and Linda Partridge. “Limits to Natural Selection.” <i>BioEssays</i>, vol. 22, no. 12, Wiley-Blackwell, 2000, pp. 1075–84, doi:<a href=\"https://doi.org/10.1002/1521-1878(200012)22:12&#38;lt;1075::AID-BIES5&#38;gt;3.0.CO;2-M\">10.1002/1521-1878(200012)22:12&#38;lt;1075::AID-BIES5&#38;gt;3.0.CO;2-M</a>.","ama":"Barton NH, Partridge L. Limits to natural selection. <i>BioEssays</i>. 2000;22(12):1075-1084. doi:<a href=\"https://doi.org/10.1002/1521-1878(200012)22:12&#38;lt;1075::AID-BIES5&#38;gt;3.0.CO;2-M\">10.1002/1521-1878(200012)22:12&#38;lt;1075::AID-BIES5&#38;gt;3.0.CO;2-M</a>","chicago":"Barton, Nicholas H, and Linda Partridge. “Limits to Natural Selection.” <i>BioEssays</i>. Wiley-Blackwell, 2000. <a href=\"https://doi.org/10.1002/1521-1878(200012)22:12&#38;lt;1075::AID-BIES5&#38;gt;3.0.CO;2-M\">https://doi.org/10.1002/1521-1878(200012)22:12&#38;lt;1075::AID-BIES5&#38;gt;3.0.CO;2-M</a>.","apa":"Barton, N. H., &#38; Partridge, L. (2000). Limits to natural selection. <i>BioEssays</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1002/1521-1878(200012)22:12&#38;lt;1075::AID-BIES5&#38;gt;3.0.CO;2-M\">https://doi.org/10.1002/1521-1878(200012)22:12&#38;lt;1075::AID-BIES5&#38;gt;3.0.CO;2-M</a>","ieee":"N. H. Barton and L. Partridge, “Limits to natural selection,” <i>BioEssays</i>, vol. 22, no. 12. Wiley-Blackwell, pp. 1075–1084, 2000."},"_id":"4273","pmid":1,"extern":"1","publication_identifier":{"issn":["0265-9247"]},"acknowledgement":"We thank Brian Charlesworth, Toby Johnson, and two anonymous referees for helpful discussions and criticism of the manuscript.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","quality_controlled":"1","publist_id":"1818","date_updated":"2023-04-19T09:49:52Z","volume":22,"article_processing_charge":"No","publisher":"Wiley-Blackwell","scopus_import":"1","language":[{"iso":"eng"}],"month":"12","article_type":"original","date_published":"2000-12-01T00:00:00Z","date_created":"2018-12-11T12:07:58Z","intvolume":"        22","status":"public","day":"01","type":"journal_article","issue":"12","publication":"BioEssays","page":"1075 - 1084"},{"title":"Genetic hitchhiking","external_id":{"pmid":["11127900"]},"year":"2000","doi":"10.1098/rstb.2000.0716","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1692896/"}],"abstract":[{"text":"Selection on one or more genes inevitably perturbs other genes, even when those genes have no direct effect on fitness. This article reviews the theory of such genetic hitchhiking, concentrating on effects on neutral loci. Maynard Smith and Haigh introduced the classical case where the perturbation is due to a single favourable mutation. This is contrasted with the apparently distinct effects of inherited variation in fitness due to loosely linked loci. A model of fluctuating selection is analysed which bridges these alternative treatments. When alleles sweep between extreme frequencies at a rate λ, the rate of drift is increased by a factor (1 + E[1/pq]λ/(2(2λ + r))), where the recombination rate r is much smaller than the strength of selection. In spatially structured populations, the effects of any one substitution are weaker, and only cause a local increase in the frequency of a neutral allele. This increase depends primarily on the rate of recombination relative to selection (r/s), and more weakly, on the neighbourhood size, Nb = 4πρσ2. Spatial subdivision may allow local selective sweeps to occur more frequently than is indicated by the overall rate of molecular evolution. However, it seems unlikely that such sweeps can be sufficiently frequent to increase significantly the drift of neutral alleles.","lang":"eng"}],"author":[{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","full_name":"Barton, Nicholas H"}],"publication_status":"published","citation":{"ieee":"N. H. Barton, “Genetic hitchhiking,” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>, vol. 355, no. 1403. Royal Society of London, pp. 1553–1562, 2000.","apa":"Barton, N. H. (2000). Genetic hitchhiking. <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>. Royal Society of London. <a href=\"https://doi.org/10.1098/rstb.2000.0716\">https://doi.org/10.1098/rstb.2000.0716</a>","chicago":"Barton, Nicholas H. “Genetic Hitchhiking.” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>. Royal Society of London, 2000. <a href=\"https://doi.org/10.1098/rstb.2000.0716\">https://doi.org/10.1098/rstb.2000.0716</a>.","mla":"Barton, Nicholas H. “Genetic Hitchhiking.” <i>Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences</i>, vol. 355, no. 1403, Royal Society of London, 2000, pp. 1553–62, doi:<a href=\"https://doi.org/10.1098/rstb.2000.0716\">10.1098/rstb.2000.0716</a>.","ama":"Barton NH. Genetic hitchhiking. <i>Philosophical Transactions of the Royal Society of London Series B, Biological Sciences</i>. 2000;355(1403):1553-1562. doi:<a href=\"https://doi.org/10.1098/rstb.2000.0716\">10.1098/rstb.2000.0716</a>","short":"N.H. Barton, Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences 355 (2000) 1553–1562.","ista":"Barton NH. 2000. Genetic hitchhiking. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences. 355(1403), 1553–1562."},"pmid":1,"_id":"4274","publication_identifier":{"issn":["0962-8436"]},"extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"I am grateful to B. Charlesworth and M.Slatkin for their helpful comments. This work was supported by the Biotechnology\r\nand Biological Sciences Research Council, the Natural Environment Research Council, and the Darwin Trust of Edinburgh.","oa_version":"None","quality_controlled":"1","oa":1,"date_updated":"2023-04-19T09:35:31Z","volume":355,"publist_id":"1815","article_processing_charge":"No","publisher":"Royal Society of London","scopus_import":"1","language":[{"iso":"eng"}],"month":"11","date_published":"2000-11-29T00:00:00Z","date_created":"2018-12-11T12:07:59Z","intvolume":"       355","status":"public","day":"29","type":"journal_article","issue":"1403","publication":"Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences","page":"1553 - 1562"},{"author":[{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","last_name":"Barton","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240"}],"status":"public","type":"book_chapter","publication_status":"published","citation":{"short":"N.H. Barton, in:, Encyclopedia of Biodiversity, Academic Press, 2000, pp. 85–94.","ista":"Barton NH. 2000.Differentiation. In: Encyclopedia of Biodiversity. , 85–94.","mla":"Barton, Nicholas H. “Differentiation.” <i>Encyclopedia of Biodiversity</i>, Academic Press, 2000, pp. 85–94, doi:<a href=\"https://doi.org/10.1016/B0-12-226865-2/00070-5\">10.1016/B0-12-226865-2/00070-5</a>.","ama":"Barton NH. Differentiation. In: <i>Encyclopedia of Biodiversity</i>. Academic Press; 2000:85-94. doi:<a href=\"https://doi.org/10.1016/B0-12-226865-2/00070-5\">10.1016/B0-12-226865-2/00070-5</a>","chicago":"Barton, Nicholas H. “Differentiation.” In <i>Encyclopedia of Biodiversity</i>, 85–94. Academic Press, 2000. <a href=\"https://doi.org/10.1016/B0-12-226865-2/00070-5\">https://doi.org/10.1016/B0-12-226865-2/00070-5</a>.","apa":"Barton, N. H. (2000). Differentiation. In <i>Encyclopedia of Biodiversity</i> (pp. 85–94). Academic Press. <a href=\"https://doi.org/10.1016/B0-12-226865-2/00070-5\">https://doi.org/10.1016/B0-12-226865-2/00070-5</a>","ieee":"N. H. Barton, “Differentiation,” in <i>Encyclopedia of Biodiversity</i>, Academic Press, 2000, pp. 85–94."},"day":"01","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","_id":"4275","extern":"1","publication_identifier":{"isbn":["9780122268656"]},"date_updated":"2023-04-19T09:39:55Z","publist_id":"1816","page":"85 - 94","article_processing_charge":"No","publication":"Encyclopedia of Biodiversity","language":[{"iso":"eng"}],"publisher":"Academic Press","title":"Differentiation","date_published":"2000-10-01T00:00:00Z","year":"2000","month":"10","doi":"10.1016/B0-12-226865-2/00070-5","date_created":"2018-12-11T12:07:59Z"},{"month":"06","year":"2000","doi":"10.1017/S0016672300239220","date_published":"2000-06-01T00:00:00Z","title":"Population genetics of multiple loci","publisher":"Cambridge University Press","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://www.cambridge.org/core/journals/genetics-research/article/population-genetics-of-multiple-loci-by-f-b-christiansen-wiley-series-in-mathematical-and-computational-biology-ed-s-levin-john-wiley-sons-1999-isbn-0-471-979791-365-pages-price-80-hardback/9F9E954479B9FB87B0A07250AD6AAD9C"}],"date_created":"2018-12-11T12:07:59Z","citation":{"ama":"Barton NH. Population genetics of multiple loci. <i>Genetics Research</i>. 2000;75(3):371-373. doi:<a href=\"https://doi.org/10.1017/S0016672300239220\">10.1017/S0016672300239220</a>","mla":"Barton, Nicholas H. “Population Genetics of Multiple Loci.” <i>Genetics Research</i>, vol. 75, no. 3, Cambridge University Press, 2000, pp. 371–73, doi:<a href=\"https://doi.org/10.1017/S0016672300239220\">10.1017/S0016672300239220</a>.","ista":"Barton NH. 2000. Population genetics of multiple loci. Genetics Research. 75(3), 371–373.","short":"N.H. Barton, Genetics Research 75 (2000) 371–373.","apa":"Barton, N. H. (2000). Population genetics of multiple loci. <i>Genetics Research</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/S0016672300239220\">https://doi.org/10.1017/S0016672300239220</a>","ieee":"N. H. Barton, “Population genetics of multiple loci,” <i>Genetics Research</i>, vol. 75, no. 3. Cambridge University Press, pp. 371–373, 2000.","chicago":"Barton, Nicholas H. “Population Genetics of Multiple Loci.” <i>Genetics Research</i>. Cambridge University Press, 2000. <a href=\"https://doi.org/10.1017/S0016672300239220\">https://doi.org/10.1017/S0016672300239220</a>."},"day":"01","publication_status":"published","type":"review","intvolume":"        75","author":[{"first_name":"Nicholas H","last_name":"Barton","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"status":"public","publication":"Genetics Research","issue":"3","page":"371 - 373","article_processing_charge":"No","date_updated":"2023-04-18T15:01:01Z","volume":75,"publist_id":"1814","publication_identifier":{"issn":["0016-6723"]},"extern":"1","_id":"4276","oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"},{"type":"conference","day":"01","status":"public","intvolume":"      1785","page":"299 - 314","publication":"Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","date_published":"2000-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer","date_created":"2018-12-11T12:08:50Z","conference":{"start_date":"2000-03-25","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","location":"Berlin, Germany","end_date":"2000-04-02"},"citation":{"short":"T.A. Henzinger, S. Rajamani, in:, Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer, 2000, pp. 299–314.","ista":"Henzinger TA, Rajamani S. 2000. Fair bisimulation. Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 1785, 299–314.","mla":"Henzinger, Thomas A., and Sriram Rajamani. “Fair Bisimulation.” <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 1785, Springer, 2000, pp. 299–314, doi:<a href=\"https://doi.org/10.1007/3-540-46419-0_21\">10.1007/3-540-46419-0_21</a>.","ama":"Henzinger TA, Rajamani S. Fair bisimulation. In: <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 1785. Springer; 2000:299-314. doi:<a href=\"https://doi.org/10.1007/3-540-46419-0_21\">10.1007/3-540-46419-0_21</a>","chicago":"Henzinger, Thomas A, and Sriram Rajamani. “Fair Bisimulation.” In <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 1785:299–314. Springer, 2000. <a href=\"https://doi.org/10.1007/3-540-46419-0_21\">https://doi.org/10.1007/3-540-46419-0_21</a>.","ieee":"T. A. Henzinger and S. Rajamani, “Fair bisimulation,” in <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, Berlin, Germany, 2000, vol. 1785, pp. 299–314.","apa":"Henzinger, T. A., &#38; Rajamani, S. (2000). Fair bisimulation. In <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 1785, pp. 299–314). Berlin, Germany: Springer. <a href=\"https://doi.org/10.1007/3-540-46419-0_21\">https://doi.org/10.1007/3-540-46419-0_21</a>"},"publication_status":"published","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger"},{"full_name":"Rajamani, Sriram","last_name":"Rajamani","first_name":"Sriram"}],"abstract":[{"text":"Bisimulations enjoy numerous applications in the analysis of labeled transition systems. Many of these applications are based on two central observations: first, bisimilar systems satisfy the same branching-time properties; second, bisimilarity can be checked efficiently for finite-state systems. The local character of bisimulation, however, makes it difficult to address liveness concerns. Indeed, the definitions of fair bisimulation that have been proposed in the literature sacrifice locality, and with it, also efficient checkability. We put forward a new definition of fair bisimulation which does not suffer from this drawback.\r\nThe bisimilarity of two systems can be viewed in terms of a game played between a protagonist and an adversary. In each step of the infinite bisimulation game, the adversary chooses one system, makes a move, and the protagonist matches it with a move of the other system. Consistent with this game-based view, we call two fair transition systems bisimilar if in the bisimulation game, the infinite path produced in the first system is fair iff the infinite path produced in the second system is fair.\r\nWe show that this notion of fair bisimulation enjoys the following properties. First, fairly bisimilar systems satisfy the same formulas of the logics Fair-AFMC (the fair alternation-free μ-calculus) and Fair-CTL*. Therefore, fair bisimulations can serve as property-preserving abstractions for these logics and weaker ones, such as Fair-CTL and LTL. Indeed, Fair-AFMC provides an exact logical characterization of fair bisimilarity. Second, it can be checked in time polynomial in the number of states if two systems are fairly bisimilar. This is in stark contrast to all trace-based equivalences, which are traditionally used for addressing liveness but require exponential time for checking.","lang":"eng"}],"article_processing_charge":"No","volume":1785,"date_updated":"2023-04-18T13:11:07Z","publist_id":"297","quality_controlled":"1","oa_version":"None","acknowledgement":"This research was supported in part by the DARPA (NASA) grant NAG2-1214, the SRC contract 99-TJ-683.003, the MARCO grant 98-DT-660, the DARPA (MARCO) grant MDA972-99-1-0001, and the NSF CAREER award CCR-9501708.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"isbn":["9783540672821"]},"extern":"1","_id":"4433","doi":"10.1007/3-540-46419-0_21","year":"2000","title":"Fair bisimulation","alternative_title":["LNCS"]},{"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A"},{"first_name":"Jean","last_name":"Raskin","full_name":"Raskin, Jean"}],"abstract":[{"text":"The algorithmic approach to the analysis of timed and hybrid systems is fundamentally limited by undecidability, of universality in the timed case (where all continuous variables are clocks), and of emptiness in the rectangular case (which includes drifting clocks). Traditional proofs of undecidability encode a single Turing computation by a single timed trajectory. These proofs have nurtured the hope that the introduction of “fuzziness” into timed and hybrid models (in the sense that a system cannot distinguish between trajectories that are sufficiently similar) may lead to decidability. We show that this is not the case, by sharpening both fundamental undecidability results. Besides the obvious blow our results deal to the algorithmic method, they also prove that the standard model of timed and hybrid systems, while not “robust” in its definition of trajectory acceptance (which is affected by tiny perturbations in the timing of events), is quite robust in its mathematical properties: the undecidability barriers are not affected by reasonable perturbations of the model.","lang":"eng"}],"citation":{"short":"T.A. Henzinger, J. Raskin, in:, Proceedings of the 3rd International Workshop on Hybrid Systems, Springer, 2000, pp. 145–159.","ista":"Henzinger TA, Raskin J. 2000. Robust undecidability of timed and hybrid systems. Proceedings of the 3rd International Workshop on Hybrid Systems. HSCC: Hybrid Systems - Computation and Control, LNCS, vol. 1790, 145–159.","mla":"Henzinger, Thomas A., and Jean Raskin. “Robust Undecidability of Timed and Hybrid Systems.” <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i>, vol. 1790, Springer, 2000, pp. 145–59, doi:<a href=\"https://doi.org/10.1007/3-540-46430-1_15\">10.1007/3-540-46430-1_15</a>.","ama":"Henzinger TA, Raskin J. Robust undecidability of timed and hybrid systems. In: <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i>. Vol 1790. Springer; 2000:145-159. doi:<a href=\"https://doi.org/10.1007/3-540-46430-1_15\">10.1007/3-540-46430-1_15</a>","chicago":"Henzinger, Thomas A, and Jean Raskin. “Robust Undecidability of Timed and Hybrid Systems.” In <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i>, 1790:145–59. Springer, 2000. <a href=\"https://doi.org/10.1007/3-540-46430-1_15\">https://doi.org/10.1007/3-540-46430-1_15</a>.","apa":"Henzinger, T. A., &#38; Raskin, J. (2000). Robust undecidability of timed and hybrid systems. In <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i> (Vol. 1790, pp. 145–159). Pittsburgh, PA, USA: Springer. <a href=\"https://doi.org/10.1007/3-540-46430-1_15\">https://doi.org/10.1007/3-540-46430-1_15</a>","ieee":"T. A. Henzinger and J. Raskin, “Robust undecidability of timed and hybrid systems,” in <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i>, Pittsburgh, PA, USA, 2000, vol. 1790, pp. 145–159."},"publication_status":"published","oa_version":"None","quality_controlled":"1","acknowledgement":"This research was supported in part by the DARPA (NASA) grant NAG2-1214, the DARPA (Wright-Patterson AFB) grant F33615-C-98-3614, the ARO MURI grant DAAH-04-96-1-0341, and the NSF CAREER award CCR-9501708. ","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"isbn":["9783540672593"]},"extern":"1","_id":"4434","article_processing_charge":"No","volume":1790,"publist_id":"298","date_updated":"2023-04-18T13:16:13Z","title":"Robust undecidability of timed and hybrid systems","doi":"10.1007/3-540-46430-1_15","year":"2000","alternative_title":["LNCS"],"status":"public","intvolume":"      1790","type":"conference","day":"01","page":"145 - 159","publication":"Proceedings of the 3rd International Workshop on Hybrid Systems","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer","date_published":"2000-01-01T00:00:00Z","month":"01","date_created":"2018-12-11T12:08:50Z","conference":{"start_date":"2000-03-23","name":"HSCC: Hybrid Systems - Computation and Control","location":"Pittsburgh, PA, USA","end_date":"2000-03-25"}},{"alternative_title":["LNCS"],"doi":"10.1007/3-540-46419-0_11","year":"2000","title":"Symbolic model checking for rectangular hybrid systems","publist_id":"293","volume":1785,"date_updated":"2023-04-18T13:08:09Z","article_processing_charge":"No","acknowledgement":"This research was supported in part by the DARPA (NASA) grant NAG2-1214, the DARPA (Wright-Patterson AFB) grant F33615-C-98-3614, the MARCO grant 98-DT-660, the ARO MURI grant DAAH-04-96-1-0341, and the NSF CAREER award CCR-9501708.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","quality_controlled":"1","oa_version":"None","_id":"4435","extern":"1","publication_identifier":{"isbn":["9783540672821"]},"publication_status":"published","citation":{"apa":"Henzinger, T. A., &#38; Majumdar, R. (2000). Symbolic model checking for rectangular hybrid systems. In <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 1785, pp. 142–156). Berlin, Germany: Springer. <a href=\"https://doi.org/10.1007/3-540-46419-0_11\">https://doi.org/10.1007/3-540-46419-0_11</a>","ieee":"T. A. Henzinger and R. Majumdar, “Symbolic model checking for rectangular hybrid systems,” in <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, Berlin, Germany, 2000, vol. 1785, pp. 142–156.","chicago":"Henzinger, Thomas A, and Ritankar Majumdar. “Symbolic Model Checking for Rectangular Hybrid Systems.” In <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 1785:142–56. Springer, 2000. <a href=\"https://doi.org/10.1007/3-540-46419-0_11\">https://doi.org/10.1007/3-540-46419-0_11</a>.","ama":"Henzinger TA, Majumdar R. Symbolic model checking for rectangular hybrid systems. In: <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 1785. Springer; 2000:142-156. doi:<a href=\"https://doi.org/10.1007/3-540-46419-0_11\">10.1007/3-540-46419-0_11</a>","mla":"Henzinger, Thomas A., and Ritankar Majumdar. “Symbolic Model Checking for Rectangular Hybrid Systems.” <i>Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 1785, Springer, 2000, pp. 142–56, doi:<a href=\"https://doi.org/10.1007/3-540-46419-0_11\">10.1007/3-540-46419-0_11</a>.","ista":"Henzinger TA, Majumdar R. 2000. Symbolic model checking for rectangular hybrid systems. Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 1785, 142–156.","short":"T.A. Henzinger, R. Majumdar, in:, Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer, 2000, pp. 142–156."},"author":[{"first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Majumdar","full_name":"Majumdar, Ritankar","first_name":"Ritankar"}],"abstract":[{"text":"An important case of hybrid systems are the rectangular automata. First, rectangular dynamics can naturally and arbitrarily closely approximate more general, nonlinear dynamics. Second, rectangular automata are the most general type of hybrid systems for which model checking -in particular, Ltl model checking- is decidable. However, on one hand, the original proofs of decidability did not suggest practical algorithms and, on the other hand, practical symbolic model-checking procedures -such as those implemented in HyTech- were not known to terminate on rectangular automata. We remedy this unsatisfactory situation: we present a symbolic method for Ltl model checking which can be performed by HyTech and is guaranteed to terminate on all rectangular automata. We do so by proving that our method for symbolic Ltl model checking terminates on an infinite-state transition system if the trace-equivalence relation of the system has finite index, which is the case for all rectangular automata.","lang":"eng"}],"date_created":"2018-12-11T12:08:50Z","conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","end_date":"2000-04-02","location":"Berlin, Germany","start_date":"2000-03-25"},"date_published":"2000-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"publisher":"Springer","scopus_import":"1","page":"142 - 156","publication":"Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","type":"conference","day":"01","status":"public","intvolume":"      1785"},{"volume":1770,"publist_id":"292","date_updated":"2023-04-18T13:02:39Z","article_processing_charge":"No","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"This research was supported in part by the DARPA (NASA) grant NAG2-1214, the DARPA (Wright-Patterson AFB) grant F33615-C-98-3614, the MARCO grant 98-DT-660, the ARO MURI grant DAAH-04-96-1-0341, and the NSF CAREER award CCR-9501708.","quality_controlled":"1","oa_version":"None","_id":"4439","publication_identifier":{"isbn":["9783540671411"]},"extern":"1","publication_status":"published","citation":{"ieee":"T. A. Henzinger and R. Majumdar, “A classification of symbolic transition systems,” in <i>Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science</i>, Lille, France, 2000, vol. 1770, pp. 13–34.","apa":"Henzinger, T. A., &#38; Majumdar, R. (2000). A classification of symbolic transition systems. In <i>Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science</i> (Vol. 1770, pp. 13–34). Lille, France: Springer. <a href=\"https://doi.org/10.1007/3-540-46541-3_2\">https://doi.org/10.1007/3-540-46541-3_2</a>","chicago":"Henzinger, Thomas A, and Ritankar Majumdar. “A Classification of Symbolic Transition Systems.” In <i>Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science</i>, 1770:13–34. Springer, 2000. <a href=\"https://doi.org/10.1007/3-540-46541-3_2\">https://doi.org/10.1007/3-540-46541-3_2</a>.","ama":"Henzinger TA, Majumdar R. A classification of symbolic transition systems. In: <i>Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science</i>. Vol 1770. Springer; 2000:13-34. doi:<a href=\"https://doi.org/10.1007/3-540-46541-3_2\">10.1007/3-540-46541-3_2</a>","mla":"Henzinger, Thomas A., and Ritankar Majumdar. “A Classification of Symbolic Transition Systems.” <i>Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science</i>, vol. 1770, Springer, 2000, pp. 13–34, doi:<a href=\"https://doi.org/10.1007/3-540-46541-3_2\">10.1007/3-540-46541-3_2</a>.","short":"T.A. Henzinger, R. Majumdar, in:, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Springer, 2000, pp. 13–34.","ista":"Henzinger TA, Majumdar R. 2000. A classification of symbolic transition systems. Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science. STACS: Theoretical Aspects of Computer Science, LNCS, vol. 1770, 13–34."},"author":[{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Ritankar","full_name":"Majumdar, Ritankar","last_name":"Majumdar"}],"abstract":[{"text":"We define five increasingly comprehensive classes of infinite-state systems, called STS1–5, whose state spaces have finitary structure. For four of these classes, we provide examples from hybrid systems.\r\nSTS1 These are the systems with finite bisimilarity quotients. They can be analyzed symbolically by (1) iterating the predecessor and boolean operations starting from a finite set of observable state sets, and (2) terminating when no new state sets are generated. This enables model checking of the μ-calculus.\r\nSTS2 These are the systems with finite similarity quotients. They can be analyzed symbolically by iterating the predecessor and positive boolean operations. This enables model checking of the existential and universal fragments of the μ-calculus.\r\nSTS3 These are the systems with finite trace-equivalence quotients. They can be analyzed symbolically by iterating the predecessor operation and a restricted form of positive boolean operations (intersection is restricted to intersection with observables). This enables model checking of linear temporal logic.\r\nSTS4 These are the systems with finite distance-equivalence quotients (two states are equivalent if for every distance d, the same observables can be reached in d transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new state sets are generated. This enables model checking of the existential conjunction-free and universal disjunction-free fragments of the μ-calculus.\r\nSTS5 These are the systems with finite bounded-reachability quotients (two states are equivalent if for every distance d, the same observables can be reached in d or fewer transitions). The systems in this class can be analyzed symbolically by iterating the predecessor operation and terminating when no new states are encountered. This enables model checking of reachability properties.","lang":"eng"}],"alternative_title":["LNCS"],"year":"2000","doi":"10.1007/3-540-46541-3_2","title":"A classification of symbolic transition systems","page":"13 - 34","publication":"Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science","type":"conference","day":"01","status":"public","intvolume":"      1770","date_created":"2018-12-11T12:08:51Z","conference":{"start_date":"2000-02-17","name":"STACS: Theoretical Aspects of Computer Science","location":"Lille, France","end_date":"2000-02-19"},"date_published":"2000-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"publisher":"Springer","scopus_import":"1"},{"alternative_title":["LNCS"],"doi":"10.1007/3-540-46430-1_14","year":"2000","title":"Beyond HyTech: Hybrid systems analysis using interval numerical methods","volume":1790,"date_updated":"2023-04-18T12:44:52Z","publist_id":"247","article_processing_charge":"No","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"This research was supported in part by the DARPA (NASA) grant NAG2-1214, the DARPA (Wright-Patterson AFB) grant F33615-C-98-3614, the ARO MURI grant DAAH-04-96-1-0341, and the NSF CAREER award CCR-9501708.","quality_controlled":"1","oa_version":"None","_id":"4481","publication_identifier":{"isbn":["9783540672593"]},"extern":"1","publication_status":"published","citation":{"ieee":"T. A. Henzinger, B. Horowitz, R. Majumdar, and H. Wong Toi, “Beyond HyTech: Hybrid systems analysis using interval numerical methods,” in <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i>, Pittsburgh, PA, USA, 2000, vol. 1790, pp. 130–144.","apa":"Henzinger, T. A., Horowitz, B., Majumdar, R., &#38; Wong Toi, H. (2000). Beyond HyTech: Hybrid systems analysis using interval numerical methods. In <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i> (Vol. 1790, pp. 130–144). Pittsburgh, PA, USA: Springer. <a href=\"https://doi.org/10.1007/3-540-46430-1_14\">https://doi.org/10.1007/3-540-46430-1_14</a>","chicago":"Henzinger, Thomas A, Benjamin Horowitz, Ritankar Majumdar, and Howard Wong Toi. “Beyond HyTech: Hybrid Systems Analysis Using Interval Numerical Methods.” In <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i>, 1790:130–44. Springer, 2000. <a href=\"https://doi.org/10.1007/3-540-46430-1_14\">https://doi.org/10.1007/3-540-46430-1_14</a>.","mla":"Henzinger, Thomas A., et al. “Beyond HyTech: Hybrid Systems Analysis Using Interval Numerical Methods.” <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i>, vol. 1790, Springer, 2000, pp. 130–44, doi:<a href=\"https://doi.org/10.1007/3-540-46430-1_14\">10.1007/3-540-46430-1_14</a>.","ama":"Henzinger TA, Horowitz B, Majumdar R, Wong Toi H. Beyond HyTech: Hybrid systems analysis using interval numerical methods. In: <i>Proceedings of the 3rd International Workshop on Hybrid Systems</i>. Vol 1790. Springer; 2000:130-144. doi:<a href=\"https://doi.org/10.1007/3-540-46430-1_14\">10.1007/3-540-46430-1_14</a>","ista":"Henzinger TA, Horowitz B, Majumdar R, Wong Toi H. 2000. Beyond HyTech: Hybrid systems analysis using interval numerical methods. Proceedings of the 3rd International Workshop on Hybrid Systems. HSCC: Hybrid Systems - Computation and Control, LNCS, vol. 1790, 130–144.","short":"T.A. Henzinger, B. Horowitz, R. Majumdar, H. Wong Toi, in:, Proceedings of the 3rd International Workshop on Hybrid Systems, Springer, 2000, pp. 130–144."},"author":[{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Benjamin","last_name":"Horowitz","full_name":"Horowitz, Benjamin"},{"last_name":"Majumdar","full_name":"Majumdar, Ritankar","first_name":"Ritankar"},{"first_name":"Howard","last_name":"Wong Toi","full_name":"Wong Toi, Howard"}],"abstract":[{"lang":"eng","text":"Since hybrid embedded systems are pervasive and often safety-critical, guarantees about their correct performance are desirable. The hybrid systems model checker HyTech provides such guarantees and has successfully verified some systems. However, HyTech severely restricts the continuous dynamics of the system being analyzed and, therefore, often forces the use of prohibitively expensive discrete and polyhedral abstractions. We have designed a new algorithm, which is capable of directly verifying hybrid systems with general continuous dynamics, such as linear and nonlinear differential equations. The new algorithm conservatively overapproximates the reachable states of a hybrid automaton by using interval numerical methods. Interval numerical methods return sets of points that enclose the true result of numerical computation and, thus, avoid distortions due to the accumulation of round-off errors. We have implemented the new algorithm in a successor tool to HyTech called HyperTech. We consider three examples: a thermostat with delay, a two-tank water system, and an air-traffic collision avoidance protocol. HyperTech enables the direct, fully automatic analysis of these systems, which is also more accurate than the use of polyhedral abstractions."}],"date_created":"2018-12-11T12:09:04Z","conference":{"start_date":"2000-03-23","name":"HSCC: Hybrid Systems - Computation and Control","end_date":"2000-03-25","location":"Pittsburgh, PA, USA"},"date_published":"2000-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"publisher":"Springer","scopus_import":"1","page":"130 - 144","publication":"Proceedings of the 3rd International Workshop on Hybrid Systems","type":"conference","day":"01","status":"public","intvolume":"      1790"},{"citation":{"chicago":"Henzinger, Thomas A, Ritankar Majumdar, Freddy Mang, and Jean Raskin. “Abstract Interpretation of Game Properties.” In <i>Proceedings of the 7th International Symposium on Static Analysis</i>, 1824:220–39. Springer, 2000. <a href=\"https://doi.org/10.1007/978-3-540-45099-3_12\">https://doi.org/10.1007/978-3-540-45099-3_12</a>.","apa":"Henzinger, T. A., Majumdar, R., Mang, F., &#38; Raskin, J. (2000). Abstract interpretation of game properties. In <i>Proceedings of the 7th International Symposium on Static Analysis</i> (Vol. 1824, pp. 220–239). Santa Barbara, CA, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-540-45099-3_12\">https://doi.org/10.1007/978-3-540-45099-3_12</a>","ieee":"T. A. Henzinger, R. Majumdar, F. Mang, and J. Raskin, “Abstract interpretation of game properties,” in <i>Proceedings of the 7th International Symposium on Static Analysis</i>, Santa Barbara, CA, USA, 2000, vol. 1824, pp. 220–239.","short":"T.A. Henzinger, R. Majumdar, F. Mang, J. Raskin, in:, Proceedings of the 7th International Symposium on Static Analysis, Springer, 2000, pp. 220–239.","ista":"Henzinger TA, Majumdar R, Mang F, Raskin J. 2000. Abstract interpretation of game properties. Proceedings of the 7th International Symposium on Static Analysis. SAS: Static Analysis Symposium, LNCS, vol. 1824, 220–239.","ama":"Henzinger TA, Majumdar R, Mang F, Raskin J. Abstract interpretation of game properties. In: <i>Proceedings of the 7th International Symposium on Static Analysis</i>. Vol 1824. Springer; 2000:220-239. doi:<a href=\"https://doi.org/10.1007/978-3-540-45099-3_12\">10.1007/978-3-540-45099-3_12</a>","mla":"Henzinger, Thomas A., et al. “Abstract Interpretation of Game Properties.” <i>Proceedings of the 7th International Symposium on Static Analysis</i>, vol. 1824, Springer, 2000, pp. 220–39, doi:<a href=\"https://doi.org/10.1007/978-3-540-45099-3_12\">10.1007/978-3-540-45099-3_12</a>."},"publication_status":"published","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724"},{"first_name":"Ritankar","last_name":"Majumdar","full_name":"Majumdar, Ritankar"},{"first_name":"Freddy","full_name":"Mang, Freddy","last_name":"Mang"},{"last_name":"Raskin","full_name":"Raskin, Jean","first_name":"Jean"}],"abstract":[{"text":"We apply the theory of abstract interpretation to the verification of game properties for reactive systems. Unlike properties expressed in standard temporal logics, game properties can distinguish adversarial from collaborative relationships between the processes of a concurrent program, or the components of a parallel system. We consider two-player concurrent games –say, component vs. environment– and specify properties of such games –say, the component has a winning strategy to obtain a resource, no matter how the environment behaves– in the alternating-time μ-calculus (Aμ ). A sound abstraction of such a game must at the same time restrict the behaviors of the component and increase the behaviors of the environment: if a less powerful component can win against a more powerful environment, then surely the original component can win against the original environment.\r\nWe formalize the concrete semantics of a concurrent game in terms of controllable and uncontrollable predecessor predicates, which suffice for model checking all Aμ properties by applying boolean operations and iteration. We then define the abstract semantics of a concurrent game in terms of abstractions for the controllable and uncontrollable predecessor predicates. This allows us to give general characterizations for the soundness and completeness of abstract games with respect to Aμ properties. We also present a simple programming language for multi-process programs, and show how approximations of the maximal abstraction (w.r.t. Aμ properties) can be obtained from the program text. We apply the theory to two practical verification examples, a communication protocol developed at the Berkeley Wireless Research Center, and a protocol converter. In the wireless protocol, both the use of a game property for specification and the use of abstraction for automatic verification were instrumental to uncover a subtle bug.","lang":"eng"}],"article_processing_charge":"No","publist_id":"248","date_updated":"2023-04-18T12:49:56Z","volume":1824,"quality_controlled":"1","oa_version":"None","acknowledgement":"This research was supported in part by the DARPA (NASA) grant NAG2-1214, the DARPA (Wright-Patterson AFB) grant F33615-C-98-3614, the MARCO grant 98-DT-660, the ARO MURI grant DAAH-04-96-1-0341, and the NSF CAREER award CCR-9501708.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"isbn":["9783540676683"]},"extern":"1","_id":"4482","doi":"10.1007/978-3-540-45099-3_12","year":"2000","title":"Abstract interpretation of game properties","alternative_title":["LNCS"],"type":"conference","day":"01","status":"public","intvolume":"      1824","page":"220 - 239","publication":"Proceedings of the 7th International Symposium on Static Analysis","date_published":"2000-01-01T00:00:00Z","month":"01","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer","date_created":"2018-12-11T12:09:04Z","conference":{"end_date":"2000-07-06","location":"Santa Barbara, CA, USA","name":"SAS: Static Analysis Symposium","start_date":"2000-06-29"}},{"status":"public","author":[{"first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Shaz","full_name":"Qadeer, Shaz","last_name":"Qadeer"},{"full_name":"Rajamani, Sriram","last_name":"Rajamani","first_name":"Sriram"}],"abstract":[{"lang":"eng","text":"Model-checking algorithms can be used to verify, formally and automatically, if a low-level description of a design conforms with a high-level description. However, for designs with very large state spaces, prior to the application of an algorithm, the refinement-checking task needs to be decomposed into subtasks of manageable complexity. It is natural to decompose the task following the component structure of the design. However, an individual component often does not satisfy its requirements unless the component is put into the right context, which constrains the inputs to the component. Thus, in order to verify each component individually, we need to make assumptions about its inputs, which are provided by the other components of the design. This reasoning is circular: component A is verified under the assumption that context B behaves correctly, and symmetrically, B is verified assuming the correctness of A. The assume-guarantee paradigm provides a systematic theory and methodology for ensuring the soundness of the circular style of postulating and discharging assumptions in component-based reasoning.We give a tutorial introduction to the assume-guarantee paradigm for decomposing refinement-checking tasks. To illustrate the method, we step in detail through the formal verification of a processor pipeline against an instruction set architecture. In this example, the verification of a three-stage pipeline is broken up into three subtasks, one for each stage of the pipeline."}],"type":"conference","day":"01","citation":{"apa":"Henzinger, T. A., Qadeer, S., &#38; Rajamani, S. (2000). Decomposing refinement proofs using assume-guarantee reasoning. In <i>Proceedings of the 2000 International Conference on Computer-Aided Design</i> (pp. 245–252). San Jose, CA, USA: IEEE. <a href=\"https://doi.org/10.1109/ICCAD.2000.896481\">https://doi.org/10.1109/ICCAD.2000.896481</a>","ieee":"T. A. Henzinger, S. Qadeer, and S. Rajamani, “Decomposing refinement proofs using assume-guarantee reasoning,” in <i>Proceedings of the 2000 International Conference on Computer-Aided Design</i>, San Jose, CA, USA, 2000, pp. 245–252.","chicago":"Henzinger, Thomas A, Shaz Qadeer, and Sriram Rajamani. “Decomposing Refinement Proofs Using Assume-Guarantee Reasoning.” In <i>Proceedings of the 2000 International Conference on Computer-Aided Design</i>, 245–52. IEEE, 2000. <a href=\"https://doi.org/10.1109/ICCAD.2000.896481\">https://doi.org/10.1109/ICCAD.2000.896481</a>.","mla":"Henzinger, Thomas A., et al. “Decomposing Refinement Proofs Using Assume-Guarantee Reasoning.” <i>Proceedings of the 2000 International Conference on Computer-Aided Design</i>, IEEE, 2000, pp. 245–52, doi:<a href=\"https://doi.org/10.1109/ICCAD.2000.896481\">10.1109/ICCAD.2000.896481</a>.","ama":"Henzinger TA, Qadeer S, Rajamani S. Decomposing refinement proofs using assume-guarantee reasoning. In: <i>Proceedings of the 2000 International Conference on Computer-Aided Design</i>. IEEE; 2000:245-252. doi:<a href=\"https://doi.org/10.1109/ICCAD.2000.896481\">10.1109/ICCAD.2000.896481</a>","short":"T.A. Henzinger, S. Qadeer, S. Rajamani, in:, Proceedings of the 2000 International Conference on Computer-Aided Design, IEEE, 2000, pp. 245–252.","ista":"Henzinger TA, Qadeer S, Rajamani S. 2000. Decomposing refinement proofs using assume-guarantee reasoning. Proceedings of the 2000 International Conference on Computer-Aided Design. ICCAD: Computer-Aided Design, 245–252."},"publication_status":"published","oa_version":"None","quality_controlled":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"Supported in part by DARPA Information Technology Office, by the MARC0 Gigascale Silicon Research Center, and by the National Science Foundation. ","publication_identifier":{"isbn":["0780364457"]},"extern":"1","_id":"4483","article_processing_charge":"No","page":"245 - 252","publist_id":"249","date_updated":"2023-04-18T12:57:52Z","publication":"Proceedings of the 2000 International Conference on Computer-Aided Design","language":[{"iso":"eng"}],"title":"Decomposing refinement proofs using assume-guarantee reasoning","publisher":"IEEE","date_published":"2000-01-01T00:00:00Z","year":"2000","doi":"10.1109/ICCAD.2000.896481","month":"01","date_created":"2018-12-11T12:09:05Z","conference":{"end_date":"2000-11-09","location":"San Jose, CA, USA","name":"ICCAD: Computer-Aided Design","start_date":"2000-11-05"}},{"date_updated":"2023-04-13T13:48:08Z","publist_id":"215","volume":1872,"article_processing_charge":"No","_id":"4512","extern":"1","publication_identifier":{"isbn":["9783540678236"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","acknowledgement":"This research was supported in part by the DARPA grants NAG2-1214 and F33615-C-98-3614, and by the MARCO grant 98-DT-660.","oa_version":"None","quality_controlled":"1","publication_status":"published","citation":{"chicago":"Henzinger, Thomas A. “Masaccio: A Formal Model for Embedded Components.” In <i>Proceedings of the 1st International Conference on Theoretical Computer Science </i>, 1872:549–63. Springer, 2000. <a href=\"https://doi.org/10.1007/3-540-44929-9_38\">https://doi.org/10.1007/3-540-44929-9_38</a>.","ieee":"T. A. Henzinger, “Masaccio: A formal model for embedded components,” in <i>Proceedings of the 1st International Conference on Theoretical Computer Science </i>, Sendai, Japan, 2000, vol. 1872, pp. 549–563.","apa":"Henzinger, T. A. (2000). Masaccio: A formal model for embedded components. In <i>Proceedings of the 1st International Conference on Theoretical Computer Science </i> (Vol. 1872, pp. 549–563). Sendai, Japan: Springer. <a href=\"https://doi.org/10.1007/3-540-44929-9_38\">https://doi.org/10.1007/3-540-44929-9_38</a>","ista":"Henzinger TA. 2000. Masaccio: A formal model for embedded components. Proceedings of the 1st International Conference on Theoretical Computer Science . TCS: Theoretical Computer Science, LNCS, vol. 1872, 549–563.","short":"T.A. Henzinger, in:, Proceedings of the 1st International Conference on Theoretical Computer Science , Springer, 2000, pp. 549–563.","mla":"Henzinger, Thomas A. “Masaccio: A Formal Model for Embedded Components.” <i>Proceedings of the 1st International Conference on Theoretical Computer Science </i>, vol. 1872, Springer, 2000, pp. 549–63, doi:<a href=\"https://doi.org/10.1007/3-540-44929-9_38\">10.1007/3-540-44929-9_38</a>.","ama":"Henzinger TA. Masaccio: A formal model for embedded components. In: <i>Proceedings of the 1st International Conference on Theoretical Computer Science </i>. Vol 1872. Springer; 2000:549-563. doi:<a href=\"https://doi.org/10.1007/3-540-44929-9_38\">10.1007/3-540-44929-9_38</a>"},"abstract":[{"lang":"eng","text":"Masaccio is a formal model for hybrid dynamical systems which are built from atomic discrete components (difference equations) and atomic continuous components (differential equations) by parallel and serial composition, arbitrarily nested. Each system component consists of an interface, which determines the possible ways of using the component, and a set of executions, which define the possible behaviors of the component in real time.\r\nVersion 1.0 (May 2000).\r\n"}],"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","first_name":"Thomas A"}],"alternative_title":["LNCS"],"doi":"10.1007/3-540-44929-9_38","year":"2000","title":"Masaccio: A formal model for embedded components","publication":"Proceedings of the 1st International Conference on Theoretical Computer Science ","page":"549 - 563","day":"01","type":"conference","intvolume":"      1872","status":"public","conference":{"name":"TCS: Theoretical Computer Science","end_date":"2000-08-19","location":"Sendai, Japan","start_date":"2000-08-17"},"date_created":"2018-12-11T12:09:14Z","month":"01","date_published":"2000-01-01T00:00:00Z","publisher":"Springer","scopus_import":"1","language":[{"iso":"eng"}]},{"alternative_title":["NATO ASI Series F: Computer and Systems Sciences"],"title":"The theory of hybrid automata","doi":"10.1007/978-3-642-59615-5","year":"2000","quality_controlled":"1","oa_version":"None","acknowledgement":"This research was supported in part by the Office of Naval Research Young Investigator award N00014-95-1-0520, by the National Science Foundation CAREER award CCR-9501708, by the National Science Foundation grant CR9504469, by the Air Force Office of Scientific Research contract F49620-93-1-0056, by the Army Research Office MURI grant DAAH-04-96-1-0341, by the Advanced Research Projects Agency grant NAG2-892, and by the Semiconductor Research Corporation contract 96-DC-324.036. ","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","publication_identifier":{"isbn":["9783642596155"]},"_id":"4513","article_processing_charge":"No","publist_id":"216","volume":170,"date_updated":"2023-04-18T12:37:17Z","editor":[{"first_name":"M.","full_name":"Inan, M.","last_name":"Inan"},{"full_name":"Kurshan, Robert","last_name":"Kurshan","first_name":"Robert"}],"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"}],"abstract":[{"text":"A hybrid automaton is a formal model for a mixed discrete-continuous system. We classify hybrid automata according to what questions about their behavior can be answered algorithmically. The classification reveals structure on mixed discrete-continuous state spaces that was previously studied on purely discrete state spaces only. In particular, various classes of hybrid automata induce finitary trace equivalence (or similarity, or bisimilarity) relations on an uncountable state space, thus permitting the application of various model-checking techniques that were originally developed for finitestate systems. ","lang":"eng"}],"citation":{"ieee":"T. A. Henzinger, “The theory of hybrid automata,” in <i>Verification of Digital and Hybrid Systems</i>, vol. 170, M. Inan and R. Kurshan, Eds. Springer, 2000, pp. 265–292.","apa":"Henzinger, T. A. (2000). The theory of hybrid automata. In M. Inan &#38; R. Kurshan (Eds.), <i>Verification of Digital and Hybrid Systems</i> (Vol. 170, pp. 265–292). Springer. <a href=\"https://doi.org/10.1007/978-3-642-59615-5\">https://doi.org/10.1007/978-3-642-59615-5</a>","chicago":"Henzinger, Thomas A. “The Theory of Hybrid Automata.” In <i>Verification of Digital and Hybrid Systems</i>, edited by M. Inan and Robert Kurshan, 170:265–92. Springer, 2000. <a href=\"https://doi.org/10.1007/978-3-642-59615-5\">https://doi.org/10.1007/978-3-642-59615-5</a>.","ama":"Henzinger TA. The theory of hybrid automata. In: Inan M, Kurshan R, eds. <i>Verification of Digital and Hybrid Systems</i>. Vol 170. Springer; 2000:265-292. doi:<a href=\"https://doi.org/10.1007/978-3-642-59615-5\">10.1007/978-3-642-59615-5</a>","mla":"Henzinger, Thomas A. “The Theory of Hybrid Automata.” <i>Verification of Digital and Hybrid Systems</i>, edited by M. Inan and Robert Kurshan, vol. 170, Springer, 2000, pp. 265–92, doi:<a href=\"https://doi.org/10.1007/978-3-642-59615-5\">10.1007/978-3-642-59615-5</a>.","short":"T.A. Henzinger, in:, M. Inan, R. Kurshan (Eds.), Verification of Digital and Hybrid Systems, Springer, 2000, pp. 265–292.","ista":"Henzinger TA. 2000.The theory of hybrid automata. In: Verification of Digital and Hybrid Systems. NATO ASI Series F: Computer and Systems Sciences, vol. 170, 265–292."},"publication_status":"published","date_created":"2018-12-11T12:09:14Z","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Springer","date_published":"2000-04-28T00:00:00Z","month":"04","page":"265 - 292","publication":"Verification of Digital and Hybrid Systems","status":"public","intvolume":"       170","type":"book_chapter","day":"28"}]