@article{4048,
  abstract     = {Given a sequence of n points that form the vertices of a simple polygon, we show that determining a closest pair requires OMEGA(n log n) time in the algebraic decision tree model. Together with the well-known O(n log n) upper bound for finding a closest pair, this settles an open problem of Lee and Preparata. We also extend this O(n log n) upper bound to the following problem: Given a collection of sets with a total of n points in the plane, find for each point a closest neighbor that does not belong to the same set.},
  author       = {Aggarwal, Alok and Edelsbrunner, Herbert and Raghavan, Prabhakar and Tiwari, Prasoon},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {1},
  pages        = {55 -- 60},
  publisher    = {Elsevier},
  title        = {{Optimal time bounds for some proximity problems in the plane}},
  doi          = {10.1016/0020-0190(92)90133-G},
  volume       = {42},
  year         = {1992},
}

@inproceedings{4049,
  abstract     = {The edge-insertion paradigm improves a triangulation of a finite point set in R2 iteratively by adding a new edge, deleting intersecting old edges, and retriangulating the resulting two polygonal regions. After presenting an abstract view of the paradigm, this paper shows that it can be used to obtain polynomial time algorithms for several types of optimal triangulations.},
  author       = {Bern, Marshall and Edelsbrunner, Herbert and Eppstein, David and Mitchell, Stephen and Tan, Tiow},
  booktitle    = {1st Latin American Symposium on Theoretical Informatics},
  editor       = {Simon, Imre},
  isbn         = {978-3-540-55284-0},
  location     = {São Paulo, Brazil},
  pages        = {46 -- 60},
  publisher    = {Springer},
  title        = {{Edge insertion for optimal triangulations}},
  doi          = {10.1007/BFb0023816},
  volume       = {583},
  year         = {1992},
}

@article{4050,
  author       = {Edelsbrunner, Herbert},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {217 -- 217},
  publisher    = {Springer},
  title        = {{Guest editor's foreword}},
  doi          = {10.1007/BF02293046},
  volume       = {8},
  year         = {1992},
}

@article{4053,
  abstract     = {We show that the maximum number of edges bounding m faces in an arrangement of n line segments in the plane is O(m2/3n2/3+nα(n)+nlog m). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is Ω(m2/3n2/3+nα(n)). In addition, we show that the number of edges bounding any m faces in an arrangement of n line segments with a total of t intersecting pairs is O(m2/3t1/3+nα(t/n)+nmin{log m,log t/n}), almost matching the lower bound of Ω(m2/3t1/3+nα(t/n)) demonstrated in this paper.},
  author       = {Aronov, Boris and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha},
  issn         = {0209-9683},
  journal      = {Combinatorica},
  number       = {3},
  pages        = {261 -- 274},
  publisher    = {Springer},
  title        = {{The number of edges of many faces in a line segment arrangement}},
  doi          = {10.1007/BF01285815},
  volume       = {12},
  year         = {1992},
}

@article{4195,
  abstract     = {The effects of tri-iodothyronine (T3), which are known to affect cerebellar development, were tested on neuronal survival and differentiation of cultured cerebellar granule neurons. T3 in physiological concentrations increased both granule neuron survival after three days in culture and synaptic vesicle protein formation, as shown by immunostaining with antibodies against synaptophysin. Likewise, T3 increased the mRNA level for synapsin(I), but not that for GAP43 in granule neurons. Antibodies against microtubule associated protein Tau, which is expressed in developing neurites, showed that T3 also enhanced neurite formation.},
  author       = {Heisenberg, Carl-Philipp J and Thoenen, Hans and Lindholm, Dan},
  issn         = {1473-558X},
  journal      = {Neuroreport},
  number       = {8},
  pages        = {685 -- 688},
  publisher    = {Lippincott, Williams & Wilkins},
  title        = {{Triiodothyronine Regulates Survival and Differentiation of Rat Cerebellar Granule Neurons}},
  doi          = {10.1097/00001756-199208000-00008 },
  volume       = {3},
  year         = {1992},
}

@article{4305,
  abstract     = {The common shrew (Sorex araneus) is subdivided into several karyotypic races in Britain. Two of these races meet near Oxford to form the "Oxford-Hermitage" hybrid zone. We present a model which describes this system as a "tension zone," i.e., a set of clines maintained by a balance between dispersal and selection against chromosomal heterozygotes. The Oxford and Hermitage races differ by Robertsonian fusions with monobrachial homology (kq, no versus ko), and so F1 hybrids between them would have low fertility. However, the acrocentric karyotype is found at high frequency within the hybrid zone, so that complex Robertsonian heterozygotes (kq no/q ko n) are replaced by more fertile combinations, such as (kq no/k q n o). This suggests that the hybrid zone has been modified so as to increase hybrid fitness. Mathematical analysis and simulation show that, if selection against complex heterozygotes is sufficiently strong relative to selection against simple heterozygotes, acrocentrics increase, and displace the clines for kq and no from the cline for ko. Superimposed on this separation is a tendency for the hybrid zone to move m favor of the Oxford (kq no) race. We compare the model with estimates of linkage disequilibrium and cline shape made from field data.},
  author       = {Hatfield, Todd and Barton, Nicholas H and Searle, Jeremy},
  issn         = {1558-5646},
  journal      = {Evolution; International Journal of Organic Evolution},
  number       = {4},
  pages        = {1129 -- 1145},
  publisher    = {Wiley-Blackwell},
  title        = {{A model of a hybrid zone between two chromosomal races of the common shrew (Sorex araneus)}},
  doi          = {10.1111/j.1558-5646.1992.tb00624.x},
  volume       = {46},
  year         = {1992},
}

@misc{4306,
  author       = {Barton, Nicholas H and Goldman, Nick},
  booktitle    = {Nature},
  pages        = {440 -- 441},
  publisher    = {Nature Publishing Group},
  title        = {{Genetics and geography}},
  doi          = {10.1038/357440a0},
  volume       = {357},
  year         = {1992},
}

@inbook{4307,
  author       = {Barton, Nicholas H},
  booktitle    = {Animal dispersal: small mammals as a model},
  editor       = {Stenseth, Nils and Lidicker, William},
  pages        = {37 -- 60},
  publisher    = {Chapman Hall},
  title        = {{The genetic consequences of dispersal}},
  doi          = {10.1007/978-94-011-2338-9_3},
  year         = {1992},
}

@article{4308,
  author       = {Barton, Nicholas H},
  issn         = {1558-5646},
  journal      = {Evolution; International Journal of Organic Evolution},
  number       = {2},
  pages        = {551 -- 557},
  publisher    = {Wiley-Blackwell},
  title        = {{On the spread of new gene combinations in the third phase of Wright's shifting balance}},
  volume       = {46},
  year         = {1992},
}

@inproceedings{4504,
  abstract     = {Real-time systems operate in “real,” continuous time and state changes may occur at any real-numbered time point. Yet many verification methods are based on the assumption that states are observed at integer time points only. What can we conclude if a real-time system has been shown “correct” for integral observations?

Integer time verification techniques suffice if the problem of whether all real-numbered behaviors of a system satisfy a property can be reduced to the question of whether the integral observations satisfy a (possibly modified) property. We show that this reduction is possible for a large and important class of systems and properties: the class of systems includes all systems that can be modeled as timed transition systems; the class of properties includes time-bounded invariance and time-bounded response.},
  author       = {Henzinger, Thomas A and Manna, Zohar and Pnueli, Amir},
  booktitle    = {19th International Colloquium on Automata, Languages and Programming},
  location     = {Vienna, Austria},
  pages        = {545 -- 558},
  publisher    = {Springer},
  title        = {{What good are digital clocks?}},
  doi          = {10.1007/3-540-55719-9_103},
  volume       = {623},
  year         = {1992},
}

@inproceedings{4505,
  abstract     = {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 mu-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 mu-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.},
  author       = {Henzinger, Thomas A and Nicollin, Xavier and Sifakis, Joseph and Yovine, Sergio},
  booktitle    = {Proceedings of the 7th Annual IEEE Symposium on Logic in Computer Science},
  isbn         = {0-8186-2735-2},
  location     = {Santa Cruz, CA, United States of America},
  pages        = {394 -- 406},
  publisher    = {IEEE},
  title        = {{Symbolic model checking for real-time systems}},
  doi          = {10.1109/LICS.1992.185551},
  year         = {1992},
}

@inbook{4507,
  abstract     = {We incorporate time into an interleaving model of concurrency. In timed transition systems, the qualitative fairness requirements of traditional transition system are replaced (and superseded) by quantitative lower-bound and upperbound timing constraints on transitions. The purpose of this paper is to explore the scope of applicability for the abstract model of timed transition systems. We demonstrate that the model can represent a wide variety of phenomena that routinely occur in conjunction with the timed execution of concurrent processes. Our treatment covers both processes that are executed in parallel on separate processors and communicate either through shared variables or by message passing, and processes that time-share a limited number of processors under a given scheduling policy. Often it is this scheduling policy that determines if a system meets its real-time requirements. Thus we explicitly address such questions as time-outs, interrupts, static and dynamic priorities.},
  author       = {Henzinger, Thomas A and Manna, Zohar and Pnueli, Amir},
  booktitle    = {Real Time: Theory in Practice},
  pages        = {226 -- 251},
  publisher    = {Springer},
  title        = {{Timed transition systems}},
  doi          = {10.1007/BFb0031995},
  volume       = {600},
  year         = {1992},
}

@article{4517,
  abstract     = {It has been observed repeatedly that the standard safety-liveness classification for properties of reactive systems does not fit for real-time properties. This is because the implicit “liveliness” of time shifts the spectrum towards the safety side. While, for example, response—that “something good” will happen eventually—is a classical liveness property, bounded response—that “something good” will happen soon, within a certain amount of time—has many characteristics of safety. We account for this phenomenon formally by defining safety and liveness relative to a given condition, such as the progress of time.},
  author       = {Henzinger, Thomas A},
  issn         = {0020-0190},
  journal      = {Information Processing Letters},
  number       = {3},
  pages        = {135 -- 141},
  publisher    = {Elsevier},
  title        = {{Sooner Is Safer Than Later}},
  doi          = {10.1016/0020-0190(92)90005-G},
  volume       = {43},
  year         = {1992},
}

@inproceedings{4593,
  abstract     = {We survey logic-based and automata-based languages and techniques for the specification and verification of real-time systems. In particular, we discuss three syntactic extensions of temporal logic: time-bounded operators, freeze quantification, and time variables. We also discuss the extension of finite-state machines with clocks and the extension of transition systems with time bounds on the transitions. All of the resulting notations can be interpreted over a variety of different models of time and computation, including linear and branching time, interleaving and true concurrency, discrete and continuous time. For each choice of syntax and semantics, we summarize the results that are known about expressive power, algorithmic finite-state verification, and deductive verification.},
  author       = {Alur, Rajeev and Henzinger, Thomas A},
  booktitle    = {REX Workshop on Real Time: Theory in Practice},
  location     = {Mook, The Netherlands},
  pages        = {74 -- 106},
  publisher    = {Springer},
  title        = {{Logics and models of real time: A survey}},
  doi          = {10.1007/BFb0031984},
  volume       = {600},
  year         = {1992},
}

@inproceedings{4594,
  abstract     = {The authors introduce two-way timed automata-timed automata that can move back and forth while reading a timed word. Two-wayness in its unrestricted form leads, like nondeterminism, to the undecidability of language inclusion. However, if they restrict the number of times an input symbol may be revisited, then two-wayness is both harmless and desirable. The authors show that the resulting class of bounded two-way deterministic timed automata is closed under all boolean operations, has decidable (PSPACE-complete) emptiness and inclusion problems, and subsumes all decidable real-time logics we know. They obtain a strict hierarchy of real-time properties: deterministic timed automata can accept more languages as the bound on the number of times an input symbol may be revisited is increased. This hierarchy is also enforced by the number of alternations between past and future operators in temporal logic. The combination of the results leads to a decision procedure for a real-time logic with past operators
},
  author       = {Alur, Rajeev and Henzinger, Thomas A},
  booktitle    = {Proceedings of the 33rd Annual Symposium on Foundations of Computer Science},
  location     = {Pittsburgh, PA, United States of America},
  pages        = {177 -- 186},
  publisher    = {IEEE},
  title        = {{Back to the future: Towards a theory of timed regular languages}},
  doi          = {10.1109/SFCS.1992.267774},
  year         = {1992},
}