@inproceedings{4483, abstract = {Model-checking algorithms can be used to verify, formally and automatically, if a low-level description of a design conforms with a high-level description. However, for designs with very large state spaces, prior to the application of an algorithm, the refinement-checking task needs to be decomposed into subtasks of manageable complexity. It is natural to decompose the task following the component structure of the design. However, an individual component often does not satisfy its requirements unless the component is put into the right context, which constrains the inputs to the component. Thus, in order to verify each component individually, we need to make assumptions about its inputs, which are provided by the other components of the design. This reasoning is circular: component A is verified under the assumption that context B behaves correctly, and symmetrically, B is verified assuming the correctness of A. The assume-guarantee paradigm provides a systematic theory and methodology for ensuring the soundness of the circular style of postulating and discharging assumptions in component-based reasoning.We give a tutorial introduction to the assume-guarantee paradigm for decomposing refinement-checking tasks. To illustrate the method, we step in detail through the formal verification of a processor pipeline against an instruction set architecture. In this example, the verification of a three-stage pipeline is broken up into three subtasks, one for each stage of the pipeline.}, author = {Henzinger, Thomas A and Qadeer, Shaz and Rajamani, Sriram}, booktitle = {Proceedings of the 2000 International Conference on Computer-Aided Design}, isbn = {0780364457}, location = {San Jose, CA, USA}, pages = {245 -- 252}, publisher = {IEEE}, title = {{Decomposing refinement proofs using assume-guarantee reasoning}}, doi = {10.1109/ICCAD.2000.896481}, year = {2000}, } @inproceedings{4512, abstract = {Masaccio is a formal model for hybrid dynamical systems which are built from atomic discrete components (difference equations) and atomic continuous components (differential equations) by parallel and serial composition, arbitrarily nested. Each system component consists of an interface, which determines the possible ways of using the component, and a set of executions, which define the possible behaviors of the component in real time. Version 1.0 (May 2000). }, author = {Henzinger, Thomas A}, booktitle = {Proceedings of the 1st International Conference on Theoretical Computer Science }, isbn = {9783540678236}, location = {Sendai, Japan}, pages = {549 -- 563}, publisher = {Springer}, title = {{Masaccio: A formal model for embedded components}}, doi = {10.1007/3-540-44929-9_38}, volume = {1872}, year = {2000}, } @inbook{4513, abstract = {A hybrid automaton is a formal model for a mixed discrete-continuous system. We classify hybrid automata according to what questions about their behavior can be answered algorithmically. The classification reveals structure on mixed discrete-continuous state spaces that was previously studied on purely discrete state spaces only. In particular, various classes of hybrid automata induce finitary trace equivalence (or similarity, or bisimilarity) relations on an uncountable state space, thus permitting the application of various model-checking techniques that were originally developed for finitestate systems. }, author = {Henzinger, Thomas A}, booktitle = {Verification of Digital and Hybrid Systems}, editor = {Inan, M. and Kurshan, Robert}, isbn = {9783642596155}, pages = {265 -- 292}, publisher = {Springer}, title = {{The theory of hybrid automata}}, doi = {10.1007/978-3-642-59615-5}, volume = {170}, year = {2000}, } @article{4598, abstract = {A hybrid system is a dynamical system with both discrete and continuous state changes. For analysis purposes, it is often useful to abstract a system in a way that preserves the properties being analyzed while hiding the details that are of no interest. We show that interesting classes of hybrid systems can be abstracted to purely discrete systems while preserving all properties that are definable in temporal logic. The classes that permit discrete abstractions fall into two categories. Either the continuous dynamics must be restricted, as is the case for timed and rectangular hybrid systems, or the discrete dynamics must be restricted, as is the case for o-minimal hybrid systems. In this paper, we survey and unify results from both areas.}, author = {Alur, Rajeev and Henzinger, Thomas A and Lafferriere, Gerardo and Pappas, George}, issn = {0018-9219}, journal = {Proceedings of the IEEE}, number = {7}, pages = {971 -- 984}, publisher = {IEEE}, title = {{Discrete abstractions of hybrid systems}}, doi = {10.1109/5.871304 }, volume = {88}, year = {2000}, } @inproceedings{4627, abstract = {We consider two-player games, which are played on a finite state space for an infinite number of rounds. The games are concurrent, that is, in each round, the two players choose their moves independently and simultaneously; the current state and the two moves determine a successor state. We consider omega-regular winning conditions on the resulting infinite state sequence. To model the independent choice of moves, both players are allowed to use randomization for selecting their moves. This gives rise to the following qualitative modes of winning, which can be studied without numerical considerations concerning probabilities: sure-win (player 1 can ensure winning with certainty), almost-sure-win (player 1 can ensure winning with probability 1), limit-win (player 1 can ensure winning with probability arbitrarily close to 1), bounded-win (player 1 can ensure winning with probability bounded away from 0), positive-win (player 1 can ensure winning with positive probability), and exist-win (player 1 can ensure that at least one possible outcome of the game satisfies the winning condition).We provide algorithms for computing the sets of winning states for each of these winning modes. In particular, we solve concurrent Rabin-chain games in n0 (m) time, where n is the size of the game structure and m is the number of pairs in the Rabin-chain condition. While this complexity is in line with traditional turn-based games, where in each state only one of the two players has a choice of moves, our algorithms are considerably more involved than those for turn-based games are. This is because concurrent games violate two of the most fundamental properties of turn-based games. First, concurrent games are not determined, but rather exhibit a more general duality property, which involves multiple modes of winning. Second, winning strategies for concurrent games may require infinite memory.}, author = {De Alfaro, Luca and Henzinger, Thomas A}, booktitle = {Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science}, isbn = {0769507255}, location = {Santa Barbara, CA, USA}, pages = {141 -- 154}, publisher = {IEEE}, title = {{Concurrent omega-regular games}}, doi = {10.1109/LICS.2000.855763}, year = {2000}, } @inproceedings{4637, abstract = {In the synchronous composition of processes, one process may prevent another process from proceeding unless compositions without a well-defined product behavior are ruled out. They can be ruled out semantically, by insisting on the existence of certain fixed points, or syntactically, by equipping processes with types, which make the dependencies between input and output signals transparent. We classify various typing mechanisms and study their effects on the control problem. A static type enforces fixed, acyclic dependencies between input and output ports. For example, synchronous hardware without combinational loops can be typed statically. A dynamic type may vary the dependencies from state to state, while maintaining acyclicity, as in level-sensitive latches. Then, two dynamically typed processes can be syntactically compatible, if all pairs of possible dependencies are compatible, or semantically compatible, if in each state the combined dependencies remain acyclic. For a given plant process and control objective, there may be a controller of a static type, or only a controller of a syntactically compatible dynamic type, or only a controller of a semantically compatible dynamic type. We show this to be a strict hierarchy of possibilities, and we present algorithms and determine the complexity of the corresponding control problems. Furthermore, we consider versions of the control problem in which the type of the controller (static or dynamic) is given. We show that the solution of these fixed-type control problems requires the evaluation of partially ordered (Henkin) quantifiers on boolean formulas, and is therefore harder (nondeterministic exponential time) than more traditional control questions}, author = {De Alfaro, Luca and Henzinger, Thomas A and Mang, Freddy}, booktitle = {Proceedings of the 11th International Conference on Concurrency Theory}, isbn = {9783540678977}, location = {University Park, PA, USA}, pages = {458 -- 473}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The control of synchronous systems}}, doi = {10.1007/3-540-44618-4_33}, volume = {1877}, year = {2000}, } @inproceedings{4638, abstract = {Any formal method or tool is almost certainly more often applied in situations where the outcome is failure (a counterexample) rather than success (a correctness proof). We present a method for symbolic model checking that can lead to significant time and memory savings for model-checking runs that fail, while occurring only a small overhead for model-checking runs that succeed. Our method discovers an error as soon as it cannot be prevented, which can be long before it actually occurs; for example, the violation of an invariant may become unpreventable many transitions before the invariant is violated. The key observation is that “unpreventability” is a local property of a single module: an error is unpreventable in a module state if no environment can prevent it. Therefore, unpreventability is inexpensive to compute for each module, yet can save much work in the state exploration of the global, compound system. Based on different degrees of information available about the environment, we define and implement several notions of “unpreventability,” including the standard notion of uncontrollability from discrete-event control. We present experimental results for two examples, a distributed database protocol and a wireless communication protocol.}, author = {De Alfaro, Luca and Henzinger, Thomas A and Mang, Freddy}, booktitle = {Proceedings of the 12th International Conference on Computer Aided Verification}, isbn = {9783540677703}, location = {Chicago, IL, USA}, pages = {186 -- 201}, publisher = {Springer}, title = {{Detecting errors before reaching them}}, doi = {10.1007/10722167_17}, volume = {1855}, year = {2000}, } @article{842, author = {Wolf, Yuri and Kondrashov, Fyodor and Koonin, Eugene}, issn = {0168-9479}, journal = {Trends in Genetics}, number = {8}, pages = {333 -- 334}, publisher = {Elsevier}, title = {{No footprints of primordial introns in a eukaryotic genome}}, doi = {10.1016/S0168-9525(00)02059-X}, volume = {16}, year = {2000}, } @article{8525, abstract = {Let M be a smooth compact manifold of dimension at least 2 and Diffr(M) be the space of C r smooth diffeomorphisms of M. Associate to each diffeomorphism f;isin; Diffr(M) the sequence P n (f) of the number of isolated periodic points for f of period n. In this paper we exhibit an open set N in the space of diffeomorphisms Diffr(M) such for a Baire generic diffeomorphism f∈N the number of periodic points P n f grows with a period n faster than any following sequence of numbers {a n } n ∈ Z + along a subsequence, i.e. P n (f)>a ni for some n i →∞ with i→∞. In the cases of surface diffeomorphisms, i.e. dim M≡2, an open set N with a supergrowth of the number of periodic points is a Newhouse domain. A proof of the man result is based on the Gontchenko–Shilnikov–Turaev Theorem [GST]. A complete proof of that theorem is also presented.}, author = {Kaloshin, Vadim}, issn = {0010-3616}, journal = {Communications in Mathematical Physics}, keywords = {Mathematical Physics, Statistical and Nonlinear Physics}, pages = {253--271}, publisher = {Springer Nature}, title = {{Generic diffeomorphisms with superexponential growth of number of periodic orbits}}, doi = {10.1007/s002200050811}, volume = {211}, year = {2000}, } @article{3149, abstract = {The prohormone convertases (PCs) are an evolutionarily ancient group of proteases required for the maturation of neuropeptide and peptide hormone precursors. In Drosophila melanogaster, the homolog of prohormone convertase 2, dPC2 (amontillado), is required for normal hatching behavior, and immunoblotting data indicate that flies express 80- and 75-kDa forms of this protein. Because mouse PC2 (mPC2) requires 7B2, a helper protein for productive maturation, we searched the fly data base for the 7B2 signature motif PPNPCP and identified an expressed sequence tag clone encoding the entire open reading frame for this protein. dPC2 and d7B2 cDNAs were subcloned into expression vectors for transfection into HEK-293 cells; mPC2 and rat 7B2 were used as controls. Although active mPC2 was detected in medium in the presence of either d7B2 or r7B2, dPC2 showed no proteolytic activity upon coexpression of either d7B2 or r7B2. Labeling experiments showed that dPC2 was synthesized but not secreted from HEK-293 cells. However, when dPC2 and either d7B2 or r7B2 were coexpressed in Drosophila S2 cells, abundant immunoreactive dPC2 was secreted into the medium, coincident with the appearance of PC2 activity. Expression and secretion of dPC2 enzyme activity thus appears to require insect cell-specific posttranslational processing events. The significant differences in the cell biology of the insect and mammalian enzymes, with 7B2 absolutely required for secretion of dPC2 and zymogen conversion occurring intracellularly in the case of dPC2 but not mPC2, support the idea that the Drosophila enzyme has specific requirements for maturation and secretion that can be met only in insect cells.}, author = {Hwang, Jae and Siekhaus, Daria E and Fuller, Robert and Taghert, Paul and Lindberg, Iris}, issn = {0021-9258}, journal = {Journal of Biological Chemistry}, number = {23}, pages = {17886 -- 17893}, publisher = {American Society for Biochemistry and Molecular Biology}, title = {{Interaction of Drosophila melanogaster prohormone convertase 2 and 7B2: Insect cell specific processing and secretion}}, doi = {10.1074/jbc.M000032200 }, volume = {275}, year = {2000}, } @article{3489, abstract = {We have examined factors that determine the strength and dynamics of GABAergic synapses between interneurons [dentate gyrus basket cells (BCs)] and principal neurons [dentate gyrus granule cells (GCs)] using paired recordings in rat hippocampal slices at 34°C. Unitary IPSCs recorded from BC–GC pairs in high intracellular Cl− concentration showed a fast rise and a biexponential decay, with mean time constants of 2 and 9 msec. The mean quantal conductance change, determined directly at reduced extracellular Ca2+/Mg2+concentration ratios, was 1.7 nS. Quantal release at the BC–GC synapse occurred with short delay and was highly synchronized. Analysis of IPSC peak amplitudes and numbers of failures by multiple probability compound binomial analysis indicated that synaptic transmission at the BC–GC synapse involves three to seven release sites, each of which releases transmitter with high probability (∼0.5 in 2 mMCa2+/1 mM Mg2+). Unitary BC–GC IPSCs showed paired-pulse depression (PPD); maximal depression, measured for 10 msec intervals, was 37%, and recovery from depression occurred with a time constant of 2 sec. Paired-pulse depression was mainly presynaptic in origin but appeared to be independent of previous release. Synaptic transmission at the BC–GC synapse showed frequency-dependent depression, with half-maximal decrease at 5 Hz after a series of 1000 presynaptic action potentials. The relative stability of transmission at the BC–GC synapse is consistent with a model in which an activity-dependent gating mechanism reduces release probability and thereby prevents depletion of the releasable pool of synaptic vesicles. Thus several mechanisms converge on the generation of powerful and sustained transmission at interneuron–principal neuron synapses in hippocampal circuits.}, author = {Kraushaar, Udo and Jonas, Peter M}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {15}, pages = {5594 -- 5607}, publisher = {Society for Neuroscience}, title = {{Efficacy and stability of quantal GABA release at a hippocampal interneuron-principal neuron synapse}}, doi = {10.1523/JNEUROSCI.20-15-05594.2000}, volume = {20}, year = {2000}, } @article{3490, abstract = {Long-term depression (LTD) is a form of synaptic plasticity that can be induced either by low-frequency stimulation of presynaptic fibers or in an associative manner by asynchronous pairing of presynaptic and postsynaptic activity. We investigated the induction mechanisms of associative LTD in CA1 pyramidal neurons of the hippocampus using whole-cell patch-clamp recordings and Ca2+ imaging in acute brain slices. Asynchronous pairing of postsynaptic action potentials with EPSPs evoked with a delay of 20 msec induced a robust, long-lasting depression of the EPSP amplitude to 43%. Unlike LTD induced by low-frequency stimulation, associative LTD was resistant to the application of D-AP-5, indicating that it is independent of NMDA receptors. In contrast, associative LTD was inhibited by (S)-α-methyl-4-carboxyphenyl-glycine, indicating the involvement of metabotropic glutamate receptors. Furthermore, associative LTD is dependent on the activation of voltage-gated Ca2+ channels by postsynaptic action potentials. Both nifedipine, an L-type Ca2+ channel antagonist, and ω-conotoxin GVIA, a selective N-type channel blocker, abolished the induction of associative LTD. 8-hydroxy-2-dipropylaminotetralin (OH-DPAT), a 5-HT(1A) receptor agonist, inhibited postsynaptic Ca2+ influx through N-type Ca2+ channels, without affecting presynaptic transmitter release. OH-DPAT also inhibited the induction of associative LTD, suggesting that the involvement of N-type channels makes synaptic plasticity accessible to modulation by neurotransmitters. Thus, the modulation of N-type Ca2+ channels provides a gain control for synaptic depression in hippocampal pyramidal neurons.}, author = {Normann, Claus and Peckys, Diana and Schulze, Christian and Walden, Jörg and Jonas, Peter M and Bischofberger, Joseph}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {22}, pages = {8290 -- 8297}, publisher = {Society for Neuroscience}, title = {{Associative long-term depression in the hippocampus is dependent on postsynaptic N-type Ca(2+) channels}}, doi = {10.1523/JNEUROSCI.20-22-08290.2000}, volume = {20}, year = {2000}, } @article{3491, abstract = {Fast and reliable activation of inhibitory interneurons is critical for the stability of cortical neuronal networks. Active conductances in dendrites may facilitate interneuron activation, but direct experimental evidence was unavailable. Patch-clamp recordings from dendrites of hippocampal oriens- alveus interneurons revealed high densities of voltage-gated sodium and potassium ion channels. Simultaneous recordings from dendrites and somata suggested that action potential initiation occurs preferentially in the axon with long threshold stimuli, but can be shifted to somatodendritic sites when brief stimuli are applied. After initiation, action potentials propagate over the somatodendritic domain with constant amplitude, high velocity, and reliability, even during high-frequency trains.}, author = {Martina, Marco and Vida, Imre and Jonas, Peter M}, issn = {0036-8075}, journal = {Science}, number = {5451}, pages = {295 -- 300}, publisher = {American Association for the Advancement of Science}, title = {{Distal initiation and active propagation of action potentials in interneuron dendrites}}, doi = {10.1126/science.287.5451.295}, volume = {287}, year = {2000}, } @article{3492, abstract = {Analysis of presynaptic determinants of synaptic strength has been difficult at cortical synapses, mainly due to the lack of direct access to presynaptic elements. Here we report patch-clamp recordings from mossy fiber boutons (MFBs) in rat hippocampal slices. The presynaptic action potential is very short during low-frequency stimulation but is prolonged up to 3-fold during high-frequency stimulation. Voltage-gated K+ channels in MFBs inactivate rapidly but recover from inactivation very slowly, suggesting that cumulative K+ channel inactivation mediates activity-dependent spike broadening. Prolongation of the presynaptic voltage waveform leads to an increase in the number of Ca2+ ions entering the terminal per action potential and to a consecutive potentiation of evoked excitatory postsynaptic currents at MFB-CA3 pyramidal cell synapses. Thus, inactivation of presynaptic K+ channels contributes to the control of efficacy of a glutamatergic synapse in the cortex.}, author = {Geiger, Jörg and Jonas, Peter M}, issn = {0896-6273}, journal = {Neuron}, number = {3}, pages = {927 -- 939}, publisher = {Elsevier}, title = {{Dynamic control of presynaptic Ca(2+) inflow by fast-inactivating K+ channels in hippocampal mossy fiber boutons}}, doi = {10.1016/S0896-6273(00)00164-1}, volume = {28}, year = {2000}, } @article{3532, abstract = {Multichannel tetrode array recording in awake behaving animals provides a powerful method to record the activity of large numbers of neurons. The power of this method could be extended if further information concerning the intracellular state of the neurons could be extracted from the extracellularly recorded signals. Toward this end, we have simultaneously recorded intracellular and extracellular signals from hippocampal CA1 pyramidal cells and interneurons in the anesthetized rat. We found that several intracellular parameters can be deduced from extracellular spike waveforms. The width of the intracellular action potential is defined precisely by distinct points on the extracellular spike. Amplitude changes of the intracellular action potential are reflected by changes in the amplitude of the initial negative phase of the extracellular spike, and these amplitude changes are dependent on the state of the network. In addition, intracellular recordings from dendrites with simultaneous extracellular recordings from the soma indicate that, on average, action potentials are initiated in the perisomatic region and propagate to the dendrites at 1.68 m/s. Finally we determined that a tetrode in hippocampal area CA1 theoretically should be able to record electrical signals from similar to 1,000 neurons. Of these, 60-100 neurons should generate spikes of sufficient amplitude to be detectable from the noise and to allow for their separation using current spatial clustering methods. This theoretical maximum is in contrast to the approximately six units that are usually detected per tetrode. From this, we conclude that a large percentage of hippocampal CA1 pyramidal cells are silent in any given behavioral condition.}, author = {Henze, Darrell and Borhegyi, Zsolt and Csicsvari, Jozsef L and Mamiya, Akira and Harris, Kenneth and Buzsáki, György}, issn = {0022-3077}, journal = {Journal of Neurophysiology}, number = {1}, pages = {390 -- 400}, publisher = {American Physiological Society}, title = {{Intracellular features predicted by extracellular recordings in the hippocampus in vivo}}, doi = {10.1152/jn.2000.84.1.390}, volume = {84}, year = {2000}, } @article{3542, abstract = {Transfer of neuronal patterns from the CA3 to CA1 region was studied by simultaneous recording of neuronal ensembles in the behaving rat. A nonlinear interaction among pyramidal neurons was observed during sharp wave (SPW)-related population bursts, with stronger synchrony associated with more widespread spatial coherence. SPW bursts emerged in the CA3a-b subregions and spread to CA3c before invading the CA1 area. Synchronous discharge of >10% of the CA3 within a 100 ms window was required to exert a detectable influence on CA1 pyramidal cells. Activity of some CA3 pyramidal neurons differentially predicted the ripple-related discharge of circumscribed groups of CA1 pyramidal cells. We suggest that, in SPW behavioral state, the coherent discharge of a small group of CA3 cells is the primary cause of spiking activity in CA1 pyramidal neurons.}, author = {Csicsvari, Jozsef L and Hirase, Hajima and Mamiya, Akira and Buzsáki, György}, issn = {0896-6273}, journal = {Neuron}, number = {2}, pages = {585 -- 594}, publisher = {Elsevier}, title = {{Ensemble patterns of hippocampal CA3-CA1 neurons during sharp wave-associated population events}}, doi = {10.1016/S0896-6273(00)00135-5}, volume = {28}, year = {2000}, } @article{3548, abstract = {Simultaneous recording from large numbers of neurons is a prerequisite for understanding their cooperative behavior. Various recording techniques and spike separation methods are being used toward this goal. However, the error rates involved in spike separation have not yet been quantified. We studied the separation reliability of “tetrode” (4-wire electrode) recorded spikes by monitoring simultaneously from the same cell intracellularly with a glass pipette and extracellularly with a tetrode. With manual spike sorting, we found a trade-off between Type I and Type II errors, with errors typically ranging from 0 to 30% depending on the amplitude and firing pattern of the cell, the similarity of the waveshapes of neighboring neurons, and the experience of the operator. Performance using only a single wire was markedly lower, indicating the advantages of multiple-site monitoring techniques over single-wire recordings. For tetrode recordings, error rates were increased by burst activity and during periods of cellular synchrony. The lowest possible separation error rates were estimated by a search for the best ellipsoidal cluster shape. Human operator performance was significantly below the estimated optimum. Investigation of error distributions indicated that suboptimal performance was caused by inability of the operators to mark cluster boundaries accurately in a high-dimensional feature space. We therefore hypothesized that automatic spike-sorting algorithms have the potential to significantly lower error rates. Implementation of a semi-automatic classification system confirms this suggestion, reducing errors close to the estimated optimum, in the range 0-8%.}, author = {Harris, Kenneth and Henze, Darrell and Csicsvari, Jozsef L and Hirase, Hajima and Buzsáki, György}, issn = {0022-3077}, journal = {Journal of Neurophysiology}, number = {1}, pages = {401 -- 414}, publisher = {American Physiological Society}, title = {{Accuracy of tetrode spike separation as determined by simultaneous intracellular and extracellular measurements}}, doi = {10.1152/jn.2000.84.1.401}, volume = {84}, year = {2000}, } @inproceedings{3555, abstract = {A sliver is a tetrahedron whose four vertices lie close to a plane and whose perpendicular projection to that plane is a convex quadrilateral with no short edge. Slivers are both undesirable and ubiquitous in 3-dimensional Delaunay triangulations. Even when the point-set is well-spaced, slivers may result. This paper shows that such a point set permits a small perturbation whose Delaunay triangulation contains no slivers. It also gives deterministic algorithms that compute the perturbation of n points in time O(n log n) with one processor and in time O(log n) with O(n) processors.}, author = {Edelsbrunner, Herbert and Li, Xiang and Miller, Gary and Stathopoulos, Andreas and Talmor, Dafna and Teng, Shang and Üngör, Alper and Walkington, Noel}, booktitle = {Proceedings of the 32nd annual ACM symposium on Theory of computing}, isbn = {9781581131840}, location = {Portland, OR, USA}, pages = {273 -- 277}, publisher = {ACM}, title = {{Smoothing and cleaning up slivers}}, doi = {10.1145/335305.335338}, year = {2000}, } @inbook{3572, abstract = {Allzulange wurde die spielhafte Beschäftigung als Gegensatz zu ernsthafter Arbeit gesehen. Dieser Artikel propagiert die spielerische Untersuchung von Kreis- und Kugelmengen. Gleichzeitig belegt er die nutzbare Anwendung von elementaren Einsichten in der Molekularbiologie und allgemeiner in der Beschreibung von Form und Verformung.}, author = {Edelsbrunner, Herbert}, booktitle = {Zur Kunst des formalen Denkens}, isbn = {3851653580}, pages = {153 -- 171}, publisher = {Passagen Verlag}, title = {{Spielereien mit Kreisen und Kugeln. Zum Thema Form und Verformung}}, year = {2000}, } @article{3583, abstract = {The Delaunay triangulation of a finite point set is a central theme in computational geometry. It finds its major application in the generation of meshes used in the simulation of physical processes. This paper connects the predominantly combinatorial work in classical computational geometry with the numerical interest in mesh generation. It focuses on the two- and three-dimensional case and covers results obtained during the twentieth century.}, author = {Edelsbrunner, Herbert}, journal = {Acta Numerica}, pages = {133 -- 213}, publisher = {Cambridge University Press}, title = {{Triangulations and meshes in computational geometry}}, doi = {10.1017/S0962492900001331}, volume = {9}, year = {2000}, }