[{"month":"02","title":"Is Wright’s shifting balance process important in evolution?","date_updated":"2023-04-19T12:48:29Z","date_published":"2000-02-01T00:00:00Z","article_processing_charge":"No","page":"306 - 317","publication":"Evolution; International Journal of Organic Evolution","date_created":"2018-12-11T12:07:57Z","external_id":{"pmid":["10937209"]},"_id":"4269","volume":54,"issue":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 54","extern":"1","publication_identifier":{"issn":["0014-3820"]},"author":[{"full_name":"Coyne, Jerry","last_name":"Coyne","first_name":"Jerry"},{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","last_name":"Barton","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240"},{"full_name":"Turelli, Michael","last_name":"Turelli","first_name":"Michael"}],"year":"2000","oa_version":"None","doi":"10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2","day":"01","publisher":"Wiley-Blackwell","language":[{"iso":"eng"}],"pmid":1,"status":"public","publication_status":"published","publist_id":"1821","quality_controlled":"1","type":"journal_article","citation":{"apa":"Coyne, J., Barton, N. H., & Turelli, M. (2000). Is Wright’s shifting balance process important in evolution? Evolution; International Journal of Organic Evolution. Wiley-Blackwell. https://doi.org/10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2","short":"J. Coyne, N.H. Barton, M. Turelli, Evolution; International Journal of Organic Evolution 54 (2000) 306–317.","ieee":"J. Coyne, N. H. Barton, and M. Turelli, “Is Wright’s shifting balance process important in evolution?,” Evolution; International Journal of Organic Evolution, vol. 54, no. 1. Wiley-Blackwell, pp. 306–317, 2000.","ama":"Coyne J, Barton NH, Turelli M. Is Wright’s shifting balance process important in evolution? Evolution; International Journal of Organic Evolution. 2000;54(1):306-317. doi:10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2","chicago":"Coyne, Jerry, Nicholas H Barton, and Michael Turelli. “Is Wright’s Shifting Balance Process Important in Evolution?” Evolution; International Journal of Organic Evolution. Wiley-Blackwell, 2000. https://doi.org/10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2.","mla":"Coyne, Jerry, et al. “Is Wright’s Shifting Balance Process Important in Evolution?” Evolution; International Journal of Organic Evolution, vol. 54, no. 1, Wiley-Blackwell, 2000, pp. 306–17, doi:10.1554/0014-3820(2000)054[0306:IWSSBP]2.0.CO;2.","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."},"article_type":"original"},{"oa_version":"None","doi":"10.1093/genetics/155.2.981","day":"01","publisher":"Genetics Society of America","publication_identifier":{"issn":["0016-6731"]},"author":[{"first_name":"Nicolas","full_name":"Galtier, Nicolas","last_name":"Galtier"},{"full_name":"Depaulis, Frantz","last_name":"Depaulis","first_name":"Frantz"},{"full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"year":"2000","citation":{"ieee":"N. Galtier, F. Depaulis, and N. H. Barton, “Detecting bottlenecks and selective sweeps from DNA sequence polymorphism,” Genetics, vol. 155, no. 2. Genetics Society of America, pp. 981–987, 2000.","apa":"Galtier, N., Depaulis, F., & Barton, N. H. (2000). Detecting bottlenecks and selective sweeps from DNA sequence polymorphism. Genetics. Genetics Society of America. https://doi.org/10.1093/genetics/155.2.981","short":"N. Galtier, F. Depaulis, N.H. Barton, Genetics 155 (2000) 981–987.","mla":"Galtier, Nicolas, et al. “Detecting Bottlenecks and Selective Sweeps from DNA Sequence Polymorphism.” Genetics, vol. 155, no. 2, Genetics Society of America, 2000, pp. 981–87, doi:10.1093/genetics/155.2.981.","ista":"Galtier N, Depaulis F, Barton NH. 2000. Detecting bottlenecks and selective sweeps from DNA sequence polymorphism. Genetics. 155(2), 981–987.","chicago":"Galtier, Nicolas, Frantz Depaulis, and Nicholas H Barton. “Detecting Bottlenecks and Selective Sweeps from DNA Sequence Polymorphism.” Genetics. Genetics Society of America, 2000. https://doi.org/10.1093/genetics/155.2.981.","ama":"Galtier N, Depaulis F, Barton NH. Detecting bottlenecks and selective sweeps from DNA sequence polymorphism. Genetics. 2000;155(2):981-987. doi:10.1093/genetics/155.2.981"},"type":"journal_article","article_type":"original","language":[{"iso":"eng"}],"status":"public","pmid":1,"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."}],"publication_status":"published","publist_id":"1822","page":"981 - 987","publication":"Genetics","date_created":"2018-12-11T12:07:57Z","external_id":{"pmid":["10835415"]},"_id":"4270","month":"06","title":"Detecting bottlenecks and selective sweeps from DNA sequence polymorphism","date_updated":"2023-04-19T14:03:56Z","date_published":"2000-06-01T00:00:00Z","article_processing_charge":"No","extern":"1","volume":155,"main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1461106/"}],"issue":"2","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 155","oa":1},{"publication_identifier":{"issn":["0016-6723"]},"author":[{"last_name":"Barton","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Shpak, Max","last_name":"Shpak","first_name":"Max"}],"year":"2000","oa_version":"None","doi":"10.1017/S0016672399004334","day":"01","publisher":"Cambridge University Press","language":[{"iso":"eng"}],"pmid":1,"status":"public","abstract":[{"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 β << 1, fitness is reduced for a wide range of intermediate genotypes; where β >> 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 β > 1, gene number is systematically overestimated and, conversely, when β < 1, it is underestimated.\r\n","lang":"eng"}],"publication_status":"published","publist_id":"1819","quality_controlled":"1","citation":{"chicago":"Barton, Nicholas H, and Max Shpak. “The Effects of Epistasis on the Structure of Hybrid Zones.” Genetical Research. Cambridge University Press, 2000. https://doi.org/10.1017/S0016672399004334.","ama":"Barton NH, Shpak M. The effects of epistasis on the structure of hybrid zones. Genetical Research. 2000;75(2):179-198. doi:10.1017/S0016672399004334","mla":"Barton, Nicholas H., and Max Shpak. “The Effects of Epistasis on the Structure of Hybrid Zones.” Genetical Research, vol. 75, no. 2, Cambridge University Press, 2000, pp. 179–98, doi:10.1017/S0016672399004334.","ista":"Barton NH, Shpak M. 2000. The effects of epistasis on the structure of hybrid zones. Genetical Research. 75(2), 179–198.","short":"N.H. Barton, M. Shpak, Genetical Research 75 (2000) 179–198.","apa":"Barton, N. H., & Shpak, M. (2000). The effects of epistasis on the structure of hybrid zones. Genetical Research. Cambridge University Press. https://doi.org/10.1017/S0016672399004334","ieee":"N. H. Barton and M. Shpak, “The effects of epistasis on the structure of hybrid zones,” Genetical Research, vol. 75, no. 2. Cambridge University Press, pp. 179–198, 2000."},"type":"journal_article","article_type":"original","month":"04","title":"The effects of epistasis on the structure of hybrid zones","date_updated":"2023-04-19T09:58:36Z","date_published":"2000-04-01T00:00:00Z","article_processing_charge":"No","page":"179 - 198","publication":"Genetical Research","date_created":"2018-12-11T12:07:58Z","external_id":{"pmid":["10816975"]},"_id":"4271","volume":75,"issue":"2","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.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 75","scopus_import":"1","extern":"1"},{"scopus_import":"1","extern":"1","volume":57,"issue":"3","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 57","page":"249 - 263","publication":"Theoretical Population Biology","date_created":"2018-12-11T12:07:58Z","external_id":{"pmid":["10828217"]},"_id":"4272","month":"05","date_updated":"2023-04-19T12:36:39Z","title":"The stability of symmetrical solutions to polygenic models","date_published":"2000-05-01T00:00:00Z","article_processing_charge":"No","type":"journal_article","citation":{"chicago":"Barton, Nicholas H, and Max Shpak. “The Stability of Symmetrical Solutions to Polygenic Models.” Theoretical Population Biology. Academic Press, 2000. https://doi.org/10.1006/tpbi.2000.1455.","ama":"Barton NH, Shpak M. The stability of symmetrical solutions to polygenic models. Theoretical Population Biology. 2000;57(3):249-263. doi:10.1006/tpbi.2000.1455","ista":"Barton NH, Shpak M. 2000. The stability of symmetrical solutions to polygenic models. Theoretical Population Biology. 57(3), 249–263.","mla":"Barton, Nicholas H., and Max Shpak. “The Stability of Symmetrical Solutions to Polygenic Models.” Theoretical Population Biology, vol. 57, no. 3, Academic Press, 2000, pp. 249–63, doi:10.1006/tpbi.2000.1455.","apa":"Barton, N. H., & Shpak, M. (2000). The stability of symmetrical solutions to polygenic models. Theoretical Population Biology. Academic Press. https://doi.org/10.1006/tpbi.2000.1455","short":"N.H. Barton, M. Shpak, Theoretical Population Biology 57 (2000) 249–263.","ieee":"N. H. Barton and M. Shpak, “The stability of symmetrical solutions to polygenic models,” Theoretical Population Biology, vol. 57, no. 3. Academic Press, pp. 249–263, 2000."},"article_type":"original","language":[{"iso":"eng"}],"pmid":1,"status":"public","publication_status":"published","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."}],"publist_id":"1820","quality_controlled":"1","oa_version":"None","doi":"10.1006/tpbi.2000.1455","day":"01","publisher":"Academic Press","publication_identifier":{"issn":["0040-5809"]},"author":[{"first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","last_name":"Barton","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H"},{"full_name":"Shpak, Max","last_name":"Shpak","first_name":"Max"}],"year":"2000"},{"extern":"1","scopus_import":"1","intvolume":" 22","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","issue":"12","volume":22,"_id":"4273","external_id":{"pmid":["11084623"]},"date_created":"2018-12-11T12:07:58Z","publication":"BioEssays","page":"1075 - 1084","article_processing_charge":"No","date_published":"2000-12-01T00:00:00Z","title":"Limits to natural selection","date_updated":"2023-04-19T09:49:52Z","month":"12","article_type":"original","type":"journal_article","citation":{"ista":"Barton NH, Partridge L. 2000. Limits to natural selection. BioEssays. 22(12), 1075–1084.","mla":"Barton, Nicholas H., and Linda Partridge. “Limits to Natural Selection.” BioEssays, vol. 22, no. 12, Wiley-Blackwell, 2000, pp. 1075–84, doi:10.1002/1521-1878(200012)22:12<1075::AID-BIES5>3.0.CO;2-M.","ama":"Barton NH, Partridge L. Limits to natural selection. BioEssays. 2000;22(12):1075-1084. doi:10.1002/1521-1878(200012)22:12<1075::AID-BIES5>3.0.CO;2-M","chicago":"Barton, Nicholas H, and Linda Partridge. “Limits to Natural Selection.” BioEssays. Wiley-Blackwell, 2000. https://doi.org/10.1002/1521-1878(200012)22:12<1075::AID-BIES5>3.0.CO;2-M.","ieee":"N. H. Barton and L. Partridge, “Limits to natural selection,” BioEssays, vol. 22, no. 12. Wiley-Blackwell, pp. 1075–1084, 2000.","short":"N.H. Barton, L. Partridge, BioEssays 22 (2000) 1075–1084.","apa":"Barton, N. H., & Partridge, L. (2000). Limits to natural selection. BioEssays. Wiley-Blackwell. https://doi.org/10.1002/1521-1878(200012)22:12<1075::AID-BIES5>3.0.CO;2-M"},"quality_controlled":"1","publist_id":"1818","abstract":[{"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.","lang":"eng"}],"publication_status":"published","pmid":1,"status":"public","language":[{"iso":"eng"}],"publisher":"Wiley-Blackwell","day":"01","doi":"10.1002/1521-1878(200012)22:12<1075::AID-BIES5>3.0.CO;2-M","oa_version":"None","year":"2000","author":[{"last_name":"Barton","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Linda","last_name":"Partridge","full_name":"Partridge, Linda"}],"publication_identifier":{"issn":["0265-9247"]}},{"article_processing_charge":"No","date_published":"2000-11-29T00:00:00Z","date_updated":"2023-04-19T09:35:31Z","title":"Genetic hitchhiking","month":"11","_id":"4274","external_id":{"pmid":["11127900"]},"date_created":"2018-12-11T12:07:59Z","publication":"Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences","page":"1553 - 1562","oa":1,"intvolume":" 355","issue":"1403","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.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1692896/"}],"volume":355,"extern":"1","scopus_import":"1","year":"2000","author":[{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","last_name":"Barton","orcid":"0000-0002-8548-5240","full_name":"Barton, Nicholas H"}],"publication_identifier":{"issn":["0962-8436"]},"publisher":"Royal Society of London","day":"29","doi":"10.1098/rstb.2000.0716","oa_version":"None","quality_controlled":"1","publist_id":"1815","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"}],"publication_status":"published","pmid":1,"status":"public","language":[{"iso":"eng"}],"type":"journal_article","citation":{"apa":"Barton, N. H. (2000). Genetic hitchhiking. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences. Royal Society of London. https://doi.org/10.1098/rstb.2000.0716","short":"N.H. Barton, Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences 355 (2000) 1553–1562.","ieee":"N. H. Barton, “Genetic hitchhiking,” Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences, vol. 355, no. 1403. Royal Society of London, pp. 1553–1562, 2000.","chicago":"Barton, Nicholas H. “Genetic Hitchhiking.” Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences. Royal Society of London, 2000. https://doi.org/10.1098/rstb.2000.0716.","ama":"Barton NH. Genetic hitchhiking. Philosophical Transactions of the Royal Society of London Series B, Biological Sciences. 2000;355(1403):1553-1562. doi:10.1098/rstb.2000.0716","mla":"Barton, Nicholas H. “Genetic Hitchhiking.” Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences, vol. 355, no. 1403, Royal Society of London, 2000, pp. 1553–62, doi:10.1098/rstb.2000.0716.","ista":"Barton NH. 2000. Genetic hitchhiking. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences. 355(1403), 1553–1562."}},{"language":[{"iso":"eng"}],"status":"public","publication_status":"published","publist_id":"1816","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","citation":{"ieee":"N. H. Barton, “Differentiation,” in Encyclopedia of Biodiversity, Academic Press, 2000, pp. 85–94.","apa":"Barton, N. H. (2000). Differentiation. In Encyclopedia of Biodiversity (pp. 85–94). Academic Press. https://doi.org/10.1016/B0-12-226865-2/00070-5","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.” Encyclopedia of Biodiversity, Academic Press, 2000, pp. 85–94, doi:10.1016/B0-12-226865-2/00070-5.","chicago":"Barton, Nicholas H. “Differentiation.” In Encyclopedia of Biodiversity, 85–94. Academic Press, 2000. https://doi.org/10.1016/B0-12-226865-2/00070-5.","ama":"Barton NH. Differentiation. In: Encyclopedia of Biodiversity. Academic Press; 2000:85-94. doi:10.1016/B0-12-226865-2/00070-5"},"type":"book_chapter","extern":"1","month":"10","date_updated":"2023-04-19T09:39:55Z","title":"Differentiation","publication_identifier":{"isbn":["9780122268656"]},"author":[{"full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H"}],"date_published":"2000-10-01T00:00:00Z","year":"2000","article_processing_charge":"No","oa_version":"None","page":"85 - 94","publication":"Encyclopedia of Biodiversity","doi":"10.1016/B0-12-226865-2/00070-5","date_created":"2018-12-11T12:07:59Z","day":"01","publisher":"Academic Press","_id":"4275"},{"type":"review","citation":{"short":"N.H. Barton, Genetics Research 75 (2000) 371–373.","apa":"Barton, N. H. (2000). Population genetics of multiple loci. Genetics Research. Cambridge University Press. https://doi.org/10.1017/S0016672300239220","ieee":"N. H. Barton, “Population genetics of multiple loci,” Genetics Research, vol. 75, no. 3. Cambridge University Press, pp. 371–373, 2000.","ama":"Barton NH. Population genetics of multiple loci. Genetics Research. 2000;75(3):371-373. doi:10.1017/S0016672300239220","chicago":"Barton, Nicholas H. “Population Genetics of Multiple Loci.” Genetics Research. Cambridge University Press, 2000. https://doi.org/10.1017/S0016672300239220.","mla":"Barton, Nicholas H. “Population Genetics of Multiple Loci.” Genetics Research, vol. 75, no. 3, Cambridge University Press, 2000, pp. 371–73, doi:10.1017/S0016672300239220.","ista":"Barton NH. 2000. Population genetics of multiple loci. Genetics Research. 75(3), 371–373."},"extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","issue":"3","intvolume":" 75","quality_controlled":"1","language":[{"iso":"eng"}],"status":"public","publication_status":"published","volume":75,"publist_id":"1814","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","day":"01","publisher":"Cambridge University Press","_id":"4276","page":"371 - 373","oa_version":"None","publication":"Genetics Research","doi":"10.1017/S0016672300239220","author":[{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","last_name":"Barton"}],"date_published":"2000-06-01T00:00:00Z","article_processing_charge":"No","year":"2000","month":"06","title":"Population genetics of multiple loci","date_updated":"2023-04-18T15:01:01Z","publication_identifier":{"issn":["0016-6723"]}},{"publication":"Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","page":"299 - 314","_id":"4433","date_created":"2018-12-11T12:08:50Z","title":"Fair bisimulation","date_updated":"2023-04-18T13:11:07Z","month":"01","article_processing_charge":"No","date_published":"2000-01-01T00:00:00Z","extern":"1","scopus_import":"1","volume":1785,"alternative_title":["LNCS"],"intvolume":" 1785","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","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.","doi":"10.1007/3-540-46419-0_21","oa_version":"None","publisher":"Springer","day":"01","publication_identifier":{"isbn":["9783540672821"]},"year":"2000","conference":{"start_date":"2000-03-25","location":"Berlin, Germany","end_date":"2000-04-02","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems"},"author":[{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"first_name":"Sriram","last_name":"Rajamani","full_name":"Rajamani, Sriram"}],"type":"conference","citation":{"chicago":"Henzinger, Thomas A, and Sriram Rajamani. “Fair Bisimulation.” In Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 1785:299–314. Springer, 2000. https://doi.org/10.1007/3-540-46419-0_21.","ama":"Henzinger TA, Rajamani S. Fair bisimulation. In: Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Vol 1785. Springer; 2000:299-314. doi:10.1007/3-540-46419-0_21","mla":"Henzinger, Thomas A., and Sriram Rajamani. “Fair Bisimulation.” Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, vol. 1785, Springer, 2000, pp. 299–314, doi:10.1007/3-540-46419-0_21.","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.","apa":"Henzinger, T. A., & Rajamani, S. (2000). Fair bisimulation. In Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (Vol. 1785, pp. 299–314). Berlin, Germany: Springer. https://doi.org/10.1007/3-540-46419-0_21","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.","ieee":"T. A. Henzinger and S. Rajamani, “Fair bisimulation,” in Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Berlin, Germany, 2000, vol. 1785, pp. 299–314."},"publist_id":"297","abstract":[{"lang":"eng","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."}],"publication_status":"published","status":"public","language":[{"iso":"eng"}],"quality_controlled":"1"},{"publication":"Proceedings of the 3rd International Workshop on Hybrid Systems","page":"145 - 159","_id":"4434","date_created":"2018-12-11T12:08:50Z","title":"Robust undecidability of timed and hybrid systems","date_updated":"2023-04-18T13:16:13Z","month":"01","date_published":"2000-01-01T00:00:00Z","article_processing_charge":"No","scopus_import":"1","extern":"1","volume":1790,"alternative_title":["LNCS"],"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","intvolume":" 1790","doi":"10.1007/3-540-46430-1_15","oa_version":"None","publisher":"Springer","day":"01","publication_identifier":{"isbn":["9783540672593"]},"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"first_name":"Jean","full_name":"Raskin, Jean","last_name":"Raskin"}],"year":"2000","conference":{"start_date":"2000-03-23","location":"Pittsburgh, PA, USA","end_date":"2000-03-25","name":"HSCC: Hybrid Systems - Computation and Control"},"type":"conference","citation":{"chicago":"Henzinger, Thomas A, and Jean Raskin. “Robust Undecidability of Timed and Hybrid Systems.” In Proceedings of the 3rd International Workshop on Hybrid Systems, 1790:145–59. Springer, 2000. https://doi.org/10.1007/3-540-46430-1_15.","ama":"Henzinger TA, Raskin J. Robust undecidability of timed and hybrid systems. In: Proceedings of the 3rd International Workshop on Hybrid Systems. Vol 1790. Springer; 2000:145-159. doi:10.1007/3-540-46430-1_15","mla":"Henzinger, Thomas A., and Jean Raskin. “Robust Undecidability of Timed and Hybrid Systems.” Proceedings of the 3rd International Workshop on Hybrid Systems, vol. 1790, Springer, 2000, pp. 145–59, doi:10.1007/3-540-46430-1_15.","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.","short":"T.A. Henzinger, J. Raskin, in:, Proceedings of the 3rd International Workshop on Hybrid Systems, Springer, 2000, pp. 145–159.","apa":"Henzinger, T. A., & Raskin, J. (2000). Robust undecidability of timed and hybrid systems. In Proceedings of the 3rd International Workshop on Hybrid Systems (Vol. 1790, pp. 145–159). Pittsburgh, PA, USA: Springer. https://doi.org/10.1007/3-540-46430-1_15","ieee":"T. A. Henzinger and J. Raskin, “Robust undecidability of timed and hybrid systems,” in Proceedings of the 3rd International Workshop on Hybrid Systems, Pittsburgh, PA, USA, 2000, vol. 1790, pp. 145–159."},"publication_status":"published","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"}],"publist_id":"298","language":[{"iso":"eng"}],"status":"public","quality_controlled":"1"},{"oa_version":"None","doi":"10.1007/3-540-46419-0_11","day":"01","publisher":"Springer","publication_identifier":{"isbn":["9783540672821"]},"year":"2000","conference":{"location":"Berlin, Germany","start_date":"2000-03-25","end_date":"2000-04-02","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems"},"author":[{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"full_name":"Majumdar, Ritankar","last_name":"Majumdar","first_name":"Ritankar"}],"type":"conference","citation":{"ama":"Henzinger TA, Majumdar R. Symbolic model checking for rectangular hybrid systems. In: Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Vol 1785. Springer; 2000:142-156. doi:10.1007/3-540-46419-0_11","chicago":"Henzinger, Thomas A, and Ritankar Majumdar. “Symbolic Model Checking for Rectangular Hybrid Systems.” In Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, 1785:142–56. Springer, 2000. https://doi.org/10.1007/3-540-46419-0_11.","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.","mla":"Henzinger, Thomas A., and Ritankar Majumdar. “Symbolic Model Checking for Rectangular Hybrid Systems.” Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, vol. 1785, Springer, 2000, pp. 142–56, doi:10.1007/3-540-46419-0_11.","apa":"Henzinger, T. A., & Majumdar, R. (2000). Symbolic model checking for rectangular hybrid systems. In Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (Vol. 1785, pp. 142–156). Berlin, Germany: Springer. https://doi.org/10.1007/3-540-46419-0_11","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.","ieee":"T. A. Henzinger and R. Majumdar, “Symbolic model checking for rectangular hybrid systems,” in Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Berlin, Germany, 2000, vol. 1785, pp. 142–156."},"status":"public","language":[{"iso":"eng"}],"publist_id":"293","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"}],"publication_status":"published","quality_controlled":"1","page":"142 - 156","publication":"Proceedings of the 6th International Conference on Tools and Algorithms for the Construction and Analysis of Systems","date_created":"2018-12-11T12:08:50Z","_id":"4435","month":"01","title":"Symbolic model checking for rectangular hybrid systems","date_updated":"2023-04-18T13:08:09Z","article_processing_charge":"No","date_published":"2000-01-01T00:00:00Z","extern":"1","scopus_import":"1","alternative_title":["LNCS"],"volume":1785,"intvolume":" 1785","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"},{"doi":"10.1007/3-540-46541-3_2","oa_version":"None","publisher":"Springer","day":"01","publication_identifier":{"isbn":["9783540671411"]},"conference":{"start_date":"2000-02-17","location":"Lille, France","end_date":"2000-02-19","name":"STACS: Theoretical Aspects of Computer Science"},"year":"2000","author":[{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"last_name":"Majumdar","full_name":"Majumdar, Ritankar","first_name":"Ritankar"}],"citation":{"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.","mla":"Henzinger, Thomas A., and Ritankar Majumdar. “A Classification of Symbolic Transition Systems.” Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, vol. 1770, Springer, 2000, pp. 13–34, doi:10.1007/3-540-46541-3_2.","chicago":"Henzinger, Thomas A, and Ritankar Majumdar. “A Classification of Symbolic Transition Systems.” In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, 1770:13–34. Springer, 2000. https://doi.org/10.1007/3-540-46541-3_2.","ama":"Henzinger TA, Majumdar R. A classification of symbolic transition systems. In: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science. Vol 1770. Springer; 2000:13-34. doi:10.1007/3-540-46541-3_2","ieee":"T. A. Henzinger and R. Majumdar, “A classification of symbolic transition systems,” in Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, 2000, vol. 1770, pp. 13–34.","apa":"Henzinger, T. A., & Majumdar, R. (2000). A classification of symbolic transition systems. In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (Vol. 1770, pp. 13–34). Lille, France: Springer. https://doi.org/10.1007/3-540-46541-3_2","short":"T.A. Henzinger, R. Majumdar, in:, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Springer, 2000, pp. 13–34."},"type":"conference","publist_id":"292","abstract":[{"lang":"eng","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."}],"publication_status":"published","status":"public","language":[{"iso":"eng"}],"quality_controlled":"1","publication":"Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science","page":"13 - 34","_id":"4439","date_created":"2018-12-11T12:08:51Z","title":"A classification of symbolic transition systems","date_updated":"2023-04-18T13:02:39Z","month":"01","article_processing_charge":"No","date_published":"2000-01-01T00:00:00Z","extern":"1","scopus_import":"1","volume":1770,"alternative_title":["LNCS"],"intvolume":" 1770","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"},{"citation":{"ieee":"T. A. Henzinger, B. Horowitz, R. Majumdar, and H. Wong Toi, “Beyond HyTech: Hybrid systems analysis using interval numerical methods,” in Proceedings of the 3rd International Workshop on Hybrid Systems, Pittsburgh, PA, USA, 2000, vol. 1790, pp. 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.","apa":"Henzinger, T. A., Horowitz, B., Majumdar, R., & Wong Toi, H. (2000). Beyond HyTech: Hybrid systems analysis using interval numerical methods. In Proceedings of the 3rd International Workshop on Hybrid Systems (Vol. 1790, pp. 130–144). Pittsburgh, PA, USA: Springer. https://doi.org/10.1007/3-540-46430-1_14","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.","mla":"Henzinger, Thomas A., et al. “Beyond HyTech: Hybrid Systems Analysis Using Interval Numerical Methods.” Proceedings of the 3rd International Workshop on Hybrid Systems, vol. 1790, Springer, 2000, pp. 130–44, doi:10.1007/3-540-46430-1_14.","chicago":"Henzinger, Thomas A, Benjamin Horowitz, Ritankar Majumdar, and Howard Wong Toi. “Beyond HyTech: Hybrid Systems Analysis Using Interval Numerical Methods.” In Proceedings of the 3rd International Workshop on Hybrid Systems, 1790:130–44. Springer, 2000. https://doi.org/10.1007/3-540-46430-1_14.","ama":"Henzinger TA, Horowitz B, Majumdar R, Wong Toi H. Beyond HyTech: Hybrid systems analysis using interval numerical methods. In: Proceedings of the 3rd International Workshop on Hybrid Systems. Vol 1790. Springer; 2000:130-144. doi:10.1007/3-540-46430-1_14"},"type":"conference","status":"public","language":[{"iso":"eng"}],"publist_id":"247","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."}],"publication_status":"published","quality_controlled":"1","oa_version":"None","doi":"10.1007/3-540-46430-1_14","day":"01","publisher":"Springer","publication_identifier":{"isbn":["9783540672593"]},"year":"2000","conference":{"name":"HSCC: Hybrid Systems - Computation and Control","end_date":"2000-03-25","start_date":"2000-03-23","location":"Pittsburgh, PA, USA"},"author":[{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"last_name":"Horowitz","full_name":"Horowitz, Benjamin","first_name":"Benjamin"},{"first_name":"Ritankar","last_name":"Majumdar","full_name":"Majumdar, Ritankar"},{"full_name":"Wong Toi, Howard","last_name":"Wong Toi","first_name":"Howard"}],"extern":"1","scopus_import":"1","alternative_title":["LNCS"],"volume":1790,"intvolume":" 1790","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.","page":"130 - 144","publication":"Proceedings of the 3rd International Workshop on Hybrid Systems","date_created":"2018-12-11T12:09:04Z","_id":"4481","month":"01","date_updated":"2023-04-18T12:44:52Z","title":"Beyond HyTech: Hybrid systems analysis using interval numerical methods","article_processing_charge":"No","date_published":"2000-01-01T00:00:00Z"},{"date_updated":"2023-04-18T12:49:56Z","title":"Abstract interpretation of game properties","month":"01","article_processing_charge":"No","date_published":"2000-01-01T00:00:00Z","publication":"Proceedings of the 7th International Symposium on Static Analysis","page":"220 - 239","_id":"4482","date_created":"2018-12-11T12:09:04Z","volume":1824,"alternative_title":["LNCS"],"intvolume":" 1824","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","extern":"1","scopus_import":"1","publication_identifier":{"isbn":["9783540676683"]},"year":"2000","conference":{"start_date":"2000-06-29","location":"Santa Barbara, CA, USA","end_date":"2000-07-06","name":"SAS: Static Analysis Symposium"},"author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"last_name":"Majumdar","full_name":"Majumdar, Ritankar","first_name":"Ritankar"},{"first_name":"Freddy","full_name":"Mang, Freddy","last_name":"Mang"},{"last_name":"Raskin","full_name":"Raskin, Jean","first_name":"Jean"}],"doi":"10.1007/978-3-540-45099-3_12","oa_version":"None","publisher":"Springer","day":"01","publist_id":"248","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"}],"publication_status":"published","status":"public","language":[{"iso":"eng"}],"quality_controlled":"1","citation":{"apa":"Henzinger, T. A., Majumdar, R., Mang, F., & Raskin, J. (2000). Abstract interpretation of game properties. In Proceedings of the 7th International Symposium on Static Analysis (Vol. 1824, pp. 220–239). Santa Barbara, CA, USA: Springer. https://doi.org/10.1007/978-3-540-45099-3_12","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.","ieee":"T. A. Henzinger, R. Majumdar, F. Mang, and J. Raskin, “Abstract interpretation of game properties,” in Proceedings of the 7th International Symposium on Static Analysis, Santa Barbara, CA, USA, 2000, vol. 1824, pp. 220–239.","ama":"Henzinger TA, Majumdar R, Mang F, Raskin J. Abstract interpretation of game properties. In: Proceedings of the 7th International Symposium on Static Analysis. Vol 1824. Springer; 2000:220-239. doi:10.1007/978-3-540-45099-3_12","chicago":"Henzinger, Thomas A, Ritankar Majumdar, Freddy Mang, and Jean Raskin. “Abstract Interpretation of Game Properties.” In Proceedings of the 7th International Symposium on Static Analysis, 1824:220–39. Springer, 2000. https://doi.org/10.1007/978-3-540-45099-3_12.","mla":"Henzinger, Thomas A., et al. “Abstract Interpretation of Game Properties.” Proceedings of the 7th International Symposium on Static Analysis, vol. 1824, Springer, 2000, pp. 220–39, doi:10.1007/978-3-540-45099-3_12.","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."},"type":"conference"},{"citation":{"chicago":"Henzinger, Thomas A, Shaz Qadeer, and Sriram Rajamani. “Decomposing Refinement Proofs Using Assume-Guarantee Reasoning.” In Proceedings of the 2000 International Conference on Computer-Aided Design, 245–52. IEEE, 2000. https://doi.org/10.1109/ICCAD.2000.896481.","ama":"Henzinger TA, Qadeer S, Rajamani S. Decomposing refinement proofs using assume-guarantee reasoning. In: Proceedings of the 2000 International Conference on Computer-Aided Design. IEEE; 2000:245-252. doi:10.1109/ICCAD.2000.896481","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.","mla":"Henzinger, Thomas A., et al. “Decomposing Refinement Proofs Using Assume-Guarantee Reasoning.” Proceedings of the 2000 International Conference on Computer-Aided Design, IEEE, 2000, pp. 245–52, doi:10.1109/ICCAD.2000.896481.","short":"T.A. Henzinger, S. Qadeer, S. Rajamani, in:, Proceedings of the 2000 International Conference on Computer-Aided Design, IEEE, 2000, pp. 245–252.","apa":"Henzinger, T. A., Qadeer, S., & Rajamani, S. (2000). Decomposing refinement proofs using assume-guarantee reasoning. In Proceedings of the 2000 International Conference on Computer-Aided Design (pp. 245–252). San Jose, CA, USA: IEEE. https://doi.org/10.1109/ICCAD.2000.896481","ieee":"T. A. Henzinger, S. Qadeer, and S. Rajamani, “Decomposing refinement proofs using assume-guarantee reasoning,” in Proceedings of the 2000 International Conference on Computer-Aided Design, San Jose, CA, USA, 2000, pp. 245–252."},"type":"conference","extern":"1","publication_status":"published","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."}],"publist_id":"249","language":[{"iso":"eng"}],"status":"public","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. ","doi":"10.1109/ICCAD.2000.896481","publication":"Proceedings of the 2000 International Conference on Computer-Aided Design","page":"245 - 252","oa_version":"None","publisher":"IEEE","_id":"4483","date_created":"2018-12-11T12:09:05Z","day":"01","title":"Decomposing refinement proofs using assume-guarantee reasoning","date_updated":"2023-04-18T12:57:52Z","publication_identifier":{"isbn":["0780364457"]},"month":"01","date_published":"2000-01-01T00:00:00Z","author":[{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"full_name":"Qadeer, Shaz","last_name":"Qadeer","first_name":"Shaz"},{"first_name":"Sriram","full_name":"Rajamani, Sriram","last_name":"Rajamani"}],"year":"2000","conference":{"name":"ICCAD: Computer-Aided Design","start_date":"2000-11-05","location":"San Jose, CA, USA","end_date":"2000-11-09"},"article_processing_charge":"No"},{"page":"549 - 563","publication":"Proceedings of the 1st International Conference on Theoretical Computer Science ","date_created":"2018-12-11T12:09:14Z","_id":"4512","month":"01","title":"Masaccio: A formal model for embedded components","date_updated":"2023-04-13T13:48:08Z","article_processing_charge":"No","date_published":"2000-01-01T00:00:00Z","extern":"1","scopus_import":"1","volume":1872,"alternative_title":["LNCS"],"intvolume":" 1872","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.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","doi":"10.1007/3-540-44929-9_38","day":"01","publisher":"Springer","publication_identifier":{"isbn":["9783540678236"]},"year":"2000","conference":{"name":"TCS: Theoretical Computer Science","start_date":"2000-08-17","location":"Sendai, Japan","end_date":"2000-08-19"},"author":[{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"}],"citation":{"ieee":"T. A. Henzinger, “Masaccio: A formal model for embedded components,” in Proceedings of the 1st International Conference on Theoretical Computer Science , Sendai, Japan, 2000, vol. 1872, pp. 549–563.","short":"T.A. Henzinger, in:, Proceedings of the 1st International Conference on Theoretical Computer Science , Springer, 2000, pp. 549–563.","apa":"Henzinger, T. A. (2000). Masaccio: A formal model for embedded components. In Proceedings of the 1st International Conference on Theoretical Computer Science (Vol. 1872, pp. 549–563). Sendai, Japan: Springer. https://doi.org/10.1007/3-540-44929-9_38","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.","mla":"Henzinger, Thomas A. “Masaccio: A Formal Model for Embedded Components.” Proceedings of the 1st International Conference on Theoretical Computer Science , vol. 1872, Springer, 2000, pp. 549–63, doi:10.1007/3-540-44929-9_38.","ama":"Henzinger TA. Masaccio: A formal model for embedded components. In: Proceedings of the 1st International Conference on Theoretical Computer Science . Vol 1872. Springer; 2000:549-563. doi:10.1007/3-540-44929-9_38","chicago":"Henzinger, Thomas A. “Masaccio: A Formal Model for Embedded Components.” In Proceedings of the 1st International Conference on Theoretical Computer Science , 1872:549–63. Springer, 2000. https://doi.org/10.1007/3-540-44929-9_38."},"type":"conference","status":"public","language":[{"iso":"eng"}],"publist_id":"215","publication_status":"published","abstract":[{"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","lang":"eng"}],"quality_controlled":"1"},{"publisher":"Springer","day":"28","doi":"10.1007/978-3-642-59615-5","oa_version":"None","year":"2000","author":[{"orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"}],"editor":[{"first_name":"M.","last_name":"Inan","full_name":"Inan, M."},{"full_name":"Kurshan, Robert","last_name":"Kurshan","first_name":"Robert"}],"publication_identifier":{"isbn":["9783642596155"]},"citation":{"chicago":"Henzinger, Thomas A. “The Theory of Hybrid Automata.” In Verification of Digital and Hybrid Systems, edited by M. Inan and Robert Kurshan, 170:265–92. Springer, 2000. https://doi.org/10.1007/978-3-642-59615-5.","ama":"Henzinger TA. The theory of hybrid automata. In: Inan M, Kurshan R, eds. Verification of Digital and Hybrid Systems. Vol 170. Springer; 2000:265-292. doi:10.1007/978-3-642-59615-5","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.","mla":"Henzinger, Thomas A. “The Theory of Hybrid Automata.” Verification of Digital and Hybrid Systems, edited by M. Inan and Robert Kurshan, vol. 170, Springer, 2000, pp. 265–92, doi:10.1007/978-3-642-59615-5.","short":"T.A. Henzinger, in:, M. Inan, R. Kurshan (Eds.), Verification of Digital and Hybrid Systems, Springer, 2000, pp. 265–292.","apa":"Henzinger, T. A. (2000). The theory of hybrid automata. In M. Inan & R. Kurshan (Eds.), Verification of Digital and Hybrid Systems (Vol. 170, pp. 265–292). Springer. https://doi.org/10.1007/978-3-642-59615-5","ieee":"T. A. Henzinger, “The theory of hybrid automata,” in Verification of Digital and Hybrid Systems, vol. 170, M. Inan and R. Kurshan, Eds. Springer, 2000, pp. 265–292."},"type":"book_chapter","quality_controlled":"1","publist_id":"216","abstract":[{"lang":"eng","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. "}],"publication_status":"published","status":"public","language":[{"iso":"eng"}],"_id":"4513","date_created":"2018-12-11T12:09:14Z","publication":"Verification of Digital and Hybrid Systems","page":"265 - 292","article_processing_charge":"No","date_published":"2000-04-28T00:00:00Z","title":"The theory of hybrid automata","date_updated":"2023-04-18T12:37:17Z","month":"04","extern":"1","scopus_import":"1","intvolume":" 170","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","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. ","alternative_title":["NATO ASI Series F: Computer and Systems Sciences"],"volume":170},{"date_updated":"2023-04-13T13:32:11Z","title":"Discrete abstractions of hybrid systems","month":"07","article_processing_charge":"No","date_published":"2000-07-01T00:00:00Z","publication":"Proceedings of the IEEE","page":"971 - 984","_id":"4598","date_created":"2018-12-11T12:09:41Z","volume":88,"intvolume":" 88","acknowledgement":"The authors would like to thank the reviewers for their detailed comments.","issue":"7","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","scopus_import":"1","publication_identifier":{"issn":["0018-9219"]},"year":"2000","author":[{"first_name":"Rajeev","full_name":"Alur, Rajeev","last_name":"Alur"},{"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":"Gerardo","last_name":"Lafferriere","full_name":"Lafferriere, Gerardo"},{"first_name":"George","last_name":"Pappas","full_name":"Pappas, George"}],"doi":"10.1109/5.871304 ","oa_version":"None","publisher":"IEEE","day":"01","publist_id":"107","abstract":[{"text":"A hybrid system is a dynamical system with both discrete and continuous state changes. For analysis purposes, it is often useful to abstract a system in a way that preserves the properties being analyzed while hiding the details that are of no interest. We show that interesting classes of hybrid systems can be abstracted to purely discrete systems while preserving all properties that are definable in temporal logic. The classes that permit discrete abstractions fall into two categories. Either the continuous dynamics must be restricted, as is the case for timed and rectangular hybrid systems, or the discrete dynamics must be restricted, as is the case for o-minimal hybrid systems. In this paper, we survey and unify results from both areas.","lang":"eng"}],"publication_status":"published","status":"public","language":[{"iso":"eng"}],"quality_controlled":"1","citation":{"chicago":"Alur, Rajeev, Thomas A Henzinger, Gerardo Lafferriere, and George Pappas. “Discrete Abstractions of Hybrid Systems.” Proceedings of the IEEE. IEEE, 2000. https://doi.org/10.1109/5.871304 .","ama":"Alur R, Henzinger TA, Lafferriere G, Pappas G. Discrete abstractions of hybrid systems. Proceedings of the IEEE. 2000;88(7):971-984. doi:10.1109/5.871304 ","ista":"Alur R, Henzinger TA, Lafferriere G, Pappas G. 2000. Discrete abstractions of hybrid systems. Proceedings of the IEEE. 88(7), 971–984.","mla":"Alur, Rajeev, et al. “Discrete Abstractions of Hybrid Systems.” Proceedings of the IEEE, vol. 88, no. 7, IEEE, 2000, pp. 971–84, doi:10.1109/5.871304 .","apa":"Alur, R., Henzinger, T. A., Lafferriere, G., & Pappas, G. (2000). Discrete abstractions of hybrid systems. Proceedings of the IEEE. IEEE. https://doi.org/10.1109/5.871304 ","short":"R. Alur, T.A. Henzinger, G. Lafferriere, G. Pappas, Proceedings of the IEEE 88 (2000) 971–984.","ieee":"R. Alur, T. A. Henzinger, G. Lafferriere, and G. Pappas, “Discrete abstractions of hybrid systems,” Proceedings of the IEEE, vol. 88, no. 7. IEEE, pp. 971–984, 2000."},"type":"journal_article","article_type":"original"},{"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","quality_controlled":"1","language":[{"iso":"eng"}],"status":"public","publication_status":"published","abstract":[{"lang":"eng","text":"We consider two-player games, which are played on a finite state space for an infinite number of rounds. The games are concurrent, that is, in each round, the two players choose their moves independently and simultaneously; the current state and the two moves determine a successor state. We consider omega-regular winning conditions on the resulting infinite state sequence. To model the independent choice of moves, both players are allowed to use randomization for selecting their moves. This gives rise to the following qualitative modes of winning, which can be studied without numerical considerations concerning probabilities: sure-win (player 1 can ensure winning with certainty), almost-sure-win (player 1 can ensure winning with probability 1), limit-win (player 1 can ensure winning with probability arbitrarily close to 1), bounded-win (player 1 can ensure winning with probability bounded away from 0), positive-win (player 1 can ensure winning with positive probability), and exist-win (player 1 can ensure that at least one possible outcome of the game satisfies the winning condition).We provide algorithms for computing the sets of winning states for each of these winning modes. In particular, we solve concurrent Rabin-chain games in n0 (m) time, where n is the size of the game structure and m is the number of pairs in the Rabin-chain condition. While this complexity is in line with traditional turn-based games, where in each state only one of the two players has a choice of moves, our algorithms are considerably more involved than those for turn-based games are. This is because concurrent games violate two of the most fundamental properties of turn-based games. First, concurrent games are not determined, but rather exhibit a more general duality property, which involves multiple modes of winning. Second, winning strategies for concurrent games may require infinite memory."}],"publist_id":"82","scopus_import":"1","type":"conference","citation":{"ieee":"L. De Alfaro and T. A. Henzinger, “Concurrent omega-regular games,” in Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, CA, USA, 2000, pp. 141–154.","apa":"De Alfaro, L., & Henzinger, T. A. (2000). Concurrent omega-regular games. In Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science (pp. 141–154). Santa Barbara, CA, USA: IEEE. https://doi.org/10.1109/LICS.2000.855763","short":"L. De Alfaro, T.A. Henzinger, in:, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, IEEE, 2000, pp. 141–154.","mla":"De Alfaro, Luca, and Thomas A. Henzinger. “Concurrent Omega-Regular Games.” Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, IEEE, 2000, pp. 141–54, doi:10.1109/LICS.2000.855763.","ista":"De Alfaro L, Henzinger TA. 2000. Concurrent omega-regular games. Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 141–154.","ama":"De Alfaro L, Henzinger TA. Concurrent omega-regular games. In: Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science. IEEE; 2000:141-154. doi:10.1109/LICS.2000.855763","chicago":"De Alfaro, Luca, and Thomas A Henzinger. “Concurrent Omega-Regular Games.” In Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, 141–54. IEEE, 2000. https://doi.org/10.1109/LICS.2000.855763."},"extern":"1","author":[{"first_name":"Luca","last_name":"De Alfaro","full_name":"De Alfaro, Luca"},{"last_name":"Henzinger","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2000-01-01T00:00:00Z","year":"2000","conference":{"location":"Santa Barbara, CA, USA","start_date":"2000-06-26","end_date":"2000-06-28","name":"LICS: Logic in Computer Science"},"article_processing_charge":"No","month":"01","date_updated":"2023-04-13T13:24:29Z","title":"Concurrent omega-regular games","publication_identifier":{"isbn":["0769507255"]},"date_created":"2018-12-11T12:09:50Z","day":"01","publisher":"IEEE","_id":"4627","page":"141 - 154","oa_version":"None","publication":"Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science","doi":"10.1109/LICS.2000.855763"},{"extern":"1","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, the SRC contract 99-TJ-683.003, the MARCO grant 98-DT-660, and the NSF CAREER award CCR-9501708.","intvolume":" 1877","volume":1877,"alternative_title":["LNCS"],"date_created":"2018-12-11T12:09:53Z","_id":"4637","page":"458 - 473","publication":"Proceedings of the 11th International Conference on Concurrency Theory","date_published":"2000-01-01T00:00:00Z","article_processing_charge":"No","month":"01","title":"The control of synchronous systems","date_updated":"2023-04-13T11:00:46Z","citation":{"apa":"De Alfaro, L., Henzinger, T. A., & Mang, F. (2000). The control of synchronous systems. In Proceedings of the 11th International Conference on Concurrency Theory (Vol. 1877, pp. 458–473). University Park, PA, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-44618-4_33","short":"L. De Alfaro, T.A. Henzinger, F. Mang, in:, Proceedings of the 11th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2000, pp. 458–473.","ieee":"L. De Alfaro, T. A. Henzinger, and F. Mang, “The control of synchronous systems,” in Proceedings of the 11th International Conference on Concurrency Theory, University Park, PA, USA, 2000, vol. 1877, pp. 458–473.","ama":"De Alfaro L, Henzinger TA, Mang F. The control of synchronous systems. In: Proceedings of the 11th International Conference on Concurrency Theory. Vol 1877. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2000:458-473. doi:10.1007/3-540-44618-4_33","chicago":"De Alfaro, Luca, Thomas A Henzinger, and Freddy Mang. “The Control of Synchronous Systems.” In Proceedings of the 11th International Conference on Concurrency Theory, 1877:458–73. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2000. https://doi.org/10.1007/3-540-44618-4_33.","ista":"De Alfaro L, Henzinger TA, Mang F. 2000. The control of synchronous systems. Proceedings of the 11th International Conference on Concurrency Theory. CONCUR: Concurrency Theory, LNCS, vol. 1877, 458–473.","mla":"De Alfaro, Luca, et al. “The Control of Synchronous Systems.” Proceedings of the 11th International Conference on Concurrency Theory, vol. 1877, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2000, pp. 458–73, doi:10.1007/3-540-44618-4_33."},"type":"conference","quality_controlled":"1","language":[{"iso":"eng"}],"status":"public","publication_status":"published","abstract":[{"text":"In the synchronous composition of processes, one process may prevent another process from proceeding unless compositions without a well-defined product behavior are ruled out. They can be ruled out semantically, by insisting on the existence of certain fixed points, or syntactically, by equipping processes with types, which make the dependencies between input and output signals transparent. We classify various typing mechanisms and study their effects on the control problem.\r\nA static type enforces fixed, acyclic dependencies between input and output ports. For example, synchronous hardware without combinational loops can be typed statically. A dynamic type may vary the dependencies from state to state, while maintaining acyclicity, as in level-sensitive latches. Then, two dynamically typed processes can be syntactically compatible, if all pairs of possible dependencies are compatible, or semantically compatible, if in each state the combined dependencies remain acyclic. For a given plant process and control objective, there may be a controller of a static type, or only a controller of a syntactically compatible dynamic type, or only a controller of a semantically compatible dynamic type. We show this to be a strict hierarchy of possibilities, and we present algorithms and determine the complexity of the corresponding control problems.\r\nFurthermore, we consider versions of the control problem in which the type of the controller (static or dynamic) is given. We show that the solution of these fixed-type control problems requires the evaluation of partially ordered (Henkin) quantifiers on boolean formulas, and is therefore harder (nondeterministic exponential time) than more traditional control questions","lang":"eng"}],"publist_id":"69","day":"01","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa_version":"None","doi":"10.1007/3-540-44618-4_33","author":[{"first_name":"Luca","full_name":"De Alfaro, Luca","last_name":"De Alfaro"},{"first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger"},{"first_name":"Freddy","full_name":"Mang, Freddy","last_name":"Mang"}],"conference":{"name":"CONCUR: Concurrency Theory","start_date":"2000-08-22","location":"University Park, PA, USA","end_date":"2000-08-25"},"year":"2000","publication_identifier":{"isbn":["9783540678977"]}}]