---
_id: '4207'
abstract:
- lang: eng
text: Vertebrate homologues of the Strabismus/van Gogh (stbm/vang) gene have been
implicated in patterning and morphogenesis during gastrulation. Recent work shows
that stbm/vang is mutated in zebrafish trilobite mutants and that stbm/vang is
required for morphogenesis but not patterning during zebrafish gastrulation.
article_processing_charge: No
article_type: original
author:
- first_name: Carl-Philipp J
full_name: Heisenberg, Carl-Philipp J
id: 39427864-F248-11E8-B48F-1D18A9856A87
last_name: Heisenberg
orcid: 0000-0002-0912-4566
citation:
ama: 'Heisenberg C-PJ. Wnt signalling: Refocusing on Strabismus. Current Biology.
2002;12(19):R657-R659. doi:10.1016/S0960-9822(02)01160-0'
apa: 'Heisenberg, C.-P. J. (2002). Wnt signalling: Refocusing on Strabismus. Current
Biology. Cell Press. https://doi.org/10.1016/S0960-9822(02)01160-0'
chicago: 'Heisenberg, Carl-Philipp J. “Wnt Signalling: Refocusing on Strabismus.”
Current Biology. Cell Press, 2002. https://doi.org/10.1016/S0960-9822(02)01160-0.'
ieee: 'C.-P. J. Heisenberg, “Wnt signalling: Refocusing on Strabismus,” Current
Biology, vol. 12, no. 19. Cell Press, pp. R657–R659, 2002.'
ista: 'Heisenberg C-PJ. 2002. Wnt signalling: Refocusing on Strabismus. Current
Biology. 12(19), R657–R659.'
mla: 'Heisenberg, Carl-Philipp J. “Wnt Signalling: Refocusing on Strabismus.” Current
Biology, vol. 12, no. 19, Cell Press, 2002, pp. R657–59, doi:10.1016/S0960-9822(02)01160-0.'
short: C.-P.J. Heisenberg, Current Biology 12 (2002) R657–R659.
date_created: 2018-12-11T12:07:35Z
date_published: 2002-10-01T00:00:00Z
date_updated: 2023-06-06T15:09:53Z
day: '01'
doi: 10.1016/S0960-9822(02)01160-0
extern: '1'
external_id:
pmid:
- '12361585'
intvolume: ' 12'
issue: '19'
language:
- iso: eng
month: '10'
oa_version: None
page: R657 - R659
pmid: 1
publication: Current Biology
publication_identifier:
issn:
- 0960-9822
publication_status: published
publisher: Cell Press
publist_id: '1912'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Wnt signalling: Refocusing on Strabismus'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 12
year: '2002'
...
---
_id: '4209'
abstract:
- lang: eng
text: We have identified widerborst (wdb), a B' regulatory subunit of PP2A, as a
conserved component of planar cell polarization mechanisms in both Drosophila
and in zebrafish. In Drosophila, wdb acts at two steps during planar polarization
of wing epithelial cells. It is required to organize tissue polarity proteins
into proximal and distal cortical domains, thus determining wing hair orientation.
It is also needed to generate the polarized membrane outgrowth that becomes the
wing hair. Widerborst activates the catalytic subunit of PP2A and localizes to
the distal side of a planar microtubule web that lies at the level of apical cell
junctions. This suggests that polarized PP2A activation along the planar microtubule
web is important for planar polarization. In zebrafish, two wdb homologs are required
for convergent extension during gastrulation, supporting the conjecture that Drosophila
planar cell polarization and vertebrate gastrulation movements are regulated by
similar mechanisms.
acknowledgement: We gratefully acknowledge Bianca Habermann for assistance with bioinformatics,
Jens Rietdorf and Arshad Desai for help with deconvolution, and Tadashi Uemura and
Rick Fehon for providing antibodies. Arshad Desai, Christian Dahmann, Tony Hyman
and Elly Tanaka provided helpful comments on the manuscript. Part of this work was
performed at the EMBL in Heidelberg.
article_processing_charge: No
article_type: original
author:
- first_name: Michael
full_name: Hannus, Michael
last_name: Hannus
- first_name: Fabian
full_name: Feiguin, Fabian
last_name: Feiguin
- first_name: Carl-Philipp J
full_name: Heisenberg, Carl-Philipp J
id: 39427864-F248-11E8-B48F-1D18A9856A87
last_name: Heisenberg
orcid: 0000-0002-0912-4566
- first_name: Suzanne
full_name: Eaton, Suzanne
last_name: Eaton
citation:
ama: Hannus M, Feiguin F, Heisenberg C-PJ, Eaton S. Planar cell polarization requires
Widerborst, a B′ regulatory subunit of protein phosphatase 2A. Development.
2002;129(14):3493-3503. doi:10.1242/dev.129.14.3493
apa: Hannus, M., Feiguin, F., Heisenberg, C.-P. J., & Eaton, S. (2002). Planar
cell polarization requires Widerborst, a B′ regulatory subunit of protein phosphatase
2A. Development. Company of Biologists. https://doi.org/10.1242/dev.129.14.3493
chicago: Hannus, Michael, Fabian Feiguin, Carl-Philipp J Heisenberg, and Suzanne
Eaton. “Planar Cell Polarization Requires Widerborst, a B′ Regulatory Subunit
of Protein Phosphatase 2A.” Development. Company of Biologists, 2002. https://doi.org/10.1242/dev.129.14.3493.
ieee: M. Hannus, F. Feiguin, C.-P. J. Heisenberg, and S. Eaton, “Planar cell polarization
requires Widerborst, a B′ regulatory subunit of protein phosphatase 2A,” Development,
vol. 129, no. 14. Company of Biologists, pp. 3493–3503, 2002.
ista: Hannus M, Feiguin F, Heisenberg C-PJ, Eaton S. 2002. Planar cell polarization
requires Widerborst, a B′ regulatory subunit of protein phosphatase 2A. Development.
129(14), 3493–3503.
mla: Hannus, Michael, et al. “Planar Cell Polarization Requires Widerborst, a B′
Regulatory Subunit of Protein Phosphatase 2A.” Development, vol. 129, no.
14, Company of Biologists, 2002, pp. 3493–503, doi:10.1242/dev.129.14.3493.
short: M. Hannus, F. Feiguin, C.-P.J. Heisenberg, S. Eaton, Development 129 (2002)
3493–3503.
date_created: 2018-12-11T12:07:36Z
date_published: 2002-07-15T00:00:00Z
date_updated: 2023-06-06T14:07:49Z
day: '15'
doi: 10.1242/dev.129.14.3493
extern: '1'
external_id:
pmid:
- '12091318'
intvolume: ' 129'
issue: '14'
language:
- iso: eng
month: '07'
oa_version: None
page: 3493 - 3503
pmid: 1
publication: Development
publication_identifier:
issn:
- 0950-1991
publication_status: published
publisher: Company of Biologists
publist_id: '1909'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Planar cell polarization requires Widerborst, a B′ regulatory subunit of protein
phosphatase 2A
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 129
year: '2002'
...
---
_id: '4258'
abstract:
- lang: eng
text: We studied the effect of multilocus balancing selection on neutral nucleotide
variability at linked sites by simulating a model where diallelic polymorphisms
are maintained at an arbitrary number of selected loci by means of symmetric overdominance.
Different combinations of alleles define different genetic backgrounds that subdivide
the population and strongly affect variability. Several multilocus fitness regimes
with different degrees of epistasis and gametic disequilibrium are allowed. Analytical
results based on a multilocus extension of the structured coalescent predict that
the expected linked neutral diversity increases exponentially with the number
of selected loci and can become extremely large. Our simulation results show that
although variability increases with the number of genetic backgrounds that are
maintained in the population, it is reduced by random fluctuations in the frequencies
of those backgrounds and does not reach high levels even in very large populations.
We also show that previous results on balancing selection in single-locus systems
do not extend to the multilocus scenario in a straightforward way. Different patterns
of linkage disequilibrium and of the frequency spectrum of neutral mutations are
expected under different degrees of epistasis. Interestingly, the power to detect
balancing selection using deviations from a neutral distribution of allele frequencies
seems to be diminished under the fitness regime that leads to the largest increase
of variability over the neutral case. This and other results are discussed in
the light of data from the Mhc.
acknowledgement: We thank P. Andolfatto, P. Awadalla, B. Charlesworth, D. Charles-
Guillaudeux, T., M. Janer, G. K. S. Wong, T. Spies and D. E. Geraghty, F. Depaulis,
S. Otto, J. Rozas, and three anonymous reviewers for valuable discussion and criticism.
A.N. is grateful to F. Depaulis, whose comments were particularly helpful (and extremely
funny), and to D. Charlesworth, whose ideas made this work readable. This work was
supported by Biotechnology and Biological Sciences Research Council/Engineering
and Physical Sciences Research Council.
article_processing_charge: No
article_type: original
author:
- first_name: Arcadio
full_name: Navarro, Arcadio
last_name: Navarro
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Navarro A, Barton NH. The effects of multilocus balancing selection on neutral
variability. Genetics. 2002;161(2):849-863. doi:10.1093/genetics/161.2.849
apa: Navarro, A., & Barton, N. H. (2002). The effects of multilocus balancing
selection on neutral variability. Genetics. Genetics Society of America.
https://doi.org/10.1093/genetics/161.2.849
chicago: Navarro, Arcadio, and Nicholas H Barton. “The Effects of Multilocus Balancing
Selection on Neutral Variability.” Genetics. Genetics Society of America,
2002. https://doi.org/10.1093/genetics/161.2.849.
ieee: A. Navarro and N. H. Barton, “The effects of multilocus balancing selection
on neutral variability,” Genetics, vol. 161, no. 2. Genetics Society of
America, pp. 849–863, 2002.
ista: Navarro A, Barton NH. 2002. The effects of multilocus balancing selection
on neutral variability. Genetics. 161(2), 849–863.
mla: Navarro, Arcadio, and Nicholas H. Barton. “The Effects of Multilocus Balancing
Selection on Neutral Variability.” Genetics, vol. 161, no. 2, Genetics
Society of America, 2002, pp. 849–63, doi:10.1093/genetics/161.2.849.
short: A. Navarro, N.H. Barton, Genetics 161 (2002) 849–863.
date_created: 2018-12-11T12:07:53Z
date_published: 2002-06-01T00:00:00Z
date_updated: 2023-06-06T12:02:32Z
day: '01'
doi: 10.1093/genetics/161.2.849
extern: '1'
external_id:
pmid:
- '12072479'
intvolume: ' 161'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1462137/
month: '06'
oa: 1
oa_version: Published Version
page: 849 - 863
pmid: 1
publication: Genetics
publication_identifier:
issn:
- 0016-6731
publication_status: published
publisher: Genetics Society of America
publist_id: '1835'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The effects of multilocus balancing selection on neutral variability
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 161
year: '2002'
...
---
_id: '4259'
abstract:
- lang: eng
text: 'We extend current multilocus models to describe the effects of migration,
recombination, selection, and nonrandom mating on sets of genes in diploids with
varied modes of inheritance, allowing us to consider the patterns of nuclear and
cytonuclear associations (disequilibria) under various models of migration. We
show the relationship between the multilocus notation recently presented by Kirkpatrick,
Johnson, and Barton (developed from previous work by Barton and Turelli) and the
cytonuclear parameterization of Asmussen, Arnold, and Avise and extend this notation
to describe associations between cytoplasmic elements and multiple nuclear genes.
Under models with sexual symmetry, both nuclear-nuclear and cytonuclear disequilibria
are equivalent. They differ, however, in cases involving some type of sexual asymmetry,
which is then reflected in the asymmetric inheritance of cytoplasmic markers.
An example given is the case of different migration rates in males and females;
simulations using 2, 3, 4, or 5 unlinked autosomal markers with a maternally inherited
cytoplasmic marker illustrate how nuclear-nuclear and cytonuclear associations
can be used to separately estimate female and male migration rates. The general
framework developed here allows us to investigate conditions where associations
between loci with different modes of inheritance are not equivalent and to use
this nonequivalence to test for deviations from simple models of admixture. '
acknowledgement: The authors thank Toby Johnson for his helpful comments on this manuscript.
This work was supported by a National Science Foundation NATO postdoctoral fellowship
and National Science Foundation grants DEB-9813335 and DEB-0108242 to M.E.O.; N.H.B.
gratefully acknowledges the support of the Darwin Trust of Edinburgh and the National
Environmental Research Council.
article_processing_charge: No
article_type: original
author:
- first_name: Maria
full_name: Orive, Maria
last_name: Orive
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Orive M, Barton NH. Associations between cytoplasmic and nuclear loci in hybridizing
populations. Genetics. 2002;162(3):1469-1485. doi:10.1093/genetics/162.3.1469
apa: Orive, M., & Barton, N. H. (2002). Associations between cytoplasmic and
nuclear loci in hybridizing populations. Genetics. Genetics Society of
America. https://doi.org/10.1093/genetics/162.3.1469
chicago: Orive, Maria, and Nicholas H Barton. “Associations between Cytoplasmic
and Nuclear Loci in Hybridizing Populations.” Genetics. Genetics Society
of America, 2002. https://doi.org/10.1093/genetics/162.3.1469.
ieee: M. Orive and N. H. Barton, “Associations between cytoplasmic and nuclear loci
in hybridizing populations,” Genetics, vol. 162, no. 3. Genetics Society
of America, pp. 1469–1485, 2002.
ista: Orive M, Barton NH. 2002. Associations between cytoplasmic and nuclear loci
in hybridizing populations. Genetics. 162(3), 1469–1485.
mla: Orive, Maria, and Nicholas H. Barton. “Associations between Cytoplasmic and
Nuclear Loci in Hybridizing Populations.” Genetics, vol. 162, no. 3, Genetics
Society of America, 2002, pp. 1469–85, doi:10.1093/genetics/162.3.1469.
short: M. Orive, N.H. Barton, Genetics 162 (2002) 1469–1485.
date_created: 2018-12-11T12:07:54Z
date_published: 2002-11-01T00:00:00Z
date_updated: 2023-06-06T12:19:54Z
day: '01'
doi: 10.1093/genetics/162.3.1469
extern: '1'
external_id:
pmid:
- '12454089'
intvolume: ' 162'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1462324/
month: '11'
oa: 1
oa_version: Published Version
page: 1469 - 1485
pmid: 1
publication: Genetics
publication_identifier:
issn:
- 0016-6731
publication_status: published
publisher: Genetics Society of America
publist_id: '1836'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Associations between cytoplasmic and nuclear loci in hybridizing populations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 162
year: '2002'
...
---
_id: '4260'
abstract:
- lang: eng
text: 'We calculate the fixation probability of a beneficial allele that arises
as the result of a unique mutation in an asexual population that is subject to
recurrent deleterious mutation at rate U. Our analysis is an extension of previous
works, which make a biologically restrictive assumption that selection against
deleterious alleles is stronger than that on the beneficial allele of interest.
We show that when selection against deleterious alleles is weak, beneficial alleles
that confer a selective advantage that is small relative to U have greatly reduced
probabilities of fixation. We discuss the consequences of this effect for the
distribution of effects of alleles fixed during adaptation. We show that a selective
sweep will increase the fixation probabilities of other beneficial mutations arising
during some short interval afterward. We use the calculated fixation probabilities
to estimate the expected rate of fitness improvement in an asexual population
when beneficial alleles arise continually at some low rate proportional to U.
We estimate the rate of mutation that is optimal in the sense that it maximizes
this rate of fitness improvement. Again, this analysis relaxes the assumption
made previously that selection against deleterious alleles is stronger than on
beneficial alleles. '
acknowledgement: "We thank Brian Charlesworth, Arcadi Navarro, Allen Orr, Sally Otto,
Mario Pineda-Krch, Rosie Redfield, Olivier Tenaillon, and two anonymous reviewers
for discussions and/or helpful comments on the\r\nmanuscript. T.J. is supported
by Wellcome Trust International Prize Travelling Research Fellowship no. 061530.
N.B. is supported by the Biotechnology and Biological Sciences Research Council
and by the Natural Environment Research Council."
article_processing_charge: No
article_type: original
author:
- first_name: Toby
full_name: Johnson, Toby
last_name: Johnson
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Johnson T, Barton NH. The effect of deleterious alleles on adaptation in asexual
populations. Genetics. 2002;162(1):395-411. doi:10.1093/genetics/162.1.395
apa: Johnson, T., & Barton, N. H. (2002). The effect of deleterious alleles
on adaptation in asexual populations. Genetics. Genetics Society of America.
https://doi.org/10.1093/genetics/162.1.395
chicago: Johnson, Toby, and Nicholas H Barton. “The Effect of Deleterious Alleles
on Adaptation in Asexual Populations.” Genetics. Genetics Society of America,
2002. https://doi.org/10.1093/genetics/162.1.395.
ieee: T. Johnson and N. H. Barton, “The effect of deleterious alleles on adaptation
in asexual populations,” Genetics, vol. 162, no. 1. Genetics Society of
America, pp. 395–411, 2002.
ista: Johnson T, Barton NH. 2002. The effect of deleterious alleles on adaptation
in asexual populations. Genetics. 162(1), 395–411.
mla: Johnson, Toby, and Nicholas H. Barton. “The Effect of Deleterious Alleles on
Adaptation in Asexual Populations.” Genetics, vol. 162, no. 1, Genetics
Society of America, 2002, pp. 395–411, doi:10.1093/genetics/162.1.395.
short: T. Johnson, N.H. Barton, Genetics 162 (2002) 395–411.
date_created: 2018-12-11T12:07:54Z
date_published: 2002-09-01T00:00:00Z
date_updated: 2023-06-06T11:45:48Z
day: '01'
doi: 10.1093/genetics/162.1.395
extern: '1'
external_id:
pmid:
- '12242249'
intvolume: ' 162'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1462245/
month: '09'
oa: 1
oa_version: None
page: 395 - 411
pmid: 1
publication: Genetics
publication_identifier:
issn:
- 0016-6731
publication_status: published
publisher: Genetics Society of America
publist_id: '1833'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The effect of deleterious alleles on adaptation in asexual populations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 162
year: '2002'
...
---
_id: '4261'
abstract:
- lang: eng
text: Until recently, it was impracticable to identify the genes that are responsible
for variation in continuous traits, or to directly observe the effects of their
different alleles. Now, the abundance of genetic markers has made it possible
to identify quantitative trait loci (QTL) — the regions of a chromosome or, ideally,
individual sequence variants that are responsible for trait variation. What kind
of QTL do we expect to find and what can our observations of QTL tell us about
how organisms evolve? The key to understanding the evolutionary significance of
QTL is to understand the nature of inherited variation, not in the immediate mechanistic
sense of how genes influence phenotype, but, rather, to know what evolutionary
forces maintain genetic variability.
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Peter
full_name: Keightley, Peter
last_name: Keightley
citation:
ama: Barton NH, Keightley P. Understanding quantitative genetic variation. Nature
Reviews Genetics. 2002;3:11-21. doi:10.1038/nrg700
apa: Barton, N. H., & Keightley, P. (2002). Understanding quantitative genetic
variation. Nature Reviews Genetics. Nature Publishing Group. https://doi.org/10.1038/nrg700
chicago: Barton, Nicholas H, and Peter Keightley. “Understanding Quantitative Genetic
Variation.” Nature Reviews Genetics. Nature Publishing Group, 2002. https://doi.org/10.1038/nrg700.
ieee: N. H. Barton and P. Keightley, “Understanding quantitative genetic variation,”
Nature Reviews Genetics, vol. 3. Nature Publishing Group, pp. 11–21, 2002.
ista: Barton NH, Keightley P. 2002. Understanding quantitative genetic variation.
Nature Reviews Genetics. 3, 11–21.
mla: Barton, Nicholas H., and Peter Keightley. “Understanding Quantitative Genetic
Variation.” Nature Reviews Genetics, vol. 3, Nature Publishing Group, 2002,
pp. 11–21, doi:10.1038/nrg700.
short: N.H. Barton, P. Keightley, Nature Reviews Genetics 3 (2002) 11–21.
date_created: 2018-12-11T12:07:55Z
date_published: 2002-01-01T00:00:00Z
date_updated: 2023-06-06T10:07:00Z
day: '01'
doi: 10.1038/nrg700
extern: '1'
external_id:
pmid:
- '11823787'
intvolume: ' 3'
language:
- iso: eng
month: '01'
oa_version: None
page: 11 - 21
pmid: 1
publication: Nature Reviews Genetics
publication_identifier:
issn:
- 1471-0056
publication_status: published
publisher: Nature Publishing Group
publist_id: '1831'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Understanding quantitative genetic variation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 3
year: '2002'
...
---
_id: '4262'
abstract:
- lang: eng
text: Natural populations are structured spatially into local populations and genetically
into diverse ‘genetic backgrounds’ defined by different combinations of selected
alleles. If selection maintains genetic backgrounds at constant frequency then
neutral diversity is enhanced. By contrast, if background frequencies fluctuate
then diversity is reduced. Provided that the population size of each background
is large enough, these effects can be described by the structured coalescent process.
Almost all the extant results based on the coalescent deal with a single selected
locus. Yet we know that very large numbers of genes are under selection and that
any substantial effects are likely to be due to the cumulative effects of many
loci. Here, we set up a general framework for the extension of the coalescent
to multilocus scenarios and we use it to study the simplest model, where strong
balancing selection acting on a set of n loci maintains 2n backgrounds at constant
frequencies and at linkage equilibrium. Analytical results show that the expected
linked neutral diversity increases exponentially with the number of selected loci
and can become extremely large. However, simulation results reveal that the structured
coalescent approach breaks down when the number of backgrounds approaches the
population size, because of stochastic fluctuations in background frequencies.
A new method is needed to extend the structured coalescent to cases with large
numbers of backgrounds.
acknowledgement: "We thank B. Charlesworth, D. Charlesworth and F. Depaulis for valuable
discussion and criticism. We are also\r\ngrateful to an anonymous reviewer, who
pointed out an imprecision in the original manuscript. This work was\r\nsupported
by the BBSRC."
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Arcadio
full_name: Navarro, Arcadio
last_name: Navarro
citation:
ama: 'Barton NH, Navarro A. Extending the coalescent to multilocus systems: the
case of balancing selection. Genetical Research. 2002;79(2):129-139. doi:10.1017/S0016672301005493'
apa: 'Barton, N. H., & Navarro, A. (2002). Extending the coalescent to multilocus
systems: the case of balancing selection. Genetical Research. Cambridge
University Press. https://doi.org/10.1017/S0016672301005493'
chicago: 'Barton, Nicholas H, and Arcadio Navarro. “Extending the Coalescent to
Multilocus Systems: The Case of Balancing Selection.” Genetical Research.
Cambridge University Press, 2002. https://doi.org/10.1017/S0016672301005493.'
ieee: 'N. H. Barton and A. Navarro, “Extending the coalescent to multilocus systems:
the case of balancing selection,” Genetical Research, vol. 79, no. 2. Cambridge
University Press, pp. 129–139, 2002.'
ista: 'Barton NH, Navarro A. 2002. Extending the coalescent to multilocus systems:
the case of balancing selection. Genetical Research. 79(2), 129–139.'
mla: 'Barton, Nicholas H., and Arcadio Navarro. “Extending the Coalescent to Multilocus
Systems: The Case of Balancing Selection.” Genetical Research, vol. 79,
no. 2, Cambridge University Press, 2002, pp. 129–39, doi:10.1017/S0016672301005493.'
short: N.H. Barton, A. Navarro, Genetical Research 79 (2002) 129–139.
date_created: 2018-12-11T12:07:55Z
date_published: 2002-05-23T00:00:00Z
date_updated: 2023-06-06T11:23:19Z
day: '23'
doi: 10.1017/S0016672301005493
extern: '1'
external_id:
pmid:
- '12073551'
intvolume: ' 79'
issue: '2'
language:
- iso: eng
month: '05'
oa_version: None
page: 129 - 139
pmid: 1
publication: Genetical Research
publication_identifier:
issn:
- 0016-6723
publication_status: published
publisher: Cambridge University Press
publist_id: '1832'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Extending the coalescent to multilocus systems: the case of balancing selection'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 79
year: '2002'
...
---
_id: '4263'
abstract:
- lang: eng
text: 'We introduce a general recursion for the probability of identity in state
of two individuals sampled from a population subject to mutation, migration, and
random drift in a two-dimensional continuum. The recursion allows for the interactions
induced by density-dependent regulation of the population, which are inevitable
in a continuous population. We give explicit series expansions for large neighbourhood
size and for low mutation rates respectively and investigate the accuracy of the
classical Malécot formula for these general models. When neighbourhood size is
small, this formula does not give the identity even over large scales. However,
for large neighbourhood size, it is an accurate approximation which summarises
the local population structure in terms of three quantities: the effective dispersal
rate, σe; the effective population density, ρe; and a local scale, κ, at which
local interactions become significant. The results are illustrated by simulations.'
acknowledgement: This work was supported by grants from the EPSRC (GR/L10048 and an
advanced fellowship for A.M.E.) and NERC (GR3/11635) and by the Darwin Trust of
Edinburgh. We thank Anja Sturm for her assistance with the project and anonymous
reviewers for helpful comments. This paper is dedicated to Charlotte, A.M.E.’s daughter
born during the gestation of the manuscript.
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Frantz
full_name: Depaulis, Frantz
last_name: Depaulis
- first_name: Alison
full_name: Etheridge, Alison
last_name: Etheridge
citation:
ama: Barton NH, Depaulis F, Etheridge A. Neutral evolution in spatially continuous
populations. Theoretical Population Biology. 2002;61(1):31-48. doi:10.1006/tpbi.2001.1557
apa: Barton, N. H., Depaulis, F., & Etheridge, A. (2002). Neutral evolution
in spatially continuous populations. Theoretical Population Biology. Academic
Press. https://doi.org/10.1006/tpbi.2001.1557
chicago: Barton, Nicholas H, Frantz Depaulis, and Alison Etheridge. “Neutral Evolution
in Spatially Continuous Populations.” Theoretical Population Biology. Academic
Press, 2002. https://doi.org/10.1006/tpbi.2001.1557.
ieee: N. H. Barton, F. Depaulis, and A. Etheridge, “Neutral evolution in spatially
continuous populations,” Theoretical Population Biology, vol. 61, no. 1.
Academic Press, pp. 31–48, 2002.
ista: Barton NH, Depaulis F, Etheridge A. 2002. Neutral evolution in spatially continuous
populations. Theoretical Population Biology. 61(1), 31–48.
mla: Barton, Nicholas H., et al. “Neutral Evolution in Spatially Continuous Populations.”
Theoretical Population Biology, vol. 61, no. 1, Academic Press, 2002, pp.
31–48, doi:10.1006/tpbi.2001.1557.
short: N.H. Barton, F. Depaulis, A. Etheridge, Theoretical Population Biology 61
(2002) 31–48.
date_created: 2018-12-11T12:07:55Z
date_published: 2002-02-01T00:00:00Z
date_updated: 2023-06-06T09:57:49Z
day: '01'
doi: 10.1006/tpbi.2001.1557
extern: '1'
external_id:
pmid:
- '11895381'
intvolume: ' 61'
issue: '1'
language:
- iso: eng
month: '02'
oa_version: None
page: 31 - 48
pmid: 1
publication: Theoretical Population Biology
publication_identifier:
issn:
- 0040-5809
publication_status: published
publisher: Academic Press
publist_id: '1830'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Neutral evolution in spatially continuous populations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 61
year: '2002'
...
---
_id: '4347'
abstract:
- lang: eng
text: 'Phylogenetic trees can be rooted by a number of criteria. Here, we introduce
a Bayesian method for inferring the root of a phylogenetic tree by using one of
several criteria: the outgroup, molecular clock, and nonreversible model of DNA
substitution. We perform simulation analyses to examine the relative ability of
these three criteria to correctly identify the root of the tree. The outgroup
and molecular clock criteria were best able to identify the root of the tree,
whereas the nonreversible model was able to identify the root only when the substitution
process was highly nonreversible. We also examined the performance of the criteria
for a tree of four species for which the topology and root position are well supported.
Results of the analyses of these data are consistent with the simulation results.'
article_processing_charge: No
article_type: original
author:
- first_name: John
full_name: Huelsenbeck, John
last_name: Huelsenbeck
- first_name: Jonathan P
full_name: Bollback, Jonathan P
id: 2C6FA9CC-F248-11E8-B48F-1D18A9856A87
last_name: Bollback
orcid: 0000-0002-4624-4612
- first_name: Amy
full_name: Levine, Amy
last_name: Levine
citation:
ama: Huelsenbeck J, Bollback JP, Levine A. Inferring the root of a phylogenetic
tree. Systematic Biology. 2002;51(1):32-43. doi:10.1080/106351502753475862
apa: Huelsenbeck, J., Bollback, J. P., & Levine, A. (2002). Inferring the root
of a phylogenetic tree. Systematic Biology. Oxford University Press. https://doi.org/10.1080/106351502753475862
chicago: Huelsenbeck, John, Jonathan P Bollback, and Amy Levine. “Inferring the
Root of a Phylogenetic Tree.” Systematic Biology. Oxford University Press,
2002. https://doi.org/10.1080/106351502753475862.
ieee: J. Huelsenbeck, J. P. Bollback, and A. Levine, “Inferring the root of a phylogenetic
tree,” Systematic Biology, vol. 51, no. 1. Oxford University Press, pp.
32–43, 2002.
ista: Huelsenbeck J, Bollback JP, Levine A. 2002. Inferring the root of a phylogenetic
tree. Systematic Biology. 51(1), 32–43.
mla: Huelsenbeck, John, et al. “Inferring the Root of a Phylogenetic Tree.” Systematic
Biology, vol. 51, no. 1, Oxford University Press, 2002, pp. 32–43, doi:10.1080/106351502753475862.
short: J. Huelsenbeck, J.P. Bollback, A. Levine, Systematic Biology 51 (2002) 32–43.
date_created: 2018-12-11T12:08:23Z
date_published: 2002-02-01T00:00:00Z
date_updated: 2023-06-06T09:53:27Z
day: '01'
doi: 10.1080/106351502753475862
extern: '1'
external_id:
pmid:
- '11943091'
intvolume: ' 51'
issue: '1'
language:
- iso: eng
month: '02'
oa_version: None
page: 32 - 43
pmid: 1
publication: Systematic Biology
publication_identifier:
issn:
- 0039-7989
publication_status: published
publisher: Oxford University Press
publist_id: '1113'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inferring the root of a phylogenetic tree
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 51
year: '2002'
...
---
_id: '4349'
abstract:
- lang: eng
text: 'Bayesian inference is becoming a common statistical approach to phylogenetic
estimation because, among other reasons, it allows for rapid analysis of large
data sets with complex evolutionary models. Conveniently, Bayesian phylogenetic
methods use currently available stochastic models of sequence evolution. However,
as with other model-based approaches, the results of Bayesian inference are conditional
on the assumed model of evolution: inadequate models (models that poorly fit the
data) may result in erroneous inferences. In this article, I present a Bayesian
phylogenetic method that evaluates the adequacy of evolutionary models using posterior
predictive distributions. By evaluating a model''s posterior predictive performance,
an adequate model can be selected for a Bayesian phylogenetic study. Although
I present a single test statistic that assesses the overall (global) performance
of a phylogenetic model, a variety of test statistics can be tailored to evaluate
specific features (local performance) of evolutionary models to identify sources
failure. The method presented here, unlike the likelihood-ratio test and parametric
bootstrap, accounts for uncertainty in the phylogeny and model parameters.'
acknowledgement: "This work was supported by grants from the NSF to John Huelsenbeck
(MCB-0075404 and DEB0075406), to whom I am grateful for his support throughout this
project. Also, I would like to express my deep thanks to Andrea Betancourt, John
Huelsenbeck, Kelly Dyer, Rasmus Nielsen, and Frederick Ronquist for taking the time
to read early versions of the\r\nmanuscript. Each and every one of them provided
invaluable comments, that ultimately made the manuscript better. John Huelsenbeck,
Bret Larget, Rasmus Nielsen, Ken Karol, and Andrea Betancourt patiently listened
to me drone on about this project, and offered insightful comments that benefited
this work, and for this they have my deepest gratitude. And finally, I would like
to thank two anonymous reviewers who gave critical attention to the manuscript and
provided valuable comments."
article_processing_charge: No
article_type: original
author:
- first_name: Jonathan P
full_name: Bollback, Jonathan P
id: 2C6FA9CC-F248-11E8-B48F-1D18A9856A87
last_name: Bollback
orcid: 0000-0002-4624-4612
citation:
ama: Bollback JP. Bayesian model adequacy and choice in phylogenetics. Molecular
Biology and Evolution. 2002;19(7):1171-1180. doi:10.1093/oxfordjournals.molbev.a004175
apa: Bollback, J. P. (2002). Bayesian model adequacy and choice in phylogenetics.
Molecular Biology and Evolution. Oxford University Press. https://doi.org/10.1093/oxfordjournals.molbev.a004175
chicago: Bollback, Jonathan P. “Bayesian Model Adequacy and Choice in Phylogenetics.”
Molecular Biology and Evolution. Oxford University Press, 2002. https://doi.org/10.1093/oxfordjournals.molbev.a004175.
ieee: J. P. Bollback, “Bayesian model adequacy and choice in phylogenetics,” Molecular
Biology and Evolution, vol. 19, no. 7. Oxford University Press, pp. 1171–80,
2002.
ista: Bollback JP. 2002. Bayesian model adequacy and choice in phylogenetics. Molecular
Biology and Evolution. 19(7), 1171–80.
mla: Bollback, Jonathan P. “Bayesian Model Adequacy and Choice in Phylogenetics.”
Molecular Biology and Evolution, vol. 19, no. 7, Oxford University Press,
2002, pp. 1171–80, doi:10.1093/oxfordjournals.molbev.a004175.
short: J.P. Bollback, Molecular Biology and Evolution 19 (2002) 1171–80.
date_created: 2018-12-11T12:08:24Z
date_published: 2002-03-25T00:00:00Z
date_updated: 2023-06-06T09:18:18Z
day: '25'
doi: 10.1093/oxfordjournals.molbev.a004175
extern: '1'
external_id:
pmid:
- '12082136 '
intvolume: ' 19'
issue: '7'
language:
- iso: eng
month: '03'
oa_version: None
page: 1171 - 80
pmid: 1
publication: Molecular Biology and Evolution
publication_identifier:
issn:
- 0737-4038
publication_status: published
publisher: Oxford University Press
publist_id: '1112'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bayesian model adequacy and choice in phylogenetics
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 19
year: '2002'
...
---
_id: '4407'
abstract:
- lang: eng
text: 'This paper presents a complete axiomatization of two decidable propositional
real-time linear temporal logics: Event Clock Logic (EventClockTL) and Metric
Interval Temporal Logic with past (MetricIntervalTL). The completeness proof consists
of an effective proof building procedure for EventClockTL. From this result we
obtain a complete axiomatization of MetricIntervalTL by providing axioms translating
MetricIntervalTL formulae into EventClockTL formulae, the two logics being equally
expressive. Our proof is structured to yield axiomatizations also for interesting
fragments of these logics, such as the linear temporal logic of the real numbers
(TLR).'
article_processing_charge: No
article_type: original
author:
- first_name: Jean
full_name: Raskin, Jean
last_name: Raskin
- first_name: Pierre
full_name: Schobbens, Pierre
last_name: Schobbens
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Raskin J, Schobbens P, Henzinger TA. Axioms for real-time logics. Theoretical
Computer Science. 2002;274(1-2):151-182. doi:10.1016/S0304-3975(00)00308-X
apa: Raskin, J., Schobbens, P., & Henzinger, T. A. (2002). Axioms for real-time
logics. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/S0304-3975(00)00308-X
chicago: Raskin, Jean, Pierre Schobbens, and Thomas A Henzinger. “Axioms for Real-Time
Logics.” Theoretical Computer Science. Elsevier, 2002. https://doi.org/10.1016/S0304-3975(00)00308-X.
ieee: J. Raskin, P. Schobbens, and T. A. Henzinger, “Axioms for real-time logics,”
Theoretical Computer Science, vol. 274, no. 1–2. Elsevier, pp. 151–182,
2002.
ista: Raskin J, Schobbens P, Henzinger TA. 2002. Axioms for real-time logics. Theoretical
Computer Science. 274(1–2), 151–182.
mla: Raskin, Jean, et al. “Axioms for Real-Time Logics.” Theoretical Computer
Science, vol. 274, no. 1–2, Elsevier, 2002, pp. 151–82, doi:10.1016/S0304-3975(00)00308-X.
short: J. Raskin, P. Schobbens, T.A. Henzinger, Theoretical Computer Science 274
(2002) 151–182.
date_created: 2018-12-11T12:08:42Z
date_published: 2002-03-01T00:00:00Z
date_updated: 2023-06-06T09:10:56Z
day: '01'
doi: 10.1016/S0304-3975(00)00308-X
extern: '1'
intvolume: ' 274'
issue: 1-2
language:
- iso: eng
month: '03'
oa_version: None
page: 151 - 182
publication: Theoretical Computer Science
publication_identifier:
issn:
- 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '324'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Axioms for real-time logics
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 274
year: '2002'
...
---
_id: '4413'
abstract:
- lang: eng
text: 'An essential problem in component-based design is how to compose components
designed in isolation. Several approaches have been proposed for specifying component
interfaces that capture behavioral aspects such as interaction protocols, and
for verifying interface compatibility. Likewise, several approaches have been
developed for synthesizing converters between incompatible protocols. In this
paper, we introduce the notion of adaptability as the property that two interfaces
have when they can be made compatible by communicating through a converter that
meets specified requirements. We show that verifying adaptability and synthesizing
an appropriate converter are two faces of the same coin: adaptability can be formalized
and solved using a game-theoretic framework, and then the converter can be synthesized
as a strategy that always wins the game. Finally we show that this framework can
be related to the rectification problem in trace theory.'
acknowledgement: "The authors would like to thank Jerry Burch of the Cadence Berkeley
Labs for many insightful discussions and suggestions.\r\n"
article_processing_charge: No
author:
- first_name: Roberto
full_name: Passerone, Roberto
last_name: Passerone
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Alberto
full_name: Sangiovanni Vincentelli, Alberto
last_name: Sangiovanni Vincentelli
citation:
ama: 'Passerone R, De Alfaro L, Henzinger TA, Sangiovanni Vincentelli A. Convertibility
verification and converter synthesis: Two faces of the same coin. In: Proceedings
of the 11th IEEE/ACM International Conference on Computer-Aided Design. IEEE;
2002:132-139. doi:10.1145/774572.774592'
apa: 'Passerone, R., De Alfaro, L., Henzinger, T. A., & Sangiovanni Vincentelli,
A. (2002). Convertibility verification and converter synthesis: Two faces of the
same coin. In Proceedings of the 11th IEEE/ACM international conference on
Computer-aided design (pp. 132–139). San Jose, CA, USA: IEEE. https://doi.org/10.1145/774572.774592'
chicago: 'Passerone, Roberto, Luca De Alfaro, Thomas A Henzinger, and Alberto Sangiovanni
Vincentelli. “Convertibility Verification and Converter Synthesis: Two Faces of
the Same Coin.” In Proceedings of the 11th IEEE/ACM International Conference
on Computer-Aided Design, 132–39. IEEE, 2002. https://doi.org/10.1145/774572.774592.'
ieee: 'R. Passerone, L. De Alfaro, T. A. Henzinger, and A. Sangiovanni Vincentelli,
“Convertibility verification and converter synthesis: Two faces of the same coin,”
in Proceedings of the 11th IEEE/ACM international conference on Computer-aided
design, San Jose, CA, USA, 2002, pp. 132–139.'
ista: 'Passerone R, De Alfaro L, Henzinger TA, Sangiovanni Vincentelli A. 2002.
Convertibility verification and converter synthesis: Two faces of the same coin.
Proceedings of the 11th IEEE/ACM international conference on Computer-aided design.
ICCAD: Computer-Aided Design, 132–139.'
mla: 'Passerone, Roberto, et al. “Convertibility Verification and Converter Synthesis:
Two Faces of the Same Coin.” Proceedings of the 11th IEEE/ACM International
Conference on Computer-Aided Design, IEEE, 2002, pp. 132–39, doi:10.1145/774572.774592.'
short: R. Passerone, L. De Alfaro, T.A. Henzinger, A. Sangiovanni Vincentelli, in:,
Proceedings of the 11th IEEE/ACM International Conference on Computer-Aided Design,
IEEE, 2002, pp. 132–139.
conference:
end_date: 2002-11-14
location: San Jose, CA, USA
name: 'ICCAD: Computer-Aided Design'
start_date: 2002-11-10
date_created: 2018-12-11T12:08:44Z
date_published: 2002-11-01T00:00:00Z
date_updated: 2023-06-05T14:21:46Z
day: '01'
doi: 10.1145/774572.774592
extern: '1'
language:
- iso: eng
month: '11'
oa_version: None
page: 132 - 139
publication: Proceedings of the 11th IEEE/ACM international conference on Computer-aided
design
publication_identifier:
isbn:
- '9780780376076'
publication_status: published
publisher: IEEE
publist_id: '318'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Convertibility verification and converter synthesis: Two faces of the same
coin'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2002'
...
---
_id: '4414'
abstract:
- lang: eng
text: "This dissertation investigates game-theoretic approaches to the algorithmic
analysis of concurrent, reactive systems. A concurrent system comprises a number
of components working concurrently; a reactive system maintains an ongoing interaction
with its environment. Traditional approaches to the formal analysis of concurrent
reactive systems usually view the system as an unstructured state-transition graphs;
instead, we view them as collections of interacting components, where each one
is an open system which accepts inputs from the other components. The interactions
among the components are naturally modeled as games.\r\n\r\nAdopting this game-theoretic
view, we study three related problems pertaining to the verification and synthesis
of systems. Firstly, we propose two novel game-theoretic techniques for the model-checking
of concurrent reactive systems, and improve the performance of model-checking.
The first technique discovers an error as soon as it cannot be prevented, which
can be long before it actually occurs. This technique is based on the key observation
that "unpreventability" is a local property to a module: an error is
unpreventable in a module state if no environment can prevent it. The second technique
attempts to decompose a model-checking proof into smaller proof obligations by
constructing abstract modules automatically, using reachability and "unpreventability"
information about the concrete modules. Three increasingly powerful proof decomposition
rules are proposed and we show that in practice, the resulting abstract modules
are often significantly smaller than the concrete modules and can drastically
reduce the space and time requirements for verification. Both techniques fall
into the category of compositional reasoning.\r\n\r\nSecondly, we investigate
the composition and control of synchronous systems. An essential property of synchronous
systems for compositional reasoning is non-blocking. In the composition of synchronous
systems, however, due to circular causal dependency of input and output signals,
non-blocking is not always guaranteed. Blocking compositions of systems can be
ruled out semantically, by insisting on the existence of certain fixed points,
or syntactically, by equipping systems with types, which make the dependencies
between input and output signals transparent. We characterize various typing mechanisms
in game-theoretic terms, and study their effects on the controller synthesis problem.
We show that our typing systems are general enough to capture interesting real-life
synchronous systems such as all delay-insensitive digital circuits. We then study
their corresponding single-step control problems --a restricted form of controller
synthesis problem whose solutions can be iterated in appropriate manners to solve
all LTL controller synthesis problems. We also consider versions of the controller
synthesis problem in which the type of the controller 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.\r\n\r\nThirdly, we
study the synthesis of a class of open systems, namely, uninitialized state machines.
The sequential synthesis problem, which is closely related to Church's solvability
problem, asks, given a specification in the form of a binary relation between
input and output streams, for the construction of a finite-state stream transducer
that converts inputs to appropriate outputs. For efficiency reasons, practical
sequential hardware is often designed to operate without prior initialization.
Such hardware designs can be modeled by uninitialized state machines, which are
required to satisfy their specification if started from any state. We solve the
sequential synthesis problem for uninitialized systems, that is, we construct
uninitialized finite-state stream transducers. We consider specifications given
by LTL formulas, deterministic, nondeterministic, universal, and alternating Buechi
automata. We solve this uninitialized synthesis problem by reducing it to the
well-understood initialized synthesis problem. While our solution is straightforward,
it leads, for some specification formalisms, to upper bounds that are exponentially
worse than the complexity of the corresponding initialized problems. However,
we prove lower bounds to show that our simple solutions are optimal for all considered
specification formalisms. The lower bound proofs require nontrivial generic reductions."
article_processing_charge: No
author:
- first_name: Freddy
full_name: Mang, Freddy
last_name: Mang
citation:
ama: Mang F. Games in open systems verification and synthesis. 2002:1-116.
apa: Mang, F. (2002). Games in open systems verification and synthesis. University
of California, Berkeley.
chicago: Mang, Freddy. “Games in Open Systems Verification and Synthesis.” University
of California, Berkeley, 2002.
ieee: F. Mang, “Games in open systems verification and synthesis,” University of
California, Berkeley, 2002.
ista: Mang F. 2002. Games in open systems verification and synthesis. University
of California, Berkeley.
mla: Mang, Freddy. Games in Open Systems Verification and Synthesis. University
of California, Berkeley, 2002, pp. 1–116.
short: F. Mang, Games in Open Systems Verification and Synthesis, University of
California, Berkeley, 2002.
date_created: 2018-12-11T12:08:44Z
date_published: 2002-05-01T00:00:00Z
date_updated: 2021-01-12T07:56:48Z
day: '01'
extern: '1'
language:
- iso: eng
month: '05'
oa_version: None
page: 1 - 116
publication_status: published
publisher: University of California, Berkeley
publist_id: '315'
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
title: Games in open systems verification and synthesis
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2002'
...
---
_id: '4421'
abstract:
- lang: eng
text: We demonstrate the feasibility and benefits of Giotto-based control software
development by reimplementing the autopilot system of an autonomously flying model
helicopter. Giotto offers a clean separation between the platform-independent
concerns of software functionality and I/O timing, and the platform-dependent
concerns of software scheduling and execution. Functionality code such as code
computing control laws can be generated automatically from Simulink models or,
as in the case of this project, inherited from a legacy system. I/O timing code
is generated automatically from Giotto models that specify real-time requirements
such as task frequencies and actuator update rates. We extend Simulink to support
the design of Giotto models, and from these models, the automatic generation of
Giotto code that supervises the interaction of the functionality code with the
physical environment. The Giotto compiler performs a schedulability analysis on
the Giotto code, and generates timing code for the helicopter platform. The Giotto
methodology guarantees the stringent hard real-time requirements of the autopilot
system, and at the same time supports the automation of the software development
process in a way that produces a transparent software architecture with predictable
behavior and reusable components.
acknowledgement: This research was supported in part by the DARPA SEC grant F33615-C-98-3614,
the MARCO GSRC grant 98-DT-660, and the AFOSR MURI grant F49620-00-1-0327.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Marco
full_name: Sanvido, Marco
last_name: Sanvido
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Wolfgang
full_name: Pree, Wolfgang
last_name: Pree
citation:
ama: 'Kirsch C, Sanvido M, Henzinger TA, Pree W. A Giotto-based helicopter control
system. In: Proceedings of the 2nd International Conference on Embedded Software.
Vol 2491. ACM; 2002:46-60. doi:10.1007/3-540-45828-X_5'
apa: 'Kirsch, C., Sanvido, M., Henzinger, T. A., & Pree, W. (2002). A Giotto-based
helicopter control system. In Proceedings of the 2nd International Conference
on Embedded Software (Vol. 2491, pp. 46–60). Grenoble, France: ACM. https://doi.org/10.1007/3-540-45828-X_5'
chicago: Kirsch, Christoph, Marco Sanvido, Thomas A Henzinger, and Wolfgang Pree.
“A Giotto-Based Helicopter Control System.” In Proceedings of the 2nd International
Conference on Embedded Software, 2491:46–60. ACM, 2002. https://doi.org/10.1007/3-540-45828-X_5.
ieee: C. Kirsch, M. Sanvido, T. A. Henzinger, and W. Pree, “A Giotto-based helicopter
control system,” in Proceedings of the 2nd International Conference on Embedded
Software, Grenoble, France, 2002, vol. 2491, pp. 46–60.
ista: 'Kirsch C, Sanvido M, Henzinger TA, Pree W. 2002. A Giotto-based helicopter
control system. Proceedings of the 2nd International Conference on Embedded Software.
EMSOFT: Embedded Software , LNCS, vol. 2491, 46–60.'
mla: Kirsch, Christoph, et al. “A Giotto-Based Helicopter Control System.” Proceedings
of the 2nd International Conference on Embedded Software, vol. 2491, ACM,
2002, pp. 46–60, doi:10.1007/3-540-45828-X_5.
short: C. Kirsch, M. Sanvido, T.A. Henzinger, W. Pree, in:, Proceedings of the 2nd
International Conference on Embedded Software, ACM, 2002, pp. 46–60.
conference:
end_date: 2002-10-09
location: Grenoble, France
name: 'EMSOFT: Embedded Software '
start_date: 2002-10-07
date_created: 2018-12-11T12:08:46Z
date_published: 2002-09-25T00:00:00Z
date_updated: 2023-06-05T13:07:20Z
day: '25'
doi: 10.1007/3-540-45828-X_5
extern: '1'
intvolume: ' 2491'
language:
- iso: eng
month: '09'
oa_version: None
page: 46 - 60
publication: Proceedings of the 2nd International Conference on Embedded Software
publication_identifier:
isbn:
- '9783540443070'
publication_status: published
publisher: ACM
publist_id: '310'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A Giotto-based helicopter control system
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2491
year: '2002'
...
---
_id: '4422'
abstract:
- lang: eng
text: "Behavioral properties of open systems can be formalized as objectives in
two-player games. Turn-based games model asynchronous interaction between the
players (the system and its environment) by interleaving their moves. Concurrent
games model synchronous interaction: the players always move simultaneously. Infinitary
winning criteria are considered: Büchi, co-Büchi, and more general parity conditions.
A generalization of determinacy for parity games to concurrent parity games demands
probabilistic (mixed) strategies: either player 1 has a mixed strategy to win
with probability 1 (almost-sure winning), or player 2 has a mixed strategy to
win with positive probability.\r\nThis work provides efficient reductions of concurrent
probabilistic Büchi and co-Büchi games to turn-based games with Büchi condition
and parity winning condition with three priorities, respectively. From a theoretical
point of view, the latter reduction shows that one can trade the probabilistic
nature of almost-sure winning for a more general parity (fairness) condition.
The reductions improve understanding of concurrent games and provide an alternative
simple proof of determinacy of concurrent Büchi and co-Büchi games. From a practical
point of view, the reductions turn solvers of turn-based games into solvers of
concurrent probabilistic games. Thus improvements in the well-studied algorithms
for the former carry over immediately to the latter. In particular, a recent improvement
in the complexity of solving turn-based parity games yields an improvement in
time complexity of solving concurrent probabilistic co-Büchi games from cubic
to quadratic."
acknowledgement: This research was supported in part by the Polish KBN grant 7-T11C-027-20,
the AFOSR MURI grant F49620-00-1-0327, and the NSF Theory grant CCR-9988172.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Marcin
full_name: Jurdziński, Marcin
last_name: Jurdziński
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Jurdziński M, Kupferman O, Henzinger TA. Trading probability for fairness.
In: Proceedings of the 16th International Workshop on Computer Science Logic.
Vol 2471. Springer; 2002:292-305. doi:10.1007/3-540-45793-3_20'
apa: 'Jurdziński, M., Kupferman, O., & Henzinger, T. A. (2002). Trading probability
for fairness. In Proceedings of the 16th International Workshop on Computer
Science Logic (Vol. 2471, pp. 292–305). Edinburgh, Scotland: Springer. https://doi.org/10.1007/3-540-45793-3_20'
chicago: Jurdziński, Marcin, Orna Kupferman, and Thomas A Henzinger. “Trading Probability
for Fairness.” In Proceedings of the 16th International Workshop on Computer
Science Logic, 2471:292–305. Springer, 2002. https://doi.org/10.1007/3-540-45793-3_20.
ieee: M. Jurdziński, O. Kupferman, and T. A. Henzinger, “Trading probability for
fairness,” in Proceedings of the 16th International Workshop on Computer Science
Logic, Edinburgh, Scotland, 2002, vol. 2471, pp. 292–305.
ista: 'Jurdziński M, Kupferman O, Henzinger TA. 2002. Trading probability for fairness.
Proceedings of the 16th International Workshop on Computer Science Logic. CSL:
Computer Science Logic, LNCS, vol. 2471, 292–305.'
mla: Jurdziński, Marcin, et al. “Trading Probability for Fairness.” Proceedings
of the 16th International Workshop on Computer Science Logic, vol. 2471, Springer,
2002, pp. 292–305, doi:10.1007/3-540-45793-3_20.
short: M. Jurdziński, O. Kupferman, T.A. Henzinger, in:, Proceedings of the 16th
International Workshop on Computer Science Logic, Springer, 2002, pp. 292–305.
conference:
location: Edinburgh, Scotland
name: 'CSL: Computer Science Logic'
date_created: 2018-12-11T12:08:46Z
date_published: 2002-09-09T00:00:00Z
date_updated: 2023-06-05T10:02:54Z
day: '09'
doi: 10.1007/3-540-45793-3_20
extern: '1'
intvolume: ' 2471'
language:
- iso: eng
month: '09'
oa_version: None
page: 292 - 305
publication: Proceedings of the 16th International Workshop on Computer Science Logic
publication_identifier:
isbn:
- '9783540442400'
publication_status: published
publisher: Springer
publist_id: '308'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Trading probability for fairness
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2471
year: '2002'
...
---
_id: '4423'
abstract:
- lang: eng
text: Automation control systems typically incorporate legacy code and components
that were originally designed to operate independently. Furthermore, they operate
under stringent safety and timing constraints. Current design strategies deal
with these requirements and characteristics with ad hoc approaches. In particular,
when designing control laws, implementation constraints are often ignored or cursorily
estimated. Indeed, costly redesigns are needed after a prototype of the control
system is built due to missed timing constraints and subtle transient errors.
In this paper, we use the concepts of platform-based design, and the Giotto programming
language, to develop a methodology for the design of automation control systems
that builds in modularity and correct-by-construction procedures. We illustrate
our strategy by describing the (successful) application of the methodology to
the design of a time-based control system for a rotorcraft Uninhabited Aerial
Vehicle (UAV).
acknowledgement: "Research supported in part by DARPA under contract no.F33615-98-C-3614,
Software Enabled Control, administered by\r\nAFRL, Dayton OH."
article_processing_charge: No
author:
- first_name: Benjamin
full_name: Horowitz, Benjamin
last_name: Horowitz
- first_name: Judith
full_name: Liebman, Judith
last_name: Liebman
- first_name: Cedric
full_name: Ma, Cedric
last_name: Ma
- first_name: T John
full_name: Koo, T John
last_name: Koo
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Alberto
full_name: Sangiovanni Vincentelli, Alberto
last_name: Sangiovanni Vincentelli
- first_name: Shankar
full_name: Sastry, Shankar
last_name: Sastry
citation:
ama: 'Horowitz B, Liebman J, Ma C, et al. Embedded software design and system integration
for rotorcraft UAV using platforms. In: Proceedings of the 15th Triennial World
Congress of the International Federation of Automatic Control. Vol 15. Elsevier;
2002. doi:10.3182/20020721-6-ES-1901.01628'
apa: 'Horowitz, B., Liebman, J., Ma, C., Koo, T. J., Henzinger, T. A., Sangiovanni
Vincentelli, A., & Sastry, S. (2002). Embedded software design and system
integration for rotorcraft UAV using platforms. In Proceedings of the 15th
Triennial World Congress of the International Federation of Automatic Control
(Vol. 15). Barcelona, Spain: Elsevier. https://doi.org/10.3182/20020721-6-ES-1901.01628'
chicago: Horowitz, Benjamin, Judith Liebman, Cedric Ma, T John Koo, Thomas A Henzinger,
Alberto Sangiovanni Vincentelli, and Shankar Sastry. “Embedded Software Design
and System Integration for Rotorcraft UAV Using Platforms.” In Proceedings
of the 15th Triennial World Congress of the International Federation of Automatic
Control, Vol. 15. Elsevier, 2002. https://doi.org/10.3182/20020721-6-ES-1901.01628.
ieee: B. Horowitz et al., “Embedded software design and system integration
for rotorcraft UAV using platforms,” in Proceedings of the 15th Triennial World
Congress of the International Federation of Automatic Control, Barcelona,
Spain, 2002, vol. 15, no. 1.
ista: 'Horowitz B, Liebman J, Ma C, Koo TJ, Henzinger TA, Sangiovanni Vincentelli
A, Sastry S. 2002. Embedded software design and system integration for rotorcraft
UAV using platforms. Proceedings of the 15th Triennial World Congress of the International
Federation of Automatic Control. IFAC: World Congress on Automatic Control vol.
15.'
mla: Horowitz, Benjamin, et al. “Embedded Software Design and System Integration
for Rotorcraft UAV Using Platforms.” Proceedings of the 15th Triennial World
Congress of the International Federation of Automatic Control, vol. 15, no.
1, Elsevier, 2002, doi:10.3182/20020721-6-ES-1901.01628.
short: B. Horowitz, J. Liebman, C. Ma, T.J. Koo, T.A. Henzinger, A. Sangiovanni
Vincentelli, S. Sastry, in:, Proceedings of the 15th Triennial World Congress
of the International Federation of Automatic Control, Elsevier, 2002.
conference:
end_date: 2002-07-26
location: Barcelona, Spain
name: 'IFAC: World Congress on Automatic Control'
start_date: 2002-07-21
date_created: 2018-12-11T12:08:47Z
date_published: 2002-07-01T00:00:00Z
date_updated: 2023-06-05T09:55:10Z
day: '01'
doi: 10.3182/20020721-6-ES-1901.01628
extern: '1'
intvolume: ' 15'
issue: '1'
language:
- iso: eng
month: '07'
oa_version: None
publication: Proceedings of the 15th Triennial World Congress of the International
Federation of Automatic Control
publication_identifier:
issn:
- 1474-6670
publication_status: published
publisher: Elsevier
publist_id: '306'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Embedded software design and system integration for rotorcraft UAV using platforms
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '2002'
...
---
_id: '4444'
abstract:
- lang: eng
text: The Embedded Machine is a virtual machine that mediates in real time the interaction
between software processes and physical processes. It separates the compilation
of embedded programs into two phases. The first, platform-independent compiler
phase generates E code (code executed by the Embedded Machine), which supervises
the timing ---not the scheduling--- of application tasks relative to external
events, such as clock ticks and sensor interrupts. E~code is portable and exhibits,
given an input behavior, predictable (i.e., deterministic) timing and output behavior.
The second, platform-dependent compiler phase checks the time safety of the E
code, that is, whether platform performance (determined by the hardware) and platform
utilization (determined by the scheduler of the operating system) enable its timely
execution. We have used the Embedded Machine to compile and execute high-performance
control applications written in Giotto, such as the flight control system of an
autonomous model helicopter.
acknowledgement: This research was supported in part by the DARPA SEC grant F33615-C-98-3614,
the MARCO GSRC grant 98-DT- 660, the AFOSR MURI grant F49620-00-1-0327, and the
NSF ITR grant CCR-0085949.
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
citation:
ama: 'Henzinger TA, Kirsch C. The embedded machine: predictable, portable real-time
code. In: Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language
Design and Implementation. ACM; 2002:315-326. doi:10.1145/512529.512567'
apa: 'Henzinger, T. A., & Kirsch, C. (2002). The embedded machine: predictable,
portable real-time code. In Proceedings of the ACM SIGPLAN 2002 conference
on Programming language design and implementation (pp. 315–326). Berlin, Germany:
ACM. https://doi.org/10.1145/512529.512567'
chicago: 'Henzinger, Thomas A, and Christoph Kirsch. “The Embedded Machine: Predictable,
Portable Real-Time Code.” In Proceedings of the ACM SIGPLAN 2002 Conference
on Programming Language Design and Implementation, 315–26. ACM, 2002. https://doi.org/10.1145/512529.512567.'
ieee: 'T. A. Henzinger and C. Kirsch, “The embedded machine: predictable, portable
real-time code,” in Proceedings of the ACM SIGPLAN 2002 conference on Programming
language design and implementation, Berlin, Germany, 2002, pp. 315–326.'
ista: 'Henzinger TA, Kirsch C. 2002. The embedded machine: predictable, portable
real-time code. Proceedings of the ACM SIGPLAN 2002 conference on Programming
language design and implementation. PLDI: Programming Languages Design and Implementation,
315–326.'
mla: 'Henzinger, Thomas A., and Christoph Kirsch. “The Embedded Machine: Predictable,
Portable Real-Time Code.” Proceedings of the ACM SIGPLAN 2002 Conference on
Programming Language Design and Implementation, ACM, 2002, pp. 315–26, doi:10.1145/512529.512567.'
short: T.A. Henzinger, C. Kirsch, in:, Proceedings of the ACM SIGPLAN 2002 Conference
on Programming Language Design and Implementation, ACM, 2002, pp. 315–326.
conference:
end_date: 2002-06-19
location: Berlin, Germany
name: 'PLDI: Programming Languages Design and Implementation'
start_date: 2002-06-17
date_created: 2018-12-11T12:08:53Z
date_published: 2002-06-01T00:00:00Z
date_updated: 2023-06-05T09:02:23Z
day: '01'
doi: 10.1145/512529.512567
extern: '1'
language:
- iso: eng
month: '06'
oa_version: None
page: 315 - 326
publication: Proceedings of the ACM SIGPLAN 2002 conference on Programming language
design and implementation
publication_identifier:
isbn:
- '9781581134636'
publication_status: published
publisher: ACM
publist_id: '284'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The embedded machine: predictable, portable real-time code'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2002'
...
---
_id: '4470'
abstract:
- lang: eng
text: Giotto is a platform-independent language for specifying software for high-performance
control applications. In this paper we present a new approach to the compilation
of Giotto. Following this approach, the Giotto compiler generates code for a virtual
machine, called the E machine, which can be ported to different platforms. The
Giotto compiler also checks if the generated E code is time safe for a given platform,
that is, if the platform offers sufficient performance to ensure that the E code
is executed in a timely fashion that conforms with the Giotto semantics. Time-safety
checking requires a schedulability analysis. We show that while for arbitrary
E code, the analysis is exponential, for E code generated from typical Giotto
programs, the analysis is polynomial. This supports our claim that Giotto identifies
a useful fragment of embedded programs.
acknowledgement: Supported in part by the DARPA SEC grant F33615-C-98-3614, MARCO
GSRC grant 98-DT-660, AFOSR MURI grant F49620-00-1-0327, NSF grant CCR-9988172,
and a Microsoft Research Fellowship.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Slobodan
full_name: Matic, Slobodan
last_name: Matic
citation:
ama: 'Henzinger TA, Kirsch C, Majumdar R, Matic S. Time-safety checking for embedded
programs. In: Proceedings of the 2nd International Conference on Embedded Software.
Vol 2491. ACM; 2002:76-92. doi:10.1007/3-540-45828-X_7'
apa: 'Henzinger, T. A., Kirsch, C., Majumdar, R., & Matic, S. (2002). Time-safety
checking for embedded programs. In Proceedings of the 2nd International Conference
on Embedded Software (Vol. 2491, pp. 76–92). Grenoble, France: ACM. https://doi.org/10.1007/3-540-45828-X_7'
chicago: Henzinger, Thomas A, Christoph Kirsch, Ritankar Majumdar, and Slobodan
Matic. “Time-Safety Checking for Embedded Programs.” In Proceedings of the
2nd International Conference on Embedded Software, 2491:76–92. ACM, 2002.
https://doi.org/10.1007/3-540-45828-X_7.
ieee: T. A. Henzinger, C. Kirsch, R. Majumdar, and S. Matic, “Time-safety checking
for embedded programs,” in Proceedings of the 2nd International Conference
on Embedded Software, Grenoble, France, 2002, vol. 2491, pp. 76–92.
ista: 'Henzinger TA, Kirsch C, Majumdar R, Matic S. 2002. Time-safety checking for
embedded programs. Proceedings of the 2nd International Conference on Embedded
Software. EMSOFT: Embedded Software , LNCS, vol. 2491, 76–92.'
mla: Henzinger, Thomas A., et al. “Time-Safety Checking for Embedded Programs.”
Proceedings of the 2nd International Conference on Embedded Software, vol.
2491, ACM, 2002, pp. 76–92, doi:10.1007/3-540-45828-X_7.
short: T.A. Henzinger, C. Kirsch, R. Majumdar, S. Matic, in:, Proceedings of the
2nd International Conference on Embedded Software, ACM, 2002, pp. 76–92.
conference:
end_date: 2002-10-09
location: Grenoble, France
name: 'EMSOFT: Embedded Software '
start_date: 2002-10-07
date_created: 2018-12-11T12:09:01Z
date_published: 2002-09-25T00:00:00Z
date_updated: 2023-06-05T08:50:59Z
day: '25'
doi: 10.1007/3-540-45828-X_7
extern: '1'
intvolume: ' 2491'
language:
- iso: eng
month: '09'
oa_version: None
page: 76 - 92
publication: Proceedings of the 2nd International Conference on Embedded Software
publication_identifier:
isbn:
- '9783540443070'
publication_status: published
publisher: ACM
publist_id: '259'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Time-safety checking for embedded programs
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2491
year: '2002'
...
---
_id: '4471'
abstract:
- lang: eng
text: The sequential synthesis problem, which is closely related to Church’s solvability
problem, asks, given a specification in the form of a binary relation between
input and output streams, for the construction of a finite-state stream transducer
that converts inputs to appropriate outputs. For efficiency reasons, practical
sequential hardware is often designed to operate without prior initialization.
Such hardware designs can be modeled by uninitialized state machines, which are
required to satisfy their specification if started from any state. In this paper
we solve the sequential synthesis problem for uninitialized systems, that is,
we construct uninitialized finite-state stream transducers. We consider specifications
given by LTL formulas, deterministic, nondeterministic, universal, and alternating
Büchi automata. We solve this uninitialized synthesis problem by reducing it to
the well-understood initialized synthesis problem. While our solution is straightforward,
it leads, for some specification formalisms, to upper bounds that are exponentially
worse than the complexity of the corresponding initialized problems. However,
we prove lower bounds to show that our simple solutions are optimal for all considered
specification formalisms. We also study the problem of deciding whether a given
specification is uninitialized, that is, if its uninitialized and initialized
synthesis problems coincide. We show that this problem has, for each specification
formalism, the same complexity as the equivalence problem.
acknowledgement: This research was supported in part by the SRC contract 99-TJ-683.003,
the DARPA contract NAG2-1214, and the NSF grant CCR-9988172.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Sriram
full_name: Krishnan, Sriram
last_name: Krishnan
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
- first_name: Freddy
full_name: Mang, Freddy
last_name: Mang
citation:
ama: 'Henzinger TA, Krishnan S, Kupferman O, Mang F. Synthesis of uninitialized
systems. In: Proceedings of the 29th International Colloquium on Automata,
Languages and Programming. Vol 2380. Springer; 2002:644-656. doi:10.1007/3-540-45465-9_55'
apa: 'Henzinger, T. A., Krishnan, S., Kupferman, O., & Mang, F. (2002). Synthesis
of uninitialized systems. In Proceedings of the 29th International Colloquium
on Automata, Languages and Programming (Vol. 2380, pp. 644–656). Malaga, Spain:
Springer. https://doi.org/10.1007/3-540-45465-9_55'
chicago: Henzinger, Thomas A, Sriram Krishnan, Orna Kupferman, and Freddy Mang.
“Synthesis of Uninitialized Systems.” In Proceedings of the 29th International
Colloquium on Automata, Languages and Programming, 2380:644–56. Springer,
2002. https://doi.org/10.1007/3-540-45465-9_55.
ieee: T. A. Henzinger, S. Krishnan, O. Kupferman, and F. Mang, “Synthesis of uninitialized
systems,” in Proceedings of the 29th International Colloquium on Automata,
Languages and Programming, Malaga, Spain, 2002, vol. 2380, pp. 644–656.
ista: 'Henzinger TA, Krishnan S, Kupferman O, Mang F. 2002. Synthesis of uninitialized
systems. Proceedings of the 29th International Colloquium on Automata, Languages
and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 2380,
644–656.'
mla: Henzinger, Thomas A., et al. “Synthesis of Uninitialized Systems.” Proceedings
of the 29th International Colloquium on Automata, Languages and Programming,
vol. 2380, Springer, 2002, pp. 644–56, doi:10.1007/3-540-45465-9_55.
short: T.A. Henzinger, S. Krishnan, O. Kupferman, F. Mang, in:, Proceedings of the
29th International Colloquium on Automata, Languages and Programming, Springer,
2002, pp. 644–656.
conference:
end_date: 2002-07-13
location: Malaga, Spain
name: 'ICALP: Automata, Languages and Programming'
start_date: 2002-07-08
date_created: 2018-12-11T12:09:01Z
date_published: 2002-06-26T00:00:00Z
date_updated: 2023-06-05T08:05:13Z
day: '26'
doi: 10.1007/3-540-45465-9_55
extern: '1'
intvolume: ' 2380'
language:
- iso: eng
month: '06'
oa_version: None
page: 644 - 656
publication: Proceedings of the 29th International Colloquium on Automata, Languages
and Programming
publication_identifier:
isbn:
- '9783540438649'
publication_status: published
publisher: Springer
publist_id: '257'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Synthesis of uninitialized systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2380
year: '2002'
...
---
_id: '4472'
abstract:
- lang: eng
text: 'We present a methodology and tool for verifying and certifying systems code.
The verification is based on the lazy-abstraction paradigm for intertwining the
following three logical steps: construct a predicate abstraction from the code,
model check the abstraction, and automatically refine the abstraction based on
counterexample analysis. The certification is based on the proof-carrying code
paradigm. Lazy abstraction enables the automatic construction of small proof certificates.
The methodology is implemented in Blast, the Berkeley Lazy Abstraction Software
verification Tool. We describe our experience applying Blast to Linux and Windows
device drivers. Given the C code for a driver and for a temporal-safety monitor,
Blast automatically generates an easily checkable correctness certificate if the
driver satisfies the specification, and an error trace otherwise.'
acknowledgement: This work was supported in part by the NSF ITR grants CCR-0085949,
CCR-0081588, the NSF Career grant CCR-9875171, the DARPA PCES grant F33615-00-C-1693,
the MARCO GSRC grant 98-DT-660, the SRC contract 99-TJ-683, a Microsoft fellowship,
and gifts from AT&T Research and Microsoft Research.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: George
full_name: Necula, George
last_name: Necula
- first_name: Ranjit
full_name: Jhala, Ranjit
last_name: Jhala
- first_name: Grégoire
full_name: Sutre, Grégoire
last_name: Sutre
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Westley
full_name: Weimer, Westley
last_name: Weimer
citation:
ama: 'Henzinger TA, Necula G, Jhala R, Sutre G, Majumdar R, Weimer W. Temporal safety
proofs for systems code. In: Proceedings of the 14th International Conference
on Computer Aided Verification. Vol 2404. Springer; 2002:526-538. doi:10.1007/3-540-45657-0_45'
apa: 'Henzinger, T. A., Necula, G., Jhala, R., Sutre, G., Majumdar, R., & Weimer,
W. (2002). Temporal safety proofs for systems code. In Proceedings of the 14th
International Conference on Computer Aided Verification (Vol. 2404, pp. 526–538).
Copenhagen, Denmark: Springer. https://doi.org/10.1007/3-540-45657-0_45'
chicago: Henzinger, Thomas A, George Necula, Ranjit Jhala, Grégoire Sutre, Ritankar
Majumdar, and Westley Weimer. “Temporal Safety Proofs for Systems Code.” In Proceedings
of the 14th International Conference on Computer Aided Verification, 2404:526–38.
Springer, 2002. https://doi.org/10.1007/3-540-45657-0_45.
ieee: T. A. Henzinger, G. Necula, R. Jhala, G. Sutre, R. Majumdar, and W. Weimer,
“Temporal safety proofs for systems code,” in Proceedings of the 14th International
Conference on Computer Aided Verification, Copenhagen, Denmark, 2002, vol.
2404, pp. 526–538.
ista: 'Henzinger TA, Necula G, Jhala R, Sutre G, Majumdar R, Weimer W. 2002. Temporal
safety proofs for systems code. Proceedings of the 14th International Conference
on Computer Aided Verification. CAV: Computer Aided Verification, LNCS, vol. 2404,
526–538.'
mla: Henzinger, Thomas A., et al. “Temporal Safety Proofs for Systems Code.” Proceedings
of the 14th International Conference on Computer Aided Verification, vol.
2404, Springer, 2002, pp. 526–38, doi:10.1007/3-540-45657-0_45.
short: T.A. Henzinger, G. Necula, R. Jhala, G. Sutre, R. Majumdar, W. Weimer, in:,
Proceedings of the 14th International Conference on Computer Aided Verification,
Springer, 2002, pp. 526–538.
conference:
end_date: 2002-07-31
location: Copenhagen, Denmark
name: 'CAV: Computer Aided Verification'
start_date: 2002-07-27
date_created: 2018-12-11T12:09:01Z
date_published: 2002-06-19T00:00:00Z
date_updated: 2023-06-05T08:11:32Z
day: '19'
doi: 10.1007/3-540-45657-0_45
extern: '1'
intvolume: ' 2404'
language:
- iso: eng
month: '06'
oa_version: None
page: 526 - 538
publication: Proceedings of the 14th International Conference on Computer Aided Verification
publication_identifier:
isbn:
- '9783540439974'
publication_status: published
publisher: Springer
publist_id: '258'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Temporal safety proofs for systems code
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2404
year: '2002'
...