@article{2996,
abstract = {Plants, compared to animals, exhibit an amazing adaptability and plasticity in their development. This is largely dependent on the ability of plants to form new organs, such as lateral roots, leaves, and flowers during postembryonic development. Organ primordia develop from founder cell populations into organs by coordinated cell division and differentiation. Here, we show that organ formation in Arabidopsis involves dynamic gradients of the signaling molecule auxin with maxima at the primordia tips. These gradients are mediated by cellular efflux requiring asymmetrically localized PIN proteins, which represent a functionally redundant network for auxin distribution in both aerial and underground organs. PIN1 polar localization undergoes a dynamic rearrangement, which correlates with establishment of auxin gradients and primordium development. Our results suggest that PIN-dependent, local auxin gradients represent a common module for formation of all plant organs, regardless of their mature morphology or developmental origin.
},
author = {Eva Benková and Michniewicz, Marta and Sauer, Michael and Teichmann, Thomas and Seifertová, Daniela and Jürgens, Gerd and Jirí Friml},
journal = {Cell},
number = {5},
pages = {591 -- 602},
publisher = {Cell Press},
title = {{Local, efflux-dependent auxin gradients as a common module for plant organ formation}},
doi = {10.1016/S0092-8674(03)00924-3},
volume = {115},
year = {2003},
}
@misc{3139,
abstract = {Significant advances have been made during the past few years in our understanding of how the spinal monosynaptic reflex develops. Transcription factors in the Neurogenin, Runt, ETS, and LIM families control sequential steps of the specification of various subtypes of dorsal root ganglia sensory neurons. The initiation of muscle spindle differentiation requires neuregulin 1, derived from Ia afferent sensory neurons, and signaling through ErbB receptors in intrafusal muscle fibers. Several retrograde signals from the periphery are important for the establishment of late connectivity in the reflex circuit. Finally, neurotrophin 3 released from muscle spindles regulates the strength of sensory-motor connections within the spinal cord postnatally.},
author = {Chen, Hsiao Huei and Simon Hippenmeyer and Arber, Silvia and Frank, Eric},
booktitle = {Current Opinion in Neurobiology},
number = {1},
pages = {96 -- 102},
publisher = {Elsevier},
title = {{Development of the monosynaptic stretch reflex circuit}},
doi = {10.1016/S0959-4388(03)00006-0},
volume = {13},
year = {2003},
}
@article{3150,
abstract = {Tripartite G-protein-coupled receptors (GPCRs) represent one of the largest groups of signal transducers, transmitting signals from hormones, neuropeptides, odorants, food and light. Ligand-bound receptors catalyse GDP/GTP exchange on the G-protein α-subunit (Gα), leading to α-GTP separation from the βγ subunits and pathway activation. Activating mutations in the receptors or G proteins underlie many human diseases, including some cancers, dwarfism and premature puberty. Regulators of G-protein signalling (RGS proteins) are known to modulate the level and duration of ligand-induced signalling by accelerating the intrinsic GTPase activity of the Gα subunit, and thus reformation of the inactive GDP-bound Gα. Here we find that even in the absence of receptor, mutation of the RGS family member Sst2 (refs 6-9) permits spontaneous activation of the G-protein-coupled mating pathway in Saccharomyces cerevisiae at levels normally seen only in the presence of ligand. Our work demonstrates the occurence of spontaneous tripartite G-protein signalling in vivo and identifies a requirement for RGS proteins in preventing such receptor-independent activation.},
author = {Daria Siekhaus and Drubin, David G},
journal = {Nature Cell Biology},
number = {3},
pages = {231 -- 235},
publisher = {Nature Publishing Group},
title = {{Spontaneous receptor-independent heterotrimeric G-protein signalling in an RGS mutant}},
doi = {10.1038/ncb941},
volume = {5},
year = {2003},
}
@article{3151,
abstract = {Biosynthesis of most peptide hormones and neuropeptides requires proteolytic excision of the active peptide from inactive proprotein precursors, an activity carried out by subtilisin-like proprotein convertases (SPCs) in constitutive or regulated secretory pathways. The Drosophila amontillado (amon) gene encodes a homolog of the mammalian PC2 protein, an SPC that functions in the regulated secretory pathway in neuroendocrine tissues. We have identified amon mutants by isolating ethylmethanesulfonate (EMS)-induced lethal and visible mutations that define two complementation groups in the amon interval at 97D1 of the third chromosome. DNA sequencing identified the amon complementation group and the DNA sequence change for each of the nine amon alleles isolated. amon mutants display partial embryonic lethality, are defective in larval growth, and arrest during the first to second instar larval molt. Mutant larvae can be rescued by heat-shock-induced expression of the amon protein. Rescued larvae arrest at the subsequent larval molt, suggesting that amon is also required for the second to third instar larval molt. Our data indicate that the amon proprotein convertase is required during embryogenesis and larval development in Drosophila and support the hypothesis that AMON acts to proteolytically process peptide hormones that regulate hatching, larval growth, and larval ecdysis.},
author = {Rayburn, Lowell Y and Gooding, Holly C and Choksi, Semil P and Maloney, Dhea and Kidd, Ambrose R and Daria Siekhaus and Bender, Michael},
journal = {Genetics},
number = {1},
pages = {227 -- 237},
publisher = {Genetics Society of America},
title = {{Amontillado, the Drosophila homolog of the prohormone processing protease PC2, is required during embryogenesis and early larval development}},
volume = {163},
year = {2003},
}
@article{166,
abstract = {For any number field k, upper bounds are established for the number of k-rational points of bounded height on non-singular del Pezzo surfaces defined over k, which are equipped with suitable conic bundle structures over k.},
author = {Browning, Timothy D and Swarbick Jones, M},
journal = {Proceedings of the Bonn session in analytic number theory and diophantine equations},
publisher = {Mathematisches Institut der Universität Bonn},
title = {{Counting rational points on del Pezzo surfaces of degree 5}},
volume = {360},
year = {2003},
}
@article{1959,
abstract = {The molecular organization of bacterial NADH: ubiquinone oxidoreductase (complex I or NDH-1) is not established, apart from a rough separation into dehydrogenase, connecting and membrane domains. In this work, complex I was purified from Escherichia coli and fragmented by replacing dodecylmaltoside with other detergents. Exchange into decyl maltoside led to the removal of the hydrophobic subunit NuoL from the otherwise intact complex. Diheptanoyl phosphocholine led to the loss of NuoL and NuoM subunits, whereas other subunits remained in the complex. The presence of N,N-dimethyldodecylamine N-oxide or Triton X-100 led to further disruption of the membrane domain into fragments containing NuoL/M/N, NuoA/K/N, and NuoH/J subunits. Among the hydrophilic subunits, NuoCD was most readily dissociated from the complex, whereas NuoB was partially dissociated from the peripheral arm assembly in N,N-dimethyldodecylamine N-oxide. A model of subunit arrangement in bacterial complex I based on these data is proposed. Subunits NuoL and NuoM, which are homologous to antiporters and are implicated in proton pumping, are located at the distal end of the membrane arm, spatially separated from the redox centers of the peripheral arm. This is consistent with proposals that the mechanism of proton pumping by complex I is likely to involve long range conformational changes.},
author = {Holt, Peter J and Morgan, David J and Leonid Sazanov},
journal = {Journal of Biological Chemistry},
number = {44},
pages = {43114 -- 43120},
publisher = {American Society for Biochemistry and Molecular Biology},
title = {{The location of NuoL and NuoM subunits in the membrane domain of the Escherichia coli Complex I: implications for the mechanism of proton pumping}},
doi = {10.1074/jbc.M308247200},
volume = {278},
year = {2003},
}
@article{1960,
abstract = {NADH-ubiquinone oxidoreductase (complex I or NDH-1) was purified from the BL21 strain of Escherichia coli using an improved procedure. The complex was effectively stabilized by addition of divalent cations and lipids, making the preparation suitable for structural studies. The ubiquinone reductase activity of the enzyme was fully restored by addition of native E. coli lipids. Two different two-dimensional crystal forms, with p2 and p3 symmetry, were obtained using lipids containing native E. coli extracts. Analysis of the crystals showed that they are formed by fully intact complex I in an L-shaped conformation. Activity assays and single particle analysis indicated that complex I maintains this structure in detergent solution and does not adopt a different conformation in the active state. Thus, we provide the first experimental evidence that complex I from E. coli has an L-shape in a lipid bilayer and confirm that this is also the case for the active enzyme in solution. This suggests strongly that bacterial complex I exists in an L-shaped conformation in vivo. Our results also indicate that native lipids play an important role in the activation, stabilization and, as a consequence, crystallization of purified complex I from E. coli.},
author = {Leonid Sazanov and Carroll, Joe D and Holt, Peter J and Toime, Laurence J and Fearnley, Ian M},
journal = {Journal of Biological Chemistry},
number = {21},
pages = {19483 -- 19491},
publisher = {American Society for Biochemistry and Molecular Biology},
title = {{A role for native lipids in the stabilization and two dimensional crystallization of the Escherichia coli NADH ubiquinone oxidoreductase (complex I)}},
doi = {10.1074/jbc.M208959200},
volume = {278},
year = {2003},
}
@article{847,
abstract = {The accumulation of genome-wide information on single nucleotide polymorphisms in humans provides an unprecedented opportunity to detect the evolutionary forces responsible for heterogeneity of the level of genetic variability across loci. Previous studies have shown that history of recombination events has produced long haplotype blocks in the human genome, which contribute to this heterogeneity. Other factors, however, such as natural selection or the heterogeneity of mutation rates across loci, may also lead to heterogeneity of genetic variability. We compared synonymous and non-synonymous variability within human genes with their divergence from murine orthologs. We separately analyzed the non-synonymous variants predicted to damage protein structure or function and the variants predicted to be functionally benign. The predictions were based on comparative sequence analysis and, in some cases, on the analysis of protein structure. A strong correlation between non-synonymous, benign variability and non-synonymous human-mouse divergence suggests that selection played an important role in shaping the pattern of variability in coding regions of human genes. However, the lack of correlation between deleterious variability and evolutionary divergence shows that a substantial proportion of the observed non-synonymous single-nucleotide polymorphisms reduces fitness and never reaches fixation. Evolutionary and medical implications of the impact of selection on human polymorphisms are discussed.},
author = {Sunyaev, Shamil R and Fyodor Kondrashov and Bork, Peer and Ramensky, Vasily},
journal = {Human Molecular Genetics},
number = {24},
pages = {3325 -- 3330},
publisher = {Oxford University Press},
title = {{Impact of selection, mutation rate and genetic drift on human genetic variation}},
doi = {10.1093/hmg/ddg359},
volume = {12},
year = {2003},
}
@article{876,
abstract = {Alternative splicing is thought to be a major source of functional diversity in animal proteins. We analyzed the evolutionary conservation of proteins encoded by alternatively spliced genes and predicted the ancestral state for 73 cases of alternative splicing (25 insertions and 48 deletions). The amino acid sequences of most of the inserts in proteins produced by alternative splicing are as conserved as the surrounding sequences. Thus, alternative splicing often creates novel isoforms by the insertion of new, functional protein sequences that probably originated from noncoding sequences of introns.},
author = {Fyodor Kondrashov and Koonin, Eugene V},
journal = {Trends in Genetics},
number = {3},
pages = {115 -- 119},
publisher = {Elsevier},
title = {{Evolution of alternative splicing: Deletions, insertions and origin of functional parts of proteins from intron sequences}},
doi = {10.1016/S0168-9525(02)00029-X},
volume = {19},
year = {2003},
}
@article{1457,
abstract = {Among the major mathematical approaches to mirror symmetry are those of Batyrev-Borisov and Stromdnger-Yau-Zaslow (SYZ). The first is explicit and amenable to computation but is not clearly related to the physical motivation; the second is the opposite. Furthermore, it is far from obvious that mirror partners in one sense will also be mirror partners in the other. This paper concerns a class of examples that can be shown to satisfy the requirements of SYZ, but whose Hodge numbers are also equal. This provides significant evidence in support of SYZ. Moreover, the examples are of great interest in their own right: they are spaces of flat SLr-connections on a smooth curve. The mirror is the corresponding space for the Langlands dual group PGLr. These examples therefore throw a bridge from mirror symmetry to the duality theory of Lie groups and, more broadly, to the geometric Langlands program.},
author = {Tamas Hausel and Thaddeus, Michael},
journal = {Inventiones Mathematicae},
number = {1},
pages = {197 -- 229},
publisher = {Springer},
title = {{Mirror symmetry, langlands duality, and the Hitchin system}},
doi = {10.1007/s00222-003-0286-7},
volume = {153},
year = {2003},
}
@article{1458,
abstract = {The moduli space of stable bundles of rank $2$ and degree $1$ on a Riemann surface has rational cohomology generated by the so-called universal classes. The work of Baranovsky, King-Newstead, Siebert-Tian and Zagier provided a complete set of relations between these classes, expressed in terms of a recursion in the genus. This paper accomplishes the same thing for the noncompact moduli spaces of Higgs bundles, in the sense of Hitchin and Simpson. There are many more independent relations than for stable bundles, but in a sense the answer is simpler, since the formulas are completely explicit, not recursive. The results of Kirwan on equivariant cohomology for holomorphic circle actions are of key importance.},
author = {Tamas Hausel and Thaddeus, Michael},
journal = {Journal of the American Mathematical Society},
number = {2},
pages = {303 -- 329},
publisher = {American Mathematical Society},
title = {{Relations in the cohomology ring of the moduli space of rank 2 Higgs bundles}},
doi = {10.1090/S0894-0347-02-00417-4},
volume = {16},
year = {2003},
}
@article{1459,
abstract = {In this paper we explicitly calculate the analogue of the 't Hooft SU (2) Yang-Mills instantons on Gibbons-Hawking multi-centered gravitational instantons, which come in two parallel families: the multi-Eguchi-Hanson, or Ak ALE gravitational instantons and the multi-Taub-NUT spaces, or Ak ALF gravitational instantons. We calculate their energy and find the reducible ones. Following Kronheimer we also exploit the U(1) invariance of our solutions and study the corresponding explicit singular SU (2) magnetic monopole solutions of the Bogomolny equations on flat ℝ3.},
author = {Etesi, Gábor and Tamas Hausel},
journal = {Communications in Mathematical Physics},
number = {2},
pages = {275 -- 288},
publisher = {Springer},
title = {{On Yang-Mills instantons over multi-centered gravitational instantons}},
doi = {10.1007/s00220-003-0806-8},
volume = {235},
year = {2003},
}
@inproceedings{3170,
abstract = {Geodesic active contours and graph cuts are two standard image segmentation techniques. We introduce a new segmentation method combining some of their benefits. Our main intuition is that any cut on a graph embedded in some continuous space can be interpreted as a contour (in 2D) or a surface (in 3D). We show how to build a grid graph and set its edge weights so that the cost of cuts is arbitrarily close to the length (area) of the corresponding contours (surfaces) for any anisotropic Riemannian metric. There are two interesting consequences of this technical result. First, graph cut algorithms can be used to find globally minimum geodesic contours (minimal surfaces in 3D) under arbitrary Riemannian metric for a given set of boundary conditions. Second, we show how to minimize metrication artifacts in existing graph-cut based methods in vision. Theoretically speaking, our work provides an interesting link between several branches of mathematics -differential geometry, integral geometry, and combinatorial optimization. The main technical problem is solved using Cauchy-Crofton formula from integral geometry.},
author = {Boykov, Yuri and Vladimir Kolmogorov},
pages = {26 -- 33},
publisher = {IEEE},
title = {{Computing geodesics and minimal surfaces via graph cuts}},
doi = {10.1109/ICCV.2003.1238310},
volume = {1},
year = {2003},
}
@inproceedings{3171,
abstract = {Reconstructing a 3-D scene from more than one camera is a classical problem in computer vision. One of the major sources of difficulty is the fact that not all scene elements are visible from all cameras. In the last few years, two promising approaches have been developed 11,12 that formulate the scene reconstruction problem in terms of energy minimization, and minimize the energy using graph cuts. These energy minimization approaches treat the input images symmetrically, handle visibility constraints correctly, and allow spatial smoothness to be enforced. However, these algorithm propose different problem formulations, and handle a limited class of smoothness terms. One algorithm 11 uses a problem formulation that is restricted to two-camera stereo, and imposes smoothness between a pair of cameras. The other algorithm 12 can handle an arbitrary number of cameras, but imposes smoothness only with respect to a single camera. In this paper we give a more general energy minimization formulation for the problem, which allows a larger class of spatial smoothness constraints. We show that our formulation includes both of the previous approaches as special cases, as well as permitting new energy functions. Experimental results on real data with ground truth are also included. },
author = {Vladimir Kolmogorov and Zabih, Ramin and Gortler, Steven},
pages = {501 -- 516},
publisher = {Springer},
title = {{Generalized multi camera scene reconstruction using graph cuts}},
doi = {10.1007/978-3-540-45063-4_32},
volume = {2683},
year = {2003},
}
@inproceedings{3174,
abstract = {We address visual correspondence problems without assuming that scene points have similar intensities in different views. This situation is common, usually due to non-lambertian scenes or to differences between cameras. We use maximization of mutual information, a powerful technique for registering images that requires no a priori model of the relationship between scene intensities in different views. However, it has proven difficult to use mutual information to compute dense visual correspondence. Comparing fixed-size windows via mutual information suffers from the well-known problems of fixed windows, namely poor performance at discontinuities and in low-texture regions. In this paper, we show how to compute visual correspondence using mutual information without suffering from these problems. Using 'a simple approximation, mutual information can be incorporated into the standard energy minimization framework used in early vision. The energy can then be efficiently minimized using graph cuts, which preserve discontinuities and handle low-texture regions. The resulting algorithm combines the accurate disparity maps that come from graph cuts with the tolerance for intensity changes that comes from mutual information.},
author = {Kim, Junhwan and Vladimir Kolmogorov and Zabih, Ramin},
pages = {1033 -- 1040},
publisher = {IEEE},
title = {{Visual correspondence using energy minimization and mutual information}},
doi = {10.1109/ICCV.2003.1238463},
volume = {2},
year = {2003},
}
@article{3209,
abstract = {We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1]=FPT, this rules out the existence of algorithms with time complexity of O(f(k)nα) for those problems. Here n is the size of the problem instance, α is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences.},
author = {Krzysztof Pietrzak},
journal = {Journal of Computer and System Sciences},
number = {4},
pages = {757 -- 771},
publisher = {Elsevier},
title = {{On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems}},
doi = {10.1016/S0022-0000(03)00078-3},
volume = {67},
year = {2003},
}
@inproceedings{3210,
abstract = {Luby and Rackoff showed how to construct a (super-)pseudo-random permutation {0,1}2n→ {0,1}2n from some number r of pseudo-random functions {0,1}n → {0,1}n. Their construction, motivated by DES, consists of a cascade of r Feistel permutations. A Feistel permutation 1for a pseudo-random function f is defined as (L, R) → (R,L ⊕ f (R)), where L and R are the left and right part of the input and ⊕ denotes bitwise XOR or, in this paper, any other group operation on {0,1}n. The only non-trivial step of the security proof consists of proving that the cascade of r Feistel permutations with independent uniform random functions {0,1}n → {0,1}n, denoted Ψ2nr is indistinguishable from a uniform random permutation {0,1}2n → {0,1}2n by any computationally unbounded adaptive distinguisher making at most O(2cn) combined chosen plaintext/ciphertext queries for any c < α, where a is a security parameter. Luby and Rackoff proved α = 1/2 for r = 4. A natural problem, proposed by Pieprzyk is to improve on α for larger r. The best known result, α = 3/4 for r = 6, is due to Patarin. In this paper we prove a = 1 -O(1/r), i.e., the trivial upper bound α = 1 can be approached. The proof uses some new techniques that can be of independent interest. },
author = {Maurer, Ueli M and Krzysztof Pietrzak},
pages = {544 -- 561},
publisher = {Springer},
title = {{The security of many round Luby Rackoff pseudo random permutations}},
doi = {10.1007/3-540-39200-9_34},
volume = {2656},
year = {2003},
}
@inproceedings{3425,
author = {Bollenbach, Tobias and Strother, T. and Bauer, Wolfgang},
pages = {277 -- 288},
publisher = {Springer},
title = {{3D supernova collapse calculations}},
doi = {10.1007/978-1-4020-2705-5_21},
volume = {166},
year = {2003},
}
@inbook{3458,
author = {Peter Jonas and Unsicker, Klaus},
booktitle = {Lehrbuch Vorklinik},
editor = {Schmidt, R. F.},
pages = {3 -- 26},
publisher = {Deutscher Ärzte Verlag},
title = {{Molekulare und zelluläre Grundlagen des Nervensystems.}},
volume = {B},
year = {2003},
}
@article{3526,
abstract = {Neurons can produce action potentials with high temporal precision(1). A fundamental issue is whether, and how, this capability is used in information processing. According to the `cell assembly' hypothesis, transient synchrony of anatomically distributed groups of neurons underlies processing of both external sensory input and internal cognitive mechanisms(2-4). Accordingly, neuron populations should be arranged into groups whose synchrony exceeds that predicted by common modulation by sensory input. Here we find that the spike times of hippocampal pyramidal cells can be predicted more accurately by using the spike times of simultaneously recorded neurons in addition to the animals location in space. This improvement remained when the spatial prediction was refined with a spatially dependent theta phase modulation(5-8). The time window in which spike times are best predicted from simultaneous peer activity is 10-30 ms, suggesting that cell assemblies are synchronized at this timescale. Because this temporal window matches the membrane time constant of pyramidal neurons(9), the period of the hippocampal gamma oscillation(10) and the time window for synaptic plasticity(11), we propose that cooperative activity at this timescale is optimal for information transmission and storage in cortical circuits.},
author = {Harris, Kenneth D and Jozsef Csicsvari and Hirase, Hajima and Dragoi, George and Buzsáki, György},
journal = {Nature},
number = {6948},
pages = {552 -- 556},
publisher = {Nature Publishing Group},
title = {{Organization of cell assemblies in the hippocampus}},
doi = {0.1038/nature01834},
volume = {424},
year = {2003},
}
@article{3528,
abstract = {Gamma frequency oscillations (30-100 Hz) have been suggested to underlie various cognitive and motor functions. Here, we examine the generation of gamma oscillation currents in the hippocampus, using two-dimensional, 96-site silicon probes. Two gamma generators were identified, one in the dentate gyrus and another in the CA3-CA1 regions. The coupling strength between the two oscillators varied during both theta and nontheta states. Both pyramidal cells and interneurons were phase-locked to gamma waves. Anatomical connectivity, rather than physical distance, determined the coupling strength of the oscillating neurons. CA3 pyramidal neurons discharged CA3 and CA1 interneurons at latencies indicative of monosynaptic connections. Intrahippocampal gamma oscillation emerges in the CA3 recurrent system, which entrains the CA1 region via its interneurons.},
author = {Jozsef Csicsvari and Jamieson, Brian G and Wise, Kensall D and Buzsáki, György},
journal = {Neuron},
number = {2},
pages = {311 -- 322},
publisher = {Elsevier},
title = {{Mechanisms of gamma oscillations in the hippocampus of the behaving rat}},
doi = {10.1016/S0896-6273(02)01169-8},
volume = {37},
year = {2003},
}
@article{3529,
abstract = {Parallel recording of neuronal activity in the behaving animal is a prerequisite for our understanding of neuronal representation and storage of information. Here we describe the development of micro-machined silicon microelectrode arrays for unit and local field recordings. The two-dimensional probes with 96 or 64 recording sites provided high-density recording of unit and field activity with minimal tissue displacement or damage. The on-chip active circuit eliminated movement and other artifacts and greatly reduced the weight of the headgear. The precise geometry of the recording tips allowed for the estimation of the spatial location of the recorded neurons and for high-resolution estimation of extracellular current source density. Action potentials could be simultaneously recorded from the soma and dendrites of the same neurons. Silicon technology is a promising approach for high-density, high-resolution sampling of neuronal activity in both basic research and prosthetic devices.},
author = {Jozsef Csicsvari and Henze, Darrell A and Jamieson, Brian G and Harris, Kenneth D and Sirota, Anton M and Bartho, Peter and Wise, Kensall D and Buzsáki, György},
journal = {Journal of Neurophysiology},
number = {2},
pages = {1314 -- 1323},
publisher = {American Physiological Society},
title = {{Massively parallel recording of unit and local field potentials with silicon-based electrodes}},
doi = {10.1152/jn.00116.2003},
volume = {90},
year = {2003},
}
@article{3536,
abstract = {Genetic engineering of the mouse brain allows investigators to address novel hypotheses in vivo. Because of the paucity of information on the network patterns of the mouse hippocampus, we investigated the electrical patterns in the behaving animal using multisite silicon probes and wire tetrodes. Theta (6-9 Hz) and gamma (40-100 Hz) oscillations were present during exploration and rapid eye movement sleep. Gamma power and theta power were comodulated and gamma power varied as a function of the theta cycle. Pyramidal cells and putative interneurons were phase-locked to theta oscillations. During immobility, consummatory behaviors and slow-wave sleep, sharp waves were present in cornu ammonis region CA1 of the hippocampus stratum radiatum associated with 140-200-Hz “ripples” in the pyramidal cell layer and population burst of CA1 neurons. In the hilus, large-amplitude “dentate spikes” occurred in association with increased discharge of hilar neurons. The amplitude of field patterns was larger in the mouse than in the rat, likely reflecting the higher neuron density in a smaller brain. We suggest that the main hippocampal network patterns are mediated by similar pathways and mechanisms in mouse and rat. },
author = {Buzsáki, György and Buhl, Derek L and Harris, Kenneth D and Jozsef Csicsvari and Czéh, Boldizsár and Morozov, Alexei},
journal = {Neuroscience},
number = {1},
pages = {201 -- 211},
publisher = {Elsevier},
title = {{Hippocampal network patterns of activity in the mouse}},
doi = {10.1016/S0306-4522(02)00669-3},
volume = {116},
year = {2003},
}
@article{3543,
abstract = {Both neocortical and hippocampal networks organize the firing patterns of their neurons by prominent oscillations during sleep, but the functional role of these rhythms is not well understood. Here, we show a robust correlation of neuronal discharges between the somatosensory cortex and hippocampus on both slow and fine time scales in the mouse and rat. Neuronal bursts in deep cortical layers, associated with sleep spindles and delta waves/slow rhythm, effectively triggered hippocampal discharges related to fast (ripple) oscillations. We hypothesize that oscillation-mediated temporal links coordinate specific information transfer between neocortical and hippocampal cell assemblies. Such a neocortical-hippocampal interplay may be important for memory consolidation.},
author = {Sirota, Anton M and Jozsef Csicsvari and Buhl, Derek L and Buzsáki, György},
journal = {PNAS},
number = {4},
pages = {2065 -- 2069},
publisher = {National Academy of Sciences},
title = {{Communication between neocortex and hippocampus during sleep in rodents}},
doi = {10.1073/pnas.0437938100},
volume = {100},
year = {2003},
}
@inproceedings{3556,
abstract = {We define the Morse-Smale complex of a Morse function over a 3-manifold as the overlay of the descending and as- cending manifolds of all critical points. In the generic case, its 3-dimensional cells are shaped like crystals and are sepa- rated by quadrangular faces. In this paper, we give a combi- natorial algorithm for constructing such complexes for piece- wise linear data.},
author = {Herbert Edelsbrunner and Harer, John and Natarajan, Vijay and Pascucci, Valerio},
pages = {361 -- 370},
publisher = {ACM},
title = {{Morse-Smale complexes for piecewise linear 3-manifolds}},
doi = {10.1145/777792.777846},
year = {2003},
}
@inbook{3573,
abstract = {Given a finite point set in R, the surface reconstruction problem asks for a surface that passes through many but not necessarily all points. We describe an unambigu- ous definition of such a surface in geometric and topological terms, and sketch a fast algorithm for constructing it. Our solution overcomes past limitations to special point distributions and heuristic design decisions.},
author = {Herbert Edelsbrunner},
booktitle = {Discrete & Computational Geometry},
pages = {379 -- 404},
publisher = {Springer},
title = {{Surface reconstruction by wrapping finite sets in space}},
doi = {10.1007/978-3-642-55566-4_17},
year = {2003},
}
@article{3584,
abstract = {We develop fast algorithms for computing the linking number of a simplicial complex within a filtration.We give experimental results in applying our work toward the detection of non-trivial tangling in biomolecules, modeled as alpha complexes.},
author = {Edelsbrunner, Herbert and Zomorodian, Afra},
journal = {Homology, Homotopy and Applications},
number = {2},
pages = {19 -- 37},
publisher = {International Press},
title = {{Computing linking numbers of a filtration}},
volume = {5},
year = {2003},
}
@article{3593,
abstract = {Temporal logics such as Computation Tree Logic (CTL) and Linear Temporal Logic (LTL) have become popular for specifying temporal properties over a wide variety of planning and verification problems. In this paper we work towards building a generalized framework for automated reasoning based on temporal logics. We present a powerful extension of CTL with first-order quantification over the set of reachable states for reasoning about extremal properties of weighted labeled transition systems in general. The proposed logic, which we call Weighted Quantified Computation Tree Logic (WQCTL), captures the essential elements common to the domain of planning and verification problems and can thereby be used as an effective specification language in both domains. We show that in spite of the rich, expressive power of the logic, we are able to evaluate WQCTL formulas in time polynomial in the size of the state space times the length of the formula. Wepresent experimental results on the WQCTL verifier.},
author = {Krishnendu Chatterjee and Dasgupta, Pallab and Chakrabarti, Partha P},
journal = {Journal of Automated Reasoning},
number = {2},
pages = {205 -- 232},
publisher = {Springer},
title = {{A branching time temporal framework for quantitative reasoning}},
doi = {10.1023/A:1023217515688},
volume = {30},
year = {2003},
}
@article{3618,
abstract = {There are several analyses in evolutionary ecology which assume that a family of offspring has come from only two parents. Here, we present a simple test for detecting when a batch involves two or more subfamilies. It is based on the fact that the mixing of families generates associations amongst unlinked marker loci. We also present simulations illustrating the power of our method for varying numbers of loci, alleles per locus and genotyped individuals.},
author = {Vines, Timothy H and Nicholas Barton},
journal = {Molecular Ecology},
number = {7},
pages = {1999 -- 2002},
publisher = {Wiley-Blackwell},
title = {{A new approach to detecting mixed families}},
doi = {10.1046/j.1365-294X.2003.01867.x},
volume = {12},
year = {2003},
}
@article{3619,
abstract = {What is the chance that some part of a stretch of genome will survive? In a population of constant size, and with no selection, the probability of survival of some part of a stretch of map length y<1 approaches View the MathML source for View the MathML source. Thus, the whole genome is certain to be lost, but the rate of loss is extremely slow. This solution extends to give the whole distribution of surviving block sizes as a function of time. We show that the expected number of blocks at time t is 1+yt and give expressions for the moments of the number of blocks and the total amount of genome that survives for a given time. The solution is based on a branching process and assumes complete interference between crossovers, so that each descendant carries only a single block of ancestral material. We consider cases where most individuals carry multiple blocks, either because there are multiple crossovers in a long genetic map, or because enough time has passed that most individuals in the population are related to each other. For species such as ours, which have a long genetic map, the genome of any individual which leaves descendants (∼80% of the population for a Poisson offspring number with mean two) is likely to persist for an extremely long time, in the form of a few short blocks of genome.},
author = {Baird, Stuart J and Nicholas Barton and Etheridge, Alison M},
journal = {Theoretical Population Biology},
number = {4},
pages = {451 -- 471},
publisher = {Academic Press},
title = {{The distribution of surviving blocks of an ancestral genome}},
doi = {10.1016/S0040-5809(03)00098-4},
volume = {64},
year = {2003},
}
@article{3620,
abstract = {Stable hybrid zones in which ecologically divergent taxa give rise to a range of recombinants are natural laboratories in which the genetic basis of adaptation and reproductive isolation can be unraveled. One such hybrid zone is formed by the fire-bellied toads Bombina bombina and B. variegata (Anura: Discoglossidae). Adaptations to permanent and ephemeral breeding habitats, respectively, have shaped numerous phenotypic differences between the taxa. All of these are, in principle, candidates for a genetic dissection via QTL mapping. We present here a linkage map of 28 codominant and 10 dominant markers in the Bombina genome. In an F2 cross, markers that were mainly microsatellites, SSCPs or allozymes were mapped to 20 linkage groups. Among the 40 isolated CA microsatellites, we noted a preponderance of compound and frequently interleaved CA-TA repeats as well as a striking polarity at the 5′ end of the repeats.},
author = {Nürnberger, Beate and Hofman, Sebastian and Förg-Brey, Bqruni and Praetzel, Gabriele and Maclean, Alan W and Szymura, Jacek M and Abbott, Catherine M and Nicholas Barton},
journal = {Heredity},
number = {2},
pages = {136 -- 142},
publisher = {Nature Publishing Group},
title = {{A linkage map for the hybridising toads Bombina bombina and B. variegata (Anura: Discoglossidae)}},
doi = {10.1038/sj.hdy.6800291},
volume = {91},
year = {2003},
}
@phdthesis{3678,
author = {Christoph Lampert},
booktitle = {Bonner Mathematische Schriften},
pages = {1 -- 165},
publisher = {Universität Bonn, Fachbibliothek Mathematik},
title = {{The Neumann operator in strictly pseudoconvex domains with weighted Bergman metric }},
volume = {356},
year = {2003},
}
@article{3725,
abstract = {The combination of high-resolution atomic force microscopy (AFM) imaging and single-molecule force-spectroscopy was employed to unfold single bacteriorhodopsins (BR) from native purple membrane patches at various physiologically relevant temperatures. The unfolding spectra reveal detailed insight into the stability of individual structural elements of BR against mechanical unfolding. Intermittent states in the unfolding process are associated with the stepwise unfolding of alpha-helices, whereas other states are associated with the unfolding of polypeptide loops connecting the alpha-helices. It was found that the unfolding forces of the secondary structures considerably decreased upon increasing the temperature from 8 to 52°C. Associated with this effect, the probability of individual unfolding pathways of BR was significantly influenced by the temperature. At lower temperatures, transmembrane alpha-helices and extracellular polypeptide loops exhibited sufficient stability to individually establish potential barriers against unfolding, whereas they predominantly unfolded collectively at elevated temperatures. This suggests that increasing the temperature decreases the mechanical stability of secondary structural elements and changes molecular interactions between secondary structures, thereby forcing them to act as grouped structures.},
author = {Harald Janovjak and Kessler, Max and Oesterhelt, Dieter and Gaub, Hermann and Mueller, Daniel J},
journal = {EMBO Journal},
number = {19},
pages = {5220 -- 5229},
publisher = {Wiley-Blackwell},
title = {{Unfolding pathways of native bacteriorhodopsin depend on temperature}},
doi = {10.1093/emboj/cdg509},
volume = {22},
year = {2003},
}
@article{3752,
abstract = {We use the lac operon in Escherichia coli as a prototype system to illustrate the current state, applicability, and limitations of modeling the dynamics of cellular networks. We integrate three different levels of description (molecular, cellular, and that of cell population) into a single model, which seems to capture many experimental aspects of the system.},
author = {Vilar,Jose M and Calin Guet and Leibler, Stanislas},
journal = {Journal of Cell Biology},
number = {3},
pages = {471 -- 476},
publisher = {Rockefeller University Press},
title = {{Modeling network dynamics: the lac operon, a case study}},
doi = {10.1083/jcb.200301125},
volume = {161},
year = {2003},
}
@article{3797,
author = {Bauer, Wolfgang and Kleine-Berkenbusch, Marco and Bollenbach, Tobias},
journal = {Revista Mexicana De Fisica},
number = {4},
pages = {1 -- 6},
publisher = {Sociedad Mexicana de Física},
title = {{Breaking atomic nuclei into little pieces: evidence for a phase transition}},
volume = {49},
year = {2003},
}
@article{3804,
abstract = {Kv3 channels are thought to be essential for the fast-spiking (FS) phenotype in GABAergic interneurons, but how these channels confer the ability to generate action potentials (APs) at high frequency is unknown. To address this question, we developed a fast dynamic-clamp system (approximately 50 kHz) that allowed us to add a Kv3 model conductance to CA1 oriens alveus (OA) interneurons in hippocampal slices. Selective pharmacological block of Kv3 channels by 0.3 mm 4-aminopyridine or 1 mm tetraethylammonium ions led to a marked broadening of APs during trains of short stimuli and a reduction in AP frequency during 1 sec stimuli. The addition of artificial Kv3 conductance restored the original AP pattern. Subtraction of Kv3 conductance by dynamic clamp mimicked the effects of the blockers. Application of artificial Kv3 conductance also led to FS in OA interneurons after complete K+ channel block and even induced FS in hippocampal pyramidal neurons in the absence of blockers. Adding artificial Kv3 conductance with altered deactivation kinetics revealed a nonmonotonic relationship between mean AP frequency and deactivation rate, with a maximum slightly above the original value. Insertion of artificial Kv3 conductance with either lowered activation threshold or inactivation also led to a reduction in the mean AP frequency. However, the mechanisms were distinct. Shifting the activation threshold induced adaptation, whereas adding inactivation caused frequency-dependent AP broadening. In conclusion, Kv3 channels are necessary for the FS phenotype of OA interneurons, and several of their gating properties appear to be optimized for high-frequency repetitive activity.},
author = {Lien, Cheng-Chang and Peter Jonas},
journal = {Journal of Neuroscience},
number = {6},
pages = {2058 -- 68},
publisher = {Society for Neuroscience},
title = {{Kv3 potassium conductance is necessary and kinetically optimized for high-frequency action potential generation in hippocampal interneurons}},
volume = {23},
year = {2003},
}
@article{3806,
abstract = {To probe exocytosis at a cortical glutamatergic synapse, we made capacitance measurements in whole-cell recorded hippocampal mossy fiber terminals. Evaluation of different methods by using a morphology-based equivalent electrical model revealed that quantitative capacitance measurements are possible in this presynaptic structure. Voltage pulses leading to presynaptic Ca2+ inflow evoked large capacitance signals that showed saturation with increasing pulse duration. The mean peak capacitance increase was 100 fF, corresponding to a pool of approximately 1,400 releasable vesicles. Thus hippocampal mossy fiber synapses have a vesicular "maxipool." Large pool size and rapid vesicle recycling may underlie the uniquely large extent of activity-dependent plasticity in this synapse.},
author = {Hallermann, Stefan and Pawlu, Christian and Peter Jonas and Heckmann, Manfred},
journal = {PNAS},
number = {15},
pages = {8975 -- 80},
publisher = {National Academy of Sciences},
title = {{A large pool of releasable vesicles in a cortical glutamatergic synapse}},
doi = {10.1073/pnas.1432836100},
volume = {100},
year = {2003},
}
@inproceedings{3897,
abstract = {Many verification, planning, and control problems can be modeled as games played on state-transition graphs by one or two players whose conflicting goals are to form a path in the graph. The focus here is on simple stochastic parity games, that is, two-player games with turn-based probabilistic transitions and omega-regular objectives formalized as parity (Rabin chain) winning conditions. An efficient translation from simple stochastic parity games to nonstochastic parity games is given. As many algorithms are known for solving the latter, the translation yields efficient algorithms for computing the states of a simple stochastic parity game from which a player can win with probability 1. An important special case of simple stochastic parity games are the Markov decision processes with Buchi objectives. For this special case a first provably subquadratic algorithm is given for computing the states from which the single player has a strategy to achieve a Buchi objective with probability 1. For game graphs with m edges the algorithm works in time O(mrootm). Interestingly, a similar technique sheds light on the question of the computational complexity of solving simple Buchi games and yields the first provably subquadratic algorithm, with a running time of O(n(2)/log n) for game graphs with n vertices and O(n) edges.},
author = {Krishnendu Chatterjee and Jurdziński, Marcin and Thomas Henzinger},
pages = {100 -- 113},
publisher = {Springer},
title = {{Simple stochastic parity games}},
doi = {10.1007/978-3-540-45220-1_11},
volume = {2803},
year = {2003},
}
@inproceedings{3898,
abstract = {We study the problem of determining stack boundedness and the exact maximum stack size for three classes of interrupt-driven programs. Interrupt-driven programs axe used in many real-time applications that require responsive interrupt handling. In order to ensure responsiveness, programmers often enable interrupt processing in the body of lower-priority interrupt handlers. In such programs a programming error can allow interrupt handlers to be interrupted in cyclic fashion to lead to an unbounded stack, causing the system to crash. For a restricted class of interrupt-driven programs, we show that there is a polynomial-time procedure to check stack boundedness, while determining the exact maximum stack size is PSPACE-complete. For a larger class of programs, the two problems are both PSPACE-complete, and for the largest class of programs we consider, the two problems are PSPACE-hard and can be solved in exponential time.},
author = {Krishnendu Chatterjee and Ma, Di and Majumdar, Ritankar S and Zhao, Tian and Thomas Henzinger and Palsberg, Jens},
pages = {109 -- 126},
publisher = {Springer},
title = {{Stack size analysis for interrupt-driven programs}},
doi = {10.1007/3-540-44898-5_7},
volume = {2694},
year = {2003},
}
@article{204,
abstract = {Let k⩾5 be an integer, and let x⩾1 be an arbitrary real number. We derive a bound[Formula presented] for the number of positive integers less than or equal to x which can be represented as a sum of two non-negative coprime kth powers, in essentially more than one way.},
author = {Timothy Browning},
journal = {Journal of Number Theory},
number = {2},
pages = {293 -- 318},
publisher = {Academic Press},
title = {{Equal Sums of Two kth Powers}},
doi = {10.1006/jnth.2002.2800},
volume = {96},
year = {2002},
}
@inbook{2338,
author = {Lieb, Élliott H and Solovej, Jan P and Robert Seiringer and Yngvason, Jakob},
booktitle = {Current Developments in Mathematics, 2001},
pages = {131 -- 178},
publisher = {International Press},
title = {{The ground state of the Bose gas}},
doi = {http://arxiv.org/abs/math-ph/0204027},
year = {2002},
}
@inproceedings{2339,
author = {Robert Seiringer},
editor = {Weder, Richardo and Exner, Pavel and Grébert, Benoit},
pages = {281 -- 286},
publisher = {World Scientific Publishing},
title = {{Symmetry breaking in a model of a rotating Bose gas}},
doi = {10.1090/conm/307},
volume = {307},
year = {2002},
}
@article{2349,
abstract = {The Bose-Einstein condensation (BEC) of the ground state of bosonic atoms in a trap was discussed. The BEC was proved for bosons with two-body repulsive interaction potentials in the dilute limit, starting from the basic Schrodinger equation. The BEC was 100% into the state which minimized the Gross-Pitaevskii energy functional. The analysis also included rigorous proof of BEC in a physically realistic, continuum model.},
author = {Lieb, Élliott H and Robert Seiringer},
journal = {Physical Review Letters},
number = {17},
pages = {1704091 -- 1704094},
publisher = {American Physical Society},
title = {{Proof of Bose-Einstein condensation for dilute trapped gases}},
doi = {10.1103/PhysRevLett.88.170409},
volume = {88},
year = {2002},
}
@article{2350,
abstract = {Using the Pauli-Fierz model of non-relativistic quantum electrodynamics, we calculate the binding energy of an electron in the field of a nucleus of charge Z and in presence of the quantized radiation field. We consider the case of small coupling constant α, but fixed Zα and ultraviolet cut-off Λ. We prove that after renormalizing the mass the binding energy has, to leading order in α, a finite limit as Λ goes to infinity; i.e., the cut-off can be removed. The expression for the ground state energy shift thus obtained agrees with Bethe's formula for small values of Zα, but shows a different behavior for bigger values.},
author = {Hainzl, Christian and Robert Seiringer},
journal = {Advances in Theoretical and Mathematical Physics},
number = {5},
pages = {847 -- 871},
publisher = {International Press},
title = {{Mass renormalization and energy level shift in non-relativistic QED}},
volume = {6},
year = {2002},
}
@article{2351,
abstract = {We study the Gross-Pitaevskii functional for a rotating two-dimensional Bose gas in a trap. We prove that there is a breaking of the rotational symmetry in the ground state; more precisely, for any value of the angular velocity and for large enough values of the interaction strength, the ground state of the functional is not an eigenfunction of the angular momentum. This has interesting consequences on the Bose gas with spin; in particular, the ground state energy depends non-trivially on the number of spin components, and the different components do not have the same wave function. For the special case of a harmonic trap potential, we give explicit upper and lower bounds on the critical coupling constant for symmetry breaking.},
author = {Robert Seiringer},
journal = {Communications in Mathematical Physics},
number = {3},
pages = {491 -- 509},
publisher = {Springer},
title = {{Gross-Pitaevskii theory of the rotating Bose gas}},
doi = {10.1007/s00220-002-0695-2},
volume = {229},
year = {2002},
}
@article{2352,
abstract = {We present a generalization of the Fefferman-de la Llave decomposition of the Coulomb potential to quite arbitrary radial functions V on ℝn going to zero at infinity. This generalized decomposition can be used to extend previous results on N-body quantum systems with Coulomb interaction to a more general class of interactions. As an example of such an application, we derive the high density asymptotics of the ground state energy of jellium with Yukawa interaction in the thermodynamic limit, using a correlation estimate by Graf and Solovej.},
author = {Hainzl, Christian and Robert Seiringer},
journal = {Letters in Mathematical Physics},
number = {1},
pages = {75 -- 84},
publisher = {Springer},
title = {{General decomposition of radial functions on ℝn and applications to N-body quantum systems}},
doi = {10.1023/A:1020204818938},
volume = {61},
year = {2002},
}
@article{2353,
abstract = {A commonly used theoretical definition of superfluidity in the ground state of a Bose gas is based on the response of the system to an imposed velocity field or, equivalently, to twisted boundary conditions in a box. We are able to carry out this program in the case of a dilute interacting Bose gas in a trap, and we prove that a gas with repulsive interactions is 100% superfluid in the dilute limit in which the Gross-Pitaevskii equation is exact. This is the first example in an experimentally realistic continuum model in which superfluidity is rigorously verified.},
author = {Lieb, Élliott H and Robert Seiringer and Yngvason, Jakob},
journal = {Physical Review B - Condensed Matter and Materials Physics},
number = {13},
publisher = {American Physical Society},
title = {{Superfluidity in dilute trapped Bose gases}},
doi = {10.1103/PhysRevB.66.134529},
volume = {66},
year = {2002},
}
@article{2420,
abstract = {A corner cut in dimension d is a finite subset of N0d that can be separated from its complement in N0d by an affine hyperplane disjoint from N0d. Corner cuts were first investigated by Onn and Sturmfels [Adv. Appl. Math. 23 (1999) 29-48], their original motivation stemmed from computational commutative algebra. Let us write (Nd0k)cut for the set of corner cuts of cardinality k; in the computational geometer's terminology, these are the k-sets of N0d. Among other things, Onn and Sturmfels give an upper bound of O(k2d(d-1)/(d+1)) for the size of (Nd0k)cut when the dimension is fixed. In two dimensions, it is known (see [Corteel et al., Adv. Appl. Math. 23 (1) (1999) 49-53]) that #(Nd0k)cut = Θ(k log k). We will see that in general, for any fixed dimension d, the order of magnitude of #(Nd0k)cut is between kd-1 log k and (k log k)d-1. (It has been communicated to me that the same bounds have been found independently by G. Rémond.) In fact, the elements of (Nd0k)cut correspond to the vertices of a certain polytope, and what our proof shows is that the above upper bound holds for the total number of flags of that polytope.},
author = {Uli Wagner},
journal = {Advances in Applied Mathematics},
number = {2},
pages = {152 -- 161},
publisher = {ACM},
title = {{On the number of corner cuts}},
doi = {10.1016/S0196-8858(02)00014-3},
volume = {29},
year = {2002},
}
@inproceedings{2421,
abstract = {Intersection graphs of disks and of line segments, respectively, have been well studied, because of both, practical applications and theoretically interesting properties of these graphs. Despite partial results, the complexity status of the Clique problem for these two graph classes is still open. Here, we consider the Clique problem for intersection graphs of ellipses which in a sense, interpolate between disc and ellipses, and show that it is APX-hard in that case. Moreover, this holds even if for all ellipses, the ratio of the larger over the smaller radius is some prescribed number. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of objects with finite description complexity. We also describe a simple approximation algorithm for the case of ellipses for which the ratio of radii is bounded.},
author = {Ambühl, Christoph and Uli Wagner},
pages = {489 -- 500},
publisher = {Springer},
title = {{On the Clique problem in intersection graphs of ellipses}},
doi = {10.1007/3-540-36136-7_43},
volume = {2518},
year = {2002},
}
@article{2613,
abstract = {In this investigation, we report identification and characterization of a 95 kDa postsynaptic density protein (PSD-95)/discs-large/ ZO-1 (PDZ) domain-containing protein termed tamalin, also recently named GRP1-associated scaffold protein (GRASP), that interacts with group 1 metabotropic glutamate receptors (mGluRs). The yeast two-hybrid system and in vitro pull-down assays indicated that the PDZ domain-containing, amino-terminal half of tamalin directly binds to the class I PDZ-binding motif of group 1 mGluRs. The C-terminal half of tamalin also bound to cytohesins, the members of guanine nucleotide exchange factors (GEFs) specific for the ADP-ribosylation factor (ARF) family of small GTP-binding proteins. Tamalin mRNA is expressed predominantly in the telencephalic region and highly overlaps with the expression of group 1 mGluR mRNAs. Both tamalin and cytohesin-2 were enriched and codistributed with mGluR1a in postsynaptic membrane fractions. Importantly, recombinant and native mGluR1a/tamalin/cytohesin-2 complexes were coimmunoprecipitated from transfected COS-7 cells and rat brain tissue, respectively. Transfection of tamalin and mutant tamalin lacking a cytohesin-binding domain caused an increase and decrease in cell-surface expression of mGluR1a in COS-7 cells, respectively. Furthermore, adenovirus-mediated expression of tamalin and dominant-negative tamalin facilitated and reduced the neuritic distribution of endogenous mGluR5 in cultured hippocampal neurons, respectively. The results indicate that tamalin plays a key role in the association of group 1 mGluRs with the ARF-specific GEF proteins and contributes to intracellular trafficking and the macromolecular organization of group 1 mGluRs at synapses.},
author = {Kitano, Jun and Kimura, Kouji and Yamazaki, Yoshimitsu and Soda, Takeshi and Ryuichi Shigemoto and Nakajima, Yoshiaki and Nakanishi, Shigetada},
journal = {Journal of Neuroscience},
number = {4},
pages = {1280 -- 1289},
publisher = {Society for Neuroscience},
title = {{Tamalin, a PDZ domain-containing protein, links a protein complex formation of group 1 metabotropic glutamate receptors and the guanine nucleotide exchange factor cytohesins}},
volume = {22},
year = {2002},
}
@article{2614,
abstract = {Metabotropic glutamate receptors (mGluRs) from group III reduce glutamate release. Because these receptors reduce cAMP levels, we explored whether this signaling pathway contributes to release inhibition caused by mGluRs with low affinity for L-2-amino-4-phosphonobutyrate (L-AP4). In biochemical experiments with the population of cerebrocortical nerve terminals we find that L-AP4 (1 mM) inhibited the Ca2+dependent-evoked release of glutamate by 25%. This inhibitory effect was largely prevented by the pertussis toxin but was insensitive to inhibitors of protein kinase C bisindolylmaleimide and protein kinase A H-89. Furthermore, this inhibition was associated with reduction in N-type Ca2+ channel activity in the absence of any detectable change in cAMP levels. In the presence of forskolin, however, L-AP4 decreased the levels of cAMP. The activation of this additional signaling pathway was very efficient in counteracting the facilitation of glutamate release induced either by forskolin or the β-adrenergic receptor agonist isoproterenol. Imaging experiments to measure Ca2+ dynamics in single nerve terminals showed that L-AP4 strongly reduced the Ca2+ response in 28% of the nerve terminals. Moreover, immunochemical experiments showed that 25-35% of the nerve terminals that were immunopositive to synaptophysin were also immunoreactive to the low affinity L-AP4-sensitive mGluR7. Then, mGluR7 mediates the inhibition of glutamate release caused by 1 mM L-AP4, primarily by a strong inhibition of Ca2+ channels, although high cAMP uncovers the receptor ability to decrease cAMP.},
author = {Millán, Carmelo and Luján, Rafael and Ryuichi Shigemoto and Sánchez-Prieto, José},
journal = {Journal of Biological Chemistry},
number = {16},
pages = {14092 -- 14101},
publisher = {American Society for Biochemistry and Molecular Biology},
title = {{The inhibition of glutamate release by metabotropic glutamate receptor 7 affects both [Ca2+]c and cAMP. Evidence for a strong reduction of Ca2+ entry in single nerve terminals}},
doi = {10.1074/jbc.M109044200},
volume = {277},
year = {2002},
}
@article{2615,
abstract = {Taste-mGluR4, cloned from taste tissues, is a truncated variant of brain-expressed mGluR4a (brain-mGluR4), and is known to be a candidate for the receptor involved in the umami taste sense. Although the expression patterns of taste- and brain-mGluR4 mRNAs have been demonstrated, no mention has so far been made of the expression of these two mGluR4 proteins in taste tissues. The present study examined the expression of taste-mGluR4 and brain-mGluR4 proteins in rat taste tissues by using a specific antibody for mGluR4a which shared a C-terminus of both taste- and brain-mGluR4, for immunoblot analysis and immunohistochemistry. Immunoblot analysis showed that both brain-mGluR4 and taste-mGluR4 were expressed in the taste tissues. Taste-mGluR4 was not detected in the cerebellum. The immunoreactive band for brain-mGluR4 protein was much stronger than that for taste-mGluR4 protein. In the cryosections of fungiform, foliate and circumvallate papillae, the antibody against taste-mGluR4 exhibited intense labeling of the taste pores and taste hairs in all the taste buds of gustatory papillae examined; the immunoreaction to the antibody against brain-mGluR4 was more intense at the same sites of the taste buds. The portions of the taste bud cells below the taste pore and surrounding keratinocytes did not show any immunoreactivities. The results of the present study strongly suggest that, in addition to taste-mGluR4, brain-mGluR4 may function even more importantly than the former as a receptor for glutamate, i.e. the umami taste sensation.},
author = {Toyono, Takashi and Seta, Yuji and Sataoka, Shinji and Harumi Harada and Morotomi, Takahiko and Kawano, Shintaro and Ryuichi Shigemoto and Toyoshima, Kuniaki},
journal = {Archives of Histology and Cytology},
number = {1},
pages = {91 -- 96},
publisher = {Japan Society of Histological Documentation},
title = {{Expression of the metabotropic glutamate receptor, mGluR4a, in the taste hairs of taste buds in rat gustatory papillae}},
doi = {10.1679/aohc.65.91},
volume = {65},
year = {2002},
}
@article{2616,
abstract = {Neurons in the rat cerebral cortex are enriched in group I metabotropic glutamate receptor (mGluR) subtypes and respond to their activation during development. To understand better the mechanisms by which mGluR1 and mGluR5 mediate these effects, the goal of this study was to elucidate the expression pattern and to determine the cellular and the precise subcellular localization of these two receptor subtypes in the rat neocortex and hippocampus during late prenatal and postnatal development. At the light microscopic level, mGluR1 α and mGluR5 were first detected in the cerebral cortex with different expression levels at embryonic day E18. Thus, mGluR5 had a moderate expression, whereas mGluR1 α was detected as a diffuse and weak labeling. mGluR5 was localized in some Cajal-Retzius cells as well as in other cell types, such as pioneer neurons of the marginal zone. During postnatal development, the distribution of the receptors dramatically changed. From P0 to around P10, mGluR1α was localized in identified, transient Cajal-Retzius cells of neocortex and hippocampus, until these cells disappear. In addition, a population of interneurons localized the receptor from the second/third postnatal week. In contrast, mGluR5 was localized mainly in pyramidal cells and in some interneurons, with a neuropilar staining throughout the cerebral cortex. At the electron microscopic level, the immunoreactivity for both group I mGluR subtypes was expressed postsynaptically. Using immunogold methods, mGluR1α and mGluR5 immunoreactivities were found throughout postnatal development at the edge of postsynaptic specialization of asymmetrical synapses. These results show that the two group I mGluRs have a differential expression pattern in neocortex and hippocampus that may suggest roles for the receptors in the early processing of cortical information and in the control of cortical developmental events.},
author = {López-Bendito, Guillermina and Ryuichi Shigemoto and Fairén, Alfonso and Luján, Rafael},
journal = {Cerebral Cortex},
number = {6},
pages = {625 -- 638},
publisher = {Oxford University Press},
title = {{Differential distribution of group I metabotropic glutamate receptors during rat cortical development}},
doi = {10.1093/cercor/12.6.625},
volume = {12},
year = {2002},
}
@article{2617,
abstract = {Synapses exhibit different short-term plasticity patterns and this behaviour influences information processing in neuronal networks. We tested how the short-term plasticity of excitatory postsynaptic currents (EPSCs) depends on the postsynaptic cell type, identified by axonal arborizations and molecular markers in the hippocampal CA1 area. Three distinct types of short-term synaptic behaviour (facilitating, depressing and combined facilitating-depressing) were defined by fitting a dynamic neurotransmission model to the data. Approximately 75 % of the oriens-lacunosum-moleculare (O-LM) interneurones received facilitating EPSCs, but in three of 12 O-LM cells EPSCs also showed significant depression. Over 90 % of the O-LM cells were immunopositive for somatostatin and mGluR1α and all tested cells were decorated by strongly mGluR7a positive axon terminals. Responses in eight of 12 basket cells were described well with a model involving only depression, but the other cells displayed combined facilitating-depressing EPSCs. No apparent difference was found between the plasticity of EPSCs in cholecystokinin- or parvalbumin-containing basket cells. In oriens-bistratified cells (O-Bi), two of nine cells showed facilitating EPSCs, another two depressing, and the remaining five cells combined facilitating-depressing EPSCs. Seven of 10 cells tested for somatostatin were immunopositive, but mGluR1α was detectable only in two of 11 tested cells. Furthermore, most O-Bi cells projected to the CA3 area and the subiculum, as well as outside the hippocampal formation. Postsynaptic responses to action potentials recorded in vivo from a CA1 place cell were modelled, and revealed great differences between and within cell types. Our results demonstrate that the short-term plasticity of EPSCs is cell type dependent, but with significant heterogeneity within all three interneurone populations.},
author = {Losonczy, Attila and Zhang, Limei and Ryuichi Shigemoto and Somogyi, Péter and Nusser, Zoltán},
journal = {Journal of Physiology},
number = {1},
pages = {193 -- 210},
publisher = {Wiley-Blackwell},
title = {{Cell type dependence and variability in the short-term plasticity of EPSCs in identified mouse hippocampal interneurones}},
doi = {10.1113/jphysiol.2002.020024},
volume = {542},
year = {2002},
}
@article{2618,
abstract = {The unipolar brush cell (UBC) is a type of glutamatergic interneuron in the granular layer of the cerebellum. The UBC brush and a single mossy fiber (MF) terminal contact each other within a cerebellar glomerulus, forming a giant synapse. Many UBCs receive input from extrinsic MFs, whereas others are innervated by intrinsic mossy terminals formed by the axons of other UBCs. In all mammalian species so far examined, the vestibulocerebellum is enriched of UBCs that are strongly immunoreactive for the calcium binding protein calretinin (CR) in both the somatodendritic and axonal compartment. UBCs have postsynaptic ionotropic glutamate receptors and extrasynaptic metabotropic glutamate receptors that immunocytochemically highlight their somatodendritic compartment and brush, respectively. In this study on the mouse cerebellum, we present evidence that immunoreactivities to CR and mGluR1α define two distinct UBC subsets with partly overlapping distributions in lobule X (the nodulus). In sections double-labeled for CR and mGluR1α, the patterns of distributions of CR+/mGluR1α- UBCs and CR-/mGluR1α+ UBCs differed along the mediolateral and dorsoventral axes of the folium. Moreover, mGluR1α+ UBCs outnumbered CR+ UBCs. Both UBC subsets were mGluR2/3, GluR2/3, and NMDAR1 immunoreactive. The different distribution patterns of the two UBC subsets within lobule X suggest that expression of CR or mGluR1α by UBCs may be afferent-specific and related to the terminal fields of different vestibular MF afferents.},
author = {Nunzi, Maria G and Ryuichi Shigemoto and Mugnaini, Enrico},
journal = {Journal of Comparative Neurology},
number = {2},
pages = {189 -- 199},
publisher = {Wiley-Blackwell},
title = {{Differential expression of calretinin and metabotropic glutamate receptor mGluR1α defines subsets of unipolar brush cells in mouse cerebellum}},
doi = {10.1002/cne.10344},
volume = {451},
year = {2002},
}
@article{2619,
abstract = {The release of glutamate and GABA is modulated by presynaptic metabotropic glutamate receptors (mGluRs). We used immunocytochemical methods to define the location of the group III receptor mGluR7a in glutamatergic and GABAergic terminals innervating GABAergic interneurons and pyramidal cells. Immunoreactivity for mGluR7a was localized in the presynaptic active zone of both identified GABAergic and presumed glutamatergic terminals. Terminals innervating dendritic spines showed a variable level of receptor immunoreactivity, ranging from immunonegative to strongly immunopositive. The frequency of strongly mGluR7a positive terminals innervating the soma and dendrites of mGluR1α/somatostatin-expressing interneurons was very high relative to other neurons. On dendrites that received mGluR7a-enriched glutamatergic innervation, at least 80% of GABAergic terminals were immunopositive for mGluR7a. On such dendrites virtually all (95%) vasoactive intestinal polypeptide (VIP) positive (GABAergic) terminals were enriched in mGluR7a. The targets of VIP/mGluR7a-expressing terminals were mainly (88%) mGluR1α-expressing interneurons, which were mostly somatostatin immunopositive. Parvalbumin positive terminals were immunonegative for mGluR7a. Some parvalbumin immunoreactive dendrites received strongly mGluR7a positive terminals. The subcellular location, as well as the cell type and synapse-specific distribution of mGluR7a in isocortical neuronal circuits, is homologous to its distribution in the hippocampus. The specific location of mGluR7a in the presynaptic active zone of both glutamatergic and GABAergic synapses may be related to the proximity of calcium channels and the vesicle fusion machinery. The enrichment of mGluR7a in the main GABAergic, as well as in the glutamatergic, innervation of mGluR1α/somatostatin-expressing interneurons suggests that their activation is under unique regulation by extracellular glutamate.},
author = {Dalezios, Yannis and Luján, Rafael and Ryuichi Shigemoto and Roberts, John D and Somogyi, Péter},
journal = {Cerebral Cortex},
number = {9},
pages = {961 -- 974},
publisher = {Oxford University Press},
title = {{Enrichment of mGluR7a in the presynaptic active zones of GABAergic and non-GABAergic terminals on interneurons in the rat somatosensory cortex}},
doi = {10.1093/cercor/12.9.961},
volume = {12},
year = {2002},
}
@article{3919,
abstract = {Hamilton's concept of local mate competition (LMC) is the standard model to explain female-biased sex ratios in solitary Hymenoptera. In social Hymenoptera, however, LMC has remained controversial, mainly because manipulation of sex allocation by workers in response to relatedness asymmetries is an additional powerful mechanism of female bias. Furthermore, the predominant mating systems in the social insects are thought to make LMC unlikely. Nevertheless, several species exist in which dispersal of males is limited and mating occurs in the nest. Some of these species, such as the ant Cardiocondyla obscurior, have evolved dimorphic males, with one morph being specialized for dispersal and the other for fighting with nest-mate males over access to females. Such life history, combining sociality and alternative reproductive tactics in males, provides a unique opportunity to test the power of LMC as a selective force leading to female-biased sex ratios in social Hymenoptera. We show that, in concordance with LMC predictions, an experimental increase in queen number leads to a shift in sex allocation in favour of non-dispersing males, but does not influence the proportion of disperser males. Furthermore, we can assign this change in sex allocation at the colony level to the queens and rule out worker manipulation.},
author = {Cremer, Sylvia and Heinze, Jürgen},
journal = {Proceedings of the Royal Society of London Series B Biological Sciences},
number = {1489},
pages = {417 -- 422},
publisher = {Royal Society, The},
title = {{Adaptive production of fighter males: queens of the ant Cardiocondyla adjust the sex ratio under local mate competition}},
doi = {10.1098/rspb.2001.1892},
volume = {269},
year = {2002},
}
@article{3920,
abstract = {A particular Solid Injector needle, suitable for GC-MS analyses of small specimens, is described together with its application in a study on ants.},
author = {Turillazzi, Stefano and Sledge, Matthew and Cremer, Sylvia and Heinze, Jürgen},
journal = {Insect Social Life},
pages = {169 -- 175},
publisher = {Elsevier},
title = {{A method for analysing small-size specimens in GC-MS}},
volume = {4},
year = {2002},
}
@article{3924,
abstract = {Males of the ant Cardiocondyla show a dispersal dimorphism of a winged and wingless morph. The loss of flight has lead to morphological reductions in the wingless (ergatoid) males and also affected body size, eye size and pigmentation. As ergatoid males mate exclusively inside the maternal nest, they underlie increased male-male competition and therefore have also evolved additional changes in behaviour and physiology: in contrast to winged males, ergatoid males are highly aggressive towards each other and their spermatogenesis is prolonged compared to all other hymenopteran males. In addition to these two male morphs, we found males with an intermediate appearance. These "intermorphic" males provide a transitional stage between normal males in most investigated morphological and physiological parameters. As they are produced extremely rarely and only in colonies that switch between pure ergatoid to mixed male production, we argue that they likely represent a developmental mistake. Parallels between the determination of male morphs and female castes (queen-worker dimorphism and worker polymorphism) might help to understand how the large potential of phenotypic plasticity in both sexes of social insects is realised during development.},
author = {Cremer, Sylvia and Lautenschläger, Birgit and Heinze, Jürgen},
journal = {Insectes Sociaux},
number = {3},
pages = {221 -- 228},
publisher = {Springer},
title = {{A transitional stage between the ergatoid and winged male morph in the ant Cardiocondyla obscurior}},
doi = {10.1007/s00040-002-8305-z},
volume = {49},
year = {2002},
}
@article{3925,
abstract = {Males of the tropical ant Cardiocondyla obscurior are either wingless and aggressive or winged and docile, and both compete for access to virgin queens in the nest1, 2. Although the fighter males (ergatoids) attack and kill other ergatoids, they tolerate and even attempt to mate with their winged rivals. Here we show that the winged males avoid the aggression of wingless males by mimicking the chemical bouquet of virgin queens, but that their mating success is not reduced as a result. This example of female mimicry by vigorous males is surprising, as in other species it is typically used as a protective strategy by weaker males, and may explain the coexistence and equal mating success of two male morphs.},
author = {Cremer, Sylvia and Sledge, Matthew and Heinze, Jürgen},
journal = {Nature},
pages = {897 -- 897},
publisher = {Nature Publishing Group},
title = {{Chemical mimicry: Male ants disguised by the queen's bouquet}},
doi = {10.1038/419897a},
volume = {419},
year = {2002},
}
@article{3995,
abstract = {This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.},
author = {Agarwal, Pankaj K and Guibas, Leonidas J and Herbert Edelsbrunner and Erickson, Jeff and Isard, Michael and Har-Peled, Sariel and Hershberger, John and Jensen, Christian and Kavraki, Lydia and Koehl, Patrice and Lin, Ming and Manocha, Dinesh and Metaxas, Dimitris and Mirtich, Brian and Mount, David and Muthukrishnan, Sankara and Pai, Dinesh and Sacks, Elisha and Snoeyink, Jack and Suri, Subhash and Wolefson, Ouri},
journal = {ACM Computing Surveys},
number = {4},
pages = {550 -- 572},
publisher = {ACM},
title = {{Algorithmic issues in modeling motion}},
doi = {10.1145/592642.592647},
volume = {34},
year = {2002},
}
@article{3996,
abstract = {We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as either a feature or noise depending on its lifetime or persistence within the filtration. We give fast algorithms for computing persistence and experimental evidence for their speed and utility.},
author = {Herbert Edelsbrunner and Letscher, David and Zomorodian, Afra},
journal = {Discrete & Computational Geometry},
number = {4},
pages = {511 -- 533},
publisher = {Springer},
title = {{Topological persistence and simplification}},
doi = {10.1007/s00454-002-2885-2},
volume = {28},
year = {2002},
}
@article{3998,
abstract = {We present results on a two-step improvement of mesh quality in three-dimensional Delaunay triangulations. The first step refines the triangulation by inserting sinks and eliminates tetrahedra with large circumradius over shortest edge length ratio. The second step assigns weights to the vertices to eliminate slivers. Our experimental findings provide evidence for the practical effectiveness of sliver exudation.},
author = {Herbert Edelsbrunner and Guoy, Damrong},
journal = {Engineering with Computers},
number = {3},
pages = {229 -- 240},
publisher = {Springer},
title = {{An experimental study of sliver exudation}},
doi = {10.1007/s003660200020},
volume = {18},
year = {2002},
}
@article{4000,
abstract = {We present fast implementations of a hybrid algorithm for reporting box and cube intersections. Our algorithm initially takes a divide-and-conquer approach and switches to simpler algorithms for low numbers of boxes. We use our implementations as engines to solve problems about geometric primitives. We look at two such problems in the category of quality analysis of surface triangulations.},
author = {Zomorodian, Afra and Herbert Edelsbrunner},
journal = {International Journal of Computational Geometry and Applications},
number = {1-2},
pages = {143 -- 172},
publisher = {World Scientific Publishing},
title = {{Fast software for box intersections}},
doi = {10.1142/S0218195902000785},
volume = {12},
year = {2002},
}
@inproceedings{4003,
abstract = {The writhing number measures the global geometry of a closed space curve or knot. We show that this measure is related to the average winding number of its Gauss map. Using this relationship, we give an algorithm for computing the writhing number for a polygonal knot with n edges in time roughly proportional to n(1.6). We also implement a different, simple algorithm and provide experimental evidence for its practical efficiency.},
author = {Agarwal, Pankaj K and Herbert Edelsbrunner and Wang, Yusu},
pages = {791 -- 799},
publisher = {SIAM},
title = {{Computing the writhing number of a polygonal knot}},
year = {2002},
}
@article{4139,
author = {Jitka Polechova and Stopka,P.},
journal = {Canadian Journal of Zoology},
number = {8},
pages = {1383 -- 1388},
publisher = {NRC Research Press},
title = {{Geometry of social relationships in the Old World wood mouse, Apodemus sylvaticus}},
doi = {3820},
volume = {80},
year = {2002},
}
@article{4148,
abstract = {Members of the Wnt family have been implicated in a variety of developmental processes including axis formation, Patterning of the central nervous system and tissue morphogenesis. Recent studies have shown that a Wnt signalling pathway similar to that involved in the establishment of planar cell polarity in Drosophila regulates convergent extension movements during zebrafish and Xenopus gastrulation. This finding provides a good starting point to dissect the complex cell biology and genetic regulation of vertebrate gastrulation movements.},
author = {Tada, Masazumi and Concha, Miguel L and Heisenberg, Carl-Philipp},
journal = {Seminars in Cell & Developmental Biology},
number = {3},
pages = {251 -- 260},
publisher = {Academic Press},
title = {{Non-canonical Wnt signalling and regulation of gastrulation movements}},
doi = {10.1016/S1084-9521(02)00052-6},
volume = {13},
year = {2002},
}
@article{4194,
abstract = {Cells at the anterior boundary of the neural plate (ANB) can induce telencephalic gene expression when transplanted to more posterior regions. Here, we identify a secreted Frizzled-related Wnt antagonist, Tic, that is expressed in ANB cells and can cell nonautonomously promote telencephalic gene expression in a concentration-dependent manner. Moreover, abrogation of Tlc function compromises telencephalic development. We also identify Wnt8b as a locally acting modulator of regional fate in the anterior neural plate and a likely target for antagonism by Tic. Finally, we show that tlc expression is regulated by signals that establish early antero-posterior and dorso-ventral ectodermal pattern. From these studies, we propose that local antagonism of Wnt activity within the anterior ectoderm is required to establish the telencephalon.},
author = {Houart, Corinne and Caneparo, Luca and Heisenberg, Carl-Philipp and Barth, K Anukampa and Take-uchi, Masaya and Wilson, Stephen W},
journal = {Neuron},
number = {2},
pages = {255 -- 265},
publisher = {Elsevier},
title = {{Establishment of the telencephalon during gastrulation by local antagonism of Wnt signaling}},
doi = {10.1016/S0896-6273(02)00751-1},
volume = {35},
year = {2002},
}
@article{4196,
abstract = {During vertebrate gastrulation, large cellular rearrangements lead to the formation of the three germ layers, ectoderm, mesoderm and endoderm. Zebrafish offer many genetic and experimental advantages for studying vertebrate gastrulation movements. For instance, several mutants, including silberblick, knypek and trilobite, exhibit defects in morphogenesis during gastrulation. The identification of the genes mutated in these lines together with the analysis of the mutant phenotypes has provided new insights into the molecular and cellular mechanisms that underlie vertebrate gastrulation movements.},
author = {Heisenberg, Carl-Philipp and Tada, Masazumi},
journal = {Seminars in Cell & Developmental Biology},
number = {6},
pages = {471 -- 479},
publisher = {Academic Press},
title = {{Zebrafish gastrulation movements: bridging cell and developmental biology}},
doi = {10.1016/S1084952102001003},
volume = {13},
year = {2002},
}
@article{4199,
abstract = {Recent studies on vertebrate homologues of the van gogh/strabismus (vang/stbm) gene, a key player in planar cell polarity signalling in Drosophila, show that vang/stbm is involved in patterning and morphogenesis during vertebrate gastrulation where it modulates two distinct Wnt signals.},
author = {Heisenberg, Carl-Philipp and Tada, Masazumi},
journal = {Current Biology},
number = {4},
pages = {R126 -- R128},
publisher = {Cell Press},
title = {{Wnt signalling: A moving picture emerges from van gogh}},
doi = {10.1016/S0960-9822(02)00704-2},
volume = {12},
year = {2002},
}
@article{4207,
abstract = {Vertebrate homologues of the Strabismus/van Gogh (stbm/vang) gene have been implicated in patterning and morphogenesis during gastrulation. Recent work shows that stbm/vang is mutated in zebrafish trilobite mutants and that stbm/vang is required for morphogenesis but not patterning during zebrafish gastrulation.},
author = {Heisenberg, Carl-Philipp},
journal = {Current Biology},
number = {19},
pages = {R657 -- R659},
publisher = {Cell Press},
title = {{Wnt signalling: Refocusing on Strabismus}},
doi = {10.1016/S0960-9822(02)01160-0},
volume = {12},
year = {2002},
}
@article{4209,
abstract = {We have identified widerborst (wdb), a B' regulatory subunit of PP2A, as a conserved component of planar cell polarization mechanisms in both Drosophila and in zebrafish. In Drosophila, wdb acts at two steps during planar polarization of wing epithelial cells. It is required to organize tissue polarity proteins into proximal and distal cortical domains, thus determining wing hair orientation. It is also needed to generate the polarized membrane outgrowth that becomes the wing hair. Widerborst activates the catalytic subunit of PP2A and localizes to the distal side of a planar microtubule web that lies at the level of apical cell junctions. This suggests that polarized PP2A activation along the planar microtubule web is important for planar polarization. In zebrafish, two wdb homologs are required for convergent extension during gastrulation, supporting the conjecture that Drosophila planar cell polarization and vertebrate gastrulation movements are regulated by similar mechanisms.},
author = {Hannus, Michael and Feiguin, Fabian and Heisenberg, Carl-Philipp and Eaton, Suzanne},
journal = {Development},
number = {14},
pages = {3493 -- 3503},
publisher = {Company of Biologists},
title = {{Planar cell polarization requires Widerborst, a B ' regulatory subunit of protein phosphatase 2A}},
volume = {129},
year = {2002},
}
@article{4258,
abstract = {We studied the effect of multilocus balancing selection on neutral nucleotide variability at linked sites by simulating a model where diallelic polymorphisms are maintained at an arbitrary number of selected loci by means of symmetric overdominance. Different combinations of alleles define different genetic backgrounds that subdivide the population and strongly affect variability. Several multilocus fitness regimes with different degrees of epistasis and gametic disequilibrium are allowed. Analytical results based on a multilocus extension of the structured coalescent predict that the expected linked neutral diversity increases exponentially with the number of selected loci and can become extremely large. Our simulation results show that although variability increases with the number of genetic backgrounds that are maintained in the population, it is reduced by random fluctuations in the frequencies of those backgrounds and does not reach high levels even in very large populations. We also show that previous results on balancing selection in single-locus systems do not extend to the multilocus scenario in a straightforward way. Different patterns of linkage disequilibrium and of the frequency spectrum of neutral mutations are expected under different degrees of epistasis. Interestingly, the power to detect balancing selection using deviations from a neutral distribution of allele frequencies seems to be diminished under the fitness regime that leads to the largest increase of variability over the neutral case. This and other results are discussed in the light of data from the Mhc.},
author = {Navarro, Arcadio and Nicholas Barton},
journal = {Genetics},
number = {2},
pages = {849 -- 863},
publisher = {Genetics Society of America},
title = {{The effects of multilocus balancing selection on neutral variability}},
volume = {161},
year = {2002},
}
@article{4259,
abstract = {We extend current multilocus models to describe the effects of migration, recombination, selection, and nonrandom mating on sets of genes in diploids with varied modes of inheritance, allowing us to consider the patterns of nuclear and cytonuclear associations (disequilibria) under various models of migration. We show the relationship between the multilocus notation recently presented by Kirkpatrick, Johnson, and Barton (developed from previous work by Barton and Turelli) and the cytonuclear parameterization of Asmussen, Arnold, and Avise and extend this notation to describe associations between cytoplasmic elements and multiple nuclear genes. Under models with sexual symmetry, both nuclear-nuclear and cytonuclear disequilibria are equivalent. They differ, however, in cases involving some type of sexual asymmetry, which is then reflected in the asymmetric inheritance of cytoplasmic markers. An example given is the case of different migration rates in males and females; simulations using 2, 3, 4, or 5 unlinked autosomal markers with a maternally inherited cytoplasmic marker illustrate how nuclear-nuclear and cytonuclear associations can be used to separately estimate female and male migration rates. The general framework developed here allows us to investigate conditions where associations between loci with different modes of inheritance are not equivalent and to use this nonequivalence to test for deviations from simple models of admixture. },
author = {Orive, Maria E and Nicholas Barton},
journal = {Genetics},
number = {3},
pages = {1469 -- 1485},
publisher = {Genetics Society of America},
title = {{Associations between cytoplasmic and nuclear loci in hybridizing populations}},
volume = {162},
year = {2002},
}
@article{4260,
abstract = {We calculate the fixation probability of a beneficial allele that arises as the result of a unique mutation in an asexual population that is subject to recurrent deleterious mutation at rate U. Our analysis is an extension of previous works, which make a biologically restrictive assumption that selection against deleterious alleles is stronger than that on the beneficial allele of interest. We show that when selection against deleterious alleles is weak, beneficial alleles that confer a selective advantage that is small relative to U have greatly reduced probabilities of fixation. We discuss the consequences of this effect for the distribution of effects of alleles fixed during adaptation. We show that a selective sweep will increase the fixation probabilities of other beneficial mutations arising during some short interval afterward. We use the calculated fixation probabilities to estimate the expected rate of fitness improvement in an asexual population when beneficial alleles arise continually at some low rate proportional to U. We estimate the rate of mutation that is optimal in the sense that it maximizes this rate of fitness improvement. Again, this analysis relaxes the assumption made previously that selection against deleterious alleles is stronger than on beneficial alleles. },
author = {Johnson, Toby and Nicholas Barton},
journal = {Genetics},
number = {1},
pages = {395 -- 411},
publisher = {Genetics Society of America},
title = {{The effect of deleterious alleles on adaptation in asexual populations}},
volume = {162},
year = {2002},
}
@article{4261,
abstract = {Until recently, it was impracticable to identify the genes that are responsible for variation in continuous traits, or to directly observe the effects of their different alleles. Now, the abundance of genetic markers has made it possible to identify quantitative trait loci (QTL) — the regions of a chromosome or, ideally, individual sequence variants that are responsible for trait variation. What kind of QTL do we expect to find and what can our observations of QTL tell us about how organisms evolve? The key to understanding the evolutionary significance of QTL is to understand the nature of inherited variation, not in the immediate mechanistic sense of how genes influence phenotype, but, rather, to know what evolutionary forces maintain genetic variability.},
author = {Nicholas Barton and Keightley, Peter D},
journal = {Nature Reviews Genetics},
pages = {11 -- 21},
publisher = {Nature Publishing Group},
title = {{Understanding quantitative genetic variation}},
doi = {10.1038/nrg700},
volume = {3},
year = {2002},
}
@article{4262,
abstract = {Natural populations are structured spatially into local populations and genetically into diverse ‘genetic backgrounds’ defined by different combinations of selected alleles. If selection maintains genetic backgrounds at constant frequency then neutral diversity is enhanced. By contrast, if background frequencies fluctuate then diversity is reduced. Provided that the population size of each background is large enough, these effects can be described by the structured coalescent process. Almost all the extant results based on the coalescent deal with a single selected locus. Yet we know that very large numbers of genes are under selection and that any substantial effects are likely to be due to the cumulative effects of many loci. Here, we set up a general framework for the extension of the coalescent to multilocus scenarios and we use it to study the simplest model, where strong balancing selection acting on a set of n loci maintains 2n backgrounds at constant frequencies and at linkage equilibrium. Analytical results show that the expected linked neutral diversity increases exponentially with the number of selected loci and can become extremely large. However, simulation results reveal that the structured coalescent approach breaks down when the number of backgrounds approaches the population size, because of stochastic fluctuations in background frequencies. A new method is needed to extend the structured coalescent to cases with large numbers of backgrounds.},
author = {Nicholas Barton and Navarro, Arcadio},
journal = {Genetical Research},
number = {2},
pages = {129 -- 139},
publisher = {Cambridge University Press},
title = {{Extending the coalescent to multilocus systems: the case of balancing selection}},
doi = {10.1017/S0016672301005493},
volume = {79},
year = {2002},
}
@article{4263,
abstract = {We introduce a general recursion for the probability of identity in state of two individuals sampled from a population subject to mutation, migration, and random drift in a two-dimensional continuum. The recursion allows for the interactions induced by density-dependent regulation of the population, which are inevitable in a continuous population. We give explicit series expansions for large neighbourhood size and for low mutation rates respectively and investigate the accuracy of the classical Malécot formula for these general models. When neighbourhood size is small, this formula does not give the identity even over large scales. However, for large neighbourhood size, it is an accurate approximation which summarises the local population structure in terms of three quantities: the effective dispersal rate, σe; the effective population density, ρe; and a local scale, κ, at which local interactions become significant. The results are illustrated by simulations.},
author = {Nicholas Barton and Depaulis, Frantz and Etheridge, Alison M},
journal = {Theoretical Population Biology},
number = {1},
pages = {31 -- 48},
publisher = {Academic Press},
title = {{Neutral evolution in spatially continuous populations}},
doi = {10.1006/tpbi.2001.1557},
volume = {61},
year = {2002},
}
@article{4347,
abstract = {Phylogenetic trees can be rooted by a number of criteria. Here, we introduce a Bayesian method for inferring the root of a phylogenetic tree by using one of several criteria: the outgroup, molecular clock, and nonreversible model of DNA substitution. We perform simulation analyses to examine the relative ability of these three criteria to correctly identify the root of the tree. The outgroup and molecular clock criteria were best able to identify the root of the tree, whereas the nonreversible model was able to identify the root only when the substitution process was highly nonreversible. We also examined the performance of the criteria for a tree of four species for which the topology and root position are well supported. Results of the analyses of these data are consistent with the simulation results.},
author = {Huelsenbeck, John P and Jonathan Bollback and Levine, Amy M},
journal = {Systematic Biology},
number = {1},
pages = {32 -- 43},
publisher = {Oxford University Press},
title = {{Inferring the root of a phylogenetic tree}},
doi = {10.1080/106351502753475862},
volume = {51},
year = {2002},
}
@article{4349,
abstract = {Bayesian inference is becoming a common statistical approach to phylogenetic estimation because, among other reasons, it allows for rapid analysis of large data sets with complex evolutionary models. Conveniently, Bayesian phylogenetic methods use currently available stochastic models of sequence evolution. However, as with other model-based approaches, the results of Bayesian inference are conditional on the assumed model of evolution: inadequate models (models that poorly fit the data) may result in erroneous inferences. In this article, I present a Bayesian phylogenetic method that evaluates the adequacy of evolutionary models using posterior predictive distributions. By evaluating a model's posterior predictive performance, an adequate model can be selected for a Bayesian phylogenetic study. Although I present a single test statistic that assesses the overall (global) performance of a phylogenetic model, a variety of test statistics can be tailored to evaluate specific features (local performance) of evolutionary models to identify sources failure. The method presented here, unlike the likelihood-ratio test and parametric bootstrap, accounts for uncertainty in the phylogeny and model parameters.},
author = {Jonathan Bollback},
journal = {Molecular Biology and Evolution},
number = {7},
pages = {1171 -- 80},
publisher = {Oxford University Press},
title = {{Bayesian model adequacy and choice in phylogenetics}},
volume = {19},
year = {2002},
}
@article{4407,
abstract = {This paper presents a complete axiomatization of two decidable propositional real-time linear temporal logics: Event Clock Logic (EventClockTL) and Metric Interval Temporal Logic with past (MetricIntervalTL). The completeness proof consists of an effective proof building procedure for EventClockTL. From this result we obtain a complete axiomatization of MetricIntervalTL by providing axioms translating MetricIntervalTL formulae into EventClockTL formulae, the two logics being equally expressive. Our proof is structured to yield axiomatizations also for interesting fragments of these logics, such as the linear temporal logic of the real numbers (TLR).},
author = {Raskin, Jean-François and Schobbens, Pierre Y and Thomas Henzinger},
journal = {Theoretical Computer Science},
number = {1-2},
pages = {151 -- 182},
publisher = {Elsevier},
title = {{Axioms for real-time logics}},
doi = {10.1016/S0304-3975(00)00308-X},
volume = {274},
year = {2002},
}
@inproceedings{4413,
abstract = {An essential problem in component-based design is how to compose components designed in isolation. Several approaches have been proposed for specifying component interfaces that capture behavioral aspects such as interaction protocols, and for verifying interface compatibility. Likewise, several approaches have been developed for synthesizing converters between incompatible protocols. In this paper, we introduce the notion of adaptability as the property that two interfaces have when they can be made compatible by communicating through a converter that meets specified requirements. We show that verifying adaptability and synthesizing an appropriate converter are two faces of the same coin: adaptability can be formalized and solved using a game-theoretic framework, and then the converter can be synthesized as a strategy that always wins the game. Finally we show that this framework can be related to the rectification problem in trace theory.},
author = {Passerone, Roberto and de Alfaro, Luca and Thomas Henzinger and Sangiovanni-Vincentelli, Alberto},
pages = {132 -- 139},
publisher = {IEEE},
title = {{Convertibility verification and converter synthesis: Two faces of the same coin}},
doi = {10.1145/774572.774592},
year = {2002},
}
@phdthesis{4414,
abstract = {This dissertation investigates game-theoretic approaches to the algorithmic analysis of concurrent, reactive systems. A concurrent system comprises a number of components working concurrently; a reactive system maintains an ongoing interaction with its environment. Traditional approaches to the formal analysis of concurrent reactive systems usually view the system as an unstructured state-transition graphs; instead, we view them as collections of interacting components, where each one is an open system which accepts inputs from the other components. The interactions among the components are naturally modeled as games.
Adopting this game-theoretic view, we study three related problems pertaining to the verification and synthesis of systems. Firstly, we propose two novel game-theoretic techniques for the model-checking of concurrent reactive systems, and improve the performance of model-checking. The first technique discovers an error as soon as it cannot be prevented, which can be long before it actually occurs. This technique is based on the key observation that "unpreventability" is a local property to a module: an error is unpreventable in a module state if no environment can prevent it. The second technique attempts to decompose a model-checking proof into smaller proof obligations by constructing abstract modules automatically, using reachability and "unpreventability" information about the concrete modules. Three increasingly powerful proof decomposition rules are proposed and we show that in practice, the resulting abstract modules are often significantly smaller than the concrete modules and can drastically reduce the space and time requirements for verification. Both techniques fall into the category of compositional reasoning.
Secondly, we investigate the composition and control of synchronous systems. An essential property of synchronous systems for compositional reasoning is non-blocking. In the composition of synchronous systems, however, due to circular causal dependency of input and output signals, non-blocking is not always guaranteed. Blocking compositions of systems can be ruled out semantically, by insisting on the existence of certain fixed points, or syntactically, by equipping systems with types, which make the dependencies between input and output signals transparent. We characterize various typing mechanisms in game-theoretic terms, and study their effects on the controller synthesis problem. We show that our typing systems are general enough to capture interesting real-life synchronous systems such as all delay-insensitive digital circuits. We then study their corresponding single-step control problems --a restricted form of controller synthesis problem whose solutions can be iterated in appropriate manners to solve all LTL controller synthesis problems. We also consider versions of the controller synthesis problem in which the type of the controller 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.
Thirdly, we study the synthesis of a class of open systems, namely, uninitialized state machines. The sequential synthesis problem, which is closely related to Church's solvability problem, asks, given a specification in the form of a binary relation between input and output streams, for the construction of a finite-state stream transducer that converts inputs to appropriate outputs. For efficiency reasons, practical sequential hardware is often designed to operate without prior initialization. Such hardware designs can be modeled by uninitialized state machines, which are required to satisfy their specification if started from any state. We solve the sequential synthesis problem for uninitialized systems, that is, we construct uninitialized finite-state stream transducers. We consider specifications given by LTL formulas, deterministic, nondeterministic, universal, and alternating Buechi automata. We solve this uninitialized synthesis problem by reducing it to the well-understood initialized synthesis problem. While our solution is straightforward, it leads, for some specification formalisms, to upper bounds that are exponentially worse than the complexity of the corresponding initialized problems. However, we prove lower bounds to show that our simple solutions are optimal for all considered specification formalisms. The lower bound proofs require nontrivial generic reductions.},
author = {Mang, Freddy Y},
pages = {1 -- 116},
publisher = {University of California, Berkeley},
title = {{Games in open systems verification and synthesis}},
year = {2002},
}
@inproceedings{4421,
abstract = {We demonstrate the feasibility and benefits of Giotto-based control software development by reimplementing the autopilot system of an autonomously flying model helicopter. Giotto offers a clean separation between the platform-independent concerns of software functionality and I/O timing, and the platform-dependent concerns of software scheduling and execution. Functionality code such as code computing control laws can be generated automatically from Simulink models or, as in the case of this project, inherited from a legacy system. I/O timing code is generated automatically from Giotto models that specify real-time requirements such as task frequencies and actuator update rates. We extend Simulink to support the design of Giotto models, and from these models, the automatic generation of Giotto code that supervises the interaction of the functionality code with the physical environment. The Giotto compiler performs a schedulability analysis on the Giotto code, and generates timing code for the helicopter platform. The Giotto methodology guarantees the stringent hard real-time requirements of the autopilot system, and at the same time supports the automation of the software development process in a way that produces a transparent software architecture with predictable behavior and reusable components.},
author = {Kirsch, Christoph M and Sanvido, Marco A and Thomas Henzinger and Pree, Wolfgang},
pages = {46 -- 60},
publisher = {ACM},
title = {{A Giotto-based helicopter control system}},
doi = {10.1007/3-540-45828-X_5},
volume = {2491},
year = {2002},
}
@inproceedings{4422,
abstract = {Behavioral properties of open systems can be formalized as objectives in two-player games. Turn-based games model asynchronous interaction between the players (the system and its environment) by interleaving their moves. Concurrent games model synchronous interaction: the players always move simultaneously. Infinitary winning criteria are considered: Büchi, co-Büchi, and more general parity conditions. A generalization of determinacy for parity games to concurrent parity games demands probabilistic (mixed) strategies: either player 1 has a mixed strategy to win with probability 1 (almost-sure winning), or player 2 has a mixed strategy to win with positive probability.
This work provides efficient reductions of concurrent probabilistic Büchi and co-Büchi games to turn-based games with Büchi condition and parity winning condition with three priorities, respectively. From a theoretical point of view, the latter reduction shows that one can trade the probabilistic nature of almost-sure winning for a more general parity (fairness) condition. The reductions improve understanding of concurrent games and provide an alternative simple proof of determinacy of concurrent Büchi and co-Büchi games. From a practical point of view, the reductions turn solvers of turn-based games into solvers of concurrent probabilistic games. Thus improvements in the well-studied algorithms for the former carry over immediately to the latter. In particular, a recent improvement in the complexity of solving turn-based parity games yields an improvement in time complexity of solving concurrent probabilistic co-Büchi games from cubic to quadratic.},
author = {Jurdziński, Marcin and Kupferman, Orna and Thomas Henzinger},
pages = {292 -- 305},
publisher = {Springer},
title = {{Trading probability for fairness}},
doi = {10.1007/3-540-45793-3_20},
volume = {2471},
year = {2002},
}
@inproceedings{4423,
abstract = {Automation control systems typically incorporate legacy code and components that were originally designed to operate independently. Furthermore, they operate under stringent safety and timing constraints. Current design strategies deal with these requirements and characteristics with ad hoc approaches. In particular, when designing control laws, implementation constraints are often ignored or cursorily estimated. Indeed, costly redesigns are needed after a prototype of the control system is built due to missed timing constraints and subtle transient errors. In this paper, we use the concepts of platform-based design, and the Giotto programming language, to develop a methodology for the design of automation control systems that builds in modularity and correct-by-construction procedures. We illustrate our strategy by describing the (successful) application of the methodology to the design of a time-based control system for a rotorcraft Uninhabited Aerial Vehicle (UAV).},
author = {Horowitz, Benjamin and Liebman, Judith and Ma, Cedric and Koo, T John and Thomas Henzinger and Sangiovanni-Vincentelli, Alberto and Sastry, Shankar},
number = {1},
publisher = {Elsevier},
title = {{Embedded software design and system integration for rotorcraft UAV using platforms}},
doi = {10.3182/20020721-6-ES-1901.01628},
volume = {15},
year = {2002},
}
@inproceedings{4444,
abstract = {The Embedded Machine is a virtual machine that mediates in real time the interaction between software processes and physical processes. It separates the compilation of embedded programs into two phases. The first, platform-independent compiler phase generates E code (code executed by the Embedded Machine), which supervises the timing ---not the scheduling--- of application tasks relative to external events, such as clock ticks and sensor interrupts. E~code is portable and exhibits, given an input behavior, predictable (i.e., deterministic) timing and output behavior. The second, platform-dependent compiler phase checks the time safety of the E code, that is, whether platform performance (determined by the hardware) and platform utilization (determined by the scheduler of the operating system) enable its timely execution. We have used the Embedded Machine to compile and execute high-performance control applications written in Giotto, such as the flight control system of an autonomous model helicopter.},
author = {Thomas Henzinger and Kirsch, Christoph M},
pages = {315 -- 326},
publisher = {ACM},
title = {{The embedded machine: predictable, portable real-time code}},
doi = {10.1145/512529.512567},
year = {2002},
}
@inproceedings{4470,
abstract = {Giotto is a platform-independent language for specifying software for high-performance control applications. In this paper we present a new approach to the compilation of Giotto. Following this approach, the Giotto compiler generates code for a virtual machine, called the E machine, which can be ported to different platforms. The Giotto compiler also checks if the generated E code is time safe for a given platform, that is, if the platform offers sufficient performance to ensure that the E code is executed in a timely fashion that conforms with the Giotto semantics. Time-safety checking requires a schedulability analysis. We show that while for arbitrary E code, the analysis is exponential, for E code generated from typical Giotto programs, the analysis is polynomial. This supports our claim that Giotto identifies a useful fragment of embedded programs.},
author = {Thomas Henzinger and Kirsch, Christoph M and Majumdar, Ritankar S and Matic, Slobodan},
pages = {76 -- 92},
publisher = {ACM},
title = {{Time-safety checking for embedded programs}},
doi = {10.1007/3-540-45828-X_7},
volume = {2491},
year = {2002},
}
@inproceedings{4471,
abstract = {The sequential synthesis problem, which is closely related to Church’s solvability problem, asks, given a specification in the form of a binary relation between input and output streams, for the construction of a finite-state stream transducer that converts inputs to appropriate outputs. For efficiency reasons, practical sequential hardware is often designed to operate without prior initialization. Such hardware designs can be modeled by uninitialized state machines, which are required to satisfy their specification if started from any state. In this paper we solve the sequential synthesis problem for uninitialized systems, that is, we construct uninitialized finite-state stream transducers. We consider specifications given by LTL formulas, deterministic, nondeterministic, universal, and alternating Büchi automata. We solve this uninitialized synthesis problem by reducing it to the well-understood initialized synthesis problem. While our solution is straightforward, it leads, for some specification formalisms, to upper bounds that are exponentially worse than the complexity of the corresponding initialized problems. However, we prove lower bounds to show that our simple solutions are optimal for all considered specification formalisms. We also study the problem of deciding whether a given specification is uninitialized, that is, if its uninitialized and initialized synthesis problems coincide. We show that this problem has, for each specification formalism, the same complexity as the equivalence problem.},
author = {Thomas Henzinger and Krishnan, Sriram C and Kupferman, Orna and Mang, Freddy Y},
pages = {644 -- 656},
publisher = {Springer},
title = {{Synthesis of uninitialized systems}},
doi = {10.1007/3-540-45465-9_55},
volume = {2380},
year = {2002},
}
@inproceedings{4472,
abstract = {We present a methodology and tool for verifying and certifying systems code. The verification is based on the lazy-abstraction paradigm for intertwining the following three logical steps: construct a predicate abstraction from the code, model check the abstraction, and automatically refine the abstraction based on counterexample analysis. The certification is based on the proof-carrying code paradigm. Lazy abstraction enables the automatic construction of small proof certificates. The methodology is implemented in Blast, the Berkeley Lazy Abstraction Software verification Tool. We describe our experience applying Blast to Linux and Windows device drivers. Given the C code for a driver and for a temporal-safety monitor, Blast automatically generates an easily checkable correctness certificate if the driver satisfies the specification, and an error trace otherwise.},
author = {Thomas Henzinger and Necula, George C and Jhala, Ranjit and Sutre, Grégoire and Majumdar, Ritankar S and Weimer, Westley},
pages = {526 -- 538},
publisher = {Springer},
title = {{Temporal safety proofs for systems code}},
doi = {10.1007/3-540-45657-0_45},
volume = {2404},
year = {2002},
}
@article{4473,
abstract = {The simulation preorder on state transition systems is widely accepted as a useful notion of refinement, both in its own right and as an efficiently checkable sufficient condition for trace containment. For composite systems, due to the exponential explosion of the state space, there is a need for decomposing a simulation check of the form P ≤s Q, denoting "P is simulated by Q," into simpler simulation checks on the components of P and Q. We present an assume-guarantee rule that enables such a decomposition. To the best of our knowledge, this is the first assume-guarantee rule that applies to a refinement relation different from trace containment. Our rule is circular, and its soundness proof requires induction on trace trees. The proof is constructive: given simulation relations that witness the simulation preorder between corresponding components of P and Q, we provide a procedure for constructing a witness relation for P ≤s Q. We also extend our assume-guarantee rule to account for fairness constraints on transition systems.},
author = {Thomas Henzinger and Qadeer,Shaz and Rajamani, Sriram K and Tasiran, Serdar},
journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)},
number = {1},
pages = {51 -- 64},
publisher = {ACM},
title = {{An assume-guarantee rule for checking simulation}},
doi = {10.1145/509705.509707},
volume = {24},
year = {2002},
}
@article{4474,
abstract = {The simulation preorder for labeled transition systems is defined locally, and operationally, as a game that relates states with their immediate successor states. Simulation enjoys many appealing properties. First, simulation has a denotational characterization: system S simulates system I iff every computation tree embedded in the unrolling of I can be embedded also in the unrolling of S. Second, simulation has a logical characterization: S simulates I iff every universal branching-time formula satisfied by S is satisfied also by I. It follows that simulation is a suitable notion of implementation, and it is the coarsest abstraction of a system that preserves universal branching-time properties. Third, based on its local definition, simulation between finite-state systems can be checked in polynomial time. Finally, simulation implies trace containment, which cannot be defined locally and requires polynomial space for verification. Hence simulation is widely used both in manual and in automatic verification. Liveness assumptions about transition systems are typically modeled using fairness constraints. Existing notions of simulation for fair transition systems, however, are not local, and as a result, many appealing properties of the simulation preorder are lost. We propose a new view of fair simulation by extending the local definition of simulation to account for fairness: system View the MathML sourcefairly simulates system View the MathML source iff in the simulation game, there is a strategy that matches with each fair computation of View the MathML source a fair computation of View the MathML source. Our definition enjoys a denotational characterization and has a logical characterization: View the MathML source fairly simulates View the MathML source iff every fair computation tree (whose infinite paths are fair) embedded in the unrolling of View the MathML source can be embedded also in the unrolling of View the MathML source or, equivalently, iff every Fair-∀AFMC formula satisfied by View the MathML source is satisfied also by View the MathML source (∀AFMC is the universal fragment of the alternation-free μ-calculus). The locality of the definition leads us to a polynomial-time algorithm for checking fair simulation for finite-state systems with weak and strong fairness constraints. Finally, fair simulation implies fair trace containment and is therefore useful as an efficiently computable local criterion for proving linear-time abstraction hierarchies of fair systems.},
author = {Thomas Henzinger and Kupferman, Orna and Rajamani, Sriram K},
journal = {Information and Computation},
number = {1},
pages = {64 -- 81},
publisher = {Elsevier},
title = {{Fair simulation}},
doi = {10.1006/inco.2001.3085},
volume = {173},
year = {2002},
}
@inproceedings{4476,
abstract = {One approach to model checking software is based on the abstract-check-refine paradigm: build an abstract model, then check the desired property, and if the check fails, refine the model and start over. We introduce the concept of lazy abstraction to integrate and optimize the three phases of the abstract-check-refine loop. Lazy abstraction continuously builds and refines a single abstract model on demand, driven by the model checker, so that different parts of the model may exhibit different degrees of precision, namely just enough to verify the desired property. We present an algorithm for model checking safety properties using lazy abstraction and describe an implementation of the algorithm applied to C programs. We also provide sufficient conditions for the termination of the method.},
author = {Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S and Sutre, Grégoire},
pages = {58 -- 70},
publisher = {ACM},
title = {{Lazy abstraction}},
doi = {10.1145/503272.503279},
year = {2002},
}
@inproceedings{4562,
abstract = {We present interface models that describe both the input assumptions of a component, and its output behavior. By enabling us to check that the input assumptions of a component are met in a design, interface models provide a compatibility check for component-based design. When refining a design into an implementation, interface models require that the output behavior of a component satisfies the design specification only when the input assumptions of the specification are satisfied, yielding greater flexibility in the choice of implementations. Technically, our interface models are games between two players, Input and Output; the duality of the players accounts for the dual roles of inputs and outputs in composition and refinement. We present two interface models in detail, one for a simple synchronous form of interaction between components typical in hardware, and the other for more complex synchronous interactions on bidirectional connections. As an example, we specify the interface of a bidirectional bus, with the input assumption that at any time at most one component has write access to the bus. For these interface models, we present algorithms for compatibility and refinement checking, and we describe efficient symbolic implementations.},
author = {Chakrabarti, Arindam and de Alfaro, Luca and Thomas Henzinger and Mang, Freddy Y},
pages = {414 -- 427},
publisher = {Springer},
title = {{Synchronous and bidirectional component interfaces}},
doi = {10.1007/3-540-45657-0_34},
volume = {2404},
year = {2002},
}
@inproceedings{4563,
abstract = {We present a formal methodology and tool for uncovering errors in the interaction of software modules. Our methodology consists of a suite of languages for defining software interfaces, and algorithms for checking interface compatibility. We focus on interfaces that explain the method-call dependencies between software modules. Such an interface makes assumptions about the environment in the form of call and availability constraints. A call constraint restricts the accessibility of local methods to certain external methods. An availability constraint restricts the accessibility of local methods to certain states of the module. For example, the interface for a file server with local methods open and read may assert that a file cannot be read without having been opened. Checking interface compatibility requires the solution of games, and in the presence of availability constraints, of pushdown games. Based on this methodology, we have implemented a tool that has uncovered incompatibilities in TinyOS, a small operating system for sensor nodes in adhoc networks.},
author = {Chakrabarti, Arindam and de Alfaro, Luca and Thomas Henzinger and Jurdziński, Marcin and Mang, Freddy Y},
pages = {428 -- 441},
publisher = {Springer},
title = {{Interface compatibility checking for software modules}},
doi = {10.1007/3-540-45657-0_35},
volume = {2404},
year = {2002},
}
@inproceedings{4565,
abstract = {In the literature, we find several formulations of the control
problem for timed and hybrid systems. We argue that formulations where
a controller can cause an action at any point in dense (rational or real)
time are problematic, by presenting an example where the controller
must act faster and faster, yet causes no Zeno effects (say, the control
actions are at times 0, 1/2, 1, 1 1/4, 2, 2 1/8, 3, 3 1/16 ,...). Such a controller is,
of course, not implementable in software. Such controllers are avoided by formulations where the controller can cause actions only at discrete (integer) points in time. While the resulting control problem is well- understood if the time unit, or “sampling rate” of the controller, is fixed a priori, we define a novel, stronger formulation: the discrete-time control problem with unknown sampling rate asks if a sampling controller exists for some sampling rate. We prove that this problem is undecidable even in the special case of timed automata.},
author = {Cassez, Franck and Thomas Henzinger and Raskin, Jean-François},
pages = {134 -- 148},
publisher = {Springer},
title = {{A comparison of control problems for timed and hybrid systems}},
doi = {10.1007/3-540-45873-5_13},
volume = {2289},
year = {2002},
}
@article{4595,
abstract = {Temporal logic comes in two varieties: linear-time temporal logic assumes implicit universal quantification over all paths that are generated by the execution of a system; branching-time temporal logic allows explicit existential and universal quantification over all paths. We introduce a third, more general variety of temporal logic: alternating-time temporal logic offers selective quantification over those paths that are possible outcomes of games, such as the game in which the system and the environment alternate moves. While linear-time and branching-time logics are natural specification languages for closed systems, alternating-time logics are natural specification languages for open systems. For example, by preceding the temporal operator "eventually" with a selective path quantifier, we can specify that in the game between the system and the environment, the system has a strategy to reach a certain state. The problems of receptiveness, realizability, and controllability can be formulated as model-checking problems for alternating-time formulas. Depending on whether or not we admit arbitrary nesting of selective path quantifiers and temporal operators, we obtain the two alternating-time temporal logics ATL and ATL*.ATL and ATL* are interpreted over concurrent game structures. Every state transition of a concurrent game structure results from a choice of moves, one for each player. The players represent individual components and the environment of an open system. Concurrent game structures can capture various forms of synchronous composition for open systems, and if augmented with fairness constraints, also asynchronous composition. Over structures without fairness constraints, the model-checking complexity of ATL is linear in the size of the game structure and length of the formula, and the symbolic model-checking algorithm for CTL extends with few modifications to ATL. Over structures with weak-fairness constraints, ATL model checking requires the solution of 1-pair Rabin games, and can be done in polynomial time. Over structures with strong-fairness constraints, ATL model checking requires the solution of games with Boolean combinations of Büchi conditions, and can be done in PSPACE. In the case of ATL*, the model-checking problem is closely related to the synthesis problem for linear-time formulas, and requires doubly exponential time.},
author = {Alur, Rajeev and Thomas Henzinger and Kupferman, Orna},
journal = {Journal of the ACM},
number = {5},
pages = {672 -- 713},
publisher = {ACM},
title = {{Alternating-time temporal logic}},
doi = {10.1145/585265.585270},
volume = {49},
year = {2002},
}
@inproceedings{4631,
abstract = {We present a theory of timed interfaces, which is capable of specifying both the timing of the inputs a component expects from the environment, and the timing of the outputs it can produce. Two timed interfaces are compatible if there is a way to use them together such that their timing expectations are met. Our theory provides algorithms for checking the compatibility between two interfaces and for deriving the composite interface; the theory can thus be viewed as a type system for real-time interaction. Technically, a timed interface is encoded as a timed game between two players, representing the inputs and outputs of the component. The algorithms for compatibility checking and interface composition are thus derived from algorithms for solving timed games.},
author = {de Alfaro, Luca and Thomas Henzinger and Stoelinga, Mariëlle},
pages = {108 -- 122},
publisher = {ACM},
title = {{Timed interfaces}},
doi = {10.1007/3-540-45828-X_9},
volume = {2491},
year = {2002},
}
@article{6158,
abstract = {Wild isolates of Caenorhabditis elegans can feed either alone or in groups1,2. This natural variation in behaviour is associated with a single residue difference in NPR-1, a predicted G-protein-coupled neuropeptide receptor related to Neuropeptide Y receptors2. Here we show that the NPR-1 isoform associated with solitary feeding acts in neurons exposed to the body fluid to inhibit social feeding. Furthermore, suppressing the activity of these neurons, called AQR, PQR and URX, using an activated K+ channel, inhibits social feeding. NPR-1 activity in AQR, PQR and URX neurons seems to suppress social feeding by antagonizing signalling through a cyclic GMP-gated ion channel encoded by tax-2 and tax-4. We show that mutations in tax-2 or tax-4 disrupt social feeding, and that tax-4 is required in several neurons for social feeding, including one or more of AQR, PQR and URX. The AQR, PQR and URX neurons are unusual in C. elegans because they are directly exposed to the pseudocoelomic body fluid3. Our data suggest a model in which these neurons integrate antagonistic signals to control the choice between social and solitary feeding behaviour.},
author = {Coates, Juliet C. and de Bono, Mario},
issn = {0028-0836},
journal = {Nature},
number = {6910},
pages = {925--929},
publisher = {Springer Nature},
title = {{Antagonistic pathways in neurons exposed to body fluid regulate social feeding in Caenorhabditis elegans}},
doi = {10.1038/nature01170},
volume = {419},
year = {2002},
}
@article{6159,
abstract = {Natural Caenorhabditis elegans isolates exhibit either social or solitary feeding on bacteria. We show here that social feeding is induced by nociceptive neurons that detect adverse or stressful conditions. Ablation of the nociceptive neurons ASH and ADL transforms social animals into solitary feeders. Social feeding is probably due to the sensation of noxious chemicals by ASH and ADL neurons; it requires the genes ocr-2 and osm-9, which encode TRP-related transduction channels, and odr-4 and odr-8, which are required to localize sensory chemoreceptors to cilia. Other sensory neurons may suppress social feeding, as social feeding in ocr-2 and odr-4 mutants is restored by mutations in osm-3, a gene required for the development of 26 ciliated sensory neurons. Our data suggest a model for regulation of social feeding by opposing sensory inputs: aversive inputs to nociceptive neurons promote social feeding, whereas antagonistic inputs from neurons that express osm-3 inhibit aggregation.},
author = {de Bono, Mario and Tobin, David M. and Davis, M. Wayne and Avery, Leon and Bargmann, Cornelia I.},
issn = {0028-0836},
journal = {Nature},
number = {6910},
pages = {899--903},
publisher = {Springer Nature},
title = {{Social feeding in Caenorhabditis elegans is induced by neurons that detect aversive stimuli}},
doi = {10.1038/nature01169},
volume = {419},
year = {2002},
}