---
_id: '4297'
abstract:
- lang: eng
text: The F5 (2n = 34) and FM2 (2n = 44-46) chromosome races of the Sceloporus grammicus
complex form a parapatric hybrid zone in the Mexican state of Hidalgo, characterized
by steep concordant clines among three diagnostic chromosome markers across a
straight-line distance of about 2 km. Here, we show that this zone is actually
structured into local patches in which hybridization extends over an extremely
irregular front. The distribution of hybrid-index (HI) scores across the transect
reveals some hybridization at almost all localities mapped in a central 7 km x
3 km area. Pooling the central samples produces both a strong heterozygote deficit
for all diagnostic markers and strong linkage disequilibria between all pairwise
combinations of these (unlinked) markers. Moreover, a highly significant association
exists between the habitat on which each individual was caught and its karyotype
(F5 chromosomes are more likely to be found on oak). Analysis of genotype frequencies
over a range of spatial scales shows that there is no significant heterozygote
deficit or habitat association within local areas of less than about 200 m; however,
there is significant linkage disequilibrium over the smallest scales (R = D (pquv)1/2
= 0.29, support limits, 0.18-0.36) over 100 m. These patterns suggest that lizards
mate and choose habitats randomly within local patches. This conclusion is supported
by mark-recapture estimates of dispersal (≈ 80 m in a generation) and by inference
of matings from embryo and maternal karyotypes. Closer examination of the two-dimensional
pattern reveals a convoluted cline for all three markers, with a width of 830
m (support limits 770 m-930 m). This cline width, combined with the strength of
local linkage disequilibrium, implies a dispersal rate of σ = 160 m in a generation
and an effective selection pressure of 30% on each chromosome marker. The proportion
of inviable embryos is greater in females from the center of the hybrid zone;
this is caused by effects associated with both karyotype and location. The hybrid
zone is likely to be maintained by selection against chromosomal heterozygotes,
by other kinds of selection against hybrids, and by selection adapting the chromosome
races to different habitats. The structure of the contact may be caused by both
random drift and by selection in relation to habitat.
acknowledgement: For field assistance in collecting and mapping of the zone, we thank
E. Arevalo, I. Goyenechea, D. Hutchison, M. Man- cilia, F. Mendoza, D. Mink, and
J. and H. Sites. The mark- recapture work was carried out by M. Mancilla,
F Mendoza, and A. Gonzales. J.W.S. also thanks T. Hinckley and D. Stevens of the Brigham Young University Department of
Geography for lessons in surveying and map making and use of the field equipment and planimeter. B. Nürnberger provided
the digitized coordinates for individual lizards and assisted with the analysis of
spatial structure and viability. B. Nürnberger, C. MacCallum, J. Mallet, and
J. Searle also provided helpful comments on the manuscript. This work was
supported by National Science Foundation grants BSR 85- 09092 and 88-22751 to
J.W.S., and grants from the Science and Engineering Research Council (GR/H09929)
and Natural Environment Research Council (GR3/8002) and the DarwinTrust to N.H.B.
The Mexican agency Secretaria de DesarrolloUrbano y Ecologia (now Secretaria de Desarrollo Social)
kindly provided scientific collecting permits (to E. Arévalo) for field work in 1989 and 1991.
article_processing_charge: No
article_type: original
author:
- first_name: Jack
full_name: Sites, Jack
last_name: Sites
- 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: Kent
full_name: Reed, Kent
last_name: Reed
citation:
ama: Sites J, Barton NH, Reed K. The genetic structure of a mosaic hybrid zone between
two chromosome races of the Sceloporus grammicus complex (Sauria, Phrynosomatidae)
in central Mexico. Evolution. 1995;49(1):9-36. doi:10.1111/j.1558-5646.1995.tb05955.x
apa: Sites, J., Barton, N. H., & Reed, K. (1995). The genetic structure of a
mosaic hybrid zone between two chromosome races of the Sceloporus grammicus complex
(Sauria, Phrynosomatidae) in central Mexico. Evolution. Wiley-Blackwell.
https://doi.org/10.1111/j.1558-5646.1995.tb05955.x
chicago: Sites, Jack, Nicholas H Barton, and Kent Reed. “The Genetic Structure of
a Mosaic Hybrid Zone between Two Chromosome Races of the Sceloporus Grammicus
Complex (Sauria, Phrynosomatidae) in Central Mexico.” Evolution. Wiley-Blackwell,
1995. https://doi.org/10.1111/j.1558-5646.1995.tb05955.x.
ieee: J. Sites, N. H. Barton, and K. Reed, “The genetic structure of a mosaic hybrid
zone between two chromosome races of the Sceloporus grammicus complex (Sauria,
Phrynosomatidae) in central Mexico,” Evolution, vol. 49, no. 1. Wiley-Blackwell,
pp. 9–36, 1995.
ista: Sites J, Barton NH, Reed K. 1995. The genetic structure of a mosaic hybrid
zone between two chromosome races of the Sceloporus grammicus complex (Sauria,
Phrynosomatidae) in central Mexico. Evolution. 49(1), 9–36.
mla: Sites, Jack, et al. “The Genetic Structure of a Mosaic Hybrid Zone between
Two Chromosome Races of the Sceloporus Grammicus Complex (Sauria, Phrynosomatidae)
in Central Mexico.” Evolution, vol. 49, no. 1, Wiley-Blackwell, 1995, pp.
9–36, doi:10.1111/j.1558-5646.1995.tb05955.x.
short: J. Sites, N.H. Barton, K. Reed, Evolution 49 (1995) 9–36.
date_created: 2018-12-11T12:08:06Z
date_published: 1995-02-01T00:00:00Z
date_updated: 2022-06-13T09:24:40Z
day: '01'
doi: 10.1111/j.1558-5646.1995.tb05955.x
extern: '1'
external_id:
pmid:
- '28593667'
intvolume: ' 49'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1558-5646.1995.tb05955.x
month: '02'
oa: 1
oa_version: Published Version
page: 9 - 36
pmid: 1
publication: Evolution
publication_identifier:
issn:
- 0014-3820
publication_status: published
publisher: Wiley-Blackwell
publist_id: '1779'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The genetic structure of a mosaic hybrid zone between two chromosome races
of the Sceloporus grammicus complex (Sauria, Phrynosomatidae) in central Mexico
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 49
year: '1995'
...
---
_id: '4298'
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. Appendix to “A simulation study of multilocus clines” by S J E Baird.
Evolution. 1995;49(6):1038-1045. doi:10.1111/j.1558-5646.1995.tb04431.x
apa: Barton, N. H. (1995). Appendix to “A simulation study of multilocus clines”
by S J E Baird. Evolution. Wiley. https://doi.org/10.1111/j.1558-5646.1995.tb04431.x
chicago: Barton, Nicholas H. “Appendix to ‘A Simulation Study of Multilocus Clines’
by S J E Baird.” Evolution. Wiley, 1995. https://doi.org/10.1111/j.1558-5646.1995.tb04431.x.
ieee: N. H. Barton, “Appendix to ‘A simulation study of multilocus clines’ by S
J E Baird,” Evolution, vol. 49, no. 6. Wiley, pp. 1038–1045, 1995.
ista: Barton NH. 1995. Appendix to ‘A simulation study of multilocus clines’ by
S J E Baird. Evolution. 49(6), 1038–1045.
mla: Barton, Nicholas H. “Appendix to ‘A Simulation Study of Multilocus Clines’
by S J E Baird.” Evolution, vol. 49, no. 6, Wiley, 1995, pp. 1038–45, doi:10.1111/j.1558-5646.1995.tb04431.x.
short: N.H. Barton, Evolution 49 (1995) 1038–1045.
date_created: 2018-12-11T12:08:07Z
date_published: 1995-12-01T00:00:00Z
date_updated: 2022-06-28T07:47:30Z
day: '01'
doi: 10.1111/j.1558-5646.1995.tb04431.x
extern: '1'
intvolume: ' 49'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1111/j.1558-5646.1995.tb04431.x
month: '12'
oa: 1
oa_version: Published Version
page: 1038 - 1045
publication: Evolution
publication_identifier:
issn:
- 1558-5646
publication_status: published
publisher: Wiley
publist_id: '1773'
quality_controlled: '1'
status: public
title: Appendix to "A simulation study of multilocus clines" by S J E Baird
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 49
year: '1995'
...
---
_id: '4428'
abstract:
- lang: eng
text: "Hybrid systems are real-time systems that react to both discrete and continuous
activities (such as analog signals, time, temperature, and speed). Typical examples
of hybrid systems are embedded systems, timing-based communication protocols,
and digital circuits at the transistor level. Due to the rapid development of
microprocessor technology, hybrid systems directly control much of what we depend
on in our daily lives. Consequently, the formal specification and verification
of hybrid systems has become an active area of research. This dissertation presents
the first general framework for the formal specification and verification of hybrid
systems, as well as the first hybrid-system analysis tool--HyTech. The framework
consists of a graphical finite-state-machine-like language for modeling hybrid
systems, a temporal logic for modeling the requirements of hybrid systems, and
a computer procedure that verifies modeled hybrid systems against modeled requirements.
The tool HyTech is the implementation of the framework using C++ and Mathematica.\r\n\r\nMore
specifically, our hybrid-system modeling language, Hybrid Automata, is an extension
of timed automata with discrete and continuous variables whose dynamics are governed
by differential equations. Our requirement modeling language, ICTL, is a branching-time
temporal logic, and is an extension of TCTL with stop-watch variables. Our verification
procedure is a symbolic model-checking procedure that verifies linear hybrid automata
against ICTL formulas. To make HyTech more efficient and effective, we use model-checking
strategies and abstract operators that can expedite the verification process.
To enable HyTech to verify nonlinear hybrid automata, we introduce two translations
from nonlinear hybrid automata to linear hybrid automata. We have applied HyTech
to analyze more than 30 hybrid-system benchmarks. In this dissertation, we present
the application of HyTech to three nontrivial hybrid systems taken from the literature."
article_processing_charge: No
author:
- first_name: Pei
full_name: Ho, Pei
last_name: Ho
citation:
ama: Ho P. Automatic analysis of hybrid systems. 1995:1-188.
apa: Ho, P. (1995). Automatic analysis of hybrid systems. Cornell University.
chicago: Ho, Pei. “Automatic Analysis of Hybrid Systems.” Cornell University, 1995.
ieee: P. Ho, “Automatic analysis of hybrid systems,” Cornell University, 1995.
ista: Ho P. 1995. Automatic analysis of hybrid systems. Cornell University.
mla: Ho, Pei. Automatic Analysis of Hybrid Systems. Cornell University, 1995,
pp. 1–188.
short: P. Ho, Automatic Analysis of Hybrid Systems, Cornell University, 1995.
date_created: 2018-12-11T12:08:48Z
date_published: 1995-08-01T00:00:00Z
date_updated: 2022-06-28T07:30:34Z
day: '01'
degree_awarded: PhD
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hdl.handle.net/1813/7193
month: '08'
oa: 1
oa_version: Published Version
page: 1 - 188
publication_status: published
publisher: Cornell University
publist_id: '304'
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: Automatic analysis of hybrid systems
type: dissertation
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1995'
...
---
_id: '4447'
abstract:
- lang: eng
text: This paper is addressed to potential users of HyTech, the Cornell Hybrid Technology
Tool, an automatic tool for analyzing hybrid systems. We review the formal technologies
that have been incorporated into HyTech, and we illustrate the use of HyTech with
three nontrivial case studies.
acknowledgement: This research was supported in part by the National Science Foundation
under grant CCR-9200794, by the Air Force Office of Scientific Research under contract
F49620-93-1-0056, by the Office of Naval Research under YIP grant N00014-95-1-0520,
and by the Defense Advanced Research Projects Agency under grant NAG2-892.
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: Pei
full_name: Ho, Pei
last_name: Ho
citation:
ama: 'Henzinger TA, Ho P. HyTech: The Cornell Hybrid Technology Tool. In: Panos
A, Kohn W, Nerode A, Sastry S, eds. 4th International Hybrid Systems Workshop.
Vol 999. LNCS. Springer; 1995:265-293. doi:10.1007/3-540-60472-3_14'
apa: 'Henzinger, T. A., & Ho, P. (1995). HyTech: The Cornell Hybrid Technology
Tool. In A. Panos, W. Kohn, A. Nerode, & S. Sastry (Eds.), 4th International
Hybrid Systems Workshop (Vol. 999, pp. 265–293). New Brunswick, NJ, United
States of America: Springer. https://doi.org/10.1007/3-540-60472-3_14'
chicago: 'Henzinger, Thomas A, and Pei Ho. “HyTech: The Cornell Hybrid Technology
Tool.” In 4th International Hybrid Systems Workshop, edited by Antsaklis
Panos, Wolf Kohn, Anil Nerode, and Shankar Sastry, 999:265–93. LNCS. Springer,
1995. https://doi.org/10.1007/3-540-60472-3_14.'
ieee: 'T. A. Henzinger and P. Ho, “HyTech: The Cornell Hybrid Technology Tool,”
in 4th International Hybrid Systems Workshop, New Brunswick, NJ, United
States of America, 1995, vol. 999, pp. 265–293.'
ista: 'Henzinger TA, Ho P. 1995. HyTech: The Cornell Hybrid Technology Tool. 4th
International Hybrid Systems Workshop. Hybrid Systems IIILNCS, LNCS, vol. 999,
265–293.'
mla: 'Henzinger, Thomas A., and Pei Ho. “HyTech: The Cornell Hybrid Technology Tool.”
4th International Hybrid Systems Workshop, edited by Antsaklis Panos et
al., vol. 999, Springer, 1995, pp. 265–93, doi:10.1007/3-540-60472-3_14.'
short: T.A. Henzinger, P. Ho, in:, A. Panos, W. Kohn, A. Nerode, S. Sastry (Eds.),
4th International Hybrid Systems Workshop, Springer, 1995, pp. 265–293.
conference:
end_date: 1955-10-25
location: ' New Brunswick, NJ, United States of America'
name: Hybrid Systems III
start_date: 1995-10-22
date_created: 2018-12-11T12:08:54Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-10T11:24:15Z
day: '01'
doi: 10.1007/3-540-60472-3_14
editor:
- first_name: Antsaklis
full_name: Panos, Antsaklis
last_name: Panos
- first_name: Wolf
full_name: Kohn, Wolf
last_name: Kohn
- first_name: Anil
full_name: Nerode, Anil
last_name: Nerode
- first_name: Shankar
full_name: Sastry, Shankar
last_name: Sastry
extern: '1'
intvolume: ' 999'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-60472-3_14
month: '01'
oa_version: None
page: 265 - 293
publication: 4th International Hybrid Systems Workshop
publication_identifier:
isbn:
- '9783540683346'
publication_status: published
publisher: Springer
publist_id: '281'
quality_controlled: '1'
series_title: LNCS
status: public
title: 'HyTech: The Cornell Hybrid Technology Tool'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 999
year: '1995'
...
---
_id: '4448'
abstract:
- lang: eng
text: We report on several abstract interpretation strategies that are designed
to improve the performance of HyTech, a symbolic model checker for linear hybrid
systems. We (1) simultaneously compute the target region from different directions,
(2) conservatively approximate the target region by dropping constraints, and
(3) iteratively refine the approximation until sufficient precision is obtained.
We consider the standard abstract convex-hull operator and a novel abstract extrapolation
operator.
acknowledgement: ' National Science Foundation under grant CCR-9200794, by the Air
Force Office of Scientific Research under contract F49620-93-1-0056, by the Office
of Naval Research under YIP grant N00014-95-1-0520, and by the Defense Advanced
Research Projects Agency under grant NAG2-892.'
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: Pei
full_name: Ho, Pei
last_name: Ho
citation:
ama: 'Henzinger TA, Ho P. A note on abstract-interpretation strategies for hybrid
automata. In: Panos A, Kohn W, Nerode A, Sastry S, eds. 3rd International Hybrid
Systems Workshop. Vol 999. Springer; 1995:252-264. doi:10.1007/3-540-60472-3_13'
apa: 'Henzinger, T. A., & Ho, P. (1995). A note on abstract-interpretation strategies
for hybrid automata. In A. Panos, W. Kohn, A. Nerode, & S. Sastry (Eds.),
3rd International Hybrid Systems Workshop (Vol. 999, pp. 252–264). Ithaca,
NY, United States of America: Springer. https://doi.org/10.1007/3-540-60472-3_13'
chicago: Henzinger, Thomas A, and Pei Ho. “A Note on Abstract-Interpretation Strategies
for Hybrid Automata.” In 3rd International Hybrid Systems Workshop, edited
by Antsaklis Panos, Wolf Kohn, Anil Nerode, and Shankar Sastry, 999:252–64. Springer,
1995. https://doi.org/10.1007/3-540-60472-3_13.
ieee: T. A. Henzinger and P. Ho, “A note on abstract-interpretation strategies for
hybrid automata,” in 3rd International Hybrid Systems Workshop, Ithaca,
NY, United States of America, 1995, vol. 999, pp. 252–264.
ista: Henzinger TA, Ho P. 1995. A note on abstract-interpretation strategies for
hybrid automata. 3rd International Hybrid Systems Workshop. Hybrid Systems II,
LNCS, vol. 999, 252–264.
mla: Henzinger, Thomas A., and Pei Ho. “A Note on Abstract-Interpretation Strategies
for Hybrid Automata.” 3rd International Hybrid Systems Workshop, edited
by Antsaklis Panos et al., vol. 999, Springer, 1995, pp. 252–64, doi:10.1007/3-540-60472-3_13.
short: T.A. Henzinger, P. Ho, in:, A. Panos, W. Kohn, A. Nerode, S. Sastry (Eds.),
3rd International Hybrid Systems Workshop, Springer, 1995, pp. 252–264.
conference:
end_date: 1994-10-30
location: Ithaca, NY, United States of America
name: Hybrid Systems II
start_date: 1994-10-28
date_created: 2018-12-11T12:08:54Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-10T11:48:59Z
day: '01'
doi: 10.1007/3-540-60472-3_13
editor:
- first_name: Antsaklis
full_name: Panos, Antsaklis
last_name: Panos
- first_name: Wolf
full_name: Kohn, Wolf
last_name: Kohn
- first_name: Anil
full_name: Nerode, Anil
last_name: Nerode
- first_name: Shankar
full_name: Sastry, Shankar
last_name: Sastry
extern: '1'
intvolume: ' 999'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-60472-3_13
month: '01'
oa_version: None
page: 252 - 264
publication: 3rd International Hybrid Systems Workshop
publication_identifier:
isbn:
- '9783540604723'
publication_status: published
publisher: Springer
publist_id: '282'
quality_controlled: '1'
status: public
title: A note on abstract-interpretation strategies for hybrid automata
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 999
year: '1995'
...
---
_id: '4450'
abstract:
- lang: eng
text: "Hybrid systems model discrete programs that are embedded in continuous environments.
Model-checking tools are available for the analysis of linear hybrid systems,
whose continuous variables are bounded by piecewise-linear trajectories. Most
embedded programs, however, operate in nonlinear environments. We present, analyze,
and apply two algorithms for translating nonlinear hybrid systems into linear
hybrid systems.\r\nThe clock translation replaces nonlinear variables by clock
variables; the rate translation approximates nonlinear variables by piecewise-linear
envelopes. Both translations are sound for reachability; that is, if we establish
a safety property of the translated linear system, we may conclude that the original
nonlinear system satisfies the property. The clock translation is also complete
for reachability; that is, the original system and the translated system satisfy
the same safety properties. The two translations apply to incomparable classes
of nonlinear hybrid systems. From the clock translation we obtain a new decidability
result for hybrid systems.\r\nWith the help of Hytech, a symbolic model checker
for linear hybrid systems, we automatically verify a nonlinear railroad gate control
program using the clock translation, and a nonlinear temperature control program
using the rate translation."
acknowledgement: This research was supported in part by the NSF grant CCR-9200794,
by the AFOSR contract F49620-93-1-0056, and by the DARPA grant NAG2-892.
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: Pei
full_name: Ho, Pei
last_name: Ho
citation:
ama: 'Henzinger TA, Ho P. Algorithmic analysis of nonlinear hybrid systems. In:
7th International Conference on Computer Aided Verification. Vol 939. Springer;
1995:225-238. doi:10.1007/3-540-60045-0_53'
apa: 'Henzinger, T. A., & Ho, P. (1995). Algorithmic analysis of nonlinear hybrid
systems. In 7th International Conference on Computer Aided Verification
(Vol. 939, pp. 225–238). Liege, Belgium: Springer. https://doi.org/10.1007/3-540-60045-0_53'
chicago: Henzinger, Thomas A, and Pei Ho. “Algorithmic Analysis of Nonlinear Hybrid
Systems.” In 7th International Conference on Computer Aided Verification,
939:225–38. Springer, 1995. https://doi.org/10.1007/3-540-60045-0_53.
ieee: T. A. Henzinger and P. Ho, “Algorithmic analysis of nonlinear hybrid systems,”
in 7th International Conference on Computer Aided Verification, Liege,
Belgium, 1995, vol. 939, pp. 225–238.
ista: 'Henzinger TA, Ho P. 1995. Algorithmic analysis of nonlinear hybrid systems.
7th International Conference on Computer Aided Verification. CAV: Computer Aided
Verification, LNCS, vol. 939, 225–238.'
mla: Henzinger, Thomas A., and Pei Ho. “Algorithmic Analysis of Nonlinear Hybrid
Systems.” 7th International Conference on Computer Aided Verification,
vol. 939, Springer, 1995, pp. 225–38, doi:10.1007/3-540-60045-0_53.
short: T.A. Henzinger, P. Ho, in:, 7th International Conference on Computer Aided
Verification, Springer, 1995, pp. 225–238.
conference:
end_date: 1995-07-05
location: Liege, Belgium
name: 'CAV: Computer Aided Verification'
start_date: 1995-07-03
date_created: 2018-12-11T12:08:55Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-10T09:48:52Z
day: '01'
doi: 10.1007/3-540-60045-0_53
extern: '1'
intvolume: ' 939'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-60045-0_53
month: '01'
oa_version: None
page: 225 - 238
publication: 7th International Conference on Computer Aided Verification
publication_identifier:
isbn:
- '9783540494133'
publication_status: published
publisher: Springer
publist_id: '280'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithmic analysis of nonlinear hybrid systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 939
year: '1995'
...
---
_id: '4497'
abstract:
- lang: eng
text: "HyTech is a tool for the automated analysis of embedded systems. This document,
designed for the first-time user of HyTech, guides the reader through the underlying
system model, and through the input language for describing and analyzing systems.
The guide gives several examples of usage, and some hints for gaining maximal
computational efficiency from the tool.\r\nThe version of HyTech described in
this guide was released in August 1995, and is available through anonymous ftp
from ftp.cs.cornell.edu in the directory pub/tah/HyTech, and through the World-Wide
Web via HyTech's home page http:/www.cs.cornell.edu/Info/People/tah/hytech.html."
acknowledgement: This research was supported in part by the ONR YIP award N00014-95-1-0520,
by the NSF CAREER award CCR-9501708, by the NSF grants CCR-9200794 and CCR-9504469,
by the AFOSR contract F49620-93-1-0056, and by the ARPA grant NAG2-892.
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: Pei
full_name: Ho, Pei
last_name: Ho
- first_name: Howard
full_name: Wong Toi, Howard
last_name: Wong Toi
citation:
ama: 'Henzinger TA, Ho P, Wong Toi H. A user guide to HyTech. In: 1st International
Workshop on Tools and Algorithms for the Construction and Analysis of Systems.
Vol 1019. Springer; 1995:41-71. doi:10.1007/3-540-60630-0_3'
apa: 'Henzinger, T. A., Ho, P., & Wong Toi, H. (1995). A user guide to HyTech.
In 1st International Workshop on Tools and Algorithms for the Construction
and Analysis of Systems (Vol. 1019, pp. 41–71). Aarhus, Denmark: Springer.
https://doi.org/10.1007/3-540-60630-0_3'
chicago: Henzinger, Thomas A, Pei Ho, and Howard Wong Toi. “A User Guide to HyTech.”
In 1st International Workshop on Tools and Algorithms for the Construction
and Analysis of Systems, 1019:41–71. Springer, 1995. https://doi.org/10.1007/3-540-60630-0_3.
ieee: T. A. Henzinger, P. Ho, and H. Wong Toi, “A user guide to HyTech,” in 1st
International Workshop on Tools and Algorithms for the Construction and Analysis
of Systems, Aarhus, Denmark, 1995, vol. 1019, pp. 41–71.
ista: 'Henzinger TA, Ho P, Wong Toi H. 1995. A user guide to HyTech. 1st International
Workshop on Tools and Algorithms for the Construction and Analysis of Systems.
TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS,
vol. 1019, 41–71.'
mla: Henzinger, Thomas A., et al. “A User Guide to HyTech.” 1st International
Workshop on Tools and Algorithms for the Construction and Analysis of Systems,
vol. 1019, Springer, 1995, pp. 41–71, doi:10.1007/3-540-60630-0_3.
short: T.A. Henzinger, P. Ho, H. Wong Toi, in:, 1st International Workshop on Tools
and Algorithms for the Construction and Analysis of Systems, Springer, 1995, pp.
41–71.
conference:
end_date: 1995-05-20
location: Aarhus, Denmark
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 1995-05-19
date_created: 2018-12-11T12:09:09Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-10T09:00:05Z
day: '01'
doi: 10.1007/3-540-60630-0_3
extern: '1'
intvolume: ' 1019'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-60630-0_3
month: '01'
oa_version: None
page: 41 - 71
publication: 1st International Workshop on Tools and Algorithms for the Construction
and Analysis of Systems
publication_identifier:
isbn:
- '9783540606307'
publication_status: published
publisher: Springer
publist_id: '230'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A user guide to HyTech
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1019
year: '1995'
...
---
_id: '4498'
abstract:
- lang: eng
text: We present algorithms for computing similarity relations of labeled graphs.
Similarity relations have applications for the refinement and verification of
reactive systems. For finite graphs, we present an O(mn) algorithm for computing
the similarity relation of a graph with n vertices and m edges (assuming m⩾n).
For effectively presented infinite graphs, we present a symbolic similarity-checking
procedure that terminates if a finite similarity relation exists. We show that
2D rectangular automata, which model discrete reactive systems with continuous
environments, define effectively presented infinite graphs with finite similarity
relations. It follows that the refinement problem and the ∀CTL* model-checking
problem are decidable for 2D rectangular automata
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- 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: Peter
full_name: Kopke, Peter
last_name: Kopke
citation:
ama: 'Henzinger MH, Henzinger TA, Kopke P. Computing simulations on finite and infinite
graphs. In: Proceedings of IEEE 36th Annual Foundations of Computer Science.
IEEE; 1995:453-462. doi:10.1109/SFCS.1995.492576'
apa: 'Henzinger, M. H., Henzinger, T. A., & Kopke, P. (1995). Computing simulations
on finite and infinite graphs. In Proceedings of IEEE 36th Annual Foundations
of Computer Science (pp. 453–462). Milwaukee, WI, United States of America:
IEEE. https://doi.org/10.1109/SFCS.1995.492576'
chicago: Henzinger, Monika H, Thomas A Henzinger, and Peter Kopke. “Computing Simulations
on Finite and Infinite Graphs.” In Proceedings of IEEE 36th Annual Foundations
of Computer Science, 453–62. IEEE, 1995. https://doi.org/10.1109/SFCS.1995.492576.
ieee: M. H. Henzinger, T. A. Henzinger, and P. Kopke, “Computing simulations on
finite and infinite graphs,” in Proceedings of IEEE 36th Annual Foundations
of Computer Science, Milwaukee, WI, United States of America, 1995, pp. 453–462.
ista: 'Henzinger MH, Henzinger TA, Kopke P. 1995. Computing simulations on finite
and infinite graphs. Proceedings of IEEE 36th Annual Foundations of Computer Science.
FOCS: Foundations of Computer Science, 453–462.'
mla: Henzinger, Monika H., et al. “Computing Simulations on Finite and Infinite
Graphs.” Proceedings of IEEE 36th Annual Foundations of Computer Science,
IEEE, 1995, pp. 453–62, doi:10.1109/SFCS.1995.492576.
short: M.H. Henzinger, T.A. Henzinger, P. Kopke, in:, Proceedings of IEEE 36th Annual
Foundations of Computer Science, IEEE, 1995, pp. 453–462.
conference:
end_date: 1995-10-25
location: Milwaukee, WI, United States of America
name: 'FOCS: Foundations of Computer Science'
start_date: 1995-10-23
date_created: 2018-12-11T12:09:10Z
date_published: 1995-11-01T00:00:00Z
date_updated: 2023-02-09T08:43:48Z
day: '01'
doi: 10.1109/SFCS.1995.492576
extern: '1'
language:
- iso: eng
month: '11'
oa_version: None
page: 453 - 462
publication: Proceedings of IEEE 36th Annual Foundations of Computer Science
publication_identifier:
isbn:
- '0818671831'
issn:
- 0272-5428
publication_status: published
publisher: IEEE
publist_id: '231'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing simulations on finite and infinite graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1995'
...
---
_id: '4499'
abstract:
- lang: eng
text: We describe a new implementation of HYTECH, a symbolic model checker for hybrid
systems. Given a parametric description of an embedded system as a collection
of communicating automata, HYTECH automatically computes the conditions on the
parameters under which the system satisfies its safety and timing requirements.
While the original HYTECH prototype was based on the symbolic algebra tool Mathematica,
the new implementation is written in C++ and builds on geometric algorithms instead
of formula manipulation. The new HYTECH offers a cleaner and more expressive input
language, greater portability, superior performance (typically two to three orders
of magnitude), and new features such as diagnostic error-trace generation. We
illustrate the effectiveness of the new implementation by applying HYTECH to the
automatic parametric analysis of the generic railroad crossing benchmark problem
and to an active structure control algorithm
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: Pei
full_name: Ho, Pei
last_name: Ho
- first_name: Howard
full_name: Wong Toi, Howard
last_name: Wong Toi
citation:
ama: 'Henzinger TA, Ho P, Wong Toi H. HyTech: The next generation. In: Proceedings
16th IEEE Real-Time Systems Symposium. IEEE; 1995:56-65. doi:10.1109/REAL.1995.495196 '
apa: 'Henzinger, T. A., Ho, P., & Wong Toi, H. (1995). HyTech: The next generation.
In Proceedings 16th IEEE Real-Time Systems Symposium (pp. 56–65). Pisa,
Italy: IEEE. https://doi.org/10.1109/REAL.1995.495196
'
chicago: 'Henzinger, Thomas A, Pei Ho, and Howard Wong Toi. “HyTech: The next Generation.”
In Proceedings 16th IEEE Real-Time Systems Symposium, 56–65. IEEE, 1995.
https://doi.org/10.1109/REAL.1995.495196
.'
ieee: 'T. A. Henzinger, P. Ho, and H. Wong Toi, “HyTech: The next generation,” in
Proceedings 16th IEEE Real-Time Systems Symposium, Pisa, Italy, 1995, pp.
56–65.'
ista: 'Henzinger TA, Ho P, Wong Toi H. 1995. HyTech: The next generation. Proceedings
16th IEEE Real-Time Systems Symposium. RTSS: Real-Time Systems Symposium, 56–65.'
mla: 'Henzinger, Thomas A., et al. “HyTech: The next Generation.” Proceedings
16th IEEE Real-Time Systems Symposium, IEEE, 1995, pp. 56–65, doi:10.1109/REAL.1995.495196 .'
short: T.A. Henzinger, P. Ho, H. Wong Toi, in:, Proceedings 16th IEEE Real-Time
Systems Symposium, IEEE, 1995, pp. 56–65.
conference:
end_date: 1995-12-07
location: Pisa, Italy
name: 'RTSS: Real-Time Systems Symposium'
start_date: 1995-12-05
date_created: 2018-12-11T12:09:10Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-10T09:33:19Z
day: '01'
doi: '10.1109/REAL.1995.495196 '
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/document/495196
month: '01'
oa_version: None
page: 56 - 65
publication: Proceedings 16th IEEE Real-Time Systems Symposium
publication_identifier:
isbn:
- '0818673370'
publication_status: published
publisher: IEEE
publist_id: '232'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'HyTech: The next generation'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1995'
...
---
_id: '4500'
abstract:
- lang: eng
text: 'We investigate the expressive power of timing restrictions on labeled transition
systems. In particular, we show how constraints on clock variables together with
a uniform liveness condition—the divergence of time—can express Büchi, Muller,
Streett, Rabin, and weak and strong fairness conditions on a given labeled transition
system. We then consider the effect, on both timed and time-abstract expressiveness,
of varying the following parameters: time domain (discrete or dense), number of
clocks, number of states, and size of constants used in timing restrictions.'
acknowledgement: "This research was supported in part by the National Science Foundation
under grant CCR-9200794, by the United States Air Force Office of Scientific Research
under contract F49620-93-1-0056, by the Defense Advanced Research Projects Agency
under grant NAG2-892, and by the U.S. Army Research Office through the Mathematical
Sciences Institute of Cornell University, Contract Number DAAL03-91-C-0027.\r\nThe
full version of this paper is available from the Department of Computer Science,
Cornell University, Ithaca, NY 14853, as Technical Report TR95-1496."
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: Peter
full_name: Kopke, Peter
last_name: Kopke
- first_name: Howard
full_name: Wong Toi, Howard
last_name: Wong Toi
citation:
ama: 'Henzinger TA, Kopke P, Wong Toi H. The expressive power of clocks. In: 22nd
International Colloquium on Automata, Languages and Programming . Vol 944.
Springer; 1995:417-428. doi:10.1007/3-540-60084-1_93'
apa: 'Henzinger, T. A., Kopke, P., & Wong Toi, H. (1995). The expressive power
of clocks. In 22nd International Colloquium on Automata, Languages and Programming
(Vol. 944, pp. 417–428). Szeged, Hungary: Springer. https://doi.org/10.1007/3-540-60084-1_93'
chicago: Henzinger, Thomas A, Peter Kopke, and Howard Wong Toi. “The Expressive
Power of Clocks.” In 22nd International Colloquium on Automata, Languages and
Programming , 944:417–28. Springer, 1995. https://doi.org/10.1007/3-540-60084-1_93.
ieee: T. A. Henzinger, P. Kopke, and H. Wong Toi, “The expressive power of clocks,”
in 22nd International Colloquium on Automata, Languages and Programming ,
Szeged, Hungary, 1995, vol. 944, pp. 417–428.
ista: 'Henzinger TA, Kopke P, Wong Toi H. 1995. The expressive power of clocks.
22nd International Colloquium on Automata, Languages and Programming . ICALP:
Automata, Languages and Programming, LNCS, vol. 944, 417–428.'
mla: Henzinger, Thomas A., et al. “The Expressive Power of Clocks.” 22nd International
Colloquium on Automata, Languages and Programming , vol. 944, Springer, 1995,
pp. 417–28, doi:10.1007/3-540-60084-1_93.
short: T.A. Henzinger, P. Kopke, H. Wong Toi, in:, 22nd International Colloquium
on Automata, Languages and Programming , Springer, 1995, pp. 417–428.
conference:
end_date: 1995-07-14
location: Szeged, Hungary
name: 'ICALP: Automata, Languages and Programming'
start_date: 1995-07-10
date_created: 2018-12-11T12:09:10Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-09T14:58:31Z
day: '01'
doi: 10.1007/3-540-60084-1_93
extern: '1'
intvolume: ' 944'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-60084-1_93
month: '01'
oa_version: None
page: 417 - 428
publication: '22nd International Colloquium on Automata, Languages and Programming '
publication_identifier:
isbn:
- '9783540600848'
publication_status: published
publisher: Springer
publist_id: '229'
quality_controlled: '1'
status: public
title: The expressive power of clocks
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 944
year: '1995'
...
---
_id: '4502'
abstract:
- lang: eng
text: "Hybrid automata model systems with both digital and analog components, such
as embedded control programs. Many verification tasks for such programs can be
expressed as reachability problems for hybrid automata. By improving on previous
decidability and undecidability results, we identify the precise boundary between
decidability and undecidability of the reachability problem for hybrid automata.\r\n\r\nOn
the positive side, we give an (optimal) PSPACE reachability algorithm for the
case of initialized rectangular automata, where all analog variables follow trajectories
within piecewise-linear envelopes and are reinitialized whenever the envelope
changes. Our algorithm is based on the construction of a timed automaton that
contains all reachability information about a given initialized rectangular automaton.
The translation has practical significance for verification, because it guarantees
the termination of symbolic procedures for the reachability analysis of initialized
rectangular automata. The translation also preserves the omega-languages of initialized
rectangular automata with bounded nondeterminism.\r\n\r\nOn the negative side,
we show that several slight generalizations of initialized rectangular automata
lead to an undecidable reachability problem. In particular, we prove that the
reachability problem is undecidable for timed automata augmented with a single
stopwatch."
acknowledgement: "We thank Howard Wong-Toi for a careful reading.\r\n"
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: Peter
full_name: Kopke, Peter
last_name: Kopke
- first_name: Anuj
full_name: Puri, Anuj
last_name: Puri
- first_name: P.
full_name: Varaiya, P.
last_name: Varaiya
citation:
ama: 'Henzinger TA, Kopke P, Puri A, Varaiya P. What’s decidable about hybrid automata?
In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing.
ACM; 1995:373-382. doi:10.1145/225058.225162'
apa: 'Henzinger, T. A., Kopke, P., Puri, A., & Varaiya, P. (1995). What’s decidable
about hybrid automata? In Proceedings of the 27th annual ACM symposium on Theory
of computing (pp. 373–382). Las Vegas, NV, United States of America: ACM.
https://doi.org/10.1145/225058.225162'
chicago: Henzinger, Thomas A, Peter Kopke, Anuj Puri, and P. Varaiya. “What’s Decidable
about Hybrid Automata?” In Proceedings of the 27th Annual ACM Symposium on
Theory of Computing, 373–82. ACM, 1995. https://doi.org/10.1145/225058.225162.
ieee: T. A. Henzinger, P. Kopke, A. Puri, and P. Varaiya, “What’s decidable about
hybrid automata?,” in Proceedings of the 27th annual ACM symposium on Theory
of computing, Las Vegas, NV, United States of America, 1995, pp. 373–382.
ista: 'Henzinger TA, Kopke P, Puri A, Varaiya P. 1995. What’s decidable about hybrid
automata? Proceedings of the 27th annual ACM symposium on Theory of computing.
STOC: Symposium on the Theory of Computing, 373–382.'
mla: Henzinger, Thomas A., et al. “What’s Decidable about Hybrid Automata?” Proceedings
of the 27th Annual ACM Symposium on Theory of Computing, ACM, 1995, pp. 373–82,
doi:10.1145/225058.225162.
short: T.A. Henzinger, P. Kopke, A. Puri, P. Varaiya, in:, Proceedings of the 27th
Annual ACM Symposium on Theory of Computing, ACM, 1995, pp. 373–382.
conference:
end_date: 1995-06-01
location: Las Vegas, NV, United States of America
name: 'STOC: Symposium on the Theory of Computing'
start_date: 1995-05-29
date_created: 2018-12-11T12:09:11Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-09T14:40:29Z
day: '01'
doi: 10.1145/225058.225162
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://dl.acm.org/doi/10.1145/225058.225162
month: '01'
oa: 1
oa_version: Published Version
page: 373 - 382
publication: Proceedings of the 27th annual ACM symposium on Theory of computing
publication_identifier:
isbn:
- '9780897917186'
publication_status: published
publisher: ACM
publist_id: '228'
quality_controlled: '1'
status: public
title: What's decidable about hybrid automata?
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1995'
...
---
_id: '4518'
abstract:
- lang: eng
text: The analysis, verification, and control of hybrid automata with finite bisimulations
can be reduced to finite-state problems. We advocate a time-abstract, phase-based
methodology for checking if a given hybrid automaton has a finite bisimulation.
First, we factor the automaton into two components, a boolean automaton with a
discrete dynamics on the finite state space B m and a euclidean automaton with
a continuous dynamics on the infinite state space n . Second, we investigate
the phase portrait of the euclidean component. In this fashion, we obtain new
decidability results for hybrid systems as well as new, uniform proofs of known
decidability results.
acknowledgement: "This research was supported in part by the NSF grant CCR-9200794,
by the AFOSR contract F49620-93-1-0056, and by the DARPA grant NAG2-892.\r\n"
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
citation:
ama: 'Henzinger TA. Hybrid automata with finite bisimulations. In: 22nd International
Colloquium on Automata, Languages and Programming . Vol 944. Springer; 1995:324-335.
doi:10.1007/3-540-60084-1_85'
apa: 'Henzinger, T. A. (1995). Hybrid automata with finite bisimulations. In 22nd
International Colloquium on Automata, Languages and Programming (Vol. 944,
pp. 324–335). Szeged, Hungary: Springer. https://doi.org/10.1007/3-540-60084-1_85'
chicago: Henzinger, Thomas A. “Hybrid Automata with Finite Bisimulations.” In 22nd
International Colloquium on Automata, Languages and Programming , 944:324–35.
Springer, 1995. https://doi.org/10.1007/3-540-60084-1_85.
ieee: T. A. Henzinger, “Hybrid automata with finite bisimulations,” in 22nd International
Colloquium on Automata, Languages and Programming , Szeged, Hungary, 1995,
vol. 944, pp. 324–335.
ista: 'Henzinger TA. 1995. Hybrid automata with finite bisimulations. 22nd International
Colloquium on Automata, Languages and Programming . ICALP: Automata, Languages
and Programming, LNCS, vol. 944, 324–335.'
mla: Henzinger, Thomas A. “Hybrid Automata with Finite Bisimulations.” 22nd International
Colloquium on Automata, Languages and Programming , vol. 944, Springer, 1995,
pp. 324–35, doi:10.1007/3-540-60084-1_85.
short: T.A. Henzinger, in:, 22nd International Colloquium on Automata, Languages
and Programming , Springer, 1995, pp. 324–335.
conference:
end_date: 1995-07-14
location: Szeged, Hungary
name: 'ICALP: Automata, Languages and Programming'
start_date: 1995-07-10
date_created: 2018-12-11T12:09:16Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2022-06-09T14:21:08Z
day: '01'
doi: 10.1007/3-540-60084-1_85
extern: '1'
intvolume: ' 944'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-60084-1_85
month: '01'
oa_version: None
page: 324 - 335
publication: '22nd International Colloquium on Automata, Languages and Programming '
publication_identifier:
isbn:
- '9783540600848'
publication_status: published
publisher: Springer
publist_id: '212'
quality_controlled: '1'
status: public
title: Hybrid automata with finite bisimulations
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 944
year: '1995'
...