@inproceedings{4620,
abstract = {We present a verification algorithm for duration properties of finite-state real-time systems. While simple real-time properties constrain the total elapsed time between events, duration properties constrain the accumulated time during which certain state predicates hold. We formalize the concept of durations by introducing duration measures for (dense-time) timed automata. Given a timed automaton with a duration measure, a start and a target state, and a duration constraint, the duration-bounded reachability problem asks if there is a run of the automaton from the start state to the target state such that the accumulated duration along the run satisfies the constraint. Our main result is a novel decision procedure for solving the duration-bounded reachability problem. We also prove that the problem is PSPACE-complete and demonstrate how the solution can be used to verify interesting duration properties of real-time systems.},
author = {Alur, Rajeev and Courcoubetis, Costas and Thomas Henzinger},
pages = {181 -- 193},
publisher = {Springer},
title = {{Computing accumulated delays in real-time systems}},
doi = {10.1007/3-540-56922-7_16},
volume = {697},
year = {1993},
}
@article{4036,
abstract = {This paper presents a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorithm is O(nα(n)log n). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor analysis technique [in Discrete Comput. Geom., 4(1989), pp. 387-421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented.},
author = {Chazelle, Bernard and Herbert Edelsbrunner and Guibas, Leonidas and Sharir, Micha and Snoeyink, Jack},
journal = {SIAM Journal on Computing},
number = {6},
pages = {1286 -- 1302},
publisher = {SIAM},
title = {{Computing a face in an arrangement of line segments and related problems}},
doi = {10.1137/0222077 },
volume = {22},
year = {1993},
}
@article{4040,
abstract = {A plane geometric graph C in ℝ2 conforms to another such graph G if each edge of G is the union of some edges of C. It is proved that, for every G with n vertices and m edges, there is a completion of a Delaunay triangulation of O(m2 n) points that conforms to G. The algorithm that constructs the points is also described.},
author = {Herbert Edelsbrunner and Tan, Tiow Seng},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {197 -- 213},
publisher = {Springer},
title = {{An upper bound for conforming Delaunay triangulations}},
doi = {10.1007/BF02573974},
volume = {10},
year = {1993},
}
@article{4041,
abstract = {The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is O(n(d-1)). This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for d greater-than-or-equal-to 3, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. The proof is based on an inductive argument, which also applies in the case of pseudohyperplane arrangements. The fallacies of the old proof along with some ways of partially saving that approach are briefly discussed.},
author = {Herbert Edelsbrunner and Seidel, Raimund and Sharir, Micha},
journal = {SIAM Journal on Computing},
number = {2},
pages = {418 -- 429},
publisher = {SIAM},
title = {{On the zone theorem for hyperplane arrangements}},
doi = {10.1137/0222031},
volume = {22},
year = {1993},
}
@article{4042,
abstract = {It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time 0(n2). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.},
author = {Herbert Edelsbrunner and Tan, Tiow Seng},
journal = {SIAM Journal on Computing},
number = {3},
pages = {527 -- 551},
publisher = {SIAM},
title = {{A quadratic time algorithm for the minmax length triangulation}},
doi = {10.1137/0222036 },
volume = {22},
year = {1993},
}
@article{4044,
abstract = {Edge insertion iteratively improves a triangulation of a finite point set in ℜ2 by adding a new edge, deleting old edges crossing the new edge, and retriangulating the polygonal regions on either side of the new edge. This paper presents an abstract view of the edge insertion paradigm, and then shows that it gives polynomial-time algorithms for several types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface.},
author = {Bern, Marshall and Herbert Edelsbrunner and Eppstein, David and Mitchell, Stephen and Tan, Tiow Seng},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {47 -- 65},
publisher = {Springer},
title = {{Edge insertion for optimal triangulations}},
doi = {10.1007/BF02573962},
volume = {10},
year = {1993},
}
@article{4045,
abstract = {We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, an O(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(8/5+ε) algorithm for computing the width of such a set, and on O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic.},
author = {Chazelle, Bernard and Herbert Edelsbrunner and Guibas, Leonidas and Sharir, Micha},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {183 -- 196},
publisher = {Springer},
title = {{Diameter, width, closest line pair, and parametric searching}},
doi = {10.1007/BF02573973},
volume = {10},
year = {1993},
}
@article{4175,
abstract = {We have studied the effects of different neurotrophins on the survival and proliferation of rat cerebellar granule cells in culture. These neurons express trkB and trkC, the putative neuronal receptors for brain-derived neurotrophic factor (BDNF) and neurotrophin-3 (NT-3) respectively. Binding studies using iodinated BDNF and NT-3 demonstrated that both BDNF and NT-3 bind to the cerebellar granule neurons with a similar affinity of approximately 2 x 10(-9) M. The number of receptors per granule cell was surprisingly high, approximately 30 x 10(-4) and 2 x 10(5) for BDNF and NT-3, respectively. Both NT-3 and BDNF elevated c-fos mRNA in the granule neurons, but only BDNF up-regulated the mRNA encoding the low-affinity neurotrophin receptor (p75). In contrast to NT-3, BDNF acted as a survival factor for the granule neurons. BDNF also induced sprouting of the granule neurons and significantly protected them against neurotoxicity induced by high (1 mM) glutamate concentrations. Cultured granule neurons also expressed low levels of BDNF mRNA which were increased by kainic acid, a glutamate receptor agonist. Thus, BDNF, but not NT-3, is a survival factor for cultured cerebellar granule neurons and activation of glutamate receptor(s) up-regulates BDNF expression in these cells.},
author = {Lindholm, Dan and Dechant, Georg and Heisenberg, Carl-Philipp J and Thoenen, Hans},
journal = {European Journal of Neuroscience},
number = {11},
pages = {1455 -- 1464},
publisher = {Wiley-Blackwell},
title = {{Brain-derived neurotrophic factor is a survival factor for cultured rat cerebellar granule neurons and protects them against glutamate-induced neurotoxicity}},
doi = {10.1111/j.1460-9568.1993.tb00213.x},
volume = {5},
year = {1993},
}
@article{4177,
abstract = {Thyroid hormones play an important role in brain development, but the mechanism(s) by which triiodothyronine (T3) mediates neuronal differentiation is poorly understood. Here we demonstrate that T3 regulates the neurotrophic factor, neurotrophin-3 (NT-3), in developing rat cerebellar granule cells both in cell culture and in vivo. In situ hybridization experiments showed that developing Purkinje cells do not express NT-3 mRNA but do express trkC, the putative neuronal receptor for NT-3. Addition of recombinant NT-3 to cerebellar cultures from embryonic rat brain induces hypertrophy and neurite sprouting of Purkinje cells, and upregulates the mRNA encoding the calcium-binding protein, calbindin-28 kD. The present study demonstrates a novel interaction between cerebellar granule neurons and developing Purkinje cells in which NT-3 induced by T3 in the granule cells promotes Purkinje cell differentiation.},
author = {Lindholm, Dan and Castrén, Eero and Tsoulfas, Pantelis and Kolbeck, Roland and Berzaghi, Maria and Leingärtner, Axel and Heisenberg, Carl-Philipp J and Tesarollo, Lino and Parada, Luis and Thoenen, Hans},
journal = {Journal of Cell Biology},
number = {2},
pages = {443 -- 450},
publisher = {Rockefeller University Press},
title = {{Neurotrophin-3 induced by tri-iodothyronine in cerebellar granule cells promotes Purkinje cell differentiation}},
doi = {10.1083/jcb.122.2.443},
volume = {122},
year = {1993},
}
@article{4300,
abstract = {Evolutionary explanations of ageing fall into two classes. Organisms might have evolved the optimal life history, in which survival and fertility late in life are sacrificed for the sake of early reproduction and survival. Alternatively, the life history might be depressed below this optimal compromise by deleterious mutations: because selection against late-acting mutations is weaker, these will impose a greater load on late life. Evidence for the importance of both is emerging, and unravelling their relative importance presents experimentalists with a major challenge.},
author = {Partridge, Linda and Nicholas Barton},
journal = {Nature},
pages = {305 -- 311},
publisher = {Nature Publishing Group},
title = {{Optimality, mutation and the evolution of ageing}},
doi = {10.1038/362305a0},
volume = {362},
year = {1993},
}
@inbook{4301,
author = {Nicholas Barton and Gale, Katherine S},
booktitle = {Hybrid zones and the evolutionary process},
editor = {Harrison, Richard G},
pages = {13 -- 45},
publisher = {Oxford University Press},
title = {{Genetic analysis of hybrid zones}},
year = {1993},
}
@misc{4302,
author = {Nicholas Barton},
booktitle = {Genetical Research},
number = {1},
pages = {77 -- 85},
publisher = {Cambridge University Press},
title = {{Review of "The causes of molecular evolution" by J.H. Gillespie}},
doi = {10.1017/S001667230003158X },
volume = {62},
year = {1993},
}
@article{4303,
abstract = {In a stably subdivided population with symmetric migration, the chance that a favoured allele will be fixed is independent of population structure. However, random extinction introduces an extra component of sampling drift, and reduces the probability of fixation. In this paper, the fixation probability is calculated using the diffusion approximation; comparison with exact solution of the discrete model shows this to be accurate. The key parameters are the rates of selection, migration and extinction, scaled relative to population size (S = 4Ns, M = 4Nm, Λ = 4Nλ); results apply to a haploid model, or to diploids with additive selection. If new colonies derive from many demes, the fixation probability cannot be reduced by more than half. However, if colonies are initially homogeneous, fixation probability can be much reduced. In the limit of low migration and extinction rates (M, Λ 1), it is 2s/{1 + (Λ/MS)(1 −exp(−S))}, whilst in the opposite limit (S 1), it is 4sM/{Λ(Λ + M)}. In the limit of weak selection (M, Λ 1), it is 4sM/{Λ(Λ + M)}. These factors are not the same as the reduction in effective population size (Ne/N), showing that the effects of population structure on selected alleles cannot be understood from the behaviour of neutral markers.},
author = {Nicholas Barton},
journal = {Genetical Research},
number = {2},
pages = {149 -- 158},
publisher = {Cambridge University Press},
title = {{The probability of fixation of a favoured allele in a subdivided population}},
doi = {10.1017/S0016672300031748},
volume = {62},
year = {1993},
}
@misc{4304,
author = {Nicholas Barton},
booktitle = {Current Biology},
number = {11},
pages = {797 -- 799},
publisher = {Cell Press},
title = {{Why species and subspecies?}},
doi = {10.1016/0960-9822(93)90036-N},
volume = {3},
year = {1993},
}
@inbook{4506,
abstract = {We propose a formal framework for designing hybrid systems by stepwise refinement. Starting with a specification in hybrid temporal logic, we make successively more transitions explicit until we obtain an executable system.},
author = {Thomas Henzinger and Manna, Zohar and Pnueli,Amir},
booktitle = {Hybrid Systems},
editor = {Grossman, Robert L. and Nerode, Anil and Ravn, Anders P and Rischel, Hans},
pages = {60 -- 76},
publisher = {Springer},
title = {{Towards refining temporal specifications into hybrid systems}},
doi = {10.1007/3-540-57318-6_24},
volume = {736},
year = {1993},
}
@article{4589,
abstract = {The theory of the natural numbers with linear order and monadic predicates underlies propositional linear temporal logic. To study temporal logics that are suitable for reasoning about real-time systems, we combine this classical theory of infinite state sequences with a theory of discrete time, via a monotonic function that maps every state to its time. The resulting theory of timed state sequences is shown to be decidable, albeit nonelementary, and its expressive power is characterized by ω-regular sets. Several more expressive variants are proved to be highly undecidable. This framework allows us to classify a wide variety of real-time logics according to their complexity and expressiveness. Indeed, it follows that most formalisms proposed in the literature cannot be decided. We are, however, able to identify two elementary real-time temporal logics as expressively complete fragments of the theory of timed state sequences, and we present tableau-based decision procedures for checking validity. Consequently, these two formalisms are well-suited for the specification and verification of real-time systems.
Copyright © 1993 Academic Press. All rights reserved.},
author = {Alur, Rajeev and Thomas Henzinger},
journal = {Information and Computation},
number = {1},
pages = {35 -- 77},
publisher = {Elsevier},
title = {{Real-time logics: Complexity and expressiveness}},
doi = {10.1006/inco.1993.1025},
volume = {104},
year = {1993},
}
@article{3446,
abstract = {An effective character recognition procedure implemented on a new type of hardware system and using a new architecture called CNND is proposed. This CNND contains one or more analog cellular neural networks (CNNs) and some digital logic, combining the advantages of the fast analog CNN signal processing and the fast and easy decision capability of digital logic. It is shown that the CNND system can be used for recognition of multifont printed or handwritten characters and could recognize 100,000 char/s with a recognition rate of more than 95%. The more advantage of the system over competing types is that there is not an extra feature extraction procedure implemented in slow hardware},
author = {Sziranyi, Tamas and Jozsef Csicsvari},
journal = {IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing},
number = {3},
pages = {223 -- 231},
publisher = {IEEE},
title = {{High-speed character recognition using a dual cellular neural network architecture (CNND)}},
doi = {10.1109/82.222823},
volume = {40},
year = {1993},
}
@inbook{3451,
author = {Peter Jonas},
booktitle = {Molecular Basis of Ion Channels and Receptors Involved in Nerve Excitation, Synaptic Transmission, and Muscle Contraction},
pages = {126 -- 135},
publisher = {New York Academy of Sciences},
title = {{Glutamate receptors in the central nervous system}},
volume = {707},
year = {1993},
}
@inbook{3452,
abstract = {In recent years, considerable progress in our understanding of the molecular events underlying excitatory synaptic transmission has been made. This progress was mainly achieved by technical advances, among them the patch-clamp technique in brain slices (Edwards et al., 1989), fast application of agonists (Franke et al., 1987), and cloning and functional expression of GluR channels of the nonNMDA type (e.g., Hollmann et al., 1989). A suitable model for studying excitatory postsynaptic currents (EPSCs) in the brain slice with patch-clamp techniques is the mossy fiber synapse on CA3 pyramidal cells of rat hippocampus (MF-CA3 synapse). This synapse is located close to the cell soma and should provide almost ideal space-clamp conditions. A comparison of MF-CA3 EPSCs with the currents activated by fast application of glutamate on membrane patches isolated from CA3 cell somata suggests that the concentration of glutamate in the synaptic cleft during excitatory synaptic transmission is high (about 1 mM) and that the transmitter remains in the synaptic cleft only briefly (about 1 ms). It seems likely that desensitization influences the peak amplitude of the EPSC in several ways. Brief pulses of glutamate cause desensitization, from which the glutamate receptor channels recover only slowly, and micromolar ambient glutamate concentrations produce desensitization at equilibrium. From the functional properties of recombinant GluR channels, in situ hybridization data, and patch-clamp experiments on different neuronal and nonneuronal cell types, a picture of the molecular identity of native channels emerges. In neurons of the hippocampus the pharmacological features of these channels were similar to recombinant channels assembled from subunits of the AMPA/kainate subtype which are strongly expressed in these cells. The native channels are characterized by outward rectification of the steady-state I-V and low Ca permeability, similar to recombinant channels containing the GluR-B subunit. This is consistent with the ubiquitous expression of this subunit in hippocampal neurones. In contrast, GluR channels from cerebellar glial cells, which uniquely in the central nervous system lack the expression of GluR-B subunits, show double rectification and high Ca permeability. The results suggest that the native functional nonNMDA glutamate receptor channels in the CNS are assembled form subunits of the AMPA/kainate subtype in a cell-specific way, with the functional properties of GluR channels in neurones being dominated by the GluR-B subunit.},
author = {Peter Jonas},
booktitle = {Nonselective cation channels: Pharmacology, Physiology and Biophysics.},
editor = {Siemen, Detlef},
pages = {61 -- 76},
publisher = {Birkhäuser},
title = {{AMPA-type glutamate receptors - nonselective cation channels mediating fast excitatory transmission in the CNS}},
volume = {66},
year = {1993},
}
@article{3473,
abstract = {Sixteen different K+ channel subtypes have been cloned from mammalian tissue. Considering their sequence homology to Drosophila Shaker, Shab, Shaw and Shal channels, they were classified into four corresponding classes Kv1-4. All K+ channels belonging to these classes consist of four subunits with each six hydrophobic segments (S1-S6) and a characteristic structure-function relationship of certain domains in their amino acid sequence. These domains are, the inactivation gate in the N-terminal region of the sequence, the voltage sensor in the fourth hydrophobic segment (S4), and the pore-region in the H5 segment between S5 and S6. In some functional properties K+ channels cloned from the mammalian brain, however, differ from Drosophila K+ channels. These are pharmacological differences, differences in the threshold of activation and in regulation of inactivation. Part of these differences are important to understand their physiological role in the brain. Based on their functional characteristics the expression pattern of cloned K+ channels in the rat brain can be correlated with the properties of K+ currents measured in central neurones.
Copyright © 1993 S. Karger AG, Basel},
author = {Ruppersberg, Peter and Ermler, Mamfred and Knopf, Martin and Kues, Wilfried and Peter Jonas and Koenen, Michael},
journal = {Cellular Physiology and Biochemistry},
pages = {250 -- 269},
publisher = {S. Karger AG},
title = {{Properties of Shaker-homologous potassium channels expressed in the mammalian brain.}},
doi = {10.1159/000154691},
volume = {3},
year = {1993},
}