@article{11681, abstract = {We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of Ω (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of Ω (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems.}, author = {Henzinger, Monika H and Fredman, M. L.}, issn = {1432-0541}, journal = {Algorithmica}, keywords = {Dynamic planarity testing, Dynamic connectivity testing, Lower bounds, Cell probe model}, number = {3}, pages = {351--362}, publisher = {Springer Nature}, title = {{Lower bounds for fully dynamic connectivity problems in graphs}}, doi = {10.1007/pl00009228}, volume = {22}, year = {1998}, } @inproceedings{11682, abstract = {We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.}, author = {Agarwal, P. K. and EppsteinL. J. Guibas, D. and Henzinger, Monika H}, booktitle = {Proceedings of the 39th Annual Symposium on Foundations of Computer Science}, isbn = {0-8186-9172-7}, issn = {0272-5428}, location = {Palo Alto, CA, United States}, pages = {596--605}, title = {{Parametric and kinetic minimum spanning trees}}, doi = {10.1109/SFCS.1998.743510}, year = {1998}, } @article{1954, abstract = { We have examined the effects of heat stress on electron transfer in the thylakoid membrane of an engineered plastid ndh deletion mutant, Δ1, incapable of performing the Ndh-mediated reduction of the plastoquinone pool in the chloroplast. Upon heat stress in the dark, the rate of PSII- independent reduction of PSI after subsequent illumination by far-red light is dramatically enhanced in both Δ1 and a wild-type control plant (WT). In contrast, in the dark, only the WT shows an increase in the reduction state of the plastoquinone pool. We conclude that the heat stress-induced reduction of the intersystem electron transport chain can be mediated by Ndh- independent pathways in the light but that in the dark the dominant pathway for reduction of the plastoquinone pool is catalysed by the Ndh complex. Our results therefore demonstrate a functional role for the Ndh complex in the dark. }, author = {Sazanov, Leonid A and Burrows, Paul and Nixon, Peter}, issn = {0014-5793}, journal = {FEBS Letters}, number = {1}, pages = {115 -- 118}, publisher = {Elsevier}, title = {{The chloroplast Ndh complex mediates the dark reduction of the plastoquinone pool in response to heat stress in tobacco leaves}}, doi = {10.1016/S0014-5793(98)00573-0}, volume = {429}, year = {1998}, } @article{1955, abstract = {The plastid genomes of several plants contain homologues, termed ndh genes, of genes encoding subunits of the NADH:ubiquinone oxidoreductase or complex I of mitochondria and eubacteria. The functional significance of the Ndh proteins in higher plants is uncertain. We show here that tobacco chloroplasts contain a protein complex of 550 kDa consisting of at least three of the ndh gene products: NdhI, NdhJ and NdhK. We have constructed mutant tobacco plants with disrupted ndhC, ndhK and ndhJ plastid genes, indicating that the Ndh complex is dispensible for plant growth under optimal growth conditions. Chlorophyll fluorescence analysis shows that in vivo the Ndh complex catalyses the post-illumination reduction of the plastoquinone pool and in the light optimizes the induction of photosynthesis under conditions of water stress. We conclude that the Ndh complex catalyses the reduction of the plastoquinone pool using stromal reductant and so acts as a respiratory complex. Overall, our data are compatible with the participation of the Ndh complex in cyclic electron flow around the photosystem I complex in the light and possibly in a chloroplast respiratory chain in the dark.}, author = {Burrows, Paul and Sazanov, Leonid A and Sváb, Zóra and Maliga, Pàl and Nixon, Peter}, issn = {0261-4189}, journal = {EMBO Journal}, number = {4}, pages = {868 -- 876}, publisher = {Wiley-Blackwell}, title = {{Identification of a functional respiratory complex in chloroplasts through analysis of tobacco mutants containing disrupted plastid ndh genes}}, doi = {10.1093/emboj/17.4.868}, volume = {17}, year = {1998}, } @article{1956, abstract = { The plastid genomes of several plants contain ndh genes-homologues of genes encoding subunits of the proton-pumping NADH:ubiquinone oxidoreductase, or complex I, involved in respiration in mitochondria and eubacteria. From sequence similarities with these genes, the ndh gene products have been suggested to form a large protein complex (Ndh complex); however, the structure and function of this complex remains to be established. Herein we report the isolation of the Ndh complex from the chloroplasts of the higher plant Pisum sativum. The purification procedure involved selective solubilization of the thylakoid membrane with dodecyl maltoside, followed by two anion-exchange chromatography steps and one size-exclusion chromatography step. The isolated Ndh complex has an apparent total molecular mass of approximately 550 kDa and according to SDS/PAGE consists of at least 16 subunits including NdhA, NdhI, NdhJ, NdhK, and NdhH, which were identified by N-terminal sequencing and immunoblotting. The Ndh complex showed an NADH- and deamino-NADH-specific dehydrogenase activity, characteristic of complex I, when either ferricyanide or the quinones menadione and duroquinone were used as electron acceptors. This study describes the isolation of the chloroplast analogue of the respiratory complex I and provides direct evidence for the function of the plastid Ndh complex as an NADH:plastoquinone oxidoreductase. Our results are compatible with a dual role for the Ndh complex in the chloro-respiratory and cyclic photophosphorylation pathways.}, author = {Sazanov, Leonid A and Burrows, Paul and Nixon, Peter}, issn = {0027-8424}, journal = {PNAS}, number = {3}, pages = {1319 -- 1324}, publisher = {National Academy of Sciences}, title = {{The plastid ndh genes code for an NADH-specific dehydrogenase: Isolation of a complex I analogue from pea thylakoid membranes}}, doi = {10.1073/pnas.95.3.1319}, volume = {95}, year = {1998}, } @inproceedings{4603, abstract = {Alternating transition systems are a general model for composite systems which allow the study of collaborative as well as adversarial relationships between individual system components. Unlike in labeled transition systems, where each transition corresponds to a possible step of the system (which may involve some or all components), in alternating transition systems, each transition corresponds to a possible move in a game between the components. In this paper, we study refinement relations between alternating transition systems, such as “Does the implementation refine the set A of specification components without constraining the components not in A?” In particular, we generalize the definitions of the simulation and trace containment preorders from labeled transition systems to alternating transition systems. The generalizations are called alternating simulation and alternating trace containment. Unlike existing refinement relations, they allow the refinement of individual components within the context of a composite system description. We show that, like ordinary simulation, alternating simulation can be checked in polynomial time using a fixpoint computation algorithm. While ordinary trace containment is PSPACE-complete, we establish alternating trace containment to be EXPTIME-complete. Finally, we present logical characterizations for the two preorders in terms of ATL, a temporal logic capable of referring to games between system components.}, author = {Alur, Rajeev and Henzinger, Thomas A and Kupferman, Orna and Vardi, Moshe}, booktitle = {Proceedings of the 9th Interantional Conference on Concurrency Theory}, isbn = {978-3-540-64896-3}, location = {Nice, France}, pages = {163 -- 178}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Alternating refinement relations}}, doi = {10.1007/BFb0055622}, volume = {1466}, year = {1998}, } @inproceedings{4604, author = {Alur, Rajeev and Henzinger, Thomas A and Mang, Freddy and Qadeer, Shaz and Rajamani, Sriram and Tasiran, Serdar}, booktitle = {Proceedings of the 10th International Conference on Computer Aided Verification}, isbn = {9783540646082}, location = {Vancouver, Canada}, pages = {521 -- 525}, publisher = {Springer}, title = {{Mocha: Modularity in model checking}}, doi = {10.1007/BFb0028774}, volume = {1427}, year = {1998}, } @inproceedings{4606, abstract = {In formal design verification, successful model checking is typically preceded by a laborious manual process of constructing design abstractions. We present a methodology for partially—and in some cases, fully—bypassing the abstraction process. For this purpose, we provide to the designer abstraction operators which, if used judiciously in the description of a design, structure the corresponding state space hierarchically. This structure can then be exploited by verification tools, and makes possible the automatic and exhaustive exploration of state spaces that would otherwise be out of scope for existing model checkers. Specifically, we present the following contributions: - A temporal abstraction operator that aggregates transitions and hides intermediate steps. Mathematically, our abstraction operator is a function that maps a flat transition system into a two-level hierarchy where each atomic upper-level transition expands into an entire lower-level transition system. For example, an arithmetic operation may expand into a sequence of bit operations. - A BDD-based algorithm for the symbolic exploration of multi-level hierarchies of transition systems. The algorithm traverses a level-n transition by expanding the corresponding level-(n − 1) transition system on-the-fly. The level-n successors of a state are determined by computing a level-(n − 1) reach set, which is then immediately released from memory. In this fashion, we can exhaustively explore hierarchically structured state spaces whose flat counterparts cause memory overflows. - We experimentally demonstrate the efficiency of our method with three examples—a multiplier, a cache coherence protocol, and a multiprocessor system. In the first two examples, we obtain significant improvements in run times and peak BDD sizes over traditional state-space search. The third example cannot be model checked at all using conventional methods (without manual abstractions), but can be analyzed fully automatically using transition hierarchies.}, author = {Alur, Rajeev and Henzinger, Thomas A and Rajamani, Sriram}, booktitle = {Proceedings of the 4th International Conference on Tools and Algorithms for the Construction and Analysis of Systems}, isbn = {9783540643562}, location = {Lisbon, Portugal}, pages = {330 -- 344}, publisher = {Springer}, title = {{Symbolic exploration of transition hierarchies}}, doi = {10.1007/BFb0054181}, volume = {1384}, year = {1998}, } @inproceedings{4639, abstract = {An open system can be modeled as a two-player game between the system and its environment. At each round of the game, player 1 (the system) and player 2 (the environment) independently and simultaneously choose moves, and the two choices determine the next state of the game. Properties of open systems can be modeled as objectives of these two-player games. For the basic objective of reachability-can player 1 force the game to a given set of target states?-there are three types of winning states, according to the degree of certainty with which player 1 can reach the target. From type-1 states, player 1 has a deterministic strategy to always reach the target. From type-2 states, player 1 has a randomized strategy to reach the target with probability 1. From type-3 states, player 1 has for every real ε>0 a randomized strategy to reach the target with probability greater than 1-ε. We show that for finite state spaces, all three sets of winning states can be computed in polynomial time: type-1 states in linear time, and type-2 and type-3 states in quadratic time. The algorithms to compute the three sets of winning states also enable the construction of the winning and spoiling strategies. Finally, we apply our results by introducing a temporal logic in which all three kinds of winning conditions can be specified, and which can be model checked in polynomial time. This logic, called Randomized ATL, is suitable for reasoning about randomized behavior in open (two-agent) as well as multi-agent systems}, author = {De Alfaro, Luca and Henzinger, Thomas A and Kupferman, Orna}, booktitle = { Proceedings 39th Annual Symposium on Foundations of Computer Science}, isbn = {0818691727}, location = {Palo Alto, CA, United States of America}, pages = {564 -- 575}, publisher = {IEEE}, title = {{Concurrent reachability games}}, doi = {10.1109/SFCS.1998.743507 }, year = {1998}, } @article{6160, abstract = {Natural isolates of C. elegans exhibit either solitary or social feeding behavior. Solitary foragers move slowly on a bacterial lawn and disperse across it, while social foragers move rapidly on bacteria and aggregate together. A loss-of-function mutation in the npr-1 gene, which encodes a predicted G protein–coupled receptor similar to neuropeptide Y receptors, causes a solitary strain to take on social behavior. Two isoforms of NPR-1 that differ at a single residue occur in the wild. One isoform, NPR-1 215F, is found exclusively in social strains, while the other isoform, NPR-1 215V, is found exclusively in solitary strains. An NPR-1 215V transgene can induce solitary feeding behavior in a wild social strain. Thus, isoforms of a putative neuropeptide receptor generate natural variation in C. elegans feeding behavior.}, author = {de Bono, Mario and Bargmann, Cornelia I}, issn = {0092-8674}, journal = {Cell}, number = {5}, pages = {679--689}, publisher = {Elsevier}, title = {{Natural variation in a neuropeptide Y receptor homolog modifies social behavior and food response in C. elegans}}, doi = {10.1016/s0092-8674(00)81609-8}, volume = {94}, year = {1998}, } @article{1449, abstract = {In this paper we consider a canonical compactification of M, the moduli space of stable Higgs bundles with fixed determinant of odd degree over a Riemann surface Σ, producing a projective variety M̄ = M ∪ Z. We give a detailed study of the spaces M̄, Z and M. In doing so we reprove some assertions of Laumon and Thaddeus on the nilpotent cone.}, author = {Hausel, Tamas}, issn = {1435-5345}, journal = {Journal fur die Reine und Angewandte Mathematik}, number = {503}, pages = {169 -- 192}, publisher = {Walter de Gruyter}, title = {{Compactification of moduli of Higgs bundles}}, doi = {10.1515/crll.1998.096}, volume = {1998}, year = {1998}, } @article{1450, abstract = {In this paper we consider the topological side of a problem which is the analogue of Sen's S-duality testing conjecture for Hitchin's moduli space M of rank 2 stable Higgs bundles of fixed determinant of odd degree over a Riemann surface ∑. We prove that all intersection numbers in the compactly supported cohomology of M vanish, i.e. "there are no topological L2 harmonic forms on M". This result generalizes the well known vanishing of the Euler characteristic of the moduli space of rank 2 stable bundles N of fixed determinant of odd degree over ∑. Our proof shows that the vanishing of all intersection numbers of H* cpt(M) is given by relations analogous to the Mumford relations in the cohomology ring of N.}, author = {Hausel, Tamas}, issn = {1095-0761}, journal = {Advances in Theoretical and Mathematical Physics}, number = {5}, pages = {1011 -- 1040}, publisher = {International Press}, title = {{Vanishing of intersection numbers on the moduli space of Higgs bundles}}, doi = {10.4310/ATMP.1998.v2.n5.a3}, volume = {2}, year = {1998}, } @inproceedings{11926, abstract = {We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline alaorithm to the exoected number of reauests accepted by our algorithm is O(jlog n + log log M)(log n + log M) log n), where M is the number of multicast groups and n is the number of nodes in the nraoh. We show that this is close to optimum by presenting-an*R(log nlog M) lower bound on this ratio for anv randomized online algorithm against an oblivious adversary, when M is much lar&r than the link capacities. Our lower bound applies even in the restricted case where the link capacities are much larger than bandwidth requested by a single multicast. We also present a simple proof showing that it is impossible to be competitive against an adaptive online adversary. As in the previous online routing algorithms, our algorithm uses edge-costs when deciding on which is the best path to use. In contrast to the nrevious comnetitive aleorithms in the throughput modei, our cost is-not a direct function of the edne load. The new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups. }, author = {Goel, Ashish and Henzinger, Monika H and Plotkin, Serge}, booktitle = {9th Annual ACM SIAM Symposium on Discrete Algorithms}, isbn = {0898714109}, location = {San Francisco, CA, United States}, pages = {97--106}, publisher = {Society for Industrial and Applied Mathematics}, title = {{An online throughput-competitive algorithm for multicast routing and admission control}}, year = {1998}, } @article{3487, abstract = {It is widely accepted that individual neurons in the central nervous system release only a single fast transmitter. The possibility of corelease of fast neurotransmitters was examined by making paired recordings from synaptically connected neurons in spinal cord slices. Unitary inhibitory postsynaptic currents generated at interneuron-motoneuron synapses consisted of a strychnine-sensitive, glycine receptor-mediated component and a bicuculline-sensitive, γ-aminobutyric acid (GABA)(A) receptor-mediated component. These results indicate that spinal interneurons release both glycine and GABA to activate functionally distinct receptors in their postsynaptic target cells. A subset of miniature synaptic currents also showed both components, consistent with corelease from individual synaptic vesicles.}, author = {Jonas, Peter M and Bischofberger, Joseph and Sandkühler, Jürgen}, issn = {0036-8075}, journal = {Science}, number = {5375}, pages = {419 -- 424}, publisher = {American Association for the Advancement of Science}, title = {{Corelease of two fast neurotransmitters at a central synapse}}, doi = {10.1126/science.281.5375.419}, volume = {281}, year = {1998}, } @article{3488, abstract = {We have examined gating and pharmacological characteristics of somatic K+ channels in fast-spiking interneurons and regularly spiking principal neurons of hippocampal slices. In nucleated patches isolated from basket cells of the dentate gyrus, a fast delayed rectifier K+ current component that was highly sensitive to tetraethylammonium (TEA) and 4-aminopyridine (4- AP) (half-maximal inhibitory concentrations <0.1 mM) predominated, contributing an average of 58% to the total K+ current in these cells. By contrast, in pyramidal neurons of the CA1 region a rapidly inactivating A- type K+ current component that was TEA-resistant prevailed, contributing 61% to the total K+ current. Both types of neurons also showed small amounts of the K+ current component mainly found in the other type of neuron and, in addition, a slow delayed rectifier K+ current component with intermediate properties (sow inactivation, intermediate sensitivity to TEA). Single-cell RT-PCR analysis of mRNA revealed that Kv3 (Kv3.1, Kv3.2) subunit transcripts were expressed in almost all (89%) of the interneurons but only in 17% of the pyramidal neurons. In contrast, Kv4 (Kv4.2, Kv4.3) subunit mRNAs were present in 87% of pyramidal neurons but only in 55% of interneurons. Selective block of fast delayed rectifier K+ channels, presumably assembled from Kv3 subunits, by 4-AP reduced substantially the action potential frequency in interneurons. These results indicate that the differential expression of Kv3 and Kv4 subunits shapes the action potential phenotypes of principal neurons and interneurons in the cortex.}, author = {Martina, Marco and Schultz, Jobst and Ehmke, Heimo and Monyer, Hannah and Jonas, Peter M}, issn = {0270-6474}, journal = {Journal of Neuroscience}, number = {20}, pages = {8111 -- 8125}, publisher = {Society for Neuroscience}, title = {{Functional and molecular differences between voltage-gated K+ channels of fast-spiking interneurons and pyramidal neurons of rat hippocampus}}, doi = {10.1523/JNEUROSCI.18-20-08111.1998}, volume = {18}, year = {1998}, } @misc{3506, abstract = {A method of geometric morphing between a first object having a first shape and a second object having a second shape. The method includes the steps of generating a first Delaunay complex corresponding to the first shape and a second Delaunay complex corresponding to the second shape and generating a plurality of intermediary Delaunay complexes defined by a continuous family of mixed shapes corresponding to a mixing of the first shape and the second shape. The method further includes the steps of constructing a first skin corresponding to the first Delaunay complex and a second skin corresponding to the second Delaunay complex and constructing a plurality of intermediary skins corresponding to the plurality of intermediary Delaunay complexes. The first skin, second skin and plurality of intermediary skins may be visually displayed on an output device.}, author = {Edelsbrunner, Herbert and Fu, Ping}, title = {{Apparatus and method for geometric morphing}}, year = {1998}, } @article{3521, abstract = {Spike transmission probability between pyramidal cells and interneurons in the CA1 pyramidal layer was investigated in the behaving rat by the simultaneous recording of neuronal ensembles. Population synchrony was strongest during sharp wave (SPW) bursts. However, the increase was three times larger for pyramidal cells than for interneurons. The contribution of single pyramidal cells to the discharge of interneurons was often large (up to 0.6 probability), as assessed by the presence of significant (<3 ms) peaks in the cross-correlogram. Complex-spike bursts were more effective than single spikes. Single cell contribution was higher between SPW bursts than during SPWs or theta activity. Hence, single pyramidal cells can reliably discharge interneurons, and the probability of spike transmission is behavior dependent.}, author = {Csicsvari, Jozsef L and Hirase, Hajima and Czurkó, András and Buzsáki, György}, issn = {0896-6273}, journal = {Neuron}, number = {1}, pages = {179 -- 189}, publisher = {Elsevier}, title = {{Reliability and state dependence of pyramidal cell-interneuron synapses in the hippocampus: an ensemble approach in the behaving rat}}, doi = {10.1016/S0896-6273(00)80525-5}, volume = {21}, year = {1998}, } @article{3525, author = {Nádasdy, Zoltán and Jozsef Csicsvari and Hirase, Hajima and Czurkó, András and Buzsáki, György}, journal = {European Journal of Neuroscience}, number = {Suppl. 10}, pages = {9409 -- 9409}, publisher = {Wiley-Blackwell}, title = {{Persistence and temporal compression of spike sequences during fast field oscillation in the hippocampus}}, volume = {10}, year = {1998}, } @article{3527, author = {Jozsef Csicsvari and Czurkó, András and Hirase, Hajima and Buzsáki, György}, journal = {European Journal of Neuroscience}, number = {Suppl. 10}, pages = {2553 -- 2553}, publisher = {Wiley-Blackwell}, title = {{Monosynaptic interactions between CA1 Pyramidal cells and interneuron in the behaving rat}}, volume = {10}, year = {1998}, } @article{3535, author = {Hirase, Hajima and Czurkó, András and Jozsef Csicsvari and Buzsáki, György}, journal = {European Journal of Neuroscience}, number = {Suppl. 10}, pages = {9932 -- 9932}, publisher = {Wiley-Blackwell}, title = {{Hippocampal pyramidal neutrons “space-clamped” in a running wheel task: Place cells or path integrators?}}, volume = {10}, year = {1998}, }