---
_id: '4002'
abstract:
- lang: eng
text: Shape deformation refers to the continuous change of one geometric object
to another. We develop a software tool for planning, analyzing and visualizing
deformations between two shapes in R-2. The deformation is generated automatically
without any user intervention or specification of feature correspondences. A unique
property of the tool is the explicit availability of a two-dimensional shape space,
which can be used for designing the deformation either automatically by following
constraints and objectives or manually by drawing deformation paths.
acknowledgement: NSF under grants CCR-96-19542 and CCR-97-12088.
article_processing_charge: No
article_type: original
author:
- first_name: Siu
full_name: Cheng, Siu
last_name: Cheng
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Ping
full_name: Fu, Ping
last_name: Fu
- first_name: Ka
full_name: Lam, Ka
last_name: Lam
citation:
ama: 'Cheng S, Edelsbrunner H, Fu P, Lam K. Design and analysis of planar shape
deformation. Computational Geometry: Theory and Applications. 2001;19(2-3):205-218.
doi:10.1016/S0925-7721(01)00020-7'
apa: 'Cheng, S., Edelsbrunner, H., Fu, P., & Lam, K. (2001). Design and analysis
of planar shape deformation. Computational Geometry: Theory and Applications.
Elsevier. https://doi.org/10.1016/S0925-7721(01)00020-7'
chicago: 'Cheng, Siu, Herbert Edelsbrunner, Ping Fu, and Ka Lam. “Design and Analysis
of Planar Shape Deformation.” Computational Geometry: Theory and Applications.
Elsevier, 2001. https://doi.org/10.1016/S0925-7721(01)00020-7.'
ieee: 'S. Cheng, H. Edelsbrunner, P. Fu, and K. Lam, “Design and analysis of planar
shape deformation,” Computational Geometry: Theory and Applications, vol.
19, no. 2–3. Elsevier, pp. 205–218, 2001.'
ista: 'Cheng S, Edelsbrunner H, Fu P, Lam K. 2001. Design and analysis of planar
shape deformation. Computational Geometry: Theory and Applications. 19(2–3), 205–218.'
mla: 'Cheng, Siu, et al. “Design and Analysis of Planar Shape Deformation.” Computational
Geometry: Theory and Applications, vol. 19, no. 2–3, Elsevier, 2001, pp. 205–18,
doi:10.1016/S0925-7721(01)00020-7.'
short: 'S. Cheng, H. Edelsbrunner, P. Fu, K. Lam, Computational Geometry: Theory
and Applications 19 (2001) 205–218.'
date_created: 2018-12-11T12:06:22Z
date_published: 2001-07-01T00:00:00Z
date_updated: 2023-05-10T14:21:31Z
day: '01'
doi: 10.1016/S0925-7721(01)00020-7
extern: '1'
intvolume: ' 19'
issue: 2-3
language:
- iso: eng
month: '07'
oa_version: None
page: 205 - 218
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
issn:
- 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2124'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Design and analysis of planar shape deformation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 19
year: '2001'
...
---
_id: '4005'
abstract:
- lang: eng
text: This paper describes an algorithm for maintaining an approximating triangulation
of a deforming surface in R-3. The triangulation adapts dynamically to changing
shape, curvature, and topology of the surface.
article_processing_charge: No
author:
- first_name: Ho
full_name: Cheng, Ho
last_name: Cheng
- first_name: Tamal
full_name: Dey, Tamal
last_name: Dey
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: John
full_name: Sullivan, John
last_name: Sullivan
citation:
ama: 'Cheng H, Dey T, Edelsbrunner H, Sullivan J. Dynamic skin triangulation. In:
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms.
SIAM; 2001:47-56.'
apa: 'Cheng, H., Dey, T., Edelsbrunner, H., & Sullivan, J. (2001). Dynamic skin
triangulation. In Proceedings of the 12th annual ACM-SIAM symposium on Discrete
algorithms (pp. 47–56). Washington, DC, USA : SIAM.'
chicago: Cheng, Ho, Tamal Dey, Herbert Edelsbrunner, and John Sullivan. “Dynamic
Skin Triangulation.” In Proceedings of the 12th Annual ACM-SIAM Symposium on
Discrete Algorithms, 47–56. SIAM, 2001.
ieee: H. Cheng, T. Dey, H. Edelsbrunner, and J. Sullivan, “Dynamic skin triangulation,”
in Proceedings of the 12th annual ACM-SIAM symposium on Discrete algorithms,
Washington, DC, USA , 2001, pp. 47–56.
ista: 'Cheng H, Dey T, Edelsbrunner H, Sullivan J. 2001. Dynamic skin triangulation.
Proceedings of the 12th annual ACM-SIAM symposium on Discrete algorithms. SODA:
Symposium on Discrete Algorithms, 47–56.'
mla: Cheng, Ho, et al. “Dynamic Skin Triangulation.” Proceedings of the 12th
Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2001, pp. 47–56.
short: H. Cheng, T. Dey, H. Edelsbrunner, J. Sullivan, in:, Proceedings of the 12th
Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2001, pp. 47–56.
conference:
end_date: 2001-01-09
location: 'Washington, DC, USA '
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2001-01-07
date_created: 2018-12-11T12:06:23Z
date_published: 2001-01-09T00:00:00Z
date_updated: 2023-05-10T12:35:44Z
day: '09'
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.5555/365411.365418
month: '01'
oa_version: None
page: 47 - 56
publication: Proceedings of the 12th annual ACM-SIAM symposium on Discrete algorithms
publication_identifier:
isbn:
- '9780898714906'
publication_status: published
publisher: SIAM
publist_id: '2120'
quality_controlled: '1'
status: public
title: Dynamic skin triangulation
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4006'
abstract:
- lang: eng
text: The 180 models collected in this paper are produced by sampling and wrapping
point sets on tubes. The surfaces are represented as triangulated 2-manifolds
and available as st1-files from the author's web site at www.cs.duke.edu/similar
toedels. Each tube is obtained by thickening a circle or a smooth torus knot,
and for some we use the degrees of freedom in the thickening process to encode
meaningful information, such as curvature or torsion.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Edelsbrunner H. 180 wrapped tubes. Journal of Universal Computer Science.
2001;7(5):379-399. doi:10.3217/jucs-007-05-0379
apa: Edelsbrunner, H. (2001). 180 wrapped tubes. Journal of Universal Computer
Science. Springer. https://doi.org/10.3217/jucs-007-05-0379
chicago: Edelsbrunner, Herbert. “180 Wrapped Tubes.” Journal of Universal Computer
Science. Springer, 2001. https://doi.org/10.3217/jucs-007-05-0379.
ieee: H. Edelsbrunner, “180 wrapped tubes,” Journal of Universal Computer Science,
vol. 7, no. 5. Springer, pp. 379–399, 2001.
ista: Edelsbrunner H. 2001. 180 wrapped tubes. Journal of Universal Computer Science.
7(5), 379–399.
mla: Edelsbrunner, Herbert. “180 Wrapped Tubes.” Journal of Universal Computer
Science, vol. 7, no. 5, Springer, 2001, pp. 379–99, doi:10.3217/jucs-007-05-0379.
short: H. Edelsbrunner, Journal of Universal Computer Science 7 (2001) 379–399.
date_created: 2018-12-11T12:06:24Z
date_published: 2001-05-28T00:00:00Z
date_updated: 2023-05-10T12:39:54Z
day: '28'
doi: 10.3217/jucs-007-05-0379
extern: '1'
intvolume: ' 7'
issue: '5'
language:
- iso: eng
month: '05'
oa_version: None
page: 379 - 399
publication: Journal of Universal Computer Science
publication_identifier:
issn:
- 0948-695X
publication_status: published
publisher: Springer
publist_id: '2121'
quality_controlled: '1'
status: public
title: 180 wrapped tubes
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 7
year: '2001'
...
---
_id: '4007'
abstract:
- lang: eng
text: 'This paper describes an algorithm for maintaining an approximating triangulation
of a deforming surface in R 3 . The surface is the envelope of an infinite family
of spheres defined and controlled by a finite collection of weighted points. The
triangulation adapts dynamically to changing shape, curvature, and topology of
the surface. '
acknowledgement: NSF under grant DMS- 98-73945, ARO under grant DAAG55-98-1-0177,
NSF under grants CCR-96- 19542 and CCR-97-12088.
article_processing_charge: No
article_type: original
author:
- first_name: Ho
full_name: Cheng, Ho
last_name: Cheng
- first_name: Tamal
full_name: Dey, Tamal
last_name: Dey
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: John
full_name: Sullivan, John
last_name: Sullivan
citation:
ama: Cheng H, Dey T, Edelsbrunner H, Sullivan J. Dynamic skin triangulation. Discrete
& Computational Geometry. 2001;25(4):525-568. doi:10.1007/s00454-001-0007-1
apa: Cheng, H., Dey, T., Edelsbrunner, H., & Sullivan, J. (2001). Dynamic skin
triangulation. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-001-0007-1
chicago: Cheng, Ho, Tamal Dey, Herbert Edelsbrunner, and John Sullivan. “Dynamic
Skin Triangulation.” Discrete & Computational Geometry. Springer, 2001.
https://doi.org/10.1007/s00454-001-0007-1.
ieee: H. Cheng, T. Dey, H. Edelsbrunner, and J. Sullivan, “Dynamic skin triangulation,”
Discrete & Computational Geometry, vol. 25, no. 4. Springer, pp. 525–568,
2001.
ista: Cheng H, Dey T, Edelsbrunner H, Sullivan J. 2001. Dynamic skin triangulation.
Discrete & Computational Geometry. 25(4), 525–568.
mla: Cheng, Ho, et al. “Dynamic Skin Triangulation.” Discrete & Computational
Geometry, vol. 25, no. 4, Springer, 2001, pp. 525–68, doi:10.1007/s00454-001-0007-1.
short: H. Cheng, T. Dey, H. Edelsbrunner, J. Sullivan, Discrete & Computational
Geometry 25 (2001) 525–568.
date_created: 2018-12-11T12:06:24Z
date_published: 2001-04-04T00:00:00Z
date_updated: 2023-05-10T12:45:59Z
day: '04'
doi: 10.1007/s00454-001-0007-1
extern: '1'
intvolume: ' 25'
issue: '4'
language:
- iso: eng
month: '04'
oa_version: None
page: 525 - 568
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2122'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic skin triangulation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 25
year: '2001'
...
---
_id: '4200'
abstract:
- lang: eng
text: Zebrafish embryos homozygous for the masterblind (mb1) mutation exhibit a
striking phenotype in which the eyes and telencephalon are reduced or absent and
diencephalic fates expand to the front of the brain. Here we show that mb1(-/-)
embryos carry an amino-acid change at a conserved site in the Wnt pathway scaffolding
protein, Axin1. The amino-acid substitution present in the mbl allele abolishes
the binding of Axin to Gsk3 and affects Tcf-dependent transcription. Therefore,
Gsk3 activity may be decreased in mbl(-/-) embryos and in support of this possibility,
overexpression of either wild-type Axin1 or Gsk3 beta can restore eye and telencephalic
fates to mb1(-/-) embryos. Our data reveal a crucial role for Axin1-dependent
inhibition of the Wnt pathway in the early regional subdivision of the anterior
neural plate into telencephalic, diencephalic, and eye-forming territories.
acknowledgement: "We thank many colleagues who provided reagents that enabled us to
test axin1 and several other genes as candidates for the mbl mutation. In particular,
we are indebted to Masahiko Hibi, Ken Irvine, Antonio Jacinto, Yun-Jin Jiang, Julian
Lewis, and Tom Vogt for help and advice. We thank Ajay Chitnis and Dana Zivkovic
for providing information prior to publication. This study was supported primarily
by grants from the EMBO and EC to C.P.H., Wellcome Trust and EC to S.W.W., from
the MRC to D.S., from Naito to M.T., from the DHGP to G.J.R. and R.G., and from
the CRC/ICR to T.D. P.C. was supported by a PhD studentship from Fundação para a
Ciência e Tecnologia, Programa PRAXIS XXI. S.W.W. is a Wellcome Trust Senior Research
Fellow.\r\n\r\nThe publication costs of this article were defrayed in part by payment
of page charges. This article must therefore be hereby marked “advertisement” in
accordance with 18 USC section 1734 solely to indicate this fact."
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
- first_name: Corinne
full_name: Houart, Corinne
last_name: Houart
- first_name: Masaya
full_name: Take Uchi, Masaya
last_name: Take Uchi
- first_name: Gerd
full_name: Rauch, Gerd
last_name: Rauch
- first_name: Neville
full_name: Young, Neville
last_name: Young
- first_name: Pedro
full_name: Coutinho, Pedro
last_name: Coutinho
- first_name: Ichiro
full_name: Masai, Ichiro
last_name: Masai
- first_name: Luca
full_name: Caneparo, Luca
last_name: Caneparo
- first_name: Miguel
full_name: Concha, Miguel
last_name: Concha
- first_name: Robert
full_name: Geisler, Robert
last_name: Geisler
- first_name: Trevor
full_name: Dale, Trevor
last_name: Dale
- first_name: Stephen
full_name: Wilson, Stephen
last_name: Wilson
- first_name: Derek
full_name: Stemple, Derek
last_name: Stemple
citation:
ama: Heisenberg C-PJ, Houart C, Take Uchi M, et al. A mutation in the Gsk3-binding
domain of zebrafish Masterblind/Axin1 leads to a fate transformation of telencephalon
and eyes to diencephalon. Genes and Development. 2001;15(11):1427-1434.
doi:10.1101/gad.194301
apa: Heisenberg, C.-P. J., Houart, C., Take Uchi, M., Rauch, G., Young, N., Coutinho,
P., … Stemple, D. (2001). A mutation in the Gsk3-binding domain of zebrafish Masterblind/Axin1
leads to a fate transformation of telencephalon and eyes to diencephalon. Genes
and Development. Cold Spring Harbor Laboratory Press. https://doi.org/10.1101/gad.194301
chicago: Heisenberg, Carl-Philipp J, Corinne Houart, Masaya Take Uchi, Gerd Rauch,
Neville Young, Pedro Coutinho, Ichiro Masai, et al. “A Mutation in the Gsk3-Binding
Domain of Zebrafish Masterblind/Axin1 Leads to a Fate Transformation of Telencephalon
and Eyes to Diencephalon.” Genes and Development. Cold Spring Harbor Laboratory
Press, 2001. https://doi.org/10.1101/gad.194301.
ieee: C.-P. J. Heisenberg et al., “A mutation in the Gsk3-binding domain
of zebrafish Masterblind/Axin1 leads to a fate transformation of telencephalon
and eyes to diencephalon,” Genes and Development, vol. 15, no. 11. Cold
Spring Harbor Laboratory Press, pp. 1427–1434, 2001.
ista: Heisenberg C-PJ, Houart C, Take Uchi M, Rauch G, Young N, Coutinho P, Masai
I, Caneparo L, Concha M, Geisler R, Dale T, Wilson S, Stemple D. 2001. A mutation
in the Gsk3-binding domain of zebrafish Masterblind/Axin1 leads to a fate transformation
of telencephalon and eyes to diencephalon. Genes and Development. 15(11), 1427–1434.
mla: Heisenberg, Carl-Philipp J., et al. “A Mutation in the Gsk3-Binding Domain
of Zebrafish Masterblind/Axin1 Leads to a Fate Transformation of Telencephalon
and Eyes to Diencephalon.” Genes and Development, vol. 15, no. 11, Cold
Spring Harbor Laboratory Press, 2001, pp. 1427–34, doi:10.1101/gad.194301.
short: C.-P.J. Heisenberg, C. Houart, M. Take Uchi, G. Rauch, N. Young, P. Coutinho,
I. Masai, L. Caneparo, M. Concha, R. Geisler, T. Dale, S. Wilson, D. Stemple,
Genes and Development 15 (2001) 1427–1434.
date_created: 2018-12-11T12:07:33Z
date_published: 2001-06-01T00:00:00Z
date_updated: 2023-05-10T12:27:02Z
day: '01'
doi: 10.1101/gad.194301
extern: '1'
external_id:
pmid:
- '11390362'
intvolume: ' 15'
issue: '11'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC312705/
month: '06'
oa: 1
oa_version: Published Version
page: 1427 - 1434
pmid: 1
publication: Genes and Development
publication_identifier:
issn:
- 0890-9369
publication_status: published
publisher: Cold Spring Harbor Laboratory Press
publist_id: '1916'
quality_controlled: '1'
status: public
title: A mutation in the Gsk3-binding domain of zebrafish Masterblind/Axin1 leads
to a fate transformation of telencephalon and eyes to diencephalon
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '2001'
...
---
_id: '4229'
abstract:
- lang: eng
text: Bacteriophage of the family Leviviridae have played an important role in molecular
biology where representative species, such as Qβ and MS2, have been studied as
model systems for replication, translation, and the role of secondary structure
in gene regulation. Using nucleotide sequences from the coat and replicase genes
we present the first statistical estimate of phylogeny for the family Leviviridae
using maximum-likelihood and Bayesian estimation. Our analyses reveal that the
coliphage species are a monophyletic group consisting of two clades representing
the genera Levivirus and Allolevivirus. The Pseudomonas species PP7 diverged from
its common ancestor with the coliphage prior to the ancient split between these
genera and their subsequent diversification. Differences in genome size, gene
composition, and gene expression are shown with a high probability to have changed
along the lineage leading to the Allolevivirus through gene expansion. The change
in genome size of the Allolevivirus ancestor may have catalyzed subsequent changes
that led to their current genome organization and gene expression.
acknowledgement: "We thank Kenneth G. Karol, Andrea J. Betancourt, Daven C. Presgraves,
and Bret Larget for helpful comments and\r\nsuggestions. This work was supported
by funding from the National Science Foundation (MCB-0075404 and DEB-0075406) to
J.P.H."
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
- first_name: John
full_name: Huelsenbeck, John
last_name: Huelsenbeck
citation:
ama: Bollback JP, Huelsenbeck J. Phylogeny, genome evolution, and host specificity
of single-stranded RNA bacteriophage (Family Leviviridae). Journal of Molecular
Evolution. 2001;52(2):117-128. doi:10.1007/s002390010140
apa: Bollback, J. P., & Huelsenbeck, J. (2001). Phylogeny, genome evolution,
and host specificity of single-stranded RNA bacteriophage (Family Leviviridae).
Journal of Molecular Evolution. Springer. https://doi.org/10.1007/s002390010140
chicago: Bollback, Jonathan P, and John Huelsenbeck. “Phylogeny, Genome Evolution,
and Host Specificity of Single-Stranded RNA Bacteriophage (Family Leviviridae).”
Journal of Molecular Evolution. Springer, 2001. https://doi.org/10.1007/s002390010140.
ieee: J. P. Bollback and J. Huelsenbeck, “Phylogeny, genome evolution, and host
specificity of single-stranded RNA bacteriophage (Family Leviviridae),” Journal
of Molecular Evolution, vol. 52, no. 2. Springer, pp. 117–128, 2001.
ista: Bollback JP, Huelsenbeck J. 2001. Phylogeny, genome evolution, and host specificity
of single-stranded RNA bacteriophage (Family Leviviridae). Journal of Molecular
Evolution. 52(2), 117–128.
mla: Bollback, Jonathan P., and John Huelsenbeck. “Phylogeny, Genome Evolution,
and Host Specificity of Single-Stranded RNA Bacteriophage (Family Leviviridae).”
Journal of Molecular Evolution, vol. 52, no. 2, Springer, 2001, pp. 117–28,
doi:10.1007/s002390010140.
short: J.P. Bollback, J. Huelsenbeck, Journal of Molecular Evolution 52 (2001) 117–128.
date_created: 2018-12-11T12:07:43Z
date_published: 2001-02-01T00:00:00Z
date_updated: 2023-05-10T12:23:49Z
day: '01'
doi: 10.1007/s002390010140
extern: '1'
external_id:
pmid:
- '11231891'
intvolume: ' 52'
issue: '2'
language:
- iso: eng
month: '02'
oa_version: None
page: 117 - 128
pmid: 1
publication: Journal of Molecular Evolution
publication_identifier:
issn:
- 0022-2844
publication_status: published
publisher: Springer
publist_id: '1886'
quality_controlled: '1'
status: public
title: Phylogeny, genome evolution, and host specificity of single-stranded RNA bacteriophage
(Family Leviviridae)
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 52
year: '2001'
...
---
_id: '4264'
abstract:
- lang: eng
text: The study of speciation has become one of the most active areas of evolutionary
biology, and substantial progress has been made in documenting and understanding
phenomena ranging from sympatric speciation and reinforcement to the evolutionary
genetics of postzygotic isolation. This progress has been driven largely by empirical
results, and most useful theoretical work has concentrated on making sense of
empirical patterns. Given the complexity of speciation, mathematical theory is
subordinate to verbal theory and generalizations about data. Nevertheless, mathematical
theory can provide a useful classification of verbal theories; can help determine
the biological plausibility of verbal theories; can determine whether alternative
mechanisms of speciation are consistent with empirical patterns; and can occasionally
provide predictions that go beyond empirical generalizations. We discuss recent
examples of progress in each of these areas.
acknowledgement: 'We thank D. Bolnick, B. Fitzpatrick, S. Gavrilets, R. Haygood, C.D.
Jones, M. Kirkpatrick, A. Kondrashov, J.B. Mullet, S.V. Nuzhdin, H.A. Orr, T.D.
Price, T. Prout, D.W. Schemske, D. Schluter, M.R. Servedio and P.S. Ward for discussion
and comments. Some of these reviewers disagree with our conclusions. This work was
supported by US National Science Foundation grants DEB 9527808 and DEB 0089716 to
MT, grants from the Darwin Trust of Edinburgh and the Biotechnology and Biological
Sciences Research Council (GRJ/76057, GR/H/09928) to NHB, and National Institutes
of Health grant R01 GM58260 to JAC. '
article_processing_charge: No
article_type: original
author:
- first_name: Michael
full_name: Turelli, Michael
last_name: Turelli
- 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: Jerry
full_name: Coyne, Jerry
last_name: Coyne
citation:
ama: Turelli M, Barton NH, Coyne J. Theory and speciation. Trends in Ecology
and Evolution. 2001;16(7):330-343. doi:10.1016/S0169-5347(01)02177-2
apa: Turelli, M., Barton, N. H., & Coyne, J. (2001). Theory and speciation.
Trends in Ecology and Evolution. Cell Press. https://doi.org/10.1016/S0169-5347(01)02177-2
chicago: Turelli, Michael, Nicholas H Barton, and Jerry Coyne. “Theory and Speciation.”
Trends in Ecology and Evolution. Cell Press, 2001. https://doi.org/10.1016/S0169-5347(01)02177-2.
ieee: M. Turelli, N. H. Barton, and J. Coyne, “Theory and speciation,” Trends
in Ecology and Evolution, vol. 16, no. 7. Cell Press, pp. 330–343, 2001.
ista: Turelli M, Barton NH, Coyne J. 2001. Theory and speciation. Trends in Ecology
and Evolution. 16(7), 330–343.
mla: Turelli, Michael, et al. “Theory and Speciation.” Trends in Ecology and
Evolution, vol. 16, no. 7, Cell Press, 2001, pp. 330–43, doi:10.1016/S0169-5347(01)02177-2.
short: M. Turelli, N.H. Barton, J. Coyne, Trends in Ecology and Evolution 16 (2001)
330–343.
date_created: 2018-12-11T12:07:55Z
date_published: 2001-07-01T00:00:00Z
date_updated: 2023-05-10T12:16:55Z
day: '01'
doi: 10.1016/S0169-5347(01)02177-2
extern: '1'
external_id:
pmid:
- '11403865'
intvolume: ' 16'
issue: '7'
language:
- iso: eng
month: '07'
oa_version: None
page: 330 - 343
pmid: 1
publication: Trends in Ecology and Evolution
publication_identifier:
issn:
- 0169-5347
publication_status: published
publisher: Cell Press
publist_id: '1828'
quality_controlled: '1'
status: public
title: Theory and speciation
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 16
year: '2001'
...
---
_id: '4265'
abstract:
- lang: eng
text: The reasons that sex and recombination are so widespread remain elusive. One
popular hypothesis is that sex and recombination promote adaptation to a changing
environment. The strongest evidence that increased recombination may evolve because
recombination promotes adaptation comes from artificially selected populations.
Recombination rates have been found to increase as a correlated response to selection
on traits unrelated to recombination in several artificial selection experiments
and in a comparison of domesticated and nondomesticated mammals. There are, however,
several alternative explanations for the increase in recombination in such populations,
including two different evolutionary explanations. The first is that the form
of selection is epistatic, generating linkage disequilibria among selected loci,
which can indirectly favor modifier alleles that increase recombination. The second
is that random genetic drift in selected populations tends to generate disequilibria
such that beneficial alleles are often found in different individuals; modifier
alleles that increase recombination can bring together such favorable alleles
and thus may be found in individuals with greater fitness. In this paper, we compare
the evolutionary forces acting on recombination in finite populations subject
to strong selection, To our surprise, we found that drift accounted for the majority
of selection for increased recombination observed in simulations of small to moderately
large populations, suggesting that, unless selected populations are large, epistasis
plays a secondary role in the evolution of recombination.
acknowledgement: "We are grateful to P. Awadalla, T. Lenormand, A. Peters, S. West,
M. Whitlock, and two anonymous reviewers for helpful comments on the manuscript.
Funding was provided by the Natural Sciences and Engineering Research Council\r\n(Canada)
to SPO, the Centre National de la Recherche Scientifique (France) to SPO, the Darwin
Trust of Edinburgh to\r\nNHB, and the BBSRC (U.K.) to NHB. "
article_processing_charge: No
article_type: original
author:
- first_name: Sarah
full_name: Otto, Sarah
last_name: Otto
- 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: Otto S, Barton NH. Selection for recombination in small populations. Evolution;
International Journal of Organic Evolution. 2001;55(10):1921-1931. doi:10.1111/j.0014-3820.2001.tb01310.x
apa: Otto, S., & Barton, N. H. (2001). Selection for recombination in small
populations. Evolution; International Journal of Organic Evolution. Wiley-Blackwell.
https://doi.org/10.1111/j.0014-3820.2001.tb01310.x
chicago: Otto, Sarah, and Nicholas H Barton. “Selection for Recombination in Small
Populations.” Evolution; International Journal of Organic Evolution. Wiley-Blackwell,
2001. https://doi.org/10.1111/j.0014-3820.2001.tb01310.x.
ieee: S. Otto and N. H. Barton, “Selection for recombination in small populations,”
Evolution; International Journal of Organic Evolution, vol. 55, no. 10.
Wiley-Blackwell, pp. 1921–1931, 2001.
ista: Otto S, Barton NH. 2001. Selection for recombination in small populations.
Evolution; International Journal of Organic Evolution. 55(10), 1921–1931.
mla: Otto, Sarah, and Nicholas H. Barton. “Selection for Recombination in Small
Populations.” Evolution; International Journal of Organic Evolution, vol.
55, no. 10, Wiley-Blackwell, 2001, pp. 1921–31, doi:10.1111/j.0014-3820.2001.tb01310.x.
short: S. Otto, N.H. Barton, Evolution; International Journal of Organic Evolution
55 (2001) 1921–1931.
date_created: 2018-12-11T12:07:56Z
date_published: 2001-10-01T00:00:00Z
date_updated: 2023-05-10T12:12:32Z
day: '01'
doi: 10.1111/j.0014-3820.2001.tb01310.x
extern: '1'
external_id:
pmid:
- '11761054'
intvolume: ' 55'
issue: '10'
language:
- iso: eng
month: '10'
oa_version: None
page: 1921 - 1931
pmid: 1
publication: Evolution; International Journal of Organic Evolution
publication_identifier:
issn:
- 0014-3820
publication_status: published
publisher: Wiley-Blackwell
publist_id: '1827'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Selection for recombination in small populations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 55
year: '2001'
...
---
_id: '4266'
abstract:
- lang: eng
text: Hybridization may influence evolution in a variety of ways. If hybrids are
less fit, the geographical range of ecologically divergent populations may be
limited, and prezygotic reproductive isolation may be reinforced. If some hybrid
genotypes are fitter than one or both parents, at least in some environments,
then hybridization could make a positive contribution. Single alleles that are
at an advantage in the alternative environment and genetic background will introgress
readily, although such introgression may be hard to detect. 'Hybrid speciation',
in which fit combinations of alleles are established, is more problematic; its
likelihood depends on how divergent populations meet, and on the structure of
epistasis. These issues are illustrated using Fisher's model of stabilizing selection
on multiple traits, under which reproductive isolation evolves as a side-effect
of adaptation in allopatry. This confirms a priori arguments that while recombinant
hybrids are less fit on average, some gene combinations may be fitter than the
parents, even in the parental environment. Fisher's model does predict heterosis
in diploid F1s, asymmetric incompatibility in reciprocal backcrosses, and (when
dominance is included) Haldane's Rule. However, heterosis arises only when traits
are additive, whereas the latter two patterns require dominance. Moreover, because
adaptation is via substitutions of small effect, Fisher's model does not generate
the strong effects of single chromosome regions often observed in species crosses.
acknowledgement: This work was supported by the Darwin Trust of Edinburgh and by grant GR3/11635 from the Natural Environment Research
Council. I would like to thank Loren Rieseberg, Allen Orr, Michael Turelli, and
an anonymous referee for their helpful comments
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
citation:
ama: Barton NH. The role of hybridization in evolution. Molecular Ecology.
2001;10(3):551-568. doi:10.1046/j.1365-294X.2001.01216.x
apa: Barton, N. H. (2001). The role of hybridization in evolution. Molecular
Ecology. Wiley-Blackwell. https://doi.org/10.1046/j.1365-294X.2001.01216.x
chicago: Barton, Nicholas H. “The Role of Hybridization in Evolution.” Molecular
Ecology. Wiley-Blackwell, 2001. https://doi.org/10.1046/j.1365-294X.2001.01216.x.
ieee: N. H. Barton, “The role of hybridization in evolution,” Molecular Ecology,
vol. 10, no. 3. Wiley-Blackwell, pp. 551–568, 2001.
ista: Barton NH. 2001. The role of hybridization in evolution. Molecular Ecology.
10(3), 551–568.
mla: Barton, Nicholas H. “The Role of Hybridization in Evolution.” Molecular
Ecology, vol. 10, no. 3, Wiley-Blackwell, 2001, pp. 551–68, doi:10.1046/j.1365-294X.2001.01216.x.
short: N.H. Barton, Molecular Ecology 10 (2001) 551–568.
date_created: 2018-12-11T12:07:56Z
date_published: 2001-03-01T00:00:00Z
date_updated: 2023-05-10T11:45:07Z
day: '01'
doi: 10.1046/j.1365-294X.2001.01216.x
extern: '1'
external_id:
pmid:
- '11298968'
intvolume: ' 10'
issue: '3'
language:
- iso: eng
month: '03'
oa_version: None
page: 551 - 568
pmid: 1
publication: Molecular Ecology
publication_identifier:
issn:
- 962-1083
publication_status: published
publisher: Wiley-Blackwell
publist_id: '1824'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The role of hybridization in evolution
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '2001'
...
---
_id: '4267'
abstract:
- lang: eng
text: The flow of genes from the dense and well-adapted centre of a species' distribution
interferes with adaptation to marginal environments, and may sharply limit a species'
range. Deterministic models of a linear habitat suggest that populations could
in principle adapt to very steep environmental gradients, by increasing their
genetic variability. However, random fluctuations in sparse populations reduce
this variance, and may be crucial in limiting the species' range.
article_processing_charge: No
author:
- 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: 'Barton NH. Adaptation at the edge of a species’ range. In: Integrating
Ecology and Evolution in a Spatial Context. Cambridge University Press; 2001:365-392.'
apa: Barton, N. H. (2001). Adaptation at the edge of a species’ range. In Integrating
ecology and evolution in a spatial context (pp. 365–392). Cambridge University
Press.
chicago: Barton, Nicholas H. “Adaptation at the Edge of a Species’ Range.” In Integrating
Ecology and Evolution in a Spatial Context, 365–92. Cambridge University Press,
2001.
ieee: N. H. Barton, “Adaptation at the edge of a species’ range,” in Integrating
ecology and evolution in a spatial context, Cambridge University Press, 2001,
pp. 365–392.
ista: 'Barton NH. 2001.Adaptation at the edge of a species’ range. In: Integrating
ecology and evolution in a spatial context. , 365–392.'
mla: Barton, Nicholas H. “Adaptation at the Edge of a Species’ Range.” Integrating
Ecology and Evolution in a Spatial Context, Cambridge University Press, 2001,
pp. 365–92.
short: N.H. Barton, in:, Integrating Ecology and Evolution in a Spatial Context,
Cambridge University Press, 2001, pp. 365–392.
date_created: 2018-12-11T12:07:57Z
date_published: 2001-08-01T00:00:00Z
date_updated: 2023-05-10T11:59:06Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://www.cambridge.org/us/academic/subjects/life-sciences/ecology-and-conservation/integrating-ecology-and-evolution-spatial-context-14th-special-symposium-british-ecological-society?format=HB&isbn=9780521840002
month: '08'
oa_version: None
page: 365 - 392
publication: Integrating ecology and evolution in a spatial context
publication_identifier:
isbn:
- '9780521840002'
publication_status: published
publisher: Cambridge University Press
publist_id: '1825'
quality_controlled: '1'
status: public
title: Adaptation at the edge of a species' range
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4278'
abstract:
- lang: eng
text: 'The ability of species to migrate that has interested ecologists for many
years. Now that so many species and ecosystems face major environmental change,
the ability of species to adapt to these changes by dispersing, migrating, or
moving between different patches of habitat can be crucial to ensuring their survivial.
This book provides a timely and wide-ranging overview of the study of dispersal
and incorporates much of the latest research. The causes, mechanisms, and consequences
of dispersal at the individual, population, species and community levels are considered.
The potential of new techniques and models for studying dispersal, drawn from
molecular biology and demography, is also explored. Perspectives and insights
are offered from the fields of evolution, conservation biology and genetics. Throughout
the book, theoretical approaches are combined with empirical data, and care has
been taken to include examples from as wide a range of species as possible. '
article_processing_charge: No
author:
- 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: 'Barton NH. The evolutionary consequences of gene flow and local adaptation:
Future approaches. In: Dispersal. Oxford University Press; 2001.'
apa: 'Barton, N. H. (2001). The evolutionary consequences of gene flow and local
adaptation: Future approaches. In Dispersal. Oxford University Press.'
chicago: 'Barton, Nicholas H. “The Evolutionary Consequences of Gene Flow and Local
Adaptation: Future Approaches.” In Dispersal. Oxford University Press,
2001.'
ieee: 'N. H. Barton, “The evolutionary consequences of gene flow and local adaptation:
Future approaches,” in Dispersal, Oxford University Press, 2001.'
ista: 'Barton NH. 2001.The evolutionary consequences of gene flow and local adaptation:
Future approaches. In: Dispersal. .'
mla: 'Barton, Nicholas H. “The Evolutionary Consequences of Gene Flow and Local
Adaptation: Future Approaches.” Dispersal, Oxford University Press, 2001.'
short: N.H. Barton, in:, Dispersal, Oxford University Press, 2001.
date_created: 2018-12-11T12:08:00Z
date_published: 2001-04-01T00:00:00Z
date_updated: 2023-05-10T09:57:10Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://www.nhbs.com/dispersal-book
month: '04'
oa_version: None
publication: Dispersal
publication_identifier:
isbn:
- '9780198506591'
publication_status: published
publisher: Oxford University Press
publist_id: '1812'
quality_controlled: '1'
status: public
title: 'The evolutionary consequences of gene flow and local adaptation: Future approaches'
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4449'
abstract:
- lang: eng
text: Embedded software is software that interacts with physical processes. As em-
bedded systems increasingly permeate our daily lives on all levels, from micros-
copic devices to international networks, the cost-efficient development of reliable
embedded software is one of the grand challenges in computer science today. The
purpose of the workshop is to bring together researchers in all areas of computer
science that are traditionally distinct but relevant to embedded software develop-
ment, and to incubate a research community in this way. The workshop aims to cover
all aspects of the design and implementation of embedded software, inclu- ding
operating systems and middleware, programming languages and compilers, modeling
and validation, software engineering and programming methodologies, scheduling
and execution time analysis, networking and fault tolerance, as well as application
areas, such as embedded control, real-time signal processing, and telecommunications.
alternative_title:
- LNCS
article_processing_charge: No
citation:
ama: 'Henzinger TA, ed. EMSOFT: Embedded Software. Vol 2211. ACM; 2001. doi:10.1007/3-540-45449-7'
apa: 'Henzinger, T. A. (Ed.). (2001). EMSOFT: Embedded Software (Vol. 2211).
Presented at the EMSOFT 2001: Embedded Software, Tahoe City, CA, USA: ACM. https://doi.org/10.1007/3-540-45449-7'
chicago: 'Henzinger, Thomas A, ed. EMSOFT: Embedded Software. Vol. 2211.
ACM, 2001. https://doi.org/10.1007/3-540-45449-7.'
ieee: 'T. A. Henzinger, Ed., EMSOFT: Embedded Software, vol. 2211. ACM, 2001.'
ista: 'Henzinger TA ed. 2001. EMSOFT: Embedded Software, ACM,p.'
mla: 'Henzinger, Thomas A., editor. EMSOFT: Embedded Software. Vol. 2211,
ACM, 2001, doi:10.1007/3-540-45449-7.'
short: 'T.A. Henzinger, ed., EMSOFT: Embedded Software, ACM, 2001.'
conference:
end_date: 2001-10-10
location: Tahoe City, CA, USA
name: 'EMSOFT 2001: Embedded Software'
start_date: 2001-10-08
date_created: 2018-12-11T12:08:54Z
date_published: 2001-09-26T00:00:00Z
date_updated: 2023-05-10T09:53:17Z
day: '26'
doi: 10.1007/3-540-45449-7
editor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
extern: '1'
intvolume: ' 2211'
language:
- iso: eng
month: '09'
oa_version: None
publication_identifier:
isbn:
- '9783540426738'
publication_status: published
publisher: ACM
publist_id: '283'
quality_controlled: '1'
status: public
title: 'EMSOFT: Embedded Software'
type: conference_editor
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2211
year: '2001'
...
---
_id: '4475'
abstract:
- lang: eng
text: We provide an overview of the current status of HYTECH, and reflect on some
of the lessons learned from our experiences with the tool. HYTECH is a symbolic
model checker for mixed discrete-continuous systems that are modeled as automata
with piecewise-constant polyhedral differential inclusions. The use of a formal
input language and automated procedures for state-space traversal lay the foundation
for formally verifying properties of hybrid dynamical systems. We describe some
recent experiences analyzing three hybrid systems. We point out the successes
and limitations of the tool. The analysis procedure has been extended in a number
of ways to address some of the tool's shortcomings. We evaluate these extensions,
and conclude with some desiderata for verification tools for hybrid systems.
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: Joerg
full_name: Preussig, Joerg
last_name: Preussig
- first_name: Howard
full_name: Wong Toi, Howard
last_name: Wong Toi
citation:
ama: 'Henzinger TA, Preussig J, Wong Toi H. Some lessons from the HYTECH experience.
In: Proceedings of the 40th IEEE Conference on Decision and Control. Vol
3. IEEE; 2001:2887-2892. doi:10.1109/.2001.980714'
apa: 'Henzinger, T. A., Preussig, J., & Wong Toi, H. (2001). Some lessons from
the HYTECH experience. In Proceedings of the 40th IEEE Conference on Decision
and Control (Vol. 3, pp. 2887–2892). Orlando, FL, USA: IEEE. https://doi.org/10.1109/.2001.980714'
chicago: Henzinger, Thomas A, Joerg Preussig, and Howard Wong Toi. “Some Lessons
from the HYTECH Experience.” In Proceedings of the 40th IEEE Conference on
Decision and Control, 3:2887–92. IEEE, 2001. https://doi.org/10.1109/.2001.980714.
ieee: T. A. Henzinger, J. Preussig, and H. Wong Toi, “Some lessons from the HYTECH
experience,” in Proceedings of the 40th IEEE Conference on Decision and Control,
Orlando, FL, USA, 2001, vol. 3, pp. 2887–2892.
ista: 'Henzinger TA, Preussig J, Wong Toi H. 2001. Some lessons from the HYTECH
experience. Proceedings of the 40th IEEE Conference on Decision and Control. CDC:
Decision and Control vol. 3, 2887–2892.'
mla: Henzinger, Thomas A., et al. “Some Lessons from the HYTECH Experience.” Proceedings
of the 40th IEEE Conference on Decision and Control, vol. 3, IEEE, 2001, pp.
2887–92, doi:10.1109/.2001.980714.
short: T.A. Henzinger, J. Preussig, H. Wong Toi, in:, Proceedings of the 40th IEEE
Conference on Decision and Control, IEEE, 2001, pp. 2887–2892.
conference:
end_date: 2001-12-07
location: Orlando, FL, USA
name: 'CDC: Decision and Control'
start_date: 2001-12-04
date_created: 2018-12-11T12:09:02Z
date_published: 2001-05-01T00:00:00Z
date_updated: 2023-05-10T09:47:20Z
day: '01'
doi: 10.1109/.2001.980714
extern: '1'
intvolume: ' 3'
language:
- iso: eng
month: '05'
oa_version: None
page: 2887 - 2892
publication: Proceedings of the 40th IEEE Conference on Decision and Control
publication_identifier:
isbn:
- '0780370619'
publication_status: published
publisher: IEEE
publist_id: '253'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Some lessons from the HYTECH experience
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 3
year: '2001'
...
---
_id: '4477'
abstract:
- lang: eng
text: The assume-guarantee paradigm is a powerful divide-and-conquer mechanism for
decomposing a verification task about a system into subtasks about the individual
components of the system. The key to assume-guarantee reasoning is to consider
each component not in isolation, but in conjunction with assumptions about the
context of the component. Assume-guarantee principles are known for purely concurrent
contexts, which constrain the input data of a component, as well as for purely
sequential contexts, which constrain the entry configurations of a component.
We present a model for hierarchical system design which permits the arbitrary
nesting of parallel as well as serial composition, and which supports an assume-guarantee
principle for mixed parallel-serial contexts. Our model also supports both discrete
and continuous processes, and is therefore well-suited for the modeling and analysis
of embedded software systems which interact with real-world environments. Using
an example of two cooperating robots, we show refinement between a high-level
model which specifies continuous timing constraints and an implementation which
relies on discrete sampling.
acknowledgement: Support for this research was provided in part by the AFOSR MURI
grant F49620- 00-1-0327, and the DARPA SEC grant F33615-C-98-3614, the MARCO GSRC
grant 98-DT-660, the NSF ITR grant CCR-0085949.
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: Marius
full_name: Minea, Marius
last_name: Minea
- first_name: Vinayak
full_name: Prabhu, Vinayak
last_name: Prabhu
citation:
ama: 'Henzinger TA, Minea M, Prabhu V. Assume-guarantee reasoning for hierarchical
hybrid systems. In: Proceedings of the 4th International Workshop on Hybrid
Systems. Vol 2034. Springer; 2001:275-290. doi:10.1007/3-540-45351-2_24'
apa: 'Henzinger, T. A., Minea, M., & Prabhu, V. (2001). Assume-guarantee reasoning
for hierarchical hybrid systems. In Proceedings of the 4th International Workshop
on Hybrid Systems (Vol. 2034, pp. 275–290). Rome, Italy: Springer. https://doi.org/10.1007/3-540-45351-2_24'
chicago: Henzinger, Thomas A, Marius Minea, and Vinayak Prabhu. “Assume-Guarantee
Reasoning for Hierarchical Hybrid Systems.” In Proceedings of the 4th International
Workshop on Hybrid Systems, 2034:275–90. Springer, 2001. https://doi.org/10.1007/3-540-45351-2_24.
ieee: T. A. Henzinger, M. Minea, and V. Prabhu, “Assume-guarantee reasoning for
hierarchical hybrid systems,” in Proceedings of the 4th International Workshop
on Hybrid Systems, Rome, Italy, 2001, vol. 2034, pp. 275–290.
ista: 'Henzinger TA, Minea M, Prabhu V. 2001. Assume-guarantee reasoning for hierarchical
hybrid systems. Proceedings of the 4th International Workshop on Hybrid Systems.
HSCC: Hybrid Systems - Computation and Control, LNCS, vol. 2034, 275–290.'
mla: Henzinger, Thomas A., et al. “Assume-Guarantee Reasoning for Hierarchical Hybrid
Systems.” Proceedings of the 4th International Workshop on Hybrid Systems,
vol. 2034, Springer, 2001, pp. 275–90, doi:10.1007/3-540-45351-2_24.
short: T.A. Henzinger, M. Minea, V. Prabhu, in:, Proceedings of the 4th International
Workshop on Hybrid Systems, Springer, 2001, pp. 275–290.
conference:
end_date: 2001-03-30
location: Rome, Italy
name: 'HSCC: Hybrid Systems - Computation and Control'
start_date: 2001-03-28
date_created: 2018-12-11T12:09:03Z
date_published: 2001-03-14T00:00:00Z
date_updated: 2023-05-09T14:47:37Z
day: '14'
doi: 10.1007/3-540-45351-2_24
extern: '1'
intvolume: ' 2034'
language:
- iso: eng
month: '03'
oa_version: None
page: 275 - 290
publication: Proceedings of the 4th International Workshop on Hybrid Systems
publication_identifier:
isbn:
- '9783540418665'
publication_status: published
publisher: Springer
publist_id: '250'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Assume-guarantee reasoning for hierarchical hybrid systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2034
year: '2001'
...
---
_id: '4478'
abstract:
- lang: eng
text: Giotto is a principled, tool-supported design methodology for implementing
embedded control systems on platforms of possibly distributed sensors, actuators,
CPUs, and networks. Giotto is based on the principle that time-triggered task
invocations plus time-triggered mode switches can form the abstract essence of
programming real-time control systems. Giotto consists of a programming language
with a formal semantics, and a retargetable compiler and runtime library. Giotto
supports the automation of control system design by strictly separating platform-independent
functionality and timing concerns from platform-dependent scheduling and communication
issues. The time-triggered predictability of Giotto makes it particularly suitable
for safety-critical applications with hard real-time constraints. We illustrate
the platform-independence and time-triggered execution of Giotto by coordinating
a heterogeneous flock of Intel x86 robots and Lego Mindstorms robots.
acknowledgement: We thank Rupak Majumdar for implementing a prototype Giotto compiler
for Lego Mindstorms robots. We thank Dmitry Derevyanko and Winthrop Williams for
building our Intel x86 robots. We thank Edward Lee and Xiaojun Liu for help with
a Ptolemy II [4] implementation of Giotto. This research was supported in part by
the DARPA SEC grant F33615-C-98-3614, the DARPA MoBIES grant F33615- 00-C-1703,
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: Benjamin
full_name: Horowitz, Benjamin
last_name: Horowitz
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
citation:
ama: 'Henzinger TA, Horowitz B, Kirsch C. Embedded control systems development with
Giotto. In: Proceedings of the 2nd ACM SIGPLAN Workshop on Languages, Compilers
and Tools for Embedded Systems. ACM; 2001:64-72. doi:10.1145/384197.384208'
apa: 'Henzinger, T. A., Horowitz, B., & Kirsch, C. (2001). Embedded control
systems development with Giotto. In Proceedings of the 2nd ACM SIGPLAN workshop
on Languages, compilers and tools for embedded systems (pp. 64–72). New York,
NY, United States: ACM. https://doi.org/10.1145/384197.384208'
chicago: Henzinger, Thomas A, Benjamin Horowitz, and Christoph Kirsch. “Embedded
Control Systems Development with Giotto.” In Proceedings of the 2nd ACM SIGPLAN
Workshop on Languages, Compilers and Tools for Embedded Systems, 64–72. ACM,
2001. https://doi.org/10.1145/384197.384208.
ieee: T. A. Henzinger, B. Horowitz, and C. Kirsch, “Embedded control systems development
with Giotto,” in Proceedings of the 2nd ACM SIGPLAN workshop on Languages,
compilers and tools for embedded systems, New York, NY, United States, 2001,
pp. 64–72.
ista: 'Henzinger TA, Horowitz B, Kirsch C. 2001. Embedded control systems development
with Giotto. Proceedings of the 2nd ACM SIGPLAN workshop on Languages, compilers
and tools for embedded systems. LCTES: Languages, Compilers, and Tools for Embedded
Systems, 64–72.'
mla: Henzinger, Thomas A., et al. “Embedded Control Systems Development with Giotto.”
Proceedings of the 2nd ACM SIGPLAN Workshop on Languages, Compilers and Tools
for Embedded Systems, ACM, 2001, pp. 64–72, doi:10.1145/384197.384208.
short: T.A. Henzinger, B. Horowitz, C. Kirsch, in:, Proceedings of the 2nd ACM SIGPLAN
Workshop on Languages, Compilers and Tools for Embedded Systems, ACM, 2001, pp.
64–72.
conference:
location: New York, NY, United States
name: 'LCTES: Languages, Compilers, and Tools for Embedded Systems'
date_created: 2018-12-11T12:09:03Z
date_published: 2001-06-01T00:00:00Z
date_updated: 2023-05-10T09:37:20Z
day: '01'
doi: 10.1145/384197.384208
extern: '1'
language:
- iso: eng
month: '06'
oa_version: None
page: 64 - 72
publication: Proceedings of the 2nd ACM SIGPLAN workshop on Languages, compilers and
tools for embedded systems
publication_identifier:
isbn:
- '9781581134254'
publication_status: published
publisher: ACM
publist_id: '251'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Embedded control systems development with Giotto
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4479'
abstract:
- lang: eng
text: Giotto provides an abstract programmer’s model for the implementation of embedded
control systems with hard real-time constraints. A typical control application
consists of periodic software tasks together with a mode switching logic for enabling
and disabling tasks. Giotto specifies time-triggered sensor readings, task invocations,
and mode switches independent of any implementation platform. Giotto can be annotated
with platform constraints such as task-to-host mappings, and task and communication
schedules. The annotations are directives for the Giotto compiler, but they do
not alter the functionality and timing of a Giotto program. By separating the
platform-independent from the platform-dependent concerns, Giotto enables a great
deal of flexibility in choosing control platforms as well as a great deal of automation
in the validation and synthesis of control software. The time-triggered nature
of Giotto achieves timing predictability, which makes Giotto particularly suitable
for safety-critical applications.
acknowledgement: This research was supported in part by the DARPA SEC grant F33615-C-98-3614
and by the MARCO GSRC grant 98-DT-660.
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: Benjamin
full_name: Horowitz, Benjamin
last_name: Horowitz
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
citation:
ama: 'Henzinger TA, Horowitz B, Kirsch C. Giotto: A time-triggered language for
embedded programming. In: Proceedings of the 1st International Workshop on
Embedded Software. Vol 2211. ACM; 2001:166-184. doi:10.1007/3-540-45449-7_12'
apa: 'Henzinger, T. A., Horowitz, B., & Kirsch, C. (2001). Giotto: A time-triggered
language for embedded programming. In Proceedings of the 1st International
Workshop on Embedded Software (Vol. 2211, pp. 166–184). Tahoe City, CA, USA:
ACM. https://doi.org/10.1007/3-540-45449-7_12'
chicago: 'Henzinger, Thomas A, Benjamin Horowitz, and Christoph Kirsch. “Giotto:
A Time-Triggered Language for Embedded Programming.” In Proceedings of the
1st International Workshop on Embedded Software, 2211:166–84. ACM, 2001. https://doi.org/10.1007/3-540-45449-7_12.'
ieee: 'T. A. Henzinger, B. Horowitz, and C. Kirsch, “Giotto: A time-triggered language
for embedded programming,” in Proceedings of the 1st International Workshop
on Embedded Software, Tahoe City, CA, USA, 2001, vol. 2211, pp. 166–184.'
ista: 'Henzinger TA, Horowitz B, Kirsch C. 2001. Giotto: A time-triggered language
for embedded programming. Proceedings of the 1st International Workshop on Embedded
Software. EMSOFT: Embedded Software , LNCS, vol. 2211, 166–184.'
mla: 'Henzinger, Thomas A., et al. “Giotto: A Time-Triggered Language for Embedded
Programming.” Proceedings of the 1st International Workshop on Embedded Software,
vol. 2211, ACM, 2001, pp. 166–84, doi:10.1007/3-540-45449-7_12.'
short: T.A. Henzinger, B. Horowitz, C. Kirsch, in:, Proceedings of the 1st International
Workshop on Embedded Software, ACM, 2001, pp. 166–184.
conference:
end_date: 2001-10-10
location: Tahoe City, CA, USA
name: 'EMSOFT: Embedded Software '
start_date: 2001-10-08
date_created: 2018-12-11T12:09:04Z
date_published: 2001-09-26T00:00:00Z
date_updated: 2023-05-10T09:42:10Z
day: '26'
doi: 10.1007/3-540-45449-7_12
extern: '1'
intvolume: ' 2211'
language:
- iso: eng
month: '09'
oa_version: None
page: 166 - 184
publication: Proceedings of the 1st International Workshop on Embedded Software
publication_identifier:
isbn:
- '9783540426738'
publication_status: published
publisher: ACM
publist_id: '252'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Giotto: A time-triggered language for embedded programming'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2211
year: '2001'
...
---
_id: '4564'
abstract:
- lang: eng
text: This paper presents a concept for integrating the embedded programming methodology
Giotto and the object-oriented AOCS Framework to create an environment for the
rapid development of distributed software for safety-critical embedded control
systems with hard real-time requirements of the kind typically found in aerospace
applications.
acknowledgement: 'This research was supported in part by DARPA under grants F336 15-C-98-36
14, F33615-00-(2-1693, and F33615-00-C-1703, and by MARC0 under grant 98-DT-660. '
article_processing_charge: No
author:
- first_name: Timothy
full_name: Brown, Timothy
last_name: Brown
- first_name: Alessandro
full_name: Pasetti, Alessandro
last_name: Pasetti
- first_name: Wolfgang
full_name: Pree, Wolfgang
last_name: Pree
- 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: 'Brown T, Pasetti A, Pree W, Henzinger TA, Kirsch C. A reusable and platform-independent
framework for distributed control systems. In: Proceedings of the 20th Digital
Avionics Systems Conference. IEEE; 2001:1-11. doi:10.1109/DASC.2001.964169'
apa: 'Brown, T., Pasetti, A., Pree, W., Henzinger, T. A., & Kirsch, C. (2001).
A reusable and platform-independent framework for distributed control systems.
In Proceedings of the 20th Digital Avionics Systems Conference (pp. 1–11).
Daytona Beach, FL, USA: IEEE. https://doi.org/10.1109/DASC.2001.964169'
chicago: Brown, Timothy, Alessandro Pasetti, Wolfgang Pree, Thomas A Henzinger,
and Christoph Kirsch. “A Reusable and Platform-Independent Framework for Distributed
Control Systems.” In Proceedings of the 20th Digital Avionics Systems Conference,
1–11. IEEE, 2001. https://doi.org/10.1109/DASC.2001.964169.
ieee: T. Brown, A. Pasetti, W. Pree, T. A. Henzinger, and C. Kirsch, “A reusable
and platform-independent framework for distributed control systems,” in Proceedings
of the 20th Digital Avionics Systems Conference, Daytona Beach, FL, USA, 2001,
pp. 1–11.
ista: 'Brown T, Pasetti A, Pree W, Henzinger TA, Kirsch C. 2001. A reusable and
platform-independent framework for distributed control systems. Proceedings of
the 20th Digital Avionics Systems Conference. DASC: Digital Avionics Systems Conference,
1–11.'
mla: Brown, Timothy, et al. “A Reusable and Platform-Independent Framework for Distributed
Control Systems.” Proceedings of the 20th Digital Avionics Systems Conference,
IEEE, 2001, pp. 1–11, doi:10.1109/DASC.2001.964169.
short: T. Brown, A. Pasetti, W. Pree, T.A. Henzinger, C. Kirsch, in:, Proceedings
of the 20th Digital Avionics Systems Conference, IEEE, 2001, pp. 1–11.
conference:
end_date: 2001-10-18
location: Daytona Beach, FL, USA
name: 'DASC: Digital Avionics Systems Conference'
start_date: 2001-10-14
date_created: 2018-12-11T12:09:30Z
date_published: 2001-08-06T00:00:00Z
date_updated: 2023-05-09T12:23:16Z
day: '06'
doi: 10.1109/DASC.2001.964169
extern: '1'
language:
- iso: eng
month: '08'
oa_version: None
page: 1 - 11
publication: Proceedings of the 20th Digital Avionics Systems Conference
publication_identifier:
isbn:
- '0780370341'
publication_status: published
publisher: IEEE
publist_id: '143'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A reusable and platform-independent framework for distributed control systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4599'
abstract:
- lang: eng
text: 'State-space explosion is a fundamental obstacle in the formal verification
of designs and protocols. Several techniques for combating this problem have emerged
in the past few years, among which two are significant: partial-order reduction
and symbolic state-space search. In asynchronous systems, interleavings of independent
concurrent events are equivalent, and only a representative interleaving needs
to be explored to verify local properties. Partial-order methods exploit this
redundancy and visit only a subset of the reachable states. Symbolic techniques,
on the other hand, capture the transition relation of a system and the set of
reachable states as boolean functions. In many cases, these functions can be represented
compactly using binary decision diagrams (BDDs). Traditionally, the two techniques
have been practiced by two different schools—partial-order methods with enumerative
depth-first search for the analysis of asynchronous network protocols, and symbolic
breadth-first search for the analysis of synchronous hardware designs. We combine
both approaches and develop a method for using partial-order reduction techniques
in symbolic BDD-based invariant checking. We present theoretical results to prove
the correctness of the method, and experimental results to demonstrate its efficacy.'
acknowledgement: Gerard Holzmann provided us with information on SPIN. Ken McMillan
and Doron Peled contributed through discussions. The VIS group at UC Berkeley and
Rajeev Ranjan in particular helped with the experiments.
article_processing_charge: No
article_type: original
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Robert
full_name: Brayton, Robert
last_name: Brayton
- 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: Shaz
full_name: Qadeer, Shaz
last_name: Qadeer
- first_name: Sriram
full_name: Rajamani, Sriram
last_name: Rajamani
citation:
ama: Alur R, Brayton R, Henzinger TA, Qadeer S, Rajamani S. Partial-order reduction
in symbolic state-space exploration. Formal Methods in System Design. 2001;18(2):97-116.
doi:10.1023/A:1008767206905
apa: Alur, R., Brayton, R., Henzinger, T. A., Qadeer, S., & Rajamani, S. (2001).
Partial-order reduction in symbolic state-space exploration. Formal Methods
in System Design. Springer. https://doi.org/10.1023/A:1008767206905
chicago: Alur, Rajeev, Robert Brayton, Thomas A Henzinger, Shaz Qadeer, and Sriram
Rajamani. “Partial-Order Reduction in Symbolic State-Space Exploration.” Formal
Methods in System Design. Springer, 2001. https://doi.org/10.1023/A:1008767206905.
ieee: R. Alur, R. Brayton, T. A. Henzinger, S. Qadeer, and S. Rajamani, “Partial-order
reduction in symbolic state-space exploration,” Formal Methods in System Design,
vol. 18, no. 2. Springer, pp. 97–116, 2001.
ista: Alur R, Brayton R, Henzinger TA, Qadeer S, Rajamani S. 2001. Partial-order
reduction in symbolic state-space exploration. Formal Methods in System Design.
18(2), 97–116.
mla: Alur, Rajeev, et al. “Partial-Order Reduction in Symbolic State-Space Exploration.”
Formal Methods in System Design, vol. 18, no. 2, Springer, 2001, pp. 97–116,
doi:10.1023/A:1008767206905.
short: R. Alur, R. Brayton, T.A. Henzinger, S. Qadeer, S. Rajamani, Formal Methods
in System Design 18 (2001) 97–116.
date_created: 2018-12-11T12:09:41Z
date_published: 2001-03-01T00:00:00Z
date_updated: 2023-05-08T12:22:38Z
day: '01'
doi: 10.1023/A:1008767206905
extern: '1'
intvolume: ' 18'
issue: '2'
language:
- iso: eng
month: '03'
oa_version: None
page: 97 - 116
publication: Formal Methods in System Design
publication_identifier:
issn:
- 0925-9856
publication_status: published
publisher: Springer
publist_id: '108'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Partial-order reduction in symbolic state-space exploration
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 18
year: '2001'
...
---
_id: '4600'
abstract:
- lang: eng
text: 'Model checking is a practical tool for automated debugging of embedded software.
In model checking, a high-level description of a system is compared against a
logical correctness requirement to discover inconsistencies. Since model checking
is based on exhaustive state-space exploration and the size of the state space
of a design grows exponentially with the size of the description, scalability
remains a challenge. We have thus developed techniques for exploiting modular
design structure during model checking, and the model checker jMocha (Java MOdel-CHecking
Algorithm) is based on this theme. Instead of manipulating unstructured state-transition
graphs, it supports the hierarchical modeling framework of reactive modules. jMocha
is a growing interactive software environment for specification, simulation and
verification, and is intended as a vehicle for the development of new verification
algorithms and approaches. It is written in Java and uses native C-code BDD libraries
from VIS. jMocha offers: (1) a GUI that looks familiar to Windows/Java users;
(2) a simulator that displays traces in a message sequence chart fashion; (3)
requirements verification both by symbolic and enumerative model checking; (4)
implementation verification by checking trace containment; (5) a proof manager
that aids compositional and assume-guarantee reasoning; and (6) SLANG (Scripting
LANGuage) for the rapid and structured development of new verification algorithms.
jMocha is available publicly at ; it is a successor and extension of the original
Mocha tool that was entirely written in C.'
acknowledgement: 'We thank Himyanshu Anand, Ben Horowitz, Franjo Ivancic, Michael
McDougall, Marius Minea, Oliver Moeller. Shaz Qadeer, Sriram Rajamani, and Jean-Francois
Raskin for their assistance in the development of JMOCHA. The MOCHA project is funded
in part by the DARPA grant NAG2-1214, the NSF CAREER awards CCR95-01708 and CCR97-34115,
the NSF grant CCR99-70925, the NSF ITR grant CCR0085949, the MARC0 grant 98-DT-660,
and the SRC contracts 99-TJ-683.003 and 99-TJ-688. '
article_processing_charge: No
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Radu
full_name: Grosu, Radu
last_name: Grosu
- 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: Myong
full_name: Kang, Myong
last_name: Kang
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Freddy
full_name: Mang, Freddy
last_name: Mang
- first_name: Bow
full_name: Wang, Bow
last_name: Wang
citation:
ama: 'Alur R, De Alfaro L, Grosu R, et al. jMocha: A model-checking tool that exploits
design structure. In: Proceedings of the 23rd International Conference on Software
Engineering. IEEE; 2001:835-836. doi:10.1109/ICSE.2001.919196'
apa: 'Alur, R., De Alfaro, L., Grosu, R., Henzinger, T. A., Kang, M., Kirsch, C.,
… Wang, B. (2001). jMocha: A model-checking tool that exploits design structure.
In Proceedings of the 23rd International Conference on Software Engineering
(pp. 835–836). IEEE. https://doi.org/10.1109/ICSE.2001.919196'
chicago: 'Alur, Rajeev, Luca De Alfaro, Radu Grosu, Thomas A Henzinger, Myong Kang,
Christoph Kirsch, Ritankar Majumdar, Freddy Mang, and Bow Wang. “JMocha: A Model-Checking
Tool That Exploits Design Structure.” In Proceedings of the 23rd International
Conference on Software Engineering, 835–36. IEEE, 2001. https://doi.org/10.1109/ICSE.2001.919196.'
ieee: 'R. Alur et al., “jMocha: A model-checking tool that exploits design
structure,” in Proceedings of the 23rd International Conference on Software
Engineering, 2001, pp. 835–836.'
ista: 'Alur R, De Alfaro L, Grosu R, Henzinger TA, Kang M, Kirsch C, Majumdar R,
Mang F, Wang B. 2001. jMocha: A model-checking tool that exploits design structure.
Proceedings of the 23rd International Conference on Software Engineering. ICSE:
Software Engineering, 835–836.'
mla: 'Alur, Rajeev, et al. “JMocha: A Model-Checking Tool That Exploits Design Structure.”
Proceedings of the 23rd International Conference on Software Engineering,
IEEE, 2001, pp. 835–36, doi:10.1109/ICSE.2001.919196.'
short: R. Alur, L. De Alfaro, R. Grosu, T.A. Henzinger, M. Kang, C. Kirsch, R. Majumdar,
F. Mang, B. Wang, in:, Proceedings of the 23rd International Conference on Software
Engineering, IEEE, 2001, pp. 835–836.
conference:
name: 'ICSE: Software Engineering'
date_created: 2018-12-11T12:09:41Z
date_published: 2001-08-07T00:00:00Z
date_updated: 2023-05-08T14:06:55Z
day: '07'
doi: 10.1109/ICSE.2001.919196
extern: '1'
language:
- iso: eng
month: '08'
oa_version: None
page: 835 - 836
publication: Proceedings of the 23rd International Conference on Software Engineering
publication_identifier:
isbn:
- '0769510507'
publication_status: published
publisher: IEEE
publist_id: '109'
quality_controlled: '1'
status: public
title: 'jMocha: A model-checking tool that exploits design structure'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...
---
_id: '4622'
abstract:
- lang: eng
text: Conventional type systems specify interfaces in terms of values and domains.
We present a light-weight formalism that captures the temporal aspects of software
component interfaces. Specifically, we use an automata-based language to capture
both input assumptions about the order in which the methods of a component are
called, and output guarantees about the order in which the component calls external
methods. The formalism supports automatic compatability checks between interface
models, and thus constitutes a type system for component interaction. Unlike traditional
uses of automata, our formalism is based on an optimistic approach to composition,
and on an alternating approach to design refinement. According to the optimistic
approach, two components are compatible if there is some environment that can
make them work together. According to the alternating approach, one interface
refines another if it has weaker input assumptions, and stronger output guarantees.
We show that these notions have game-theoretic foundations that lead to efficient
algorithms for checking compatibility and refinement.
acknowledgement: We thank Edward A. Lee, Xiaojun Liu, Freddy Mang, and Yuhong Xiong
for fruitful discussions. This research was supported in part by the AFOSR MURI
grant F49620-00-1-0327, the DARPA MoBIES grant F33615-00-C-1703, the MARCO GSRC
grant 98-DT-660, the NSF Theory grant CCR-9988172, and the NSF ITR grant CCR-0085949.
article_processing_charge: No
author:
- 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
citation:
ama: 'De Alfaro L, Henzinger TA. Interface automata. In: Proceedings of the 8th
European Software Engineering Conference. ACM; 2001:109-120. doi:10.1145/503209.503226'
apa: 'De Alfaro, L., & Henzinger, T. A. (2001). Interface automata. In Proceedings
of the 8th European software engineering conference (pp. 109–120). Vienna,
Austria: ACM. https://doi.org/10.1145/503209.503226'
chicago: De Alfaro, Luca, and Thomas A Henzinger. “Interface Automata.” In Proceedings
of the 8th European Software Engineering Conference, 109–20. ACM, 2001. https://doi.org/10.1145/503209.503226.
ieee: L. De Alfaro and T. A. Henzinger, “Interface automata,” in Proceedings
of the 8th European software engineering conference, Vienna, Austria, 2001,
pp. 109–120.
ista: 'De Alfaro L, Henzinger TA. 2001. Interface automata. Proceedings of the 8th
European software engineering conference. FSE: Foundations of Software Engineering,
109–120.'
mla: De Alfaro, Luca, and Thomas A. Henzinger. “Interface Automata.” Proceedings
of the 8th European Software Engineering Conference, ACM, 2001, pp. 109–20,
doi:10.1145/503209.503226.
short: L. De Alfaro, T.A. Henzinger, in:, Proceedings of the 8th European Software
Engineering Conference, ACM, 2001, pp. 109–120.
conference:
end_date: 2001-09-14
location: Vienna, Austria
name: 'FSE: Foundations of Software Engineering'
start_date: 2001-09-10
date_created: 2018-12-11T12:09:48Z
date_published: 2001-06-01T00:00:00Z
date_updated: 2023-05-08T12:01:02Z
day: '01'
doi: 10.1145/503209.503226
extern: '1'
language:
- iso: eng
month: '06'
oa_version: None
page: 109 - 120
publication: Proceedings of the 8th European software engineering conference
publication_identifier:
isbn:
- '9781581133905'
publication_status: published
publisher: ACM
publist_id: '83'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Interface automata
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '2001'
...