---
_id: '3485'
abstract:
- lang: eng
text: 1. GABAergic interneurones differ from glutamatergic principal neurones in
their ability to discharge high-frequency trains of action potentials without
adaptation. To examine whether Na+ channel gating contributed to these differences,
Na+ currents were recorded in nucleated patches from interneurones (dentate gyrus
basket cells, BCs) and principal neurones (CA1 pyramidal cells, PCs) of rat hippocampal
slices. 2. The voltage dependence of Na+ channel activation in BCs and PCs was
similar. The slope factors of the activation curves, fitted with Boltzmann functions
raised to the third power, were 11.5 and 11.8 mV, and the mid-point potentials
were -25.1 and -23.9 mV, respectively. 3. Whereas the time course of Na+ channel
activation (-30 to +40 mV) was similar, the deactivation kinetics (-100 to -40
mV) were faster in BCs than in PCs (tail current decay time constants, 0.13 and
0.20 ms, respectively, at -40 mV). 4. Na+ channels in BCs and PCs differed in
the voltage dependence of inactivation. The slope factors of the steady-state
inactivation curves fitted with Boltzmann functions were 6.7 and 10.7 mV, and
the mid-point potentials were -58.3 and -62.9 mV, respectively. 5. The onset of
Na+ channel inactivation at -55 mV was slower in BC's than in PCs; the inactivation
time constants were 18.6 and 9.3 ms, respectively. At more positive potentials
the differences in inactivation onset were smaller. 6. The time course of recovery
of Na+ channels from inactivation induced by a 30 ms pulse was fast and mono-exponential
(τ = 2.0 ms at -120 mV) in BCs, whereas it was slower and biexponential in PCs
(τ1 = 2.0 ms and τ2 = 133 ms; amplitude contribution of the slow component, 15%).
7. We conclude that Na+ channels of BCs and PCs differ in gating properties that
contribute to the characteristic action potential patterns of the two types of
neurones.
acknowledgement: We thank Drs J. Bischofberger and J. R. P. Geiger for critically
reading the manuscript, Mrs B. Plessow-Freudenberg and K. Zipfel for technical assistance,
and Mrs B. Hillers for typing. This work was supported by the German Israeli Foundation
grant I 0352–073.01/94 to P. J.
article_processing_charge: No
article_type: original
author:
- first_name: Marco
full_name: Martina, Marco
last_name: Martina
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
citation:
ama: Martina M, Jonas PM. Functional differences in Na+ channel gating between fast-spiking
interneurones and principal neurones in rat hippocampus. Journal of Physiology.
1997;505(3):593-603. doi:10.1111/j.1469-7793.1997.593ba.x
apa: Martina, M., & Jonas, P. M. (1997). Functional differences in Na+ channel
gating between fast-spiking interneurones and principal neurones in rat hippocampus.
Journal of Physiology. Wiley-Blackwell. https://doi.org/10.1111/j.1469-7793.1997.593ba.x
chicago: Martina, Marco, and Peter M Jonas. “Functional Differences in Na+ Channel
Gating between Fast-Spiking Interneurones and Principal Neurones in Rat Hippocampus.”
Journal of Physiology. Wiley-Blackwell, 1997. https://doi.org/10.1111/j.1469-7793.1997.593ba.x.
ieee: M. Martina and P. M. Jonas, “Functional differences in Na+ channel gating
between fast-spiking interneurones and principal neurones in rat hippocampus,”
Journal of Physiology, vol. 505, no. 3. Wiley-Blackwell, pp. 593–603, 1997.
ista: Martina M, Jonas PM. 1997. Functional differences in Na+ channel gating between
fast-spiking interneurones and principal neurones in rat hippocampus. Journal
of Physiology. 505(3), 593–603.
mla: Martina, Marco, and Peter M. Jonas. “Functional Differences in Na+ Channel
Gating between Fast-Spiking Interneurones and Principal Neurones in Rat Hippocampus.”
Journal of Physiology, vol. 505, no. 3, Wiley-Blackwell, 1997, pp. 593–603,
doi:10.1111/j.1469-7793.1997.593ba.x.
short: M. Martina, P.M. Jonas, Journal of Physiology 505 (1997) 593–603.
date_created: 2018-12-11T12:03:34Z
date_published: 1997-12-15T00:00:00Z
date_updated: 2022-08-22T08:25:26Z
day: '15'
doi: 10.1111/j.1469-7793.1997.593ba.x
extern: '1'
external_id:
pmid:
- '9457638'
intvolume: ' 505'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1160038/
month: '12'
oa: 1
oa_version: Published Version
page: 593 - 603
pmid: 1
publication: Journal of Physiology
publication_identifier:
issn:
- 0022-3751
publication_status: published
publisher: Wiley-Blackwell
publist_id: '2902'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Functional differences in Na+ channel gating between fast-spiking interneurones
and principal neurones in rat hippocampus
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 505
year: '1997'
...
---
_id: '3486'
abstract:
- lang: eng
text: 1. Dendritic patch-clamp recordings were obtained from mitral cells in rat
olfactory bulb slices, up to 350 μm from the soma. Simultaneous dendritic and
somatic whole-cell recordings indicated that action potentials (APs) evoked by
somatic or dendritic current injection were initiated near the soma. Both the
large amplitude (100.7 ± 1.1 mV) and the short duration (1.38 ± 0.07 ms) of the
AP were maintained as the AP propagated back into the primary mitral cell dendrites.
2. Outside-out patches isolated from mitral cell dendrites contained voltage-gated
Na+ channels (peak conductance density, 90 pS μm-2 at -10 mV). When an AP was
used as a somatic voltage-clamp command in the presence of 1 μM tetrodotoxin (TTX),
the amplitude of the dendritic potential was attenuated to 48 ± 14 mV. This shows
that dendritic Na+ channels support the active back-propagation of APs. 3. Dendritic
patches contained voltage-gated K+ channels with high density (conductance density,
513 pS μm-2 at 30 mV. Dendritic K+ currents were reduced to 35% by 1 mM external
tetraethylammonium chloride (TEACl). When an AP was used as a somatic voltage
clamp command in the presence of TEACl, the dendritic potential was markedly prolonged.
This indicates that dendritic K+ channels mediate the fast repolarization of dendritic
APs. 4. We conclude that voltage gated Na+ and K+ channels support dendritic APs
with large amplitudes and short durations that may trigger fast transmitter release
at dendrodendritic synapses in the olfactory bulb.
acknowledgement: We thank Drs J. R. P. Geiger, M. Martina, and D. Schild for critically
reading the manuscript, and Mrs B. Plessow-Freudenberg for technical assistance.
This work was supported by DFG grant BI 642/1-1 and German Israeli Foundation grant
I 0352-073.01/94.
article_processing_charge: No
article_type: original
author:
- first_name: Joseph
full_name: Bischofberger, Joseph
last_name: Bischofberger
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
citation:
ama: Bischofberger J, Jonas PM. Action potential propagation into the presynaptic
dendrites of rat mitral cells. Journal of Physiology. 1997;504(Pt 2):359-365.
doi:10.1111/j.1469-7793.1997.359be.x
apa: Bischofberger, J., & Jonas, P. M. (1997). Action potential propagation
into the presynaptic dendrites of rat mitral cells. Journal of Physiology.
Wiley-Blackwell. https://doi.org/10.1111/j.1469-7793.1997.359be.x
chicago: Bischofberger, Joseph, and Peter M Jonas. “Action Potential Propagation
into the Presynaptic Dendrites of Rat Mitral Cells.” Journal of Physiology.
Wiley-Blackwell, 1997. https://doi.org/10.1111/j.1469-7793.1997.359be.x.
ieee: J. Bischofberger and P. M. Jonas, “Action potential propagation into the presynaptic
dendrites of rat mitral cells,” Journal of Physiology, vol. 504, no. Pt
2. Wiley-Blackwell, pp. 359–365, 1997.
ista: Bischofberger J, Jonas PM. 1997. Action potential propagation into the presynaptic
dendrites of rat mitral cells. Journal of Physiology. 504(Pt 2), 359–365.
mla: Bischofberger, Joseph, and Peter M. Jonas. “Action Potential Propagation into
the Presynaptic Dendrites of Rat Mitral Cells.” Journal of Physiology,
vol. 504, no. Pt 2, Wiley-Blackwell, 1997, pp. 359–65, doi:10.1111/j.1469-7793.1997.359be.x.
short: J. Bischofberger, P.M. Jonas, Journal of Physiology 504 (1997) 359–365.
date_created: 2018-12-11T12:03:35Z
date_published: 1997-10-15T00:00:00Z
date_updated: 2022-08-19T12:02:21Z
day: '15'
doi: 10.1111/j.1469-7793.1997.359be.x
extern: '1'
external_id:
pmid:
- '9365910'
intvolume: ' 504'
issue: Pt 2
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1159916/
month: '10'
oa: 1
oa_version: Published Version
page: 359 - 365
pmid: 1
publication: Journal of Physiology
publication_identifier:
issn:
- 0022-3751
publication_status: published
publisher: Wiley-Blackwell
publist_id: '2901'
quality_controlled: '1'
status: public
title: Action potential propagation into the presynaptic dendrites of rat mitral cells
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 504
year: '1997'
...
---
_id: '4022'
abstract:
- lang: eng
text: A halving hyperplane of a set S of n points in R(d) contains d affinely independent
points of S so that equally many of the points off the hyperplane lie in each
of the two half-spaces. We prove bounds on the number of halving hyperplanes under
the condition that the ratio of largest over smallest distance between any two
points is at most delta n(1/d), delta some constant. Such a set S is called dense.
In d = 2 dimensions the number of halving lines for a dense set can be as much
as Omega(n log n), and it cannot exceed O (n(5/4)/log* n). The upper bound improves
over the current best bound of O (n(3/2)/log* n) which holds more generally without
any density assumption. In d = 3 dimensions we show that O (n(7/3)) is an upper
bound on the number of halving planes for a dense set, The proof is based on a
metric argument that can be extended to d greater than or equal to 4 dimensions,
where it leads to O (n(d-2/d)) as an upper bound for the number of halving hyperplanes.
acknowledgement: Partially supported by the National Science Foundation, under Grant
ASC-9200301 and the Alan T. Waterman award, Grant CCR-9118874.
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
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Edelsbrunner H, Valtr P, Welzl E. Cutting dense point sets in half. Discrete
& Computational Geometry. 1997;17(3):243-255. doi:10.1007/PL00009291
apa: Edelsbrunner, H., Valtr, P., & Welzl, E. (1997). Cutting dense point sets
in half. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/PL00009291
chicago: Edelsbrunner, Herbert, Pavel Valtr, and Emo Welzl. “Cutting Dense Point
Sets in Half.” Discrete & Computational Geometry. Springer, 1997. https://doi.org/10.1007/PL00009291.
ieee: H. Edelsbrunner, P. Valtr, and E. Welzl, “Cutting dense point sets in half,”
Discrete & Computational Geometry, vol. 17, no. 3. Springer, pp. 243–255,
1997.
ista: Edelsbrunner H, Valtr P, Welzl E. 1997. Cutting dense point sets in half.
Discrete & Computational Geometry. 17(3), 243–255.
mla: Edelsbrunner, Herbert, et al. “Cutting Dense Point Sets in Half.” Discrete
& Computational Geometry, vol. 17, no. 3, Springer, 1997, pp. 243–55,
doi:10.1007/PL00009291.
short: H. Edelsbrunner, P. Valtr, E. Welzl, Discrete & Computational Geometry
17 (1997) 243–255.
date_created: 2018-12-11T12:06:29Z
date_published: 1997-04-01T00:00:00Z
date_updated: 2022-08-18T14:08:38Z
day: '01'
doi: 10.1007/PL00009291
extern: '1'
intvolume: ' 17'
issue: '3'
language:
- iso: eng
month: '04'
oa_version: None
page: 243 - 255
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2103'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Cutting dense point sets in half
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 17
year: '1997'
...
---
_id: '4174'
abstract:
- lang: eng
text: The epiphysial region of the dorsal diencephalon is the first site at which
neurogenesis occurs in the roof of the zebrafish forebrain. We show that the homeobox
containing gene floating head (flh) is required for neurogenesis to proceed in
the epiphysis. In flh(-) embryos, the first few epiphysial neurons are generated,
but beyond the 18 somite stage, neuronal production ceases. In contrast, in masterblind(-)
(mbl(-)) embryos, epiphysial neurons are generated throughout the dorsal forebrain.
We show that mbl is required to prevent the expression of flh in dorsal forebrain
cells rostral to the epiphysis. Furthermore, epiphysial neurons are not ectopically
induced in mbl(-)/flh(-) embryos, demonstrating that the epiphysial phenotype
of mbl(-) embryos is mediated by ectopic Flh activity. We propose a role for Flh
in linking the signaling pathways that regulate regional patterning to the signaling
pathways that regulate neurogenesis.
acknowledgement: 'We thank Igor DaMd. Tom Jessell, David Kimelman. Vladimir Koah,
Karen Larison. Ingvild Mikkola, Laurie Molday. and Eric Weinberg for probes and
antibod-ies: Alex Schist and Juliet Williams for help with the TUNEL tech-nique;
Dominic Delaney for analysis of the fih neural plate: Brian Gashing and Geraldine
Millard for fish care; Christian Nusslein Volhard for her support: and Corinne Houart.
Nigel Holder, and other members of the DBRC for comments on the manuscript. Electron
microscopy of the developing epiphysis cited in this study was carried out with
the help of Celeste Malinoski. funded by a grant (EY-00168)awarded to Stephen S.
Easter. This study was supported by grants from Welcome Trust to S. W. and Human
Frontier Science Program to I. M. S.W. is a Wellcome Trust Senior Research Fellow. '
article_processing_charge: No
article_type: original
author:
- first_name: Ichiro
full_name: Masai, Ichiro
last_name: Masai
- 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: K Anukampa
full_name: Barth, K Anukampa
last_name: Barth
- first_name: Rachel
full_name: Macdonald, Rachel
last_name: Macdonald
- first_name: Sylwia
full_name: Adamek, Sylwia
last_name: Adamek
- first_name: Stephen
full_name: Wilson, Stephen
last_name: Wilson
citation:
ama: Masai I, Heisenberg C-PJ, Barth KA, Macdonald R, Adamek S, Wilson S. Floating
head and masterblind regulate neuronal patterning in the roof of the forebrain.
Neuron. 1997;18(1):43-57. doi:10.1016/S0896-6273(01)80045-3
apa: Masai, I., Heisenberg, C.-P. J., Barth, K. A., Macdonald, R., Adamek, S., &
Wilson, S. (1997). Floating head and masterblind regulate neuronal patterning
in the roof of the forebrain. Neuron. Elsevier. https://doi.org/10.1016/S0896-6273(01)80045-3
chicago: Masai, Ichiro, Carl-Philipp J Heisenberg, K Anukampa Barth, Rachel Macdonald,
Sylwia Adamek, and Stephen Wilson. “Floating Head and Masterblind Regulate Neuronal
Patterning in the Roof of the Forebrain.” Neuron. Elsevier, 1997. https://doi.org/10.1016/S0896-6273(01)80045-3.
ieee: I. Masai, C.-P. J. Heisenberg, K. A. Barth, R. Macdonald, S. Adamek, and S.
Wilson, “Floating head and masterblind regulate neuronal patterning in the roof
of the forebrain,” Neuron, vol. 18, no. 1. Elsevier, pp. 43–57, 1997.
ista: Masai I, Heisenberg C-PJ, Barth KA, Macdonald R, Adamek S, Wilson S. 1997.
Floating head and masterblind regulate neuronal patterning in the roof of the
forebrain. Neuron. 18(1), 43–57.
mla: Masai, Ichiro, et al. “Floating Head and Masterblind Regulate Neuronal Patterning
in the Roof of the Forebrain.” Neuron, vol. 18, no. 1, Elsevier, 1997,
pp. 43–57, doi:10.1016/S0896-6273(01)80045-3.
short: I. Masai, C.-P.J. Heisenberg, K.A. Barth, R. Macdonald, S. Adamek, S. Wilson,
Neuron 18 (1997) 43–57.
date_created: 2018-12-11T12:07:24Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-18T14:02:49Z
day: '01'
doi: 10.1016/S0896-6273(01)80045-3
extern: '1'
external_id:
pmid:
- '9010204'
intvolume: ' 18'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/S0896627301800453?via%3Dihub
month: '01'
oa: 1
oa_version: Published Version
page: 43 - 57
pmid: 1
publication: Neuron
publication_identifier:
issn:
- 0896-6273
publication_status: published
publisher: Elsevier
publist_id: '1946'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Floating head and masterblind regulate neuronal patterning in the roof of the
forebrain
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 18
year: '1997'
...
---
_id: '4285'
abstract:
- lang: eng
text: One of the oldest hypotheses for the advantage of recombination is that recombination
allo rvs beneficial mutations that arise in different individuals to be placed
together on the same chromosome. Unless recombination occurs, one of the beneficial
alleles is doomed to extinction, slowing the rate at which adaptive mutations
are incorporated within a population. We model the effects of a modifier of recombination
on the fixation probability of beneficial mutations when beneficial alleles are
segregating at other loci. We find that modifier alleles that increase recombination
do increase the fixation probability of beneficial mutants and subsequently hitchhike
along as the mutants rise in frequency. The strength of selection favoring a modifier
that increases recombination is proportional to lambda(2)S delta r/r when linkage
is tight and lambda(2)S(3) delta r/N when linkage is loose, where lambda is the
beneficial mutation rate per genome per generation throughout a population of
size N, S is the average mutant effect, r is the average recombination rate, and
delta ris the amount that recombination is modified. We conclude that selection
for recombination will be substantial only if there is tight linkage within the
genome or if many loci are subject to directional selection as during periods
of rapid evolutionary change.
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. The evolution of recombination: Removing the limits to
natural selection. Genetics. 1997;147(2):879-906. doi:10.1093/genetics/147.2.879'
apa: 'Otto, S., & Barton, N. H. (1997). The evolution of recombination: Removing
the limits to natural selection. Genetics. Genetics Society of America.
https://doi.org/10.1093/genetics/147.2.879'
chicago: 'Otto, Sarah, and Nicholas H Barton. “The Evolution of Recombination: Removing
the Limits to Natural Selection.” Genetics. Genetics Society of America,
1997. https://doi.org/10.1093/genetics/147.2.879.'
ieee: 'S. Otto and N. H. Barton, “The evolution of recombination: Removing the limits
to natural selection,” Genetics, vol. 147, no. 2. Genetics Society of America,
pp. 879–906, 1997.'
ista: 'Otto S, Barton NH. 1997. The evolution of recombination: Removing the limits
to natural selection. Genetics. 147(2), 879–906.'
mla: 'Otto, Sarah, and Nicholas H. Barton. “The Evolution of Recombination: Removing
the Limits to Natural Selection.” Genetics, vol. 147, no. 2, Genetics Society
of America, 1997, pp. 879–906, doi:10.1093/genetics/147.2.879.'
short: S. Otto, N.H. Barton, Genetics 147 (1997) 879–906.
date_created: 2018-12-11T12:08:02Z
date_published: 1997-10-01T00:00:00Z
date_updated: 2022-08-18T11:36:10Z
day: '01'
doi: 10.1093/genetics/147.2.879
extern: '1'
external_id:
pmid:
- '9335621'
intvolume: ' 147'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://academic.oup.com/genetics/article/147/2/879/6054161
month: '10'
oa: 1
oa_version: Published Version
page: 879 - 906
pmid: 1
publication: Genetics
publication_identifier:
issn:
- 0016-6731
publication_status: published
publisher: Genetics Society of America
publist_id: '1796'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The evolution of recombination: Removing the limits to natural selection'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 147
year: '1997'
...
---
_id: '4441'
abstract:
- lang: eng
text: Rectangular hybrid automata model digital control programs of analog plant
environments. We study rectangular hybrid automata where the plant state evolves
continuously in real-numbered time, and the controller samples the plant state
and changes the control state discretely, only at the integer points in time.
We prove that rectangular hybrid automata have finite bisimilarity quotients when
all control transitions happen at integer times, even if the constraints on the
derivatives of the variables vary between control states. This is sharply in contrast
with the conventional model where control transitions may happen at any real time,
and already the reachability problem is undecidable. Based on the finite bisimilarity
quotients, we give an exponential algorithm for the symbolic sampling-controller
synthesis of rectangular automata. We show our algorithm to be optimal by proving
the problem to be EXPTIME-hard. We also show that rectangular automata form a
maximal class of systems for which the sampling-controller synthesis problem can
be solved algorithmically.
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 grant CCR-9504469, by the AFOSR
contract F49620-93-1-0056, by the ARO MURI contract DAAH-04-96-1-0341, by the ARO
contract DAAL03-91-C-0027 through the MSI at Cornell University, by the ARPA grant
NAG2-892, and by the SRC contract 95-DC-324.036.
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
citation:
ama: 'Henzinger TA, Kopke P. Discrete-time control for rectangular hybrid automata.
In: Proceedings of the 24th International Colloquium on Automata, Languages
and Programming. Vol 1256. Springer; 1997:582-593. doi:10.1007/3-540-63165-8_213'
apa: 'Henzinger, T. A., & Kopke, P. (1997). Discrete-time control for rectangular
hybrid automata. In Proceedings of the 24th International Colloquium on Automata,
Languages and Programming (Vol. 1256, pp. 582–593). Bologna, Italy: Springer.
https://doi.org/10.1007/3-540-63165-8_213'
chicago: Henzinger, Thomas A, and Peter Kopke. “Discrete-Time Control for Rectangular
Hybrid Automata.” In Proceedings of the 24th International Colloquium on Automata,
Languages and Programming, 1256:582–93. Springer, 1997. https://doi.org/10.1007/3-540-63165-8_213.
ieee: T. A. Henzinger and P. Kopke, “Discrete-time control for rectangular hybrid
automata,” in Proceedings of the 24th International Colloquium on Automata,
Languages and Programming, Bologna, Italy, 1997, vol. 1256, pp. 582–593.
ista: 'Henzinger TA, Kopke P. 1997. Discrete-time control for rectangular hybrid
automata. Proceedings of the 24th International Colloquium on Automata, Languages
and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 1256,
582–593.'
mla: Henzinger, Thomas A., and Peter Kopke. “Discrete-Time Control for Rectangular
Hybrid Automata.” Proceedings of the 24th International Colloquium on Automata,
Languages and Programming, vol. 1256, Springer, 1997, pp. 582–93, doi:10.1007/3-540-63165-8_213.
short: T.A. Henzinger, P. Kopke, in:, Proceedings of the 24th International Colloquium
on Automata, Languages and Programming, Springer, 1997, pp. 582–593.
conference:
end_date: 1997-07-11
location: Bologna, Italy
name: 'ICALP: Automata, Languages and Programming'
start_date: 1997-07-07
date_created: 2018-12-11T12:08:52Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-17T12:04:15Z
day: '01'
doi: 10.1007/3-540-63165-8_213
extern: '1'
intvolume: ' 1256'
language:
- iso: eng
month: '01'
oa_version: None
page: 582 - 593
publication: Proceedings of the 24th International Colloquium on Automata, Languages
and Programming
publication_identifier:
isbn:
- '9783540631651'
publication_status: published
publisher: Springer
publist_id: '289'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Discrete-time control for rectangular hybrid automata
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1256
year: '1997'
...
---
_id: '4494'
abstract:
- lang: eng
text: A hybrid system consists of a collection of digital programs that interact
with each other and with an analog environment. Examples of hybrid systems include
medical equipment, manufacturing controllers, automotive controllers, and robots.
The formal analysis of the mixed digital-analog nature of these systems requires
a model that incorporates the discrete behavior of computer programs with the
continuous behavior of environment variables, such as temperature and pressure.
Hybrid automata capture both types of behavior by combining finite automata with
differential inclusions (i.e. differential inequalities). HyTech is a symbolic
model checker for linear hybrid automata, an expressive, yet automatically analyzable,
subclass of hybrid automata. A key feature of HyTech is its ability to perform
parametric analysis, i.e. to determine the values of design parameters for which
a linear hybrid automaton satisfies a temporal requirement.
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 grant CCR-9504469, by the AFOSR
contract F49620-93-1-0056, by the ARO MURI grant DAAH-04-96-1-0341, by the ARPA
grant NAG2-892, and by the SRC contract 95-DC-324.036.
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. HyTech: A model checker for hybrid systems.
In: Vol 1254. Springer; 1997:460-463. doi:10.1007/3-540-63166-6_48'
apa: 'Henzinger, T. A., Ho, P., & Wong Toi, H. (1997). HyTech: A model checker
for hybrid systems (Vol. 1254, pp. 460–463). Presented at the CAV: Computer Aided
Verification, Haifa, Israel: Springer. https://doi.org/10.1007/3-540-63166-6_48'
chicago: 'Henzinger, Thomas A, Pei Ho, and Howard Wong Toi. “HyTech: A Model Checker
for Hybrid Systems,” 1254:460–63. Springer, 1997. https://doi.org/10.1007/3-540-63166-6_48.'
ieee: 'T. A. Henzinger, P. Ho, and H. Wong Toi, “HyTech: A model checker for hybrid
systems,” presented at the CAV: Computer Aided Verification, Haifa, Israel, 1997,
vol. 1254, pp. 460–463.'
ista: 'Henzinger TA, Ho P, Wong Toi H. 1997. HyTech: A model checker for hybrid
systems. CAV: Computer Aided Verification, LNCS, vol. 1254, 460–463.'
mla: 'Henzinger, Thomas A., et al. HyTech: A Model Checker for Hybrid Systems.
Vol. 1254, Springer, 1997, pp. 460–63, doi:10.1007/3-540-63166-6_48.'
short: T.A. Henzinger, P. Ho, H. Wong Toi, in:, Springer, 1997, pp. 460–463.
conference:
end_date: 1997-06-25
location: Haifa, Israel
name: 'CAV: Computer Aided Verification'
start_date: 1997-06-22
date_created: 2018-12-11T12:09:08Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-17T11:06:13Z
day: '01'
doi: 10.1007/3-540-63166-6_48
extern: '1'
intvolume: ' 1254'
language:
- iso: eng
month: '01'
oa_version: None
page: 460 - 463
publication_identifier:
isbn:
- '9783540631668'
publication_status: published
publisher: Springer
publist_id: '235'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'HyTech: A model checker for hybrid systems'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1254
year: '1997'
...
---
_id: '4496'
abstract:
- lang: eng
text: 'The simulation preorder for labeled transition systems is defined locally
as a game that relates states with their immediate successor states. Liveness
assumptions about transition systems are typically modeled using fairness constraints.
Existing notions of simulation for fair transition systems, however, are not local,
and as a result, many appealing properties of the simulation preorder are lost.
We extend the local definition of simulation to account for fairness: system S
fairly simulates system I iff in the simulation game, there is a strategy that
matches with each fair computation of I a fair computation of S. Our definition
enjoys a fully abstract semantics and has a logical characterization: S fairly
simulates I iff every fair computation tree embedded in the unrolling of I can
be embedded also in the unrolling of S or, equivalently, iff every Fair-AFMC formula
satisfied by I is satisfied also by S (AFMC is the universal fragment of the alternation-free
-calculus). The locality of the definition leads us to a polynomial-time algorithm
for checking fair simulation for finite-state systems with weak and strong fairness
constraints. Finally, fair simulation implies fair trace-containment, and is therefore
useful as an efficientlycomputable local criterion for proving linear-time abstraction
hierarchies.'
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 grant CCR-9504469, by the AFOSR
contract F49620-93-1-0056, by the ARO MURI grant DAAH-04-96-1-0341, by the ARPA
grant NAG2-892, and by the SRC contract 95-DC-324.036.
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: Orna
full_name: Kupferman, Orna
last_name: Kupferman
- first_name: Sriram
full_name: Rajamani, Sriram
last_name: Rajamani
citation:
ama: 'Henzinger TA, Kupferman O, Rajamani S. Fair simulation. In: Proceedings
of the 8th International Conference on Concurrency Theory. Vol 1243. Springer;
1997:273-287. doi:10.1007/3-540-63141-0_19'
apa: 'Henzinger, T. A., Kupferman, O., & Rajamani, S. (1997). Fair simulation.
In Proceedings of the 8th International Conference on Concurrency Theory
(Vol. 1243, pp. 273–287). Warsaw, Poland: Springer. https://doi.org/10.1007/3-540-63141-0_19'
chicago: Henzinger, Thomas A, Orna Kupferman, and Sriram Rajamani. “Fair Simulation.”
In Proceedings of the 8th International Conference on Concurrency Theory,
1243:273–87. Springer, 1997. https://doi.org/10.1007/3-540-63141-0_19.
ieee: T. A. Henzinger, O. Kupferman, and S. Rajamani, “Fair simulation,” in Proceedings
of the 8th International Conference on Concurrency Theory, Warsaw, Poland,
1997, vol. 1243, pp. 273–287.
ista: 'Henzinger TA, Kupferman O, Rajamani S. 1997. Fair simulation. Proceedings
of the 8th International Conference on Concurrency Theory. CONCUR: Concurrency
Theory, LNCS, vol. 1243, 273–287.'
mla: Henzinger, Thomas A., et al. “Fair Simulation.” Proceedings of the 8th International
Conference on Concurrency Theory, vol. 1243, Springer, 1997, pp. 273–87, doi:10.1007/3-540-63141-0_19.
short: T.A. Henzinger, O. Kupferman, S. Rajamani, in:, Proceedings of the 8th International
Conference on Concurrency Theory, Springer, 1997, pp. 273–287.
conference:
end_date: 1997-07-04
location: Warsaw, Poland
name: 'CONCUR: Concurrency Theory'
start_date: 1997-07-01
date_created: 2018-12-11T12:09:09Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-17T09:09:13Z
day: '01'
doi: 10.1007/3-540-63141-0_19
extern: '1'
intvolume: ' 1243'
language:
- iso: eng
month: '01'
oa_version: None
page: 273 - 287
publication: Proceedings of the 8th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783540631415'
publication_status: published
publisher: Springer
publist_id: '234'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fair simulation
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1243
year: '1997'
...
---
_id: '4583'
abstract:
- lang: eng
text: In a trace-based world, the modular specification, verification, and control
of live systems require each module to be receptive; that is, each module must
be able to meet its liveness assumptions no matter how the other modules behave.
In a real-time world, liveness is automatically present in the form of diverging
time. The receptiveness condition, then, translates to the requirement that a
module must be able to let time diverge no matter how the environment behaves.
We study the receptiveness condition for real-time systems by extending the model
of reactive modules to timed and hybrid modules. We define the receptiveness of
such a module as the existence of a winning strategy in a game of the module against
its environment. By solving the game on region graphs, we present an (optimal)
Exptime algorithm for checking the receptiveness of prepositional timed modules.
By giving a fixpoint characterization of the game, we present a symbolic procedure
for checking the receptiveness of linear hybrid modules. Finally, we present an
assume-guarantee principle for reasoning about timed and hybrid modules, and a
method for synthesizing receptive controllers of timed and hybrid modules.
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 grant CCR-9504469, by the AFOSR
contract F49620-93-1-0056, by the ARO MURI grant DAAH-04-96-1-0341, by the ARPA
grant NAG2-892, and by the SRC contract 95-DC-324.036.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- 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: 'Alur R, Henzinger TA. Modularity for timed and hybrid systems. In: 8th
International Conference on Concurrency Theory. Vol 1243. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 1997:74-88. doi:10.1007/3-540-63141-0_6'
apa: 'Alur, R., & Henzinger, T. A. (1997). Modularity for timed and hybrid systems.
In 8th International Conference on Concurrency Theory (Vol. 1243, pp. 74–88).
Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-63141-0_6'
chicago: Alur, Rajeev, and Thomas A Henzinger. “Modularity for Timed and Hybrid
Systems.” In 8th International Conference on Concurrency Theory, 1243:74–88.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1997. https://doi.org/10.1007/3-540-63141-0_6.
ieee: R. Alur and T. A. Henzinger, “Modularity for timed and hybrid systems,” in
8th International Conference on Concurrency Theory, Warsaw, Poland, 1997,
vol. 1243, pp. 74–88.
ista: 'Alur R, Henzinger TA. 1997. Modularity for timed and hybrid systems. 8th
International Conference on Concurrency Theory. CONCUR: Concurrency Theory, LNCS,
vol. 1243, 74–88.'
mla: Alur, Rajeev, and Thomas A. Henzinger. “Modularity for Timed and Hybrid Systems.”
8th International Conference on Concurrency Theory, vol. 1243, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 1997, pp. 74–88, doi:10.1007/3-540-63141-0_6.
short: R. Alur, T.A. Henzinger, in:, 8th International Conference on Concurrency
Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1997, pp. 74–88.
conference:
end_date: 1997-07-04
location: Warsaw, Poland
name: 'CONCUR: Concurrency Theory'
start_date: 1997-07-01
date_created: 2018-12-11T12:09:36Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-17T08:47:55Z
day: '01'
doi: 10.1007/3-540-63141-0_6
extern: '1'
intvolume: ' 1243'
language:
- iso: eng
month: '01'
oa_version: None
page: 74 - 88
publication: 8th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783540691884'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '124'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Modularity for timed and hybrid systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1243
year: '1997'
...
---
_id: '11804'
abstract:
- lang: eng
text: "This paper shows how a general technique, called lock-step search, used in
dynamic graph algorithms, can be used to improve the running time of two problems
arising in program verification and communication protocol design.\r\n(1)We consider
the nonemptiness problem for Streett automata: We are given a directed graph G
= (V, E) with n = ¦V¦ and m = ¦E¦, and a collection of pairs of subsets of vertices,
called Streett pairs,〈L i , U i 〉, i = 1.k. The question is whether G has a cycle
(not necessarily simple) which, for each 1 ≤ i ≤ k, if it contains a vertex from
L i then it also contains a vertex of U i . Let b=Σ i=1..k |L i |+|U i |. The
previously best algorithm takes time O((m + b) min{n, k}). We present an algorithm
that takes time \U0001D442(\U0001D45Amin{\U0001D45A\U0001D459\U0001D45C\U0001D454\U0001D45B,‾‾‾‾‾‾√\U0001D458,\U0001D45B}+\U0001D44F\U0001D45A\U0001D456\U0001D45B{\U0001D459\U0001D45C\U0001D454\U0001D45B,\U0001D458}).\r\n(2)In
communication protocol pruning we are given a directed graph G = (V, E) with l
special vertices. The problem is to efficiently maintain the strongly-connected
components of the special vertices on a restricted set of edge deletions. Let
m i be the number of edges in the strongly connected component of the ith special
vertex. The previously best algorithm repeatedly recomputes the strongly-connected
components which leads to a running time of O(Σ i m 2i). We present an algorithm
with time \U0001D442(\U0001D459√∑\U0001D456\U0001D45A1.5\U0001D456)."
alternative_title:
- LNCS
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: Jan Arne
full_name: Telle, Jan Arne
last_name: Telle
citation:
ama: 'Henzinger M, Telle JA. Faster algorithms for the nonemptiness of streett automata
and for communication protocol pruning. In: 5th Scandinavian Workshop on Algorithm
Theory. Vol 1097. Springer Nature; 1996:16–27. doi:10.1007/3-540-61422-2_117'
apa: 'Henzinger, M., & Telle, J. A. (1996). Faster algorithms for the nonemptiness
of streett automata and for communication protocol pruning. In 5th Scandinavian
Workshop on Algorithm Theory (Vol. 1097, pp. 16–27). Reykjavik, Iceland: Springer
Nature. https://doi.org/10.1007/3-540-61422-2_117'
chicago: Henzinger, Monika, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness
of Streett Automata and for Communication Protocol Pruning.” In 5th Scandinavian
Workshop on Algorithm Theory, 1097:16–27. Springer Nature, 1996. https://doi.org/10.1007/3-540-61422-2_117.
ieee: M. Henzinger and J. A. Telle, “Faster algorithms for the nonemptiness of streett
automata and for communication protocol pruning,” in 5th Scandinavian Workshop
on Algorithm Theory, Reykjavik, Iceland, 1996, vol. 1097, pp. 16–27.
ista: 'Henzinger M, Telle JA. 1996. Faster algorithms for the nonemptiness of streett
automata and for communication protocol pruning. 5th Scandinavian Workshop on
Algorithm Theory. SWAT: Scandinavian Workshop on Algorithm Theory, LNCS, vol.
1097, 16–27.'
mla: Henzinger, Monika, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness
of Streett Automata and for Communication Protocol Pruning.” 5th Scandinavian
Workshop on Algorithm Theory, vol. 1097, Springer Nature, 1996, pp. 16–27,
doi:10.1007/3-540-61422-2_117.
short: M. Henzinger, J.A. Telle, in:, 5th Scandinavian Workshop on Algorithm Theory,
Springer Nature, 1996, pp. 16–27.
conference:
end_date: 1996-07-05
location: Reykjavik, Iceland
name: 'SWAT: Scandinavian Workshop on Algorithm Theory'
start_date: 1996-07-03
date_created: 2022-08-11T13:42:42Z
date_published: 1996-07-01T00:00:00Z
date_updated: 2024-11-06T12:13:51Z
day: '01'
doi: 10.1007/3-540-61422-2_117
extern: '1'
intvolume: ' 1097'
language:
- iso: eng
month: '07'
oa_version: None
page: 16–27
publication: 5th Scandinavian Workshop on Algorithm Theory
publication_identifier:
eisbn:
- '9783540685296'
eissn:
- 1611-3349
isbn:
- '9783540614227'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster algorithms for the nonemptiness of streett automata and for communication
protocol pruning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1097
year: '1996'
...
---
_id: '11910'
abstract:
- lang: eng
text: "We state a new sampling lemma and use it to improve the running time of dynamic
graph algorithms.\r\n\r\nFor the dynamic connectivity problem the previously best
randomized algorithm takes expected time O(log3 n) per update, amortized over
Ω(m) updates. Using the new sampling lemma, we improve its running time to O(log2
n). There exists a lower bound in the cell probe model for the time per operation
of Ω(log n/ log log n) for this problem.\r\n\r\nSimilarly improved running times
are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness."
alternative_title:
- LNCS
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: Mikkel
full_name: Thorup, Mikkel
last_name: Thorup
citation:
ama: 'Henzinger M, Thorup M. Improved sampling with applications to dynamic graph
algorithms. In: 23rd International Colloquium on Automata, Languages, and Programming.
Vol 1099. Springer Nature; 1996:290-299. doi:10.1007/3-540-61440-0_136'
apa: 'Henzinger, M., & Thorup, M. (1996). Improved sampling with applications
to dynamic graph algorithms. In 23rd International Colloquium on Automata,
Languages, and Programming (Vol. 1099, pp. 290–299). Paderborn, Germany: Springer
Nature. https://doi.org/10.1007/3-540-61440-0_136'
chicago: Henzinger, Monika, and Mikkel Thorup. “Improved Sampling with Applications
to Dynamic Graph Algorithms.” In 23rd International Colloquium on Automata,
Languages, and Programming, 1099:290–99. Springer Nature, 1996. https://doi.org/10.1007/3-540-61440-0_136.
ieee: M. Henzinger and M. Thorup, “Improved sampling with applications to dynamic
graph algorithms,” in 23rd International Colloquium on Automata, Languages,
and Programming, Paderborn, Germany, 1996, vol. 1099, pp. 290–299.
ista: 'Henzinger M, Thorup M. 1996. Improved sampling with applications to dynamic
graph algorithms. 23rd International Colloquium on Automata, Languages, and Programming.
ICALP: International Colloquium on Automata, Languages, and Programming, LNCS,
vol. 1099, 290–299.'
mla: Henzinger, Monika, and Mikkel Thorup. “Improved Sampling with Applications
to Dynamic Graph Algorithms.” 23rd International Colloquium on Automata, Languages,
and Programming, vol. 1099, Springer Nature, 1996, pp. 290–99, doi:10.1007/3-540-61440-0_136.
short: M. Henzinger, M. Thorup, in:, 23rd International Colloquium on Automata,
Languages, and Programming, Springer Nature, 1996, pp. 290–299.
conference:
end_date: 1996-07-12
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 1996-07-08
date_created: 2022-08-18T06:42:24Z
date_published: 1996-07-01T00:00:00Z
date_updated: 2024-11-06T12:25:11Z
day: '01'
doi: 10.1007/3-540-61440-0_136
extern: '1'
intvolume: ' 1099'
language:
- iso: eng
month: '07'
oa_version: None
page: 290-299
publication: 23rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
eisbn:
- '9783540685807'
eissn:
- 1611-3349
isbn:
- '9783540614401'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved sampling with applications to dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1099
year: '1996'
...
---
_id: '11927'
abstract:
- lang: eng
text: "We are given a set 7 = {Tl , Tz, . . . , Tk} of rooted binary trees, each
Ti leaf-labeled by a subset L(x) c {1,2 )...) n}. IfT is a tree on {1,2, . . ,
n}, we let T]L denote the subtree of T induced by the nodes of L and all their
ancestors. The consensus tree problem asks whether there exists a tree T* such
that for every I, T’ IC(Ti) is homeomorphic to Ti. We present algorithms which
test if a given set of trees has a consensus tree and if so, construct one. The
deterministic algorithm takes time min{O(mn’/‘), O(m + n2 logn)}, where m = Ci
IZl and uses linear space. The randomized algorithm takes\r\ntime O(m log3 n)
and uses linear space. The previous best for this problem was an 1981 O(mn) algorithm
by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm
for the following interesting dynamic graph problem: Given a graph G with n nodes
and m edges and a sequence of b batches of one or more edge deletions, then after
each batch, either find a new component that has just been created or determine
that there is no such component. For this\r\nproblem, we have a simple algorithm
with running time O(n2 log n + be min{ n2, m log n}), where be is the number of
batches which do not result in a new component. For our particular application,
bc 5 1. If all edges are deleted, then the best previously known deterministic
algorithm requires time O(mJ;ii) to solve this problem. computational evolutionary
biology. The first application is in the problem of inferring consensus of trees
when there can be disagreement[l6]. There have, been several models suggested
for this problem[2, 3, 4, 8, ?, 11, 17, 181, of which one is called the Local
Consensus Tree[l5]. The local consensus tree model presumes that the user provides
a local consensus rule which determines the form of the output tree on (perhaps)
each triple of leaves, and the objective is to determine whether a tree exists
which is consistent with each of the constraints. We will show that we can construct
the local consensus tree of k trees on n species in O(kn3) time, improving on
the O(lcn3 + n”) running time if we use the Aho et al algorithm. The second application
is a\r\nheuristic for constructing the maximum likelihood tree based upon combining
solutions to small subproblems.\r\nThis is a simple and yet potentially significantly
interesting approach to the evolutionary tree construction\r\nproblem. "
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: Valerie
full_name: King, Valerie
last_name: King
- first_name: Tandy
full_name: Warnow, Tandy
last_name: Warnow
citation:
ama: 'Henzinger M, King V, Warnow T. Constructing a tree from homeomorphic subtrees,
with applications to computational evolutionary biology. In: 7th Annual ACM-SIAM
Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics;
1996:333-340.'
apa: 'Henzinger, M., King, V., & Warnow, T. (1996). Constructing a tree from
homeomorphic subtrees, with applications to computational evolutionary biology.
In 7th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 333–340).
Atlanta, GA, United States: Society for Industrial and Applied Mathematics.'
chicago: Henzinger, Monika, Valerie King, and Tandy Warnow. “Constructing a Tree
from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.”
In 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 333–40. Society
for Industrial and Applied Mathematics, 1996.
ieee: M. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic
subtrees, with applications to computational evolutionary biology,” in 7th
Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, United States,
1996, pp. 333–340.
ista: 'Henzinger M, King V, Warnow T. 1996. Constructing a tree from homeomorphic
subtrees, with applications to computational evolutionary biology. 7th Annual
ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms,
333–340.'
mla: Henzinger, Monika, et al. “Constructing a Tree from Homeomorphic Subtrees,
with Applications to Computational Evolutionary Biology.” 7th Annual ACM-SIAM
Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
1996, pp. 333–40.
short: M. Henzinger, V. King, T. Warnow, in:, 7th Annual ACM-SIAM Symposium on Discrete
Algorithms, Society for Industrial and Applied Mathematics, 1996, pp. 333–340.
conference:
end_date: 1996-01-30
location: Atlanta, GA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 1996-01-28
date_created: 2022-08-19T06:57:47Z
date_published: 1996-01-28T00:00:00Z
date_updated: 2024-11-04T11:41:22Z
day: '28'
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://dl.acm.org/doi/10.5555/313852.314080
month: '01'
oa: 1
oa_version: Published Version
page: 333 -340
publication: 7th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '0898713668'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '11679'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Constructing a tree from homeomorphic subtrees, with applications to computational
evolutionary biology
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1996'
...
---
_id: '17822'
abstract:
- lang: eng
text: We investigate the formation of molecular hydrogen (H_2_) in a primordial
H + He gas cloud irradiated by a power-law UV flux. We find that at high densities
(~>1 cm^-3^) and low temperatures (<~10^4^ K), the background radiation enhances
the formation of H_2_ and results in molecular cooling dominating over photoionization
heating. This process could accelerate the collapse and fragmentation of dense
objects at high redshifts.
article_number: '522'
article_processing_charge: No
article_type: original
author:
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
orcid: 0000-0003-3633-5403
- first_name: Martin J.
full_name: Rees, Martin J.
last_name: Rees
- first_name: Abraham
full_name: Loeb, Abraham
last_name: Loeb
citation:
ama: Haiman Z, Rees MJ, Loeb A. H 2 cooling of primordial gas triggered by UV irradiation.
The Astrophysical Journal. 1996;467. doi:10.1086/177628
apa: Haiman, Z., Rees, M. J., & Loeb, A. (1996). H 2 cooling of primordial gas
triggered by UV irradiation. The Astrophysical Journal. American Astronomical
Society. https://doi.org/10.1086/177628
chicago: Haiman, Zoltán, Martin J. Rees, and Abraham Loeb. “H 2 Cooling of Primordial
Gas Triggered by UV Irradiation.” The Astrophysical Journal. American Astronomical
Society, 1996. https://doi.org/10.1086/177628.
ieee: Z. Haiman, M. J. Rees, and A. Loeb, “H 2 cooling of primordial gas triggered
by UV irradiation,” The Astrophysical Journal, vol. 467. American Astronomical
Society, 1996.
ista: Haiman Z, Rees MJ, Loeb A. 1996. H 2 cooling of primordial gas triggered by
UV irradiation. The Astrophysical Journal. 467, 522.
mla: Haiman, Zoltán, et al. “H 2 Cooling of Primordial Gas Triggered by UV Irradiation.”
The Astrophysical Journal, vol. 467, 522, American Astronomical Society,
1996, doi:10.1086/177628.
short: Z. Haiman, M.J. Rees, A. Loeb, The Astrophysical Journal 467 (1996).
date_created: 2024-09-06T11:54:20Z
date_published: 1996-08-01T00:00:00Z
date_updated: 2024-12-10T09:18:05Z
day: '01'
doi: 10.1086/177628
extern: '1'
external_id:
unknown:
- astro-ph/9511126
intvolume: ' 467'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.astro-ph/9511126
month: '08'
oa: 1
oa_version: Preprint
publication: The Astrophysical Journal
publication_identifier:
eissn:
- 1538-4357
issn:
- 0004-637X
publication_status: published
publisher: American Astronomical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: H 2 cooling of primordial gas triggered by UV irradiation
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 467
year: '1996'
...
---
OA_place: repository
OA_type: green
_id: '17834'
abstract:
- lang: eng
text: 'We investigate the early formation of bound objects with masses comparable
to the cosmological Jeans mass (~10^5^ M_sun_). We follow the growth of isolated
spherically symmetric density peaks starting from the linear perturbative regime.
The initial parameters correspond to density peaks of various widths and heights
in a cold dark matter cosmology. We use a one-dimensional spherical Lagrangian
hydrodynamics code to follow the dynamical, thermal, and nonequilibrium chemical
evolution of the gas. The system includes a collisionless dark matter component
and a baryonic component composed of the nine species H, H^-^, H^+^, He, He^+^,
He^++^, H_2_, H_2_^+^, and e^-^. All relevant chemical reactions between these
species and their cooling mechanisms are included in the calculations. We explore
the dependence of the dynamical evolution of the gas on two parameters: the initial
mass scale and the initial overdensity of the system. We follow the evolution
of the density, temperature, and abundance profiles within the cloud, assuming
two types of central boundary conditions for the collisionless component: in one
the infalling dark matter virializes through a reflection from a hard sphere,
while in the other it accretes onto a central sink. We find that in both cases,
radiative cooling by H_2_ affects the collapse dynamics of the gas only after
it has already virialized and become part of the bound object. Therefore, radiative
cooling is unlikely to have triggered the initial collapse of perturbations at
redshifts z > 10. Nevertheless, baryonic objects with masses well below the linear
theory Jeans mass (<~10^3^ M_sun_) form at high redshifts because of shell crossing
by the dark matter. Such objects could be the progenitors of a primordial population
of high-mass stars in the intergalactic medium.'
article_number: '523'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Zoltán
full_name: Haiman, Zoltán
id: 7c006e8c-cc0d-11ee-8322-cb904ef76f36
last_name: Haiman
orcid: 0000-0003-3633-5403
- first_name: Anne A.
full_name: Thoul, Anne A.
last_name: Thoul
- first_name: Abraham
full_name: Loeb, Abraham
last_name: Loeb
citation:
ama: Haiman Z, Thoul AA, Loeb A. Cosmological formation of low-mass objects. The
Astrophysical Journal. 1996;464. doi:10.1086/177343
apa: Haiman, Z., Thoul, A. A., & Loeb, A. (1996). Cosmological formation of
low-mass objects. The Astrophysical Journal. American Astronomical Society.
https://doi.org/10.1086/177343
chicago: Haiman, Zoltán, Anne A. Thoul, and Abraham Loeb. “Cosmological Formation
of Low-Mass Objects.” The Astrophysical Journal. American Astronomical
Society, 1996. https://doi.org/10.1086/177343.
ieee: Z. Haiman, A. A. Thoul, and A. Loeb, “Cosmological formation of low-mass objects,”
The Astrophysical Journal, vol. 464. American Astronomical Society, 1996.
ista: Haiman Z, Thoul AA, Loeb A. 1996. Cosmological formation of low-mass objects.
The Astrophysical Journal. 464, 523.
mla: Haiman, Zoltán, et al. “Cosmological Formation of Low-Mass Objects.” The
Astrophysical Journal, vol. 464, 523, American Astronomical Society, 1996,
doi:10.1086/177343.
short: Z. Haiman, A.A. Thoul, A. Loeb, The Astrophysical Journal 464 (1996).
date_created: 2024-09-06T12:12:52Z
date_published: 1996-06-01T00:00:00Z
date_updated: 2025-01-03T11:34:15Z
day: '01'
doi: 10.1086/177343
extern: '1'
external_id:
arxiv:
- astro-ph/9507111
intvolume: ' 464'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/astro-ph/9507111
month: '06'
oa: 1
oa_version: Preprint
publication: The Astrophysical Journal
publication_identifier:
eissn:
- 1538-4357
issn:
- 0004-637X
publication_status: published
publisher: American Astronomical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Cosmological formation of low-mass objects
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 464
year: '1996'
...
---
_id: '4612'
alternative_title:
- LNCS
article_processing_charge: No
citation:
ama: 'Alur R, Henzinger TA, Sontag ED, eds. Hybrid Systems III: Verification
and Control. Vol 1066. Berlin ; Heidelberg: Springer; 1996. doi:10.1007/BFb0020931'
apa: 'Alur, R., Henzinger, T. A., & Sontag, E. D. (Eds.). (1996). Hybrid
Systems III: Verification and Control (Vol. 1066). Berlin ; Heidelberg: Springer.
https://doi.org/10.1007/BFb0020931'
chicago: 'Alur, Rajeev, Thomas A Henzinger, and Eduardo D Sontag, eds. Hybrid
Systems III: Verification and Control. Vol. 1066. Lecture Notes in Computer
Science. Berlin ; Heidelberg: Springer, 1996. https://doi.org/10.1007/BFb0020931.'
ieee: 'R. Alur, T. A. Henzinger, and E. D. Sontag, Eds., Hybrid Systems III:
Verification and Control, vol. 1066. Berlin ; Heidelberg: Springer, 1996.'
ista: 'Alur R, Henzinger TA, Sontag ED eds. 1996. Hybrid Systems III: Verification
and Control, Berlin ; Heidelberg: Springer, IX, 619p.'
mla: 'Alur, Rajeev, et al., editors. Hybrid Systems III: Verification and Control.
Vol. 1066, Springer, 1996, doi:10.1007/BFb0020931.'
short: 'R. Alur, T.A. Henzinger, E.D. Sontag, eds., Hybrid Systems III: Verification
and Control, Springer, Berlin ; Heidelberg, 1996.'
date_created: 2018-12-11T12:09:45Z
date_published: 1996-01-01T00:00:00Z
date_updated: 2021-12-22T13:57:33Z
day: '01'
doi: 10.1007/BFb0020931
editor:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- 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: Eduardo D
full_name: Sontag, Eduardo D
last_name: Sontag
extern: '1'
intvolume: ' 1066'
language:
- iso: eng
month: '01'
oa_version: None
page: IX, 619
place: Berlin ; Heidelberg
publication_identifier:
isbn:
- 978-3-540-61155-4
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '97'
quality_controlled: '1'
series_title: Lecture Notes in Computer Science
status: public
title: 'Hybrid Systems III: Verification and Control'
type: book_editor
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 1066
year: '1996'
...
---
_id: '4027'
abstract:
- lang: eng
text: 'Questions about lines in space arise frequently as subproblems in three-dimensional
computational geometry. In this paper we study a number of fundamental combinatorial
and algorithmic problems involving arrangements of n lines in three-dimensional
space. Our main results include: 1. A tight Θ(n2) bound on the maximum combinatorial
description complexity of the set of all oriented lines that have specified orientations
relative to the n given lines. 2. A similar bound of Θ(n3) for the complexity
of the set of all lines passing above the n given lines. 3. A preprocessing procedure
using O(n2+ε) time and storage, for any ε > 0, that builds a structure supporting
O(logn)-time queries for testing if a line lies above all the given lines. 4.
An algorithm that tests the "towering property" in O(n4/3+ε) time, for
any ε > 0: do n given red lines lie all above n given blue lines? The tools
used to obtain these and other results include Plücker coordinates for lines in
space and ε-nets for various geometric range spaces.'
acknowledgement: Work on this paper by Bernard Chazelle has been supported by NSF
Grant CCR-87-00917. Work on this paper by Herbert Edelsbrunner has been supported
by NSF Grant CCR-87-14565. Work on this paper by Leonidas Guibas has been supported
by grants from the Mitsubishi and Toshiba Corporations. Work on this paper by Micha
Sharir has been supported by ONR Grant N00014-87-K-0129, by NSF Grants DCR-83-20085
and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation,
the NCRD — the Israeli National Council for Research and Development, and the EMET
Fund of the Israeli Academy of Sciences.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
- first_name: Jorge
full_name: Stolfi, Jorge
last_name: Stolfi
citation:
ama: 'Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Stolfi J. Lines in space:
Combinatorics and algorithms. Algorithmica. 1996;15(5):428-447. doi:10.1007/BF01955043'
apa: 'Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Stolfi, J. (1996).
Lines in space: Combinatorics and algorithms. Algorithmica. Springer. https://doi.org/10.1007/BF01955043'
chicago: 'Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir,
and Jorge Stolfi. “Lines in Space: Combinatorics and Algorithms.” Algorithmica.
Springer, 1996. https://doi.org/10.1007/BF01955043.'
ieee: 'B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Stolfi, “Lines
in space: Combinatorics and algorithms,” Algorithmica, vol. 15, no. 5.
Springer, pp. 428–447, 1996.'
ista: 'Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Stolfi J. 1996. Lines in
space: Combinatorics and algorithms. Algorithmica. 15(5), 428–447.'
mla: 'Chazelle, Bernard, et al. “Lines in Space: Combinatorics and Algorithms.”
Algorithmica, vol. 15, no. 5, Springer, 1996, pp. 428–47, doi:10.1007/BF01955043.'
short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Stolfi, Algorithmica
15 (1996) 428–447.
date_created: 2018-12-11T12:06:31Z
date_published: 1996-05-01T00:00:00Z
date_updated: 2022-08-09T09:55:46Z
day: '01'
doi: 10.1007/BF01955043
extern: '1'
intvolume: ' 15'
issue: '5'
language:
- iso: eng
month: '05'
oa_version: None
page: 428 - 447
publication: Algorithmica
publication_identifier:
issn:
- 0178-4617
publication_status: published
publisher: Springer
publist_id: '2100'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Lines in space: Combinatorics and algorithms'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 15
year: '1996'
...
---
_id: '4164'
abstract:
- lang: eng
text: In a large-scale screen for mutants with defects in embryonic development
we identified 17 genes (65 mutants) specifically required for the development
of xanthophores, We provide evidence that these genes are required for three different
aspects of xanthophore development, (1) Pigment cell formation and migration (pfeffer
and salt); (2) pigment synthesis (edison, yobo, yocca and brie) and (3) pigment
translocation (esrom, tilsit and tofu). The number of xanthophore cells that appear
in the body is reduced in embryos with mutations in the two genes, salt and pfeffer.
In heterozygous and homozygous salt and pfeffer adults, the melanophore stripes
are interrupted, indicating that xanthophore cells have an important function
in adult melanophore pattern formation, Most other genes affect only larval pigmentation,
In embryos mutant for edison, yobo, yocca and brie, differences in pteridine synthesis
can be observed under UV light and by thin-layer chromatography. Homozygous mutant
females of yobo show a recessive maternal effect, Embryonic development is slowed
down and embryos display head and tail truncations, Xanthophores in larvae mutant
in the three genes esrom, tilsit and tofu appear less spread out, In addition,
these mutants display a defect in retinotectal axon pathfinding, These mutations
may affect xanthophore pigment distribution within the cells or xanthophore cell
shape, Mutations in seven genes affecting xanthophore pigmentation remain unclassified.
acknowledgement: We thank Silke Rudolph for technical assistance, Joel Wilson and
Cornelia Fricke for their help in the fish work and the thin layer chromatography,
and Darren Gilmour for help with the manuscript.
article_processing_charge: No
article_type: original
author:
- first_name: Jörg
full_name: Odenthal, Jörg
last_name: Odenthal
- first_name: Karin
full_name: Rossnagel, Karin
last_name: Rossnagel
- first_name: Pascal
full_name: Haffter, Pascal
last_name: Haffter
- first_name: Robert
full_name: Kelsh, Robert
last_name: Kelsh
- first_name: Elisabeth
full_name: Vogelsang, Elisabeth
last_name: Vogelsang
- first_name: Michael
full_name: Brand, Michael
last_name: Brand
- first_name: Fredericus
full_name: Van Eeden, Fredericus
last_name: Van Eeden
- first_name: Makoto
full_name: Furutani Seiki, Makoto
last_name: Furutani Seiki
- first_name: Michael
full_name: Granato, Michael
last_name: Granato
- first_name: Matthias
full_name: Hammerschmidt, Matthias
last_name: Hammerschmidt
- 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: Yunjin
full_name: Jiang, Yunjin
last_name: Jiang
- first_name: Donald
full_name: Kane, Donald
last_name: Kane
- first_name: Mary
full_name: Mullins, Mary
last_name: Mullins
- first_name: Christiane
full_name: Nüsslein Volhard, Christiane
last_name: Nüsslein Volhard
citation:
ama: Odenthal J, Rossnagel K, Haffter P, et al. Mutations affecting xanthophore
pigmentation in the zebrafish, Danio rerio. Development. 1996;123(1):391-398.
doi:10.1242/dev.123.1.391
apa: Odenthal, J., Rossnagel, K., Haffter, P., Kelsh, R., Vogelsang, E., Brand,
M., … Nüsslein Volhard, C. (1996). Mutations affecting xanthophore pigmentation
in the zebrafish, Danio rerio. Development. Company of Biologists. https://doi.org/10.1242/dev.123.1.391
chicago: Odenthal, Jörg, Karin Rossnagel, Pascal Haffter, Robert Kelsh, Elisabeth
Vogelsang, Michael Brand, Fredericus Van Eeden, et al. “Mutations Affecting Xanthophore
Pigmentation in the Zebrafish, Danio Rerio.” Development. Company of Biologists,
1996. https://doi.org/10.1242/dev.123.1.391.
ieee: J. Odenthal et al., “Mutations affecting xanthophore pigmentation in
the zebrafish, Danio rerio,” Development, vol. 123, no. 1. Company of Biologists,
pp. 391–398, 1996.
ista: Odenthal J, Rossnagel K, Haffter P, Kelsh R, Vogelsang E, Brand M, Van Eeden
F, Furutani Seiki M, Granato M, Hammerschmidt M, Heisenberg C-PJ, Jiang Y, Kane
D, Mullins M, Nüsslein Volhard C. 1996. Mutations affecting xanthophore pigmentation
in the zebrafish, Danio rerio. Development. 123(1), 391–398.
mla: Odenthal, Jörg, et al. “Mutations Affecting Xanthophore Pigmentation in the
Zebrafish, Danio Rerio.” Development, vol. 123, no. 1, Company of Biologists,
1996, pp. 391–98, doi:10.1242/dev.123.1.391.
short: J. Odenthal, K. Rossnagel, P. Haffter, R. Kelsh, E. Vogelsang, M. Brand,
F. Van Eeden, M. Furutani Seiki, M. Granato, M. Hammerschmidt, C.-P.J. Heisenberg,
Y. Jiang, D. Kane, M. Mullins, C. Nüsslein Volhard, Development 123 (1996) 391–398.
date_created: 2018-12-11T12:07:20Z
date_published: 1996-12-01T00:00:00Z
date_updated: 2022-08-08T08:08:51Z
day: '01'
doi: 10.1242/dev.123.1.391
extern: '1'
external_id:
pmid:
- '9007257 '
intvolume: ' 123'
issue: '1'
language:
- iso: eng
month: '12'
oa_version: None
page: 391 - 398
pmid: 1
publication: Development
publication_identifier:
issn:
- 0950-1991
publication_status: published
publisher: Company of Biologists
publist_id: '1955'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Mutations affecting xanthophore pigmentation in the zebrafish, Danio rerio
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 123
year: '1996'
...
---
_id: '4212'
abstract:
- lang: eng
text: In a large-scale screen, we isolated mutants displaying a specific visible
phenotype in embryos or early larvae of the zebrafish, Danio rerio. Males were
mutagenized with ethylnitrosourea (ENU) and F-2 families of single pair matings
between sibling F-l fish, heterozygous for a mutagenized genome, were raised.
Egg lays were obtained from several crosses between F-2 siblings, resulting in
scoring of 3857 mutagenized genomes. F-3 progeny were scored at the second, third
and sixth day of development, using a stereomicroscope. In a subsequent screen,
fixed embryos were analyzed for correct retinotectal projection. A total of 4264
mutants were identified. Two thirds of the mutants displaying rather general abnormalities
were eventually discarded. We kept and characterized 1163 mutants. In complementation
crosses performed between mutants with similar phenotypes, 894 mutants have been
assigned to 372 genes. The average allele frequency is 2.4. We identified genes
involved in early development, notochord, brain, spinal cord, somites, muscles,
heart, circulation, blood, skin, fin, eye, otic vesicle, jaw and branchial arches,
pigment pattern, pigment formation, gut, liver, motility and touch response. Our
collection contains alleles of almost all previously described zebrafish mutants.
From the allele frequencies and other considerations we estimate that the 372
genes defined by the mutants probably represent more than half of all genes that
could have been discovered using the criteria of our screen. Here we give an overview
of the spectrum of mutant phenotypes obtained, and discuss the limits and the
potentials of a genetic saturation screen in the zebrafish.
acknowledgement: "This work was a collaborative effort in which a large number of
people participated during all or part of the three years of raising the families,
screening and evaluation of the mutants. We thank Rachel Warga, Tatjana Piotrowski,
Francisco Pelegri, Karin Rossnagel and Hans-Martin Maischein for collaboration at
the beginning and the end of the screening and evaluation periods respectively;
Hans-Georg Frohnhöfer for fish health care and for establishing the Tübingen zebrafish
stockcenter; and Wolfgang Driever, Marc Fishman and collaborators, for sharing unpublished
results. We enjoyed the visits of Alison Brownlie, Jau-Nian Chen, Nancy Hopkins,
Corinne Houart, Shuo Lin, David Ransom, Thomas Schilling, Tanya Whitfield and Catherine
Willet, who participated in the analysis of individual mutant classes. We also want
to thank many undergraduate students from the Tübingen University for conscientious
and efficient help in the maintenance and identification of fish, and Torsten Trowe,
Rolf Karlstrom, Barbara Grunwald and Friedrich Bonhoeffer for pleasant and interesting
conversations and collaborations. We thank the staff of our workshop for patience,
\r\n Inventiveness and a very large number of fish containers. We thank Herwig Baier,
Robert Geisler, Darren Gilmour,\r\nNancy Hopkins, Suresh Jesuthasan, Gerd Jürgens,
Francisco Pelegri, Siegfried Roth, Stefan Schulte-Merker, Ralf Sommer, Daniel St
Johnston and Tanya Whitfield, for many helpful suggestions on the manuscript; Robert
Geisler for invaluable help with computers, cameras and colour printers, and the
Tübingen fly group for interest, endless patience and support."
article_processing_charge: No
article_type: original
author:
- first_name: Pascal
full_name: Haffter, Pascal
last_name: Haffter
- first_name: Michael
full_name: Granato, Michael
last_name: Granato
- first_name: Michael
full_name: Brand, Michael
last_name: Brand
- first_name: Mary
full_name: Mullins, Mary
last_name: Mullins
- first_name: Matthias
full_name: Hammerschmidt, Matthias
last_name: Hammerschmidt
- first_name: Donald
full_name: Kane, Donald
last_name: Kane
- first_name: Jörg
full_name: Odenthal, Jörg
last_name: Odenthal
- first_name: Fredericus
full_name: Van Eeden, Fredericus
last_name: Van Eeden
- first_name: Yunjin
full_name: Jiang, Yunjin
last_name: Jiang
- 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: Robert
full_name: Kelsh, Robert
last_name: Kelsh
- first_name: Makoto
full_name: Furutani Seiki, Makoto
last_name: Furutani Seiki
- first_name: Elisabeth
full_name: Vogelsang, Elisabeth
last_name: Vogelsang
- first_name: Dirk
full_name: Beuchle, Dirk
last_name: Beuchle
- first_name: Ursula
full_name: Schach, Ursula
last_name: Schach
- first_name: Cosima
full_name: Fabian, Cosima
last_name: Fabian
- first_name: Christiane
full_name: Nüsslein Volhard, Christiane
last_name: Nüsslein Volhard
citation:
ama: Haffter P, Granato M, Brand M, et al. The identification of genes with unique
and essential functions in the development of the zebrafish, Danio rerio. Development.
1996;123(1):1-36. doi:10.1242/dev.123.1.1
apa: Haffter, P., Granato, M., Brand, M., Mullins, M., Hammerschmidt, M., Kane,
D., … Nüsslein Volhard, C. (1996). The identification of genes with unique and
essential functions in the development of the zebrafish, Danio rerio. Development.
Company of Biologists. https://doi.org/10.1242/dev.123.1.1
chicago: Haffter, Pascal, Michael Granato, Michael Brand, Mary Mullins, Matthias
Hammerschmidt, Donald Kane, Jörg Odenthal, et al. “The Identification of Genes
with Unique and Essential Functions in the Development of the Zebrafish, Danio
Rerio.” Development. Company of Biologists, 1996. https://doi.org/10.1242/dev.123.1.1 .
ieee: P. Haffter et al., “The identification of genes with unique and essential
functions in the development of the zebrafish, Danio rerio,” Development,
vol. 123, no. 1. Company of Biologists, pp. 1–36, 1996.
ista: Haffter P, Granato M, Brand M, Mullins M, Hammerschmidt M, Kane D, Odenthal
J, Van Eeden F, Jiang Y, Heisenberg C-PJ, Kelsh R, Furutani Seiki M, Vogelsang
E, Beuchle D, Schach U, Fabian C, Nüsslein Volhard C. 1996. The identification
of genes with unique and essential functions in the development of the zebrafish,
Danio rerio. Development. 123(1), 1–36.
mla: Haffter, Pascal, et al. “The Identification of Genes with Unique and Essential
Functions in the Development of the Zebrafish, Danio Rerio.” Development,
vol. 123, no. 1, Company of Biologists, 1996, pp. 1–36, doi:10.1242/dev.123.1.1 .
short: P. Haffter, M. Granato, M. Brand, M. Mullins, M. Hammerschmidt, D. Kane,
J. Odenthal, F. Van Eeden, Y. Jiang, C.-P.J. Heisenberg, R. Kelsh, M. Furutani
Seiki, E. Vogelsang, D. Beuchle, U. Schach, C. Fabian, C. Nüsslein Volhard, Development
123 (1996) 1–36.
date_created: 2018-12-11T12:07:37Z
date_published: 1996-12-01T00:00:00Z
date_updated: 2022-08-04T14:41:37Z
day: '01'
doi: '10.1242/dev.123.1.1 '
extern: '1'
external_id:
pmid:
- '9007226 '
intvolume: ' 123'
issue: '1'
language:
- iso: eng
month: '12'
oa_version: None
page: 1 - 36
pmid: 1
publication: Development
publication_identifier:
issn:
- 0950-1991
publication_status: published
publisher: Company of Biologists
publist_id: '1905'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The identification of genes with unique and essential functions in the development
of the zebrafish, Danio rerio
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 123
year: '1996'
...
---
_id: '4443'
abstract:
- lang: eng
text: "Three natural equivalence relations on the infinite state space of a hybrid
automaton are language equivalence, simulation equivalence, and bisimulation equivalence.
When one of these equivalence relations has a finite quotient, certain model checking
and controller synthesis problems are decidable. When bounds on the number of
equivalence classes are obtained, bounds on the running times of model checking
and synthesis algorithms follow as corollaries.\r\nWe characterize the time-abstract
versions of these equivalence relations on the state spaces of rectangular hybrid
automata (RHA), in which each continuous variable is a clock with bounded drift.
These automata are useful for modeling communications protocols with drifting
local clocks, and for the conservative approximation of more complex hybrid systems.
Of our two main results, one has positive implications for automatic verification,
and the other has negative implications. On the positive side, we find that the
(finite) language equivalence quotient for RHA is coarser than was previously
known by a multiplicative exponential factor. On the negative side, we show that
simulation equivalence for RHA is equality (which obviously has an infinite quotient).\r\nOur
main positive result is established by analyzing a subclass of timed automata,
called one-sided timed automata (OTA), for which the language equivalence quotient
is coarser than for the class of all timed automata. An exact characterization
of language equivalence for OTA requires a distinction between synchronous and
asynchronous definitions of (bi)simulation: if time actions are silent, then the
induced quotient for OTA is coarser than if time actions (but not their durations)
are visible."
acknowledgement: This research was supported in part by ONR Young Investigator award
N00014-95-1-0520, by NSF CAREER award CCR-9501708, by NSF grant CCR-9504469, by
Air Force Office of Scientific Research contract F49620-93-1-0056, by ARPA 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.
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
citation:
ama: 'Henzinger TA, Kopke P. State equivalences for rectangular hybrid automata.
In: 7th International Conference on Concurrency Theory. Vol 1119. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 1996:530-545. doi:10.1007/3-540-61604-7_74'
apa: 'Henzinger, T. A., & Kopke, P. (1996). State equivalences for rectangular
hybrid automata. In 7th International Conference on Concurrency Theory
(Vol. 1119, pp. 530–545). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.1007/3-540-61604-7_74'
chicago: Henzinger, Thomas A, and Peter Kopke. “State Equivalences for Rectangular
Hybrid Automata.” In 7th International Conference on Concurrency Theory,
1119:530–45. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1996. https://doi.org/10.1007/3-540-61604-7_74.
ieee: T. A. Henzinger and P. Kopke, “State equivalences for rectangular hybrid automata,”
in 7th International Conference on Concurrency Theory, Pisa, Italy, 1996,
vol. 1119, pp. 530–545.
ista: 'Henzinger TA, Kopke P. 1996. State equivalences for rectangular hybrid automata.
7th International Conference on Concurrency Theory. CONCUR: Concurrency Theory,
LNCS, vol. 1119, 530–545.'
mla: Henzinger, Thomas A., and Peter Kopke. “State Equivalences for Rectangular
Hybrid Automata.” 7th International Conference on Concurrency Theory, vol.
1119, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1996, pp. 530–45, doi:10.1007/3-540-61604-7_74.
short: T.A. Henzinger, P. Kopke, in:, 7th International Conference on Concurrency
Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1996, pp. 530–545.
conference:
end_date: 1996-08-29
location: Pisa, Italy
name: 'CONCUR: Concurrency Theory'
start_date: 1996-08-26
date_created: 2018-12-11T12:08:52Z
date_published: 1996-01-01T00:00:00Z
date_updated: 2022-07-06T08:43:23Z
day: '01'
doi: 10.1007/3-540-61604-7_74
extern: '1'
intvolume: ' 1119'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-61604-7_74
month: '01'
oa_version: None
page: 530 - 545
publication: 7th International Conference on Concurrency Theory
publication_identifier:
isbn:
- '9783540616047'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '288'
quality_controlled: '1'
status: public
title: State equivalences for rectangular hybrid automata
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1119
year: '1996'
...
---
_id: '4495'
abstract:
- lang: eng
text: In temporal-logic model checking, we verify the correctness of a program with
respect to a desired behavior by checking whether a structure that models the
program satisfies a temporal-logic formula that specifies the behavior. The main
practical limitation of model checking is caused by the size of the state space
of the program, which grows exponentially with the number of concurrent components.
This problem, known as the state-explosion problem, becomes more difficult when
we consider real-time model checking, where the program and the specification
involve quantitative references to time. In particular, when use timed automata
to describe real-time programs and we specify timed behaviors in the logic TCTL,
a real-time extension of the temporal logic CTL with clock variables, then the
state space under consideration grows exponentially not only with the number of
concurrent components, but also with the number of clocks and the length of the
clock constraints used in the program and the specification. Two powerful methods
for coping with the state-explosion problem are on-the-fly and space-efficient
model checking. In on-the-fly model checking, we explore only the portion of the
state space of the program whose exploration is essential for determining the
satisfaction of the specification. In space-efficient model checking, we store
in memory the minimal information required, preferring to spend time on reconstructing
information rather than spend space on storing it. In this work we develop an
automata-theoretic approach to TCTL model checking that combines both methods.
We suggest, for the first time, a PSPACE on-the-fly model-checking algorithm for
TCTL.
acknowledgement: Supported in part by the ONR YIP award N00014-95-1-0520, by the NSF
CAREER award CCR-9501708, by the NSF grant 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: Orna
full_name: Kupferman, Orna
last_name: Kupferman
- first_name: Moshe
full_name: Vardi, Moshe
last_name: Vardi
citation:
ama: 'Henzinger TA, Kupferman O, Vardi M. A space-efficient on-the-fly algorithm
for real-time model checking. In: 7th International Conference on Concurrency
Theory. Vol 1119. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 1996:514-529.
doi:10.1007/3-540-61604-7_73'
apa: 'Henzinger, T. A., Kupferman, O., & Vardi, M. (1996). A space-efficient
on-the-fly algorithm for real-time model checking. In 7th International Conference
on Concurrency Theory (Vol. 1119, pp. 514–529). Pisa, Italy: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-61604-7_73'
chicago: Henzinger, Thomas A, Orna Kupferman, and Moshe Vardi. “A Space-Efficient
on-the-Fly Algorithm for Real-Time Model Checking.” In 7th International Conference
on Concurrency Theory, 1119:514–29. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 1996. https://doi.org/10.1007/3-540-61604-7_73.
ieee: T. A. Henzinger, O. Kupferman, and M. Vardi, “A space-efficient on-the-fly
algorithm for real-time model checking,” in 7th International Conference on
Concurrency Theory, Pisa, Italy, 1996, vol. 1119, pp. 514–529.
ista: 'Henzinger TA, Kupferman O, Vardi M. 1996. A space-efficient on-the-fly algorithm
for real-time model checking. 7th International Conference on Concurrency Theory.
CONCUR: Concurrency Theory, LNCS, vol. 1119, 514–529.'
mla: Henzinger, Thomas A., et al. “A Space-Efficient on-the-Fly Algorithm for Real-Time
Model Checking.” 7th International Conference on Concurrency Theory, vol.
1119, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1996, pp. 514–29, doi:10.1007/3-540-61604-7_73.
short: T.A. Henzinger, O. Kupferman, M. Vardi, in:, 7th International Conference
on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1996,
pp. 514–529.
conference:
end_date: 1996-08-29
location: Pisa, Italy
name: 'CONCUR: Concurrency Theory'
start_date: 1996-08-26
date_created: 2018-12-11T12:09:08Z
date_published: 1996-01-01T00:00:00Z
date_updated: 2022-07-06T08:21:20Z
day: '01'
doi: 10.1007/3-540-61604-7_73
extern: '1'
intvolume: ' 1119'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-61604-7_73
month: '01'
oa_version: None
page: 514 - 529
publication: 7th International Conference on Concurrency Theory
publication_identifier:
isbn:
- 978-3-540-70625-0
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '233'
quality_controlled: '1'
status: public
title: A space-efficient on-the-fly algorithm for real-time model checking
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1119
year: '1996'
...