---
_id: '11857'
abstract:
- lang: eng
text: Two edges e/sub 1/ and e/sub 2/ of an undirected graph are cycle-equivalent
iff all cycles that contain e/sub 1/ also contain e/sub 2/, i.e., iff e/sub 1/
and e/sub 2/ are a cut-edge pair. The cycle-equivalence classes of the control-flow
graph are used in optimizing compilers to speed up existing control-flow and data-flow
algorithms. While the cycle-equivalence classes can be computed in linear time,
we present the first fully dynamic algorithm for maintaining the cycle-equivalence
relation. In an n-node graph our data structure executes an edge insertion or
deletion in O(/spl radic/n log n) time and answers the query whether two given
edges are cycle-equivalent in O(log/sup 2/ n) time. We also present an algorithm
for plane graphs with O(log n) update and query time and for planar graphs with
O(log n) insertion time and O(log/sup 2/ n) query and deletion time. Additionally,
we show a lower bound of /spl Omega/(log n/log log n) for the amortized time per
operation for the dynamic cycle-equivalence problem in the cell probe model.<
>
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
citation:
ama: 'Henzinger MH. Fully dynamic cycle-equivalence in graphs. In: 35th Annual
Symposium on Foundations of Computer Science. Institute of Electrical and
Electronics Engineers; 1994:744-755. doi:10.1109/sfcs.1994.365718'
apa: 'Henzinger, M. H. (1994). Fully dynamic cycle-equivalence in graphs. In 35th
Annual Symposium on Foundations of Computer Science (pp. 744–755). Santa Fe,
NM, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/sfcs.1994.365718'
chicago: Henzinger, Monika H. “Fully Dynamic Cycle-Equivalence in Graphs.” In 35th
Annual Symposium on Foundations of Computer Science, 744–55. Institute of
Electrical and Electronics Engineers, 1994. https://doi.org/10.1109/sfcs.1994.365718.
ieee: M. H. Henzinger, “Fully dynamic cycle-equivalence in graphs,” in 35th Annual
Symposium on Foundations of Computer Science, Santa Fe, NM, United States,
1994, pp. 744–755.
ista: 'Henzinger MH. 1994. Fully dynamic cycle-equivalence in graphs. 35th Annual
Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of
Computer Science, 744–755.'
mla: Henzinger, Monika H. “Fully Dynamic Cycle-Equivalence in Graphs.” 35th Annual
Symposium on Foundations of Computer Science, Institute of Electrical and
Electronics Engineers, 1994, pp. 744–55, doi:10.1109/sfcs.1994.365718.
short: M.H. Henzinger, in:, 35th Annual Symposium on Foundations of Computer Science,
Institute of Electrical and Electronics Engineers, 1994, pp. 744–755.
conference:
end_date: 1994-11-22
location: Santa Fe, NM, United States
name: 'FOCS: Symposium on Foundations of Computer Science'
start_date: 1994-11-20
date_created: 2022-08-16T08:29:08Z
date_published: 1994-11-01T00:00:00Z
date_updated: 2023-02-17T09:58:04Z
day: '01'
doi: 10.1109/sfcs.1994.365718
extern: '1'
language:
- iso: eng
month: '11'
oa_version: None
page: 744 - 755
publication: 35th Annual Symposium on Foundations of Computer Science
publication_identifier:
isbn:
- 0-8186-6580-7
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic cycle-equivalence in graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1994'
...
---
_id: '3453'
alternative_title:
- Advances in second messenger and phosphoprotein research
article_processing_charge: No
author:
- first_name: Eberhard
full_name: Von Kitzing, Eberhard
last_name: Von Kitzing
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
- first_name: Bert
full_name: Sakmann, Bert
last_name: Sakmann
citation:
ama: Von Kitzing E, Jonas PM, Sakmann B. Quantal analysis of excitatory postsynaptic
currents at the hippocampal mossy fiber-CA3 pyramidal cell synapse. Molecular
and cellular mechanisms of neurotransmitter release. 1994;29:235-260. doi:10.1016/0166-2236(95)90088-8
apa: Von Kitzing, E., Jonas, P. M., & Sakmann, B. (1994). Quantal analysis of
excitatory postsynaptic currents at the hippocampal mossy fiber-CA3 pyramidal
cell synapse. Molecular and Cellular Mechanisms of Neurotransmitter Release.
Raven Press. https://doi.org/10.1016/0166-2236(95)90088-8
chicago: Von Kitzing, Eberhard, Peter M Jonas, and Bert Sakmann. “Quantal Analysis
of Excitatory Postsynaptic Currents at the Hippocampal Mossy Fiber-CA3 Pyramidal
Cell Synapse.” Molecular and Cellular Mechanisms of Neurotransmitter Release.
Raven Press, 1994. https://doi.org/10.1016/0166-2236(95)90088-8.
ieee: E. Von Kitzing, P. M. Jonas, and B. Sakmann, “Quantal analysis of excitatory
postsynaptic currents at the hippocampal mossy fiber-CA3 pyramidal cell synapse,”
Molecular and cellular mechanisms of neurotransmitter release, vol. 29.
Raven Press, pp. 235–260, 1994.
ista: Von Kitzing E, Jonas PM, Sakmann B. 1994. Quantal analysis of excitatory postsynaptic
currents at the hippocampal mossy fiber-CA3 pyramidal cell synapse. Molecular
and cellular mechanisms of neurotransmitter release. 29, 235–260.
mla: Von Kitzing, Eberhard, et al. “Quantal Analysis of Excitatory Postsynaptic
Currents at the Hippocampal Mossy Fiber-CA3 Pyramidal Cell Synapse.” Molecular
and Cellular Mechanisms of Neurotransmitter Release, vol. 29, Raven Press,
1994, pp. 235–60, doi:10.1016/0166-2236(95)90088-8.
short: E. Von Kitzing, P.M. Jonas, B. Sakmann, Molecular and Cellular Mechanisms
of Neurotransmitter Release 29 (1994) 235–260.
date_created: 2018-12-11T12:03:24Z
date_published: 1994-01-01T00:00:00Z
date_updated: 2022-06-03T11:46:09Z
day: '01'
doi: 10.1016/0166-2236(95)90088-8
extern: '1'
external_id:
pmid:
- '7848714 '
intvolume: ' 29'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0166223695900888?via%3Dihub
month: '01'
oa_version: None
page: 235 - 260
pmid: 1
publication: Molecular and cellular mechanisms of neurotransmitter release
publication_identifier:
isbn:
- '0781702208'
publication_status: published
publisher: Raven Press
publist_id: '2934'
quality_controlled: '1'
status: public
title: Quantal analysis of excitatory postsynaptic currents at the hippocampal mossy
fiber-CA3 pyramidal cell synapse
type: review
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 29
year: '1994'
...
---
_id: '3460'
abstract:
- lang: eng
text: Excitatory postsynaptic currents in neurones of the central nervous system
have a dual-component time course that results from the co-activation of AMPA/kainate-type
and NMDA-type glutamate receptors. New approaches in electrophysiology and molecular
biology have provided a better understanding of the factors that determine the
kinectics of excitatory postsynaptic currents. Recent studies suggest that the
time course of neurotransmitter concentration in the synaptic cleft, the gating
properties of the native channels, and the glutamate receptor subunit composition
all appear to be important factors.
acknowledgement: 'We thank JGG Borst, N Burnashev, M Häusser, G Stuart and A Viilarroel
for critically reading the manuscript and E von Kitzing and A Roth for doing the
simulations and for many helpful discussions. Supported by the Deutsche Forschungsgemeinschaft
(SFB 317-B14) and the Alexander von Humboldt Foundation. '
article_processing_charge: No
article_type: original
author:
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
- first_name: Nelson
full_name: Spruston, Nelson
last_name: Spruston
citation:
ama: Jonas PM, Spruston N. Mechanisms shaping glutamate-mediated excitatory postsynaptic
currents in the CNS. Current Opinion in Neurobiology. 1994;4(3):366-372.
doi:10.1016/0959-4388(94)90098-1
apa: Jonas, P. M., & Spruston, N. (1994). Mechanisms shaping glutamate-mediated
excitatory postsynaptic currents in the CNS. Current Opinion in Neurobiology.
Elsevier. https://doi.org/10.1016/0959-4388(94)90098-1
chicago: Jonas, Peter M, and Nelson Spruston. “Mechanisms Shaping Glutamate-Mediated
Excitatory Postsynaptic Currents in the CNS.” Current Opinion in Neurobiology.
Elsevier, 1994. https://doi.org/10.1016/0959-4388(94)90098-1.
ieee: P. M. Jonas and N. Spruston, “Mechanisms shaping glutamate-mediated excitatory
postsynaptic currents in the CNS,” Current Opinion in Neurobiology, vol.
4, no. 3. Elsevier, pp. 366–372, 1994.
ista: Jonas PM, Spruston N. 1994. Mechanisms shaping glutamate-mediated excitatory
postsynaptic currents in the CNS. Current Opinion in Neurobiology. 4(3), 366–372.
mla: Jonas, Peter M., and Nelson Spruston. “Mechanisms Shaping Glutamate-Mediated
Excitatory Postsynaptic Currents in the CNS.” Current Opinion in Neurobiology,
vol. 4, no. 3, Elsevier, 1994, pp. 366–72, doi:10.1016/0959-4388(94)90098-1.
short: P.M. Jonas, N. Spruston, Current Opinion in Neurobiology 4 (1994) 366–372.
date_created: 2018-12-11T12:03:27Z
date_published: 1994-06-01T00:00:00Z
date_updated: 2022-06-03T11:26:52Z
day: '01'
doi: 10.1016/0959-4388(94)90098-1
extern: '1'
external_id:
pmid:
- '7522678 '
intvolume: ' 4'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0959438894900981?via%3Dihub
month: '06'
oa_version: None
page: 366 - 372
pmid: 1
publication: Current Opinion in Neurobiology
publication_identifier:
issn:
- 0959-4388
publication_status: published
publisher: Elsevier
publist_id: '2927'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Mechanisms shaping glutamate-mediated excitatory postsynaptic currents in the
CNS
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 4
year: '1994'
...
---
_id: '3475'
abstract:
- lang: eng
text: '1. A potassium channel activated by internal Na+ ions (K+Na channel) was
identified in peripheral myelinated axons of Xenopus laevis using the cell-attached
and excised configurations of the patch clamp technique. 2. The single-channel
conductance for the main open state was 88 pS with [K+]o = 105 mM and pS with
[K+]o = 2.5 mM ([K+]i = 105 mM). The channel was selectively permeable to K+ over
Na+ ions. A characteristic feature of the K+Na channel was the frequent occurrence
of subconductance states. 3. The open probability of the channel was strongly
dependent on the concentration of Na+ ions at the inner side of the membrane.
The half-maximal activating Na+ concentration and the Hill coefficient were 33
mM and 2.9, respectively. The open probability of the channel showed only weak
potential dependence. 4. The K+Na channel was relatively insensitive to external
tetraethylammonium (TEA+) in comparison with voltage-dependent axonal K+ channels;
the half-maximal inhibitory concentration (IC50) was 21.3 mM (at -90 mV). In contrast,
the channel was blocked by low concentrations of external Ba2+ and Cs+ ions, with
IC50 values of 0.7 and 1.1 mM, respectively (at -90 mV). The block by Ba2+ and
Cs+ was more pronounced at negative than at positive membrane potentials. 5. A
comparison of the number of K+Na channels in nodal and paranodal patches from
the same axon revealed that the channel density was about 10-fold higher at the
node of Ranvier than at the paranode. Moreover, a correlation between the number
of K+Na channels and voltage-dependent Na+ channels in the same patches was found,
suggesting co-localization of both channel types. 6. As weakly potential-dependent
(''leakage'') channels, axonal K+Na channels may be involved in setting the resting
potential of vertebrate axons. Simulations of Na+ ion diffusion suggest two possible
mechanisms of activation of K+Na channels: the local increase of Na+ concentration
in a cluster of Na+ channels during a single action potential or the accumulation
in the intracellular axonal compartment during a train of action potentials.'
acknowledgement: 'We thank Drs M.Häusser and A. Villarroel for critically reading
the manuscript, Dr E. v. Kitzing and A. Roth for many helpful discussions. This
work was supported by the Deutsche Forschungsgemeinschaft (Vo188/13-2). '
article_processing_charge: No
article_type: original
author:
- first_name: Duk
full_name: Koh, Duk
last_name: Koh
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
- first_name: Werner
full_name: Vogel, Werner
last_name: Vogel
citation:
ama: Koh D, Jonas PM, Vogel W. Na+-activated K+ channels localized in the nodal
region of myelinated axons of Xenopus. Journal of Physiology. 1994;479:183-197.
doi:10.1113/jphysiol.1994.sp020287
apa: Koh, D., Jonas, P. M., & Vogel, W. (1994). Na+-activated K+ channels localized
in the nodal region of myelinated axons of Xenopus. Journal of Physiology.
Wiley-Blackwell. https://doi.org/10.1113/jphysiol.1994.sp020287
chicago: Koh, Duk, Peter M Jonas, and Werner Vogel. “Na+-Activated K+ Channels Localized
in the Nodal Region of Myelinated Axons of Xenopus.” Journal of Physiology.
Wiley-Blackwell, 1994. https://doi.org/10.1113/jphysiol.1994.sp020287.
ieee: D. Koh, P. M. Jonas, and W. Vogel, “Na+-activated K+ channels localized in
the nodal region of myelinated axons of Xenopus,” Journal of Physiology,
vol. 479. Wiley-Blackwell, pp. 183–197, 1994.
ista: Koh D, Jonas PM, Vogel W. 1994. Na+-activated K+ channels localized in the
nodal region of myelinated axons of Xenopus. Journal of Physiology. 479, 183–197.
mla: Koh, Duk, et al. “Na+-Activated K+ Channels Localized in the Nodal Region of
Myelinated Axons of Xenopus.” Journal of Physiology, vol. 479, Wiley-Blackwell,
1994, pp. 183–97, doi:10.1113/jphysiol.1994.sp020287.
short: D. Koh, P.M. Jonas, W. Vogel, Journal of Physiology 479 (1994) 183–197.
date_created: 2018-12-11T12:03:31Z
date_published: 1994-01-01T00:00:00Z
date_updated: 2022-06-03T11:09:21Z
day: '01'
doi: 10.1113/jphysiol.1994.sp020287
extern: '1'
external_id:
pmid:
- '7799220 '
intvolume: ' 479'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1155738/
month: '01'
oa: 1
oa_version: Published Version
page: 183 - 197
pmid: 1
publication: Journal of Physiology
publication_identifier:
issn:
- 0022-3751
publication_status: published
publisher: Wiley-Blackwell
publist_id: '2912'
quality_controlled: '1'
status: public
title: Na+-activated K+ channels localized in the nodal region of myelinated axons
of Xenopus
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 479
year: '1994'
...
---
_id: '3476'
abstract:
- lang: eng
text: Tight-seal whole-cell recordings were made from cleaned somata of CA3 pyramidal
cells deep in hippocampal slices from 19–21-d-old rats. The cells were filled
with biocytin, and their voltage responses to short current pulses were recorded.
After washout of initial sag, responses scaled linearly with injected current
and were stable over time. The dendritic and axonal arbors of four cells were
reconstructed and measured using light microscopy. Dendritic spines and axonal
boutons were counted and the additional membrane area was incorporated into the
relevant segments. The morphology of each neuron was converted into a detailed
branching cable model by assuming values for specific membrane capacitance Cm
and resistance Rm, and cytoplasmic resistivity Ri. These parameters were optimized
for each cell by directly matching the model's response to that of the real cell
by means of a modified weighted least-squares fitting procedure. By comparing
the deviations between model and experimental responses to control noise recordings,
approximate 95% confidence intervals were established for each parameter. If a
somatic shunt was allowed, a wide range of possible Rm values produced acceptable
fits. With zero shunt, Cm was 0.7–0.8 microFcm-2, Ri was 170–340 omega cm, and
Rm ranged between 120 and 200 k omega cm2. The electrotonic lengths of the basal
and oblique dendrites were 0.2–0.3 space constants, and those of the apical tufts
were 0.4–0.7 space constants. The steady-state electrical geometry of these cells
was therefore compact; average dendritic tip/soma relative synaptic efficacies
were > 93% for the basal and oblique dendrites, and > 81% for the tufts.
With fast transient synaptic inputs, however, the models produced a wide range
of postsynaptic potential shapes and marked filtering of voltage-clamp currents.
acknowledgement: 'logy Training Fellowship. A.L. was supported by a Royal Society
Fellowship. The Oxford part of the collaboration was funded by a Wellcome Trust
Programme Grant, the Heidelberg part by the Max-Planck Gesellschaft. We are grateful
to Sir David Cox for his comments on the statistics, to K. Stratford, M. Hausser,
D. Flitney, M. O’Neill, S. Gough, G. Stuart, N. Spruston, P. Stem, and K. Bauer
for their help and useful discussions, and to M. Kaiser for technical assistance. '
article_processing_charge: No
article_type: original
author:
- first_name: Guy
full_name: Major, Guy
last_name: Major
- first_name: Alan
full_name: Larkman, Alan
last_name: Larkman
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
- first_name: Bert
full_name: Sakmann, Bert
last_name: Sakmann
- first_name: Julian
full_name: Jack, Julian
last_name: Jack
citation:
ama: Major G, Larkman A, Jonas PM, Sakmann B, Jack J. Detailed passive cable models
of whole-cell recorded CA3 pyramidal neurons in rat hippocampal slices. Journal
of Neuroscience. 1994;14(8):4613-4638. doi:10.1523/JNEUROSCI.14-08-04613.1994
apa: Major, G., Larkman, A., Jonas, P. M., Sakmann, B., & Jack, J. (1994). Detailed
passive cable models of whole-cell recorded CA3 pyramidal neurons in rat hippocampal
slices. Journal of Neuroscience. Society for Neuroscience. https://doi.org/10.1523/JNEUROSCI.14-08-04613.1994
chicago: Major, Guy, Alan Larkman, Peter M Jonas, Bert Sakmann, and Julian Jack.
“Detailed Passive Cable Models of Whole-Cell Recorded CA3 Pyramidal Neurons in
Rat Hippocampal Slices.” Journal of Neuroscience. Society for Neuroscience,
1994. https://doi.org/10.1523/JNEUROSCI.14-08-04613.1994.
ieee: G. Major, A. Larkman, P. M. Jonas, B. Sakmann, and J. Jack, “Detailed passive
cable models of whole-cell recorded CA3 pyramidal neurons in rat hippocampal slices,”
Journal of Neuroscience, vol. 14, no. 8. Society for Neuroscience, pp.
4613–4638, 1994.
ista: Major G, Larkman A, Jonas PM, Sakmann B, Jack J. 1994. Detailed passive cable
models of whole-cell recorded CA3 pyramidal neurons in rat hippocampal slices.
Journal of Neuroscience. 14(8), 4613–4638.
mla: Major, Guy, et al. “Detailed Passive Cable Models of Whole-Cell Recorded CA3
Pyramidal Neurons in Rat Hippocampal Slices.” Journal of Neuroscience,
vol. 14, no. 8, Society for Neuroscience, 1994, pp. 4613–38, doi:10.1523/JNEUROSCI.14-08-04613.1994.
short: G. Major, A. Larkman, P.M. Jonas, B. Sakmann, J. Jack, Journal of Neuroscience
14 (1994) 4613–4638.
date_created: 2018-12-11T12:03:32Z
date_published: 1994-08-01T00:00:00Z
date_updated: 2022-06-03T09:36:43Z
day: '01'
doi: 10.1523/JNEUROSCI.14-08-04613.1994
extern: '1'
external_id:
pmid:
- '8046439 '
intvolume: ' 14'
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://europepmc.org/article/med/8046439
month: '08'
oa: 1
oa_version: Published Version
page: 4613 - 4638
pmid: 1
publication: Journal of Neuroscience
publication_identifier:
issn:
- 0270-6474
publication_status: published
publisher: Society for Neuroscience
publist_id: '2911'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Detailed passive cable models of whole-cell recorded CA3 pyramidal neurons
in rat hippocampal slices
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 14
year: '1994'
...
---
_id: '3477'
abstract:
- lang: eng
text: Fast excitatory synaptic transmission in the CNS is mediated by AMPA-type
glutamate receptor (GluR) channels. Heterologous expression suggested that the
Ca2+ permeability of these receptors critically depends on the subunit composition.
Using patch-clamp techniques in brain slices, we found that the Ca2+ permeability
of native AMPA-type GluRs was markedly higher in nonpyramidal (P(Ca)/P(K) ≃ 0.63)
than in pyramidal (P(Ca)/P(K) ≃ 0.05) neurons of rat neocortex. Analysis of mRNA
in single cells indicated that the relative abundance of GluR-B-specific mRNA
was significantly lower in nonpyramidal (GluR-B/GluR-non-B ≃ 0.3) than in pyramidal
(GluR-B/GluR-non-B ≃ 3) cells. This suggests that differences in relative abundance
of GluR-B- specific mRNA generate functional diversity of AMPA-type GluRs in neurons
with respect to Ca2+ permeability.
acknowledgement: We thank Drs. B. Lambolez and J. Rossier for helping to establish
the method of single-cell PCR, Dr. M. Frotscher for help with cell identification,
Dr. N. Spruston for critically reading the manuscript, and M. Kaiser and U. Keller
for technical assistance. This work was supported in part by BMFT grant BCT 364
AZ 3211 7291 (P. H. S.) and by DFG grant SFB-317/B14 (P. J.). The costs of publication
of this article were defrayed in part by the payment of page charges. This article
must therefore be hereby marked “advertisement” in accordance with 18 USC Section
1734 solely to indicate this fact.
article_processing_charge: No
article_type: original
author:
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
- first_name: Claudia
full_name: Racca, Claudia
last_name: Racca
- first_name: Bert
full_name: Sakmann, Bert
last_name: Sakmann
- first_name: Peter
full_name: Seeburg, Peter
last_name: Seeburg
- first_name: Hannah
full_name: Monyer, Hannah
last_name: Monyer
citation:
ama: Jonas PM, Racca C, Sakmann B, Seeburg P, Monyer H. Differences in Ca(2+) permeability
of AMPA-type glutamate receptor channels in neocortical neurons caused by differential
GluR-B subunit expression. Neuron. 1994;12(6):1281-1289. doi:10.1016/0896-6273(94)90444-8
apa: Jonas, P. M., Racca, C., Sakmann, B., Seeburg, P., & Monyer, H. (1994).
Differences in Ca(2+) permeability of AMPA-type glutamate receptor channels in
neocortical neurons caused by differential GluR-B subunit expression. Neuron.
Elsevier. https://doi.org/10.1016/0896-6273(94)90444-8
chicago: Jonas, Peter M, Claudia Racca, Bert Sakmann, Peter Seeburg, and Hannah
Monyer. “Differences in Ca(2+) Permeability of AMPA-Type Glutamate Receptor Channels
in Neocortical Neurons Caused by Differential GluR-B Subunit Expression.” Neuron.
Elsevier, 1994. https://doi.org/10.1016/0896-6273(94)90444-8.
ieee: P. M. Jonas, C. Racca, B. Sakmann, P. Seeburg, and H. Monyer, “Differences
in Ca(2+) permeability of AMPA-type glutamate receptor channels in neocortical
neurons caused by differential GluR-B subunit expression,” Neuron, vol.
12, no. 6. Elsevier, pp. 1281–1289, 1994.
ista: Jonas PM, Racca C, Sakmann B, Seeburg P, Monyer H. 1994. Differences in Ca(2+)
permeability of AMPA-type glutamate receptor channels in neocortical neurons caused
by differential GluR-B subunit expression. Neuron. 12(6), 1281–1289.
mla: Jonas, Peter M., et al. “Differences in Ca(2+) Permeability of AMPA-Type Glutamate
Receptor Channels in Neocortical Neurons Caused by Differential GluR-B Subunit
Expression.” Neuron, vol. 12, no. 6, Elsevier, 1994, pp. 1281–89, doi:10.1016/0896-6273(94)90444-8.
short: P.M. Jonas, C. Racca, B. Sakmann, P. Seeburg, H. Monyer, Neuron 12 (1994)
1281–1289.
date_created: 2018-12-11T12:03:32Z
date_published: 1994-06-01T00:00:00Z
date_updated: 2022-06-03T09:29:36Z
day: '01'
doi: 10.1016/0896-6273(94)90444-8
extern: '1'
external_id:
pmid:
- '8011338 '
intvolume: ' 12'
issue: '6'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0896627394904448?via%3Dihub
month: '06'
oa_version: None
page: 1281 - 1289
pmid: 1
publication: Neuron
publication_identifier:
issn:
- 0896-6273
publication_status: published
publisher: Elsevier
publist_id: '2910'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Differences in Ca(2+) permeability of AMPA-type glutamate receptor channels
in neocortical neurons caused by differential GluR-B subunit expression
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 12
year: '1994'
...
---
_id: '3550'
acknowledgement: This work is partially supported by the National Science Foundation,
under grant ASC-9200301 and the Alan T. Waterman award, grant CCR-9118874
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 'Edelsbrunner H. Modeling with simplicial complexes (topology, geometry and
algorithms). In: Proceedings of the 6th Canadian Conference on Computational
Geometry. ; 1994:36-44.'
apa: Edelsbrunner, H. (1994). Modeling with simplicial complexes (topology, geometry
and algorithms). In Proceedings of the 6th Canadian Conference on Computational
Geometry (pp. 36–44). Saskatoon, Canada.
chicago: Edelsbrunner, Herbert. “Modeling with Simplicial Complexes (Topology, Geometry
and Algorithms).” In Proceedings of the 6th Canadian Conference on Computational
Geometry, 36–44, 1994.
ieee: H. Edelsbrunner, “Modeling with simplicial complexes (topology, geometry and
algorithms),” in Proceedings of the 6th Canadian Conference on Computational
Geometry, Saskatoon, Canada, 1994, pp. 36–44.
ista: 'Edelsbrunner H. 1994. Modeling with simplicial complexes (topology, geometry
and algorithms). Proceedings of the 6th Canadian Conference on Computational Geometry.
CCCG: Canadian Conference on Computational Geometry, 36–44.'
mla: Edelsbrunner, Herbert. “Modeling with Simplicial Complexes (Topology, Geometry
and Algorithms).” Proceedings of the 6th Canadian Conference on Computational
Geometry, 1994, pp. 36–44.
short: H. Edelsbrunner, in:, Proceedings of the 6th Canadian Conference on Computational
Geometry, 1994, pp. 36–44.
conference:
location: Saskatoon, Canada
name: 'CCCG: Canadian Conference on Computational Geometry'
date_created: 2018-12-11T12:03:55Z
date_published: 1994-08-01T00:00:00Z
date_updated: 2022-06-03T08:50:45Z
day: '01'
extern: '1'
language:
- iso: eng
month: '08'
oa_version: None
page: 36 - 44
publication: Proceedings of the 6th Canadian Conference on Computational Geometry
publication_status: published
publist_id: '2835'
quality_controlled: '1'
status: public
title: Modeling with simplicial complexes (topology, geometry and algorithms)
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1994'
...
---
_id: '3641'
abstract:
- lang: eng
text: The probability of fixation of a mutation with selective advantage s will
be reduced by substitutions at other loci. The effect of a single substitution,
with selective advantage S0016672300032857inline1, can be approximated as a sudden
reduction in the frequency of the favourable allele, by a fraction w = 1 −(s/S)r/s
(where r is the recombination rate). An expression for the effect of a given sequence
of such catastrophes is derived. This also applies to the ecological prxoblem
of finding the probability that a small population will survive, despite occasional
disasters. It is shown that if substitutions occur at a rate Δ, and are scattered
randomly over a genetic map of length R, then an allele is unlikely to be fixed
if its advantage is less than a critical value, Scrit = (π2/6)(2ΔS/(Rlog(S/s))).
This threshold depends primarily on the variance in fitness per unit map length
dueto substitutions, var(W)/R = 2ΔS/R. With no recombination, the fixation probability
can be calculated for a finite population. If Δ > s, it is of the same order
as for a neutral allele ( ≈ Δ/(2N(Δ−s))), whilst if S0016672300032857inline2,
fixation probability is much higher than for a neutral allele, but much lower
than in the absence of hitch-hiking S0016672300032857inline3. These results suggest
that hitch-hiking may substantially impede the accumulation of weakly favoured
adaptations.
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: Barton NH. The reduction in fixation probability caused by substitutions at
linked loci. Genetical Research. 1994;64(3):199-208. doi:10.1017/S0016672300032857
apa: Barton, N. H. (1994). The reduction in fixation probability caused by substitutions
at linked loci. Genetical Research. Cambridge University Press. https://doi.org/10.1017/S0016672300032857
chicago: Barton, Nicholas H. “The Reduction in Fixation Probability Caused by Substitutions
at Linked Loci.” Genetical Research. Cambridge University Press, 1994.
https://doi.org/10.1017/S0016672300032857
.
ieee: N. H. Barton, “The reduction in fixation probability caused by substitutions
at linked loci,” Genetical Research, vol. 64, no. 3. Cambridge University
Press, pp. 199–208, 1994.
ista: Barton NH. 1994. The reduction in fixation probability caused by substitutions
at linked loci. Genetical Research. 64(3), 199–208.
mla: Barton, Nicholas H. “The Reduction in Fixation Probability Caused by Substitutions
at Linked Loci.” Genetical Research, vol. 64, no. 3, Cambridge University
Press, 1994, pp. 199–208, doi:10.1017/S0016672300032857 .
short: N.H. Barton, Genetical Research 64 (1994) 199–208.
date_created: 2018-12-11T12:04:23Z
date_published: 1994-12-01T00:00:00Z
date_updated: 2022-06-03T08:34:32Z
day: '01'
doi: '10.1017/S0016672300032857 '
extern: '1'
intvolume: ' 64'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://www.cambridge.org/core/journals/genetics-research/article/reduction-in-fixation-probability-caused-by-substitutions-at-linked-loci/458BBF3E7FE92E4EA6AFB2B000A98945
month: '12'
oa_version: None
page: 199 - 208
publication: Genetical Research
publication_identifier:
issn:
- 0016-6723
publication_status: published
publisher: Cambridge University Press
publist_id: '2742'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The reduction in fixation probability caused by substitutions at linked loci
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 64
year: '1994'
...
---
_id: '3642'
abstract:
- lang: eng
text: We develop a general population genetic framework for analyzing selection
on many loci, and apply it to strong truncation and disruptive selection on an
additive polygenic trait. We first present statistical methods for analyzing the
infinitesimal model, in which offspring breeding values are normally distributed
around the mean of the parents, with fixed variance. These show that the usual
assumption of a Gaussian distribution of breeding values in the population gives
remarkably accurate predictions for the mean and the variance, even when disruptive
selection generates substantial deviations from normality. We then set out a general
genetic analysis of selection and recombination. The population is represented
by multilocus cumulants describing the distribution of haploid genotypes, and
selection is described by the relation between mean fitness and these cumulants.
We provide exact recursions in terms of generating functions for the effects of
selection on non-central moments. The effects of recombination are simply calculated
as a weighted sum over all the permutations produced by meiosis. Finally, the
new cumulants that describe the next generation are computed from the non-central
moments. Although this scheme is applied here in detail only to selection on an
additive trait, it is quite general. For arbitrary epistasis and linkage, we describe
a consistent infinitesimal limit in which the short-term selection response is
dominated by infinitesimal allele frequency changes and linkage disequilibria.
Numerical multilocus results show that the standard Gaussian approximation gives
accurate predictions for the dynamics of the mean and genetic variance in this
limit. Even with intense truncation selection, linkage disequilibria of order
three and higher never cause much deviation from normality. Thus, the empirical
deviations frequently found between predicted and observed responses to artificial
selection are not caused by linkage-disequilibrium-induced departures from normality.
Disruptive selection can generate substantial four-way disequilibria, and hence
kurtosis; but even then, the Gaussian assumption predicts the variance accurately.
In contrast to the apparent simplicity of the infinitesimal limit, data suggest
that changes in genetic variance after 10 or more generations of selection are
likely to be dominated by allele frequency dynamics that depend on genetic details.
article_processing_charge: No
article_type: original
author:
- first_name: Michael
full_name: Turelli, Michael
last_name: Turelli
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
citation:
ama: 'Turelli M, Barton NH. Genetic and statistical analyses of strong selection
on polygenic traits: What, me normal? Genetics. 1994;138(3):913-941. doi:10.1093/genetics/138.3.913'
apa: 'Turelli, M., & Barton, N. H. (1994). Genetic and statistical analyses
of strong selection on polygenic traits: What, me normal? Genetics. Genetics
Society of America. https://doi.org/10.1093/genetics/138.3.913'
chicago: 'Turelli, Michael, and Nicholas H Barton. “Genetic and Statistical Analyses
of Strong Selection on Polygenic Traits: What, Me Normal?” Genetics. Genetics
Society of America, 1994. https://doi.org/10.1093/genetics/138.3.913.'
ieee: 'M. Turelli and N. H. Barton, “Genetic and statistical analyses of strong
selection on polygenic traits: What, me normal?,” Genetics, vol. 138, no.
3. Genetics Society of America, pp. 913–941, 1994.'
ista: 'Turelli M, Barton NH. 1994. Genetic and statistical analyses of strong selection
on polygenic traits: What, me normal? Genetics. 138(3), 913–941.'
mla: 'Turelli, Michael, and Nicholas H. Barton. “Genetic and Statistical Analyses
of Strong Selection on Polygenic Traits: What, Me Normal?” Genetics, vol.
138, no. 3, Genetics Society of America, 1994, pp. 913–41, doi:10.1093/genetics/138.3.913.'
short: M. Turelli, N.H. Barton, Genetics 138 (1994) 913–941.
date_created: 2018-12-11T12:04:24Z
date_published: 1994-11-01T00:00:00Z
date_updated: 2022-06-03T08:18:54Z
day: '01'
doi: 10.1093/genetics/138.3.913
extern: '1'
external_id:
pmid:
- '7851785'
intvolume: ' 138'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://pubmed.ncbi.nlm.nih.gov/7851785/
month: '11'
oa: 1
oa_version: Published Version
page: 913 - 941
pmid: 1
publication: Genetics
publication_identifier:
issn:
- 0016-6731
publication_status: published
publisher: Genetics Society of America
publist_id: '2741'
quality_controlled: '1'
status: public
title: 'Genetic and statistical analyses of strong selection on polygenic traits:
What, me normal?'
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 138
year: '1994'
...
---
_id: '4032'
abstract:
- lang: eng
text: Every collection of t≥2 n2 triangles with a total of n vertices in ℝ3 has
Ω(t4/n6) crossing pairs. This implies that one of their edges meets Ω(t3/n6) of
the triangles. From this it follows that n points in ℝ3 have only O(n8/3) halving
planes.
acknowledgement: The research of H. Edelsbrunner was supported by the National Science
Foundation under Grant CCR-8921421 and under an Alan T. Waterman award, Grant CCR-9118874.
Any opinions, findings and conclusions or recommendations expressed in this publication
are those of the authors and do not necessarily reflect the view of the National
Science Foundation.
article_processing_charge: No
article_type: original
author:
- first_name: Tamal
full_name: Dey, Tamal
last_name: Dey
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Dey T, Edelsbrunner H. Counting triangle crossings and halving planes. Discrete
& Computational Geometry. 1994;12(1):281-289. doi:10.1007/BF02574381
apa: Dey, T., & Edelsbrunner, H. (1994). Counting triangle crossings and halving
planes. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02574381
chicago: Dey, Tamal, and Herbert Edelsbrunner. “Counting Triangle Crossings and
Halving Planes.” Discrete & Computational Geometry. Springer, 1994.
https://doi.org/10.1007/BF02574381.
ieee: T. Dey and H. Edelsbrunner, “Counting triangle crossings and halving planes,”
Discrete & Computational Geometry, vol. 12, no. 1. Springer, pp. 281–289,
1994.
ista: Dey T, Edelsbrunner H. 1994. Counting triangle crossings and halving planes.
Discrete & Computational Geometry. 12(1), 281–289.
mla: Dey, Tamal, and Herbert Edelsbrunner. “Counting Triangle Crossings and Halving
Planes.” Discrete & Computational Geometry, vol. 12, no. 1, Springer,
1994, pp. 281–89, doi:10.1007/BF02574381.
short: T. Dey, H. Edelsbrunner, Discrete & Computational Geometry 12 (1994)
281–289.
date_created: 2018-12-11T12:06:33Z
date_published: 1994-09-01T00:00:00Z
date_updated: 2022-06-02T12:53:01Z
day: '01'
doi: 10.1007/BF02574381
extern: '1'
intvolume: ' 12'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02574381
month: '09'
oa_version: None
page: 281 - 289
publication: Discrete & Computational Geometry
publication_identifier:
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2091'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting triangle crossings and halving planes
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 12
year: '1994'
...
---
_id: '4033'
abstract:
- lang: eng
text: 'A collection of geometric selection lemmas is proved, such as the following:
For any set P of n points in three-dimensional space and any set S of m spheres,
where each sphere passes through a distinct point pair in P. there exists a point
x, not necessarily in P, that is enclosed by Ω(m2/(n2 log6 n2/m)) of the spheres
in S. Similar results apply in arbitrary fixed dimensions, and for geometric bodies
other than spheres. The results have applications in reducing the size of geometric
structures, such as three-dimensional Delaunay triangulations and Gabriel graphs,
by adding extra points to their defining sets.'
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: John
full_name: Hershberger, John
last_name: Hershberger
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Selecting
heavily covered points. SIAM Journal on Computing. 1994;23(6):1138-1151.
doi:10.1137/S0097539790179919
apa: Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., &
Sharir, M. (1994). Selecting heavily covered points. SIAM Journal on Computing.
SIAM. https://doi.org/10.1137/S0097539790179919
chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger,
Raimund Seidel, and Micha Sharir. “Selecting Heavily Covered Points.” SIAM
Journal on Computing. SIAM, 1994. https://doi.org/10.1137/S0097539790179919 .
ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M.
Sharir, “Selecting heavily covered points,” SIAM Journal on Computing,
vol. 23, no. 6. SIAM, pp. 1138–1151, 1994.
ista: Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. 1994.
Selecting heavily covered points. SIAM Journal on Computing. 23(6), 1138–1151.
mla: Chazelle, Bernard, et al. “Selecting Heavily Covered Points.” SIAM Journal
on Computing, vol. 23, no. 6, SIAM, 1994, pp. 1138–51, doi:10.1137/S0097539790179919 .
short: B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir,
SIAM Journal on Computing 23 (1994) 1138–1151.
date_created: 2018-12-11T12:06:33Z
date_published: 1994-12-01T00:00:00Z
date_updated: 2022-06-03T06:41:56Z
day: '01'
doi: '10.1137/S0097539790179919 '
extern: '1'
intvolume: ' 23'
issue: '6'
language:
- iso: eng
main_file_link:
- url: https://epubs.siam.org/doi/10.1137/S0097539790179919
month: '12'
oa_version: None
page: 1138 - 1151
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
publication_status: published
publisher: SIAM
publist_id: '2092'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Selecting heavily covered points
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 23
year: '1994'
...
---
_id: '4037'
abstract:
- lang: eng
text: Frequently, data in scientific computing is in its abstract form a finite
point set in space, and it is sometimes useful or required to compute what one
might call the `'shape” of the set. For that purpose, this article introduces
the formal notion of the family of alpha-shapes of a finite point set in R3. Each
shape is a well-defined polytope, derived from the Delaunay triangulation of the
point set, with a parameter alpha is-an-element-of R controlling the desired level
of detail. An algorithm is presented that constructs the entire family of shapes
for a given set of size n in time O(n2), worst case. A robust implementation of
the algorithm is discussed, and several applications in the area of scientific
computing are mentioned.
acknowledgement: National Science Foundation under grant CCR-8921421 and Alan T.
Waterman award, grant CCR-9118874.
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Ernst
full_name: Mücke, Ernst
last_name: Mücke
citation:
ama: Edelsbrunner H, Mücke E. Three-dimensional alpha shapes. ACM Transactions
on Graphics. 1994;13(1):43-72. doi:10.1145/174462.156635
apa: Edelsbrunner, H., & Mücke, E. (1994). Three-dimensional alpha shapes. ACM
Transactions on Graphics. ACM. https://doi.org/10.1145/174462.156635
chicago: Edelsbrunner, Herbert, and Ernst Mücke. “Three-Dimensional Alpha Shapes.”
ACM Transactions on Graphics. ACM, 1994. https://doi.org/10.1145/174462.156635.
ieee: H. Edelsbrunner and E. Mücke, “Three-dimensional alpha shapes,” ACM Transactions
on Graphics, vol. 13, no. 1. ACM, pp. 43–72, 1994.
ista: Edelsbrunner H, Mücke E. 1994. Three-dimensional alpha shapes. ACM Transactions
on Graphics. 13(1), 43–72.
mla: Edelsbrunner, Herbert, and Ernst Mücke. “Three-Dimensional Alpha Shapes.” ACM
Transactions on Graphics, vol. 13, no. 1, ACM, 1994, pp. 43–72, doi:10.1145/174462.156635.
short: H. Edelsbrunner, E. Mücke, ACM Transactions on Graphics 13 (1994) 43–72.
date_created: 2018-12-11T12:06:34Z
date_published: 1994-01-01T00:00:00Z
date_updated: 2022-06-02T12:00:42Z
day: '01'
doi: 10.1145/174462.156635
extern: '1'
intvolume: ' 13'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://dl.acm.org/doi/10.1145/174462.156635
month: '01'
oa: 1
oa_version: None
page: 43 - 72
publication: ACM Transactions on Graphics
publication_status: published
publisher: ACM
publist_id: '2088'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Three-dimensional alpha shapes
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 13
year: '1994'
...
---
_id: '4038'
abstract:
- lang: eng
text: We consider a variety of problems on the interaction between two sets of line
segments in two and three dimensions. These problems range from counting the number
of intersecting pairs between m blue segments and n red segments in the plane
(assuming that two line segments are disjoint if they have the same color) to
finding the smallest vertical distance between two nonintersecting polyhedral
terrains in three-dimensional space. We solve these problems efficiently by using
a variant of the segment tree. For the three-dimensional problems we also apply
a variety of recent combinatorial and algorithmic techniques involving arrangements
of lines in three-dimensional space, as developed in a companion paper.
acknowledgement: Supported in part by the National Science Foundation under Grant
CCR-8714565.
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
citation:
ama: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Algorithms for bichromatic
line-segment problems and polyhedral terrains. Algorithmica. 1994;11(2):116-132.
doi:10.1007/BF01182771
apa: Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1994). Algorithms
for bichromatic line-segment problems and polyhedral terrains. Algorithmica.
Springer. https://doi.org/10.1007/BF01182771
chicago: Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
“Algorithms for Bichromatic Line-Segment Problems and Polyhedral Terrains.” Algorithmica.
Springer, 1994. https://doi.org/10.1007/BF01182771.
ieee: B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Algorithms for bichromatic
line-segment problems and polyhedral terrains,” Algorithmica, vol. 11,
no. 2. Springer, pp. 116–132, 1994.
ista: Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1994. Algorithms for bichromatic
line-segment problems and polyhedral terrains. Algorithmica. 11(2), 116–132.
mla: Chazelle, Bernard, et al. “Algorithms for Bichromatic Line-Segment Problems
and Polyhedral Terrains.” Algorithmica, vol. 11, no. 2, Springer, 1994,
pp. 116–32, doi:10.1007/BF01182771.
short: B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Algorithmica 11 (1994)
116–132.
date_created: 2018-12-11T12:06:34Z
date_published: 1994-02-01T00:00:00Z
date_updated: 2022-06-02T12:25:29Z
day: '01'
doi: 10.1007/BF01182771
extern: '1'
intvolume: ' 11'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01182771
month: '02'
oa_version: None
page: 116 - 132
publication: Algorithmica
publication_identifier:
issn:
- 0178-4617
publication_status: published
publisher: Springer
publist_id: '2089'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithms for bichromatic line-segment problems and polyhedral terrains
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 11
year: '1994'
...
---
_id: '4039'
abstract:
- lang: eng
text: Let P be a simple polygon with n vertices. We present a simple decomposition
scheme that partitions the interior of P into O(n) so-called geodesic triangles,
so that any line segment interior to P crosses at most 2 log n of these triangles.
This decomposition can be used to preprocess P in a very simple manner, so that
any ray-shooting query can be answered in time O(log n). The data structure requires
O(n) storage and O(n log n) preprocessing time. By using more sophisticated techniques,
we can reduce the preprocessing time to O(n). We also extend our general technique
to the case of ray shooting amidst k polygonal obstacles with a total of n edges,
so that a query can be answered in O(√ log n) time.
acknowledgement: Work by Bernard Chazelle has been supported by NSF Grant CCR-87-00917.
Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work
by Micha Sharir has been supported by ONR Grants N00014-89-J-3042 and N00014-90-J-1284,
by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science
Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences,
and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.
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: Michelangelo
full_name: Grigni, Michelangelo
last_name: Grigni
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: John
full_name: Hershberger, John
last_name: Hershberger
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
- first_name: Jack
full_name: Snoeyink, Jack
last_name: Snoeyink
citation:
ama: Chazelle B, Edelsbrunner H, Grigni M, et al. Ray shooting in polygons using
geodesic triangulations. Algorithmica. 1994;12(1):54-68. doi:10.1007/BF01377183
apa: Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Hershberger, J., Sharir,
M., & Snoeyink, J. (1994). Ray shooting in polygons using geodesic triangulations.
Algorithmica. Springer. https://doi.org/10.1007/BF01377183
chicago: Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas
Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink. “Ray Shooting in Polygons
Using Geodesic Triangulations.” Algorithmica. Springer, 1994. https://doi.org/10.1007/BF01377183.
ieee: B. Chazelle et al., “Ray shooting in polygons using geodesic triangulations,”
Algorithmica, vol. 12, no. 1. Springer, pp. 54–68, 1994.
ista: Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Hershberger J, Sharir M, Snoeyink
J. 1994. Ray shooting in polygons using geodesic triangulations. Algorithmica.
12(1), 54–68.
mla: Chazelle, Bernard, et al. “Ray Shooting in Polygons Using Geodesic Triangulations.”
Algorithmica, vol. 12, no. 1, Springer, 1994, pp. 54–68, doi:10.1007/BF01377183.
short: B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir,
J. Snoeyink, Algorithmica 12 (1994) 54–68.
date_created: 2018-12-11T12:06:35Z
date_published: 1994-07-01T00:00:00Z
date_updated: 2022-06-02T12:41:07Z
day: '01'
doi: 10.1007/BF01377183
extern: '1'
intvolume: ' 12'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01377183
month: '07'
oa_version: None
page: 54 - 68
publication: Algorithmica
publication_identifier:
issn:
- 0178-4617
publication_status: published
publisher: Springer
publist_id: '2090'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ray shooting in polygons using geodesic triangulations
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 12
year: '1994'
...
---
_id: '4179'
abstract:
- lang: eng
text: Neurotrophin-3 (NT-3) is a member of the neurotrophin gene family and is highly
expressed in the developing rat cerebellum. Here we show that brain-derived neurotrophic
factor (BDNF) increased by approximately 10-fold the NT-3 mRNA levels in cultured
cerebellar granule neurons isolated from postnatal rats, whereas nerve growth
factor (NGF) and NT-3 itself had no effect. The effect of BDNF was additive to
that of triiodothyronine (T3), which also increased NT-3 mRNA in these neurons.
The drug K252a inhibited the BDNF-mediated stimulation of NT-3 expression, suggesting
an involvement of trkB receptors. Nuclear run-on experiments showed that BDNF
enhanced NT-3 transcription, whereas the stability of NT-3 mRNA remained unchanged.
The data presented are the first demonstration that one neurotrophin regulates
the expression of another and provide evidence that NT-3 production in granule
neurons is regulated by both BDNF and T3.
acknowledgement: We thank Dorothea Stratmann and Karin Angermayer for skillful technical
assistance.
article_processing_charge: No
article_type: original
author:
- first_name: Axel
full_name: Leingärtner, Axel
last_name: Leingärtner
- 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: Roland
full_name: Kolbeck, Roland
last_name: Kolbeck
- first_name: Hans
full_name: Thoenen, Hans
last_name: Thoenen
- first_name: Dan
full_name: Lindholm, Dan
last_name: Lindholm
citation:
ama: Leingärtner A, Heisenberg C-PJ, Kolbeck R, Thoenen H, Lindholm D. Brain-derived
neurotrophic factor increases neurotrophin-3 expression in cerebellar granule
neurons. Journal of Biological Chemistry. 1994;269(2):828-830. doi:10.1016/s0021-9258(17)42186-7
apa: Leingärtner, A., Heisenberg, C.-P. J., Kolbeck, R., Thoenen, H., & Lindholm,
D. (1994). Brain-derived neurotrophic factor increases neurotrophin-3 expression
in cerebellar granule neurons. Journal of Biological Chemistry. American
Society for Biochemistry and Molecular Biology. https://doi.org/10.1016/s0021-9258(17)42186-7
chicago: Leingärtner, Axel, Carl-Philipp J Heisenberg, Roland Kolbeck, Hans Thoenen,
and Dan Lindholm. “Brain-Derived Neurotrophic Factor Increases Neurotrophin-3
Expression in Cerebellar Granule Neurons.” Journal of Biological Chemistry.
American Society for Biochemistry and Molecular Biology, 1994. https://doi.org/10.1016/s0021-9258(17)42186-7.
ieee: A. Leingärtner, C.-P. J. Heisenberg, R. Kolbeck, H. Thoenen, and D. Lindholm,
“Brain-derived neurotrophic factor increases neurotrophin-3 expression in cerebellar
granule neurons,” Journal of Biological Chemistry, vol. 269, no. 2. American
Society for Biochemistry and Molecular Biology, pp. 828–830, 1994.
ista: Leingärtner A, Heisenberg C-PJ, Kolbeck R, Thoenen H, Lindholm D. 1994. Brain-derived
neurotrophic factor increases neurotrophin-3 expression in cerebellar granule
neurons. Journal of Biological Chemistry. 269(2), 828–830.
mla: Leingärtner, Axel, et al. “Brain-Derived Neurotrophic Factor Increases Neurotrophin-3
Expression in Cerebellar Granule Neurons.” Journal of Biological Chemistry,
vol. 269, no. 2, American Society for Biochemistry and Molecular Biology, 1994,
pp. 828–30, doi:10.1016/s0021-9258(17)42186-7.
short: A. Leingärtner, C.-P.J. Heisenberg, R. Kolbeck, H. Thoenen, D. Lindholm,
Journal of Biological Chemistry 269 (1994) 828–830.
date_created: 2018-12-11T12:07:25Z
date_published: 1994-01-14T00:00:00Z
date_updated: 2022-06-02T10:23:48Z
day: '14'
doi: 10.1016/s0021-9258(17)42186-7
extern: '1'
intvolume: ' 269'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/S0021925817421867?via%3Dihub
month: '01'
oa: 1
oa_version: None
page: 828 - 830
publication: Journal of Biological Chemistry
publication_identifier:
eissn:
- 1083-351X
issn:
- 0021-9258
publication_status: published
publisher: American Society for Biochemistry and Molecular Biology
publist_id: '1941'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Brain-derived neurotrophic factor increases neurotrophin-3 expression in cerebellar
granule neurons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 269
year: '1994'
...
---
_id: '4202'
abstract:
- lang: eng
text: NERVE growth factor (NGF) injected into the otherwise unlesioned adult rat
septum induced sprouting of presumptive cholinergic fibres positive for p75(NGFR)
and acetylcholinesterase (AChE). These fibres did not stain for tyrosine hydroxylase
and therefore did not represent sympathetic ingrowth. Neurofilament staining on
adjacent sections revealed fibres with similar morphology, suggesting new outgrowth
in the form of sprouting rather than the upregulation of p75(NGFR) and AChE in
pre-existing fibres. Simultaneous injections of subneurotoxic doses of N-methyl-D-aspartate
(NMDA) significantly potentiated the effect of NGF on cholinergic fibre sprouting
and caused pronounced glial fibrillary acidic protein (GFAP)positive astrocytosis.
Application of NMDA alone did not elicit sprouting of this type. These findings
indicate that NGF can induce the sprouting of uninjured adult rat septal cholinergic
fibres in vivo and suggest that reactive astrocytes are not inhibitory to cholinergic
axonal outgrowth, and might serve as a substrate for growing axons in the presence
of NGF.
article_processing_charge: No
article_type: original
author:
- first_name: Carl-Philipp J
full_name: Heisenberg, Carl-Philipp J
id: 39427864-F248-11E8-B48F-1D18A9856A87
last_name: Heisenberg
orcid: 0000-0002-0912-4566
- first_name: John
full_name: Cooper, John
last_name: Cooper
- first_name: J
full_name: Berke, J
last_name: Berke
- first_name: Michael
full_name: Sofroniew, Michael
last_name: Sofroniew
citation:
ama: Heisenberg C-PJ, Cooper J, Berke J, Sofroniew M. NMDA potentiates NGF-induced
sprouting of septal cholinergic fibres. Neuroreport. 1994;5(4):413-416.
doi:10.1097/00001756-199401120-00010
apa: Heisenberg, C.-P. J., Cooper, J., Berke, J., & Sofroniew, M. (1994). NMDA
potentiates NGF-induced sprouting of septal cholinergic fibres. Neuroreport.
Lippincott, Williams & Wilkins. https://doi.org/10.1097/00001756-199401120-00010
chicago: Heisenberg, Carl-Philipp J, John Cooper, J Berke, and Michael Sofroniew.
“NMDA Potentiates NGF-Induced Sprouting of Septal Cholinergic Fibres.” Neuroreport.
Lippincott, Williams & Wilkins, 1994. https://doi.org/10.1097/00001756-199401120-00010 .
ieee: C.-P. J. Heisenberg, J. Cooper, J. Berke, and M. Sofroniew, “NMDA potentiates
NGF-induced sprouting of septal cholinergic fibres,” Neuroreport, vol.
5, no. 4. Lippincott, Williams & Wilkins, pp. 413–416, 1994.
ista: Heisenberg C-PJ, Cooper J, Berke J, Sofroniew M. 1994. NMDA potentiates NGF-induced
sprouting of septal cholinergic fibres. Neuroreport. 5(4), 413–416.
mla: Heisenberg, Carl-Philipp J., et al. “NMDA Potentiates NGF-Induced Sprouting
of Septal Cholinergic Fibres.” Neuroreport, vol. 5, no. 4, Lippincott,
Williams & Wilkins, 1994, pp. 413–16, doi:10.1097/00001756-199401120-00010 .
short: C.-P.J. Heisenberg, J. Cooper, J. Berke, M. Sofroniew, Neuroreport 5 (1994)
413–416.
date_created: 2018-12-11T12:07:33Z
date_published: 1994-01-12T00:00:00Z
date_updated: 2022-06-02T10:07:25Z
day: '12'
doi: '10.1097/00001756-199401120-00010 '
extern: '1'
intvolume: ' 5'
issue: '4'
language:
- iso: eng
main_file_link:
- url: https://journals.lww.com/neuroreport/Abstract/1994/01120/NMDA_potentiates_NGF_induced_sprouting_of_septal.10.aspx
month: '01'
oa_version: None
page: 413 - 416
publication: Neuroreport
publication_identifier:
issn:
- 0959-4965
publication_status: published
publisher: Lippincott, Williams & Wilkins
publist_id: '1915'
quality_controlled: '1'
scopus_import: '1'
status: public
title: NMDA potentiates NGF-induced sprouting of septal cholinergic fibres
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1994'
...
---
_id: '4420'
abstract:
- lang: eng
text: We propose a methodology for the specification, verification, and design of
hybrid systems. The methodology consists of the computational model of Concrete
Phase Transition Systems (cptss), the specification language of Hybrid Temporal
Logic (htl), the graphical system description language of Hybrid Automata, and
a proof system for verifying that hybrid automata satisfy their HTL specifications.
The novelty of the approach lies in the continuous-time logic, which allows specification
of both point-based and interval-based properties (i.e., properties which describe
changes over an interval) and provides direct references to derivatives of variables,
and in the proof system that supports verification of point-based and interval-based
properties. The proof rules demonstrate that sound and convenient induction rules
can be established for continuous-time logics. The proof rules are illustrated
on several examples.
acknowledgement: Supported in part by the National Science Foundation under grants
CCR-92-23226 and CCR-9200794, by the Defense Advanced Research Projects Agency under
grants NAG2-703 and NAG2-892, by the United States Air Force Office of Scientific
Research under contracts F49620-93-1-0139 and F49620-93-1-0056, and by the European
Community ESPRIT Basic Research Action Project 6021 (REACT). Supported in part by
a National Science Foundation Graduate Research Fellowship.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Arjun
full_name: Kapur, Arjun
last_name: Kapur
- 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: Zohar
full_name: Manna, Zohar
last_name: Manna
- first_name: Amir
full_name: Pnueli, Amir
last_name: Pnueli
citation:
ama: 'Kapur A, Henzinger TA, Manna Z, Pnueli A. Proving safety properties of hybrid
systems. In: 3rd International Symposium on Formal Techniques in Real-Time
and Fault-Tolerant Systems. Vol 863. Springer; 1994:431-454. doi:10.1007/3-540-58468-4_177'
apa: 'Kapur, A., Henzinger, T. A., Manna, Z., & Pnueli, A. (1994). Proving safety
properties of hybrid systems. In 3rd International Symposium on Formal Techniques
in Real-Time and Fault-Tolerant Systems (Vol. 863, pp. 431–454). Lübeck, Germany:
Springer. https://doi.org/10.1007/3-540-58468-4_177'
chicago: Kapur, Arjun, Thomas A Henzinger, Zohar Manna, and Amir Pnueli. “Proving
Safety Properties of Hybrid Systems.” In 3rd International Symposium on Formal
Techniques in Real-Time and Fault-Tolerant Systems, 863:431–54. Springer,
1994. https://doi.org/10.1007/3-540-58468-4_177.
ieee: A. Kapur, T. A. Henzinger, Z. Manna, and A. Pnueli, “Proving safety properties
of hybrid systems,” in 3rd International Symposium on Formal Techniques in
Real-Time and Fault-Tolerant Systems, Lübeck, Germany, 1994, vol. 863, pp.
431–454.
ista: 'Kapur A, Henzinger TA, Manna Z, Pnueli A. 1994. Proving safety properties
of hybrid systems. 3rd International Symposium on Formal Techniques in Real-Time
and Fault-Tolerant Systems. FTRTFT: Formal Techniques in Real-Time and Fault-Tolerant
Systems, LNCS, vol. 863, 431–454.'
mla: Kapur, Arjun, et al. “Proving Safety Properties of Hybrid Systems.” 3rd
International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems,
vol. 863, Springer, 1994, pp. 431–54, doi:10.1007/3-540-58468-4_177.
short: A. Kapur, T.A. Henzinger, Z. Manna, A. Pnueli, in:, 3rd International Symposium
on Formal Techniques in Real-Time and Fault-Tolerant Systems, Springer, 1994,
pp. 431–454.
conference:
end_date: 1994-09-23
location: Lübeck, Germany
name: 'FTRTFT: Formal Techniques in Real-Time and Fault-Tolerant Systems'
start_date: 1994-09-19
date_created: 2018-12-11T12:08:46Z
date_published: 1994-01-01T00:00:00Z
date_updated: 2022-06-02T09:46:37Z
day: '01'
doi: 10.1007/3-540-58468-4_177
extern: '1'
intvolume: ' 863'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-58468-4_177
month: '01'
oa_version: None
page: 431 - 454
publication: 3rd International Symposium on Formal Techniques in Real-Time and Fault-Tolerant
Systems
publication_status: published
publisher: Springer
publist_id: '309'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Proving safety properties of hybrid systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 863
year: '1994'
...
---
_id: '4440'
abstract:
- lang: eng
text: We present a methodology for proving temporal properties of the divergent
runs of reactive systems with real-valued clocks. A run diverges if time advances
beyond any bound. Since the divergent runs of a system may satisfy liveness properties
that are not satisfied by some convergent runs, the standard proof rules are incomplete
if only divergent runs are considered. First, we develop a sound and complete
proof calculus for divergence, which is based on translating clock systems into
discrete systems. Then, we show that simpler proofs can be obtained for stronger
divergence assumptions, such as unknown -divergence, which requires that all delays
have a minimum duration of some unknown constant . We classify all real-time systems
into an infinite hierarchy, according to how well they admit the translation of
eventuality properties into equivalent safety properties.
acknowledgement: 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, 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: Peter
full_name: Kopke, Peter
last_name: Kopke
citation:
ama: 'Henzinger TA, Kopke P. Verification methods for the divergent runs of clock
systems. In: 3rd International Symposium on Formal Techniques in Real-Time
and Fault-Tolerant Systems. Vol 863. Springer; 1994:351-372. doi:10.1007/3-540-58468-4_173'
apa: 'Henzinger, T. A., & Kopke, P. (1994). Verification methods for the divergent
runs of clock systems. In 3rd International Symposium on Formal Techniques
in Real-Time and Fault-Tolerant Systems (Vol. 863, pp. 351–372). Lübeck, Gernany:
Springer. https://doi.org/10.1007/3-540-58468-4_173'
chicago: Henzinger, Thomas A, and Peter Kopke. “Verification Methods for the Divergent
Runs of Clock Systems.” In 3rd International Symposium on Formal Techniques
in Real-Time and Fault-Tolerant Systems, 863:351–72. Springer, 1994. https://doi.org/10.1007/3-540-58468-4_173.
ieee: T. A. Henzinger and P. Kopke, “Verification methods for the divergent runs
of clock systems,” in 3rd International Symposium on Formal Techniques in Real-Time
and Fault-Tolerant Systems, Lübeck, Gernany, 1994, vol. 863, pp. 351–372.
ista: 'Henzinger TA, Kopke P. 1994. Verification methods for the divergent runs
of clock systems. 3rd International Symposium on Formal Techniques in Real-Time
and Fault-Tolerant Systems. FTRTFT: Formal Techniques in Real-Time and Fault-Tolerant
Systems, LNCS, vol. 863, 351–372.'
mla: Henzinger, Thomas A., and Peter Kopke. “Verification Methods for the Divergent
Runs of Clock Systems.” 3rd International Symposium on Formal Techniques in
Real-Time and Fault-Tolerant Systems, vol. 863, Springer, 1994, pp. 351–72,
doi:10.1007/3-540-58468-4_173.
short: T.A. Henzinger, P. Kopke, in:, 3rd International Symposium on Formal Techniques
in Real-Time and Fault-Tolerant Systems, Springer, 1994, pp. 351–372.
conference:
end_date: 1994-09-23
location: Lübeck, Gernany
name: 'FTRTFT: Formal Techniques in Real-Time and Fault-Tolerant Systems'
start_date: 1994-09-19
date_created: 2018-12-11T12:08:52Z
date_published: 1994-01-01T00:00:00Z
date_updated: 2022-06-02T09:35:58Z
day: '01'
doi: 10.1007/3-540-58468-4_173
extern: '1'
intvolume: ' 863'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-58468-4_173
month: '01'
oa_version: None
page: 351 - 372
publication: 3rd International Symposium on Formal Techniques in Real-Time and Fault-Tolerant
Systems
publication_status: published
publisher: Springer
publist_id: '287'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Verification methods for the divergent runs of clock systems
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 863
year: '1994'
...
---
_id: '4501'
abstract:
- lang: eng
text: 'We extend the specification language of temporal logic, the corresponding
verification framework, and the underlying computational model to deal with real-;time
properties of reactive systems. The abstract notion of timed transition systems
generalizes traditional transition systems conservatively: qualitative fairness
requirements are replaced (and superseded) by quantitative lower-bound and upper-bound
timing constraints on transitions. This framework can model real-time systems
that communicate either through shared variables or by message passing and real-time
issues such as timeouts, process priorities (interrupts), and process scheduling.
We exhibit two styles for the specification of real-time systems. While the first
approach uses time-bounded versions of the temporal operators, the second approach
allows explicit references to time through a special clock variable. Corresponding
to the two styles of specification, we present and compare two different proof
methodologies for the verification of timing requirements that are expressed in
these styles. For the bounded-operator style, we provide a set of proof rules
for establishing bounded-invariance and bounded-responce properties of timed transition
systems. This approach generalizes the standard temporal proof rules for verifying
invariance and response properties conservatively. For the explicit-clock style,
we exploit the observation that every time-bounded property is a safety property
and use the standard temporal proof rules for establishing safety properties.'
acknowledgement: 'This research was supported in part by an IBM graduate fellowship,
by the National Science Foundation under Grants CCR-9223226 and CCR-9200794. by
the Defense Advanced Research Projects Agency under Contract N00039-84-C-0211. by
the United States Air Force OMee of Scientific Research under Contracts F49620-93-141139
and F4962043-1-0056. and by the European Community ESPRIT Basic Research Action
Project 6021 (REACT). A preliminary version of Part 1 of this paper appeared in
the proceedings of the 1991 REX Workshop on Real Time Theory In Prate [HMP92a I
a preliminary version of Part II appeared in the proceedings of the 1991 ACM Symposium
on Principles of Programming Languages RIMP911. '
article_processing_charge: No
article_type: original
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: Zohar
full_name: Manna, Zohar
last_name: Manna
- first_name: Amir
full_name: Pnueli, Amir
last_name: Pnueli
citation:
ama: Henzinger TA, Manna Z, Pnueli A. Temporal proof methodologies for timed transition
systems. Information and Computation. 1994;112(2):273-337. doi:10.1006/inco.1994.1060
apa: Henzinger, T. A., Manna, Z., & Pnueli, A. (1994). Temporal proof methodologies
for timed transition systems. Information and Computation. Elsevier. https://doi.org/10.1006/inco.1994.1060
chicago: Henzinger, Thomas A, Zohar Manna, and Amir Pnueli. “Temporal Proof Methodologies
for Timed Transition Systems.” Information and Computation. Elsevier, 1994.
https://doi.org/10.1006/inco.1994.1060.
ieee: T. A. Henzinger, Z. Manna, and A. Pnueli, “Temporal proof methodologies for
timed transition systems,” Information and Computation, vol. 112, no. 2.
Elsevier, pp. 273–337, 1994.
ista: Henzinger TA, Manna Z, Pnueli A. 1994. Temporal proof methodologies for timed
transition systems. Information and Computation. 112(2), 273–337.
mla: Henzinger, Thomas A., et al. “Temporal Proof Methodologies for Timed Transition
Systems.” Information and Computation, vol. 112, no. 2, Elsevier, 1994,
pp. 273–337, doi:10.1006/inco.1994.1060.
short: T.A. Henzinger, Z. Manna, A. Pnueli, Information and Computation 112 (1994)
273–337.
date_created: 2018-12-11T12:09:10Z
date_published: 1994-08-01T00:00:00Z
date_updated: 2022-06-02T09:24:58Z
day: '01'
doi: 10.1006/inco.1994.1060
extern: '1'
intvolume: ' 112'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/S0890540184710601?via%3Dihub
month: '08'
oa: 1
oa_version: None
page: 273 - 337
publication: Information and Computation
publication_identifier:
issn:
- 0890-5401
publication_status: published
publisher: Elsevier
publist_id: '227'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Temporal proof methodologies for timed transition systems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 112
year: '1994'
...
---
_id: '4503'
abstract:
- lang: eng
text: 'We describe finite-state programs over real-numbered time in a guarded-command
language with real-valued clocks or, equivalently, as finite automata with real-valued
clocks. Model checking answers the question which states of a real-time program
satisfy a branching-time specification (given in an extension of CTL with clock
variables). We develop an algorithm that computes this set of states symbolically
as a fixpoint of a functional on state predicates, without constructing the state
space. For this purpose, we introduce a μ-calculus on computation trees over real-numbered
time. Unfortunately, many standard program properties, such as response for all
nonzeno execution sequences (during which time diverges), cannot be characterized
by fixpoints: we show that the expressiveness of the timed μ-calculus is incomparable
to the expressiveness of timed CTL. Fortunately, this result does not impair the
symbolic verification of "implementable" real-time programs-those whose
safety constraints are machine-closed with respect to diverging time and whose
fairness constraints are restricted to finite upper bounds on clock values. All
timed CTL properties of such programs are shown to be computable as finitely approximable
fixpoints in a simple decidable theory.'
acknowledgement: We thank Peter Kopke for a careful reading.
article_processing_charge: No
article_type: original
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: Xavier
full_name: Nicollin, Xavier
last_name: Nicollin
- first_name: Joseph
full_name: Sifakis, Joseph
last_name: Sifakis
- first_name: Sergio
full_name: Yovine, Sergio
last_name: Yovine
citation:
ama: Henzinger TA, Nicollin X, Sifakis J, Yovine S. Symbolic model checking for
real-time systems. Information and Computation. 1994;111(2):193-244. doi:10.1006/inco.1994.1045
apa: Henzinger, T. A., Nicollin, X., Sifakis, J., & Yovine, S. (1994). Symbolic
model checking for real-time systems. Information and Computation. Elsevier.
https://doi.org/10.1006/inco.1994.1045
chicago: Henzinger, Thomas A, Xavier Nicollin, Joseph Sifakis, and Sergio Yovine.
“Symbolic Model Checking for Real-Time Systems.” Information and Computation.
Elsevier, 1994. https://doi.org/10.1006/inco.1994.1045.
ieee: T. A. Henzinger, X. Nicollin, J. Sifakis, and S. Yovine, “Symbolic model checking
for real-time systems,” Information and Computation, vol. 111, no. 2. Elsevier,
pp. 193–244, 1994.
ista: Henzinger TA, Nicollin X, Sifakis J, Yovine S. 1994. Symbolic model checking
for real-time systems. Information and Computation. 111(2), 193–244.
mla: Henzinger, Thomas A., et al. “Symbolic Model Checking for Real-Time Systems.”
Information and Computation, vol. 111, no. 2, Elsevier, 1994, pp. 193–244,
doi:10.1006/inco.1994.1045.
short: T.A. Henzinger, X. Nicollin, J. Sifakis, S. Yovine, Information and Computation
111 (1994) 193–244.
date_created: 2018-12-11T12:09:11Z
date_published: 1994-06-01T00:00:00Z
date_updated: 2022-06-02T09:02:02Z
day: '01'
doi: 10.1006/inco.1994.1045
extern: '1'
intvolume: ' 111'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/S0890540184710455?via%3Dihub
month: '06'
oa_version: None
page: 193 - 244
publication: Information and Computation
publication_identifier:
issn:
- 0890-5401
publication_status: published
publisher: Elsevier
publist_id: '226'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Symbolic model checking for real-time systems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 111
year: '1994'
...