TY - JOUR AB - T cells develop in the thymus in a highly specialized cellular and extracellular microenvironment. The basement membrane molecule, laminin-5 (LN-5), is predominantly found in the medulla of the human thymic lobules. Using high-resolution light microscopy, we show here that LN-5 is localized in a bi-membranous conduit-like structure, together with other typical basement membrane components including collagen type IV, nidogen and perlecan. Other interstitial matrix components, such as fibrillin-1 or -2, tenascin-C or fibrillar collagen types, were also associated with these structures. Three-dimensional (3D) confocal microscopy suggested a tubular structure, whereas immunoelectron and transmission electron microscopy showed that the core of these tubes contained fibrillar collagens enwrapped by the LN-5-containing membrane. These medullary conduits are surrounded by thymic epithelial cells, which in vitro were found to bind LN-5, but also fibrillin and tenascin-C. Dendritic cells were also detected in close vicinity to the conduits. Both of these stromal cell types express major histocompatibility complex (MHC) class II molecules capable of antigen presentation. The conduits are connected to blood vessels but, with an average diameter of 2 mum, they are too small to transport cells. However, evidence is provided that smaller molecules such as a 10 kDa dextran, but not large molecules (>500 kDa), can be transported in the conduits. These results clearly demonstrate that a conduit system, which is also known from secondary lymphatic organs such as lymph nodes and spleen, is present in the medulla of the human thymus, and that it might serve to transport small blood-borne molecules or chemokines to defined locations within the medulla. AU - Drumea-Mirancea, Mihaela AU - Wessels, Johannes T AU - Müller, Claudia A AU - Essl, Mike AU - Eble, Johannes A AU - Tolosa, Eva AU - Koch, Manuel AU - Reinhardt, Dieter P AU - Michael Sixt AU - Sorokin, Lydia AU - Stierhof, York-Dieter AU - Schwarz, Heinz AU - Klein, Gerd ID - 3934 IS - Pt 7 JF - Journal of Cell Science TI - Characterization of a conduit system containing laminin-5 in the human thymus: a potential transport system for small molecules VL - 119 ER - TY - JOUR AB - Integrins regulate cell behavior through the assembly of multiprotein complexes at the site of cell adhesion. Parvins are components of such a multiprotein complex. They consist of three members (alpha-, beta-, and gamma-parvin), form a functional complex with integrin-linked kinase (ILK) and PINCH, and link integrins to the actin cytoskeleton. Whereas alpha- and beta-parvins are widely expressed, gamma-parvin has been reported to be expressed in hematopoietic organs. In the present study, we report the expression pattern of the parvins in hematopoietic cells and the phenotypic analysis of gamma-parvin-deficient mice. Whereas alpha-parvin is not expressed in hematopoietic cells, beta-parvin is only found in myeloid cells and gamma-parvin is present in both cells of the myeloid and lymphoid lineages, where it binds ILK. Surprisingly, loss of gamma-parvin expression had no effect on blood cell differentiation, proliferation, and survival and no consequence for the T-cell-dependent antibody response and lymphocyte and dendritic cell migration. These data indicate that despite the high expression of gamma-parvin in hematopoietic cells it must play a more subtle role for blood cell homeostasis. AU - Chu, Haiyan AU - Thievessen, Ingo AU - Michael Sixt AU - Lämmermann, Tim AU - Waisman, Ari AU - Braun, Attila AU - Noegel, Angelika A AU - Fässler, Reinhard ID - 3935 IS - 5 JF - Molecular and Cellular Biology TI - γ-Parvin is dispensable for hematopoiesis, leukocyte trafficking, and T-cell-dependent antibody response VL - 26 ER - TY - JOUR AB - At least eight of the twelve known members of the beta1 integrin family are expressed on hematopoietic cells. Among these, the VCAM-1 receptor alpha4beta1 has received most attention as a main factor mediating firm adhesion to the endothelium during blood cell extravasation. Therapeutic trials are ongoing into the use of antibodies and small molecule inhibitors to target this interaction and hence obtain anti-inflammatory effects. However, extravasation is only one possible process that is mediated by beta1 integrins and there is evidence that they also mediate leukocyte retention and positioning in the tissue, lymphocyte activation and possibly migration within the interstitium. Genetic mouse models where integrins are selectively deleted on blood cells have been used to investigate these functions and further studies will be invaluable to critically evaluate therapeutic trials. AU - Michael Sixt AU - Bauer, Martina AU - Lämmermann, Tim AU - Fässler, Reinhard ID - 3936 IS - 5 JF - Current Opinion in Cell Biology TI - β1 integrins: zip codes and signaling relay for blood cells VL - 18 ER - TY - JOUR AB - Wnt11 is a key signal, determining cell polarization and migration during vertebrate gastrulation. It is known that Wnt11 functionally interacts with several signaling components, the homologues of which control planar cell polarity in Drosophila melanogaster. Although in D. melanogaster these components are thought to polarize cells by asymmetrically localizing at the plasma membrane, it is not yet clear whether their subcellular localization plays a similarly important role in vertebrates. We show that in zebrafish embryonic cells, Wnt11 locally functions at the plasma membrane by accumulating its receptor, Frizzled 7, on adjacent sites of cell contacts. Wnt11-induced Frizzled 7 accumulations recruit the intracellular Wnt signaling mediator Dishevelled, as well as Wnt11 itself, and locally increase cell contact persistence. This increase in cell contact persistence is mediated by the local interaction of Wnt11, Frizzled 7, and the atypical cadherin Flamingo at the plasma membrane, and it does not require the activity of further downstream effectors of Wnt11 signaling, such as RhoA and Rok2. We propose that Wnt11, by interacting with Frizzled 7 and Flamingo, modulates local cell contact persistence to coordinate cell movements during gastrulation. AU - Witzel, Sabine AU - Zimyanin, Vitaly AU - Carreira Barbosa, Filipa AU - Tada, Masazumi AU - Heisenberg, Carl-Philipp J ID - 4140 IS - 5 JF - Journal of Cell Biology TI - Wnt11 controls cell contact persistence by local accumulation of Frizzled 7 at the plasma membrane VL - 175 ER - TY - JOUR AB - The detection of microRNAs (miRNAs) at single-cell resolution is important for studying the role of these posttranscriptional regulators. Here, we use a dual-fluorescent green fluorescent protein (GFP)-reporter/monomeric red fluorescent protein (mRFP)-sensor (DFRS) plasmid, injected into zebrafish blastomeres or electroporated into defined tissues of mouse embryos in utero or ex utero, to monitor the dynamics of specific miRNAs in individual live cells. This approach reveals, for example, that in the developing mouse central nervous system,, miR-124a is expressed not only in postmitotic neurons but also in neuronal progenitor cells. Collectively, our results demonstrate that acute administration of DFRS plasmids.offers an alternative to previous in situ hybridization and transgenic approaches and allows the monitoring of miRNA appearance and disappearance in defined cell lineages during vertebrate development. AU - Tonelli, Davide AU - Calegari, Frederico AU - Fei, Ji AU - Nomura, Tadashi AU - Osumi, Noriko AU - Heisenberg, Carl-Philipp J AU - Huttner, Wieland ID - 4145 IS - 6 JF - Biotechniques TI - Single-cell detection of microRNAs in developing vertebrate embryos after acute administration of a dual-fluorescence reporter/sensor plasmid VL - 41 ER - TY - JOUR AB - During vertebrate gastrulation, a well-orchestrated series of morphogenetic changes leads to the formation of the three germ layers: the ectoderm, mesoderm and endoderm. The analysis of gene expression patterns during gastrulation has been central to the identification of genes involved in germ layer formation. However, many proteins are regulated on a translational or post-translational level and are thus undetectable by gene expression analysis. Therefore, we developed a 2D-gel-based comparative proteomic approach to target proteins involved in germ layer morphogenesis during zebrafish gastrulation. Proteomes of ectodermal and mesendodermal progenitor cells were compared and 35 significantly regulated proteins were identified by mass spectrometry, including several proteins with predicted functions in cytoskeletal organization. A comparison of our proteomic results with data obtained in an accompanying microarray-based gene expression analysis revealed no significant overlap, confirming the complementary nature of proteomics and transcriptomics. The regulation of ezrin2, which was identified based on a reduction in spot intensity in mesendodermal cells, was independently validated. Furthermore, we show that ezrin2 is activated by phosphorylation in mesendodermal cells and is required for proper germ layer morphogenesis. We demonstrate the feasibility of proteomics in zebrafish, concluding that proteomics is a valuable tool for analysis of early development. AU - Link, Vinzenz AU - Carvalho, Lara AU - Castanon, Irinka AU - Stockinger, Petra AU - Shevchenko, Andrej AU - Heisenberg, Carl-Philipp J ID - 4176 IS - 10 JF - Journal of Cell Science TI - Identification of regulators of germ layer morphogenesis using proteomics in zebrafish VL - 119 ER - TY - JOUR AB - Background: Zebrafish (D. rerio) has become a powerful and widely used model system for the analysis of vertebrate embryogenesis and organ development. While genetic methods are readily available in zebrafish, protocols for two dimensional (2D) gel electrophoresis and proteomics have yet to be developed. Results: As a prerequisite to carry out proteomic experiments with early zebrafish embryos, we developed a method to efficiently remove the yolk from large batches of embryos. This method enabled high resolution 2D gel electrophoresis and improved Western blotting considerably. Here, we provide detailed protocols for proteomics in zebrafish from sample preparation to mass spectrometry (MS), including a comparison of databases for MS identification of zebrafish proteins. Conclusion: The provided protocols for proteomic analysis of early embryos enable research to be taken in novel directions in embryogenesis. AU - Link, Vinzenz AU - Shevchenko, Andrej AU - Heisenberg, Carl-Philipp J ID - 4173 JF - BMC Developmental Biology TI - Proteomics of early zebrafish embryos VL - 6 ER - TY - JOUR AB - Detailed reconstruction of the spatiotemporal history of embryonic cells is key to understanding tissue formation processes but is often complicated by the large number of cells involved, particularly so in vertebrates. Through a combination of high-resolution time-lapse lineage tracing and antibody staining, we have analyzed the movement of mesencephalic and metencephalic cell populations in the early zebrafish embryo. To facilitate the analysis of our cell tracking data, we have created TracePilot, a software tool that allows interactive manipulation and visualization of tracking data. We demonstrate its utility by showing novel visualizations of cell movement in the developing zebrafish brain. TracePilot (http://www.mpi-cbg.de/tracepilot) is Java-based, available free of charge, and has a program structure that allows the incorporation of additional analysis tools. AU - Langenberg, Tobias AU - Dracz, Tadeusz AU - Oates, Andrew AU - Heisenberg, Carl-Philipp J AU - Brand, Michael ID - 4178 IS - 4 JF - Developmental Dynamics TI - Analysis and visualization of cell movement in the developing zebrafish brain VL - 235 ER - TY - JOUR AB - Epithelial morphogenesis depends on coordinated changes in cell shape, a process that is still poorly understood. During zebrafish epiboly and Drosophila dorsal closure, cell-shape changes at the epithelial margin are of critical importance. Here evidence is provided for a conserved mechanism of local actin and myosin 2 recruitment during theses events. It was found that during epiboly of the zebrafish embryo, the movement of the outer epithelium (enveloping layer) over the yolk cell surface involves the constriction of marginal cells. This process depends on the recruitment of actin and myosin 2 within the yolk cytoplasm along the margin of the enveloping layer. Actin and myosin 2 recruitment within the yolk cytoplasm requires the Ste20-like kinase Msn1, an orthologue of Drosophila Misshapen. Similarly, in Drosophila, actin and myosin 2 localization and cell constriction at the margin of the epidermis mediate dorsal closure and are controlled by Misshapen. Thus, this study has characterized a conserved mechanism underlying coordinated cell-shape changes during epithelial morphogenesis. AU - Köppen, Mathias AU - Fernández, Beatriz AU - Carvalho, Lara AU - Jacinto, António AU - Heisenberg, Carl-Philipp J ID - 4184 IS - 14 JF - Development TI - Coordinated cell-shape changes control epithelial movement in zebrafish and Drosophila VL - 133 ER - TY - JOUR AB - The molecular and cellular mechanisms governing cell motility and directed migration in response to the chemokine SDF-1 are largely unknown. Here, we demonstrate that zebrafish primordial germ cells whose migration is guided by SDF-1 generate bleb-like protrusions that are powered by cytoplasmic flow. Protrusions are formed at sites of higher levels of free calcium where activation of myosin contraction occurs. Separation of the acto-myosin cortex from the plasma membrane at these sites is followed by a flow of cytoplasm into the forming bleb. We propose that polarized activation of the receptor CXCR4 leads to a rise in free calcium that in turn activates myosin contraction in the part of the cell responding to higher levels of the ligand SDF-1. The biased formation of new protrusions in a particular region of the cell in response to SDF-1 defines the leading edge and the direction of cell migration. AU - Blaser, Heiko AU - Reichman Fried, Michal AU - Castanon, Irinka AU - Dumstrei, Karin AU - Marlow, Florence AU - Kawakami, Koichi AU - Solnica Krezel, Lilianna AU - Heisenberg, Carl-Philipp J AU - Raz, Erez ID - 4218 IS - 5 JF - Developmental Cell TI - Migration of zebrafish primordial germ cells: A role for myosin contraction and cytoplasmic flow VL - 11 ER - TY - JOUR AB - The growth function of populations is central in biomathematics. The main dogma is the existence of density-dependence mechanisms, which can be modelled with distinct functional forms that depend on the size of the Population. One important class of regulatory functions is the theta-logistic, which generalizes the logistic equation. Using this model as a motivation, this paper introduces a simple dynamical reformulation that generalizes many growth functions. The reformulation consists of two equations, one for population size, and one for the growth rate. Furthermore, the model shows that although population is density-dependent, the dynamics of the growth rate does not depend either on population size, nor on the carrying capacity. Actually, the growth equation is uncoupled from the population size equation, and the model has only two parameters, a Malthusian parameter rho and a competition coefficient theta. Distinct sign combinations of these parameters reproduce not only the family of theta-logistics, but also the van Bertalanffy, Gompertz and Potential Growth equations, among other possibilities. It is also shown that, except for two critical points, there is a general size-scaling relation that includes those appearing in the most important allometric theories, including the recently proposed Metabolic Theory of Ecology. With this model, several issues of general interest are discussed such as the growth of animal population, extinctions, cell growth and allometry, and the effect of environment over a population. (c) 2005 Elsevier Ltd. All rights reserved. AU - de Vladar, Harold ID - 4237 IS - 2 JF - Journal of Theoretical Biology TI - Density-dependence as a size-independent regulatory mechanism VL - 238 ER - TY - JOUR AU - Harold Vladar AU - González,J. A ID - 4235 JF - Journal of Theoretical Biology TI - Dynamic response of cancer under the influence of immunological activity and therapy ER - TY - JOUR AB - In finite populations, genetic drift generates interference between selected loci, causing advantageous alleles to be found more often on different chromosomes than on the same chromosome, which reduces the rate of adaptation. This “Hill–Robertson effect” generates indirect selection to increase recombination rates. We present a new method to quantify the strength of this selection. Our model represents a new beneficial allele (A) entering a population as a single copy, while another beneficial allele (B) is sweeping at another locus. A third locus affects the recombination rate between selected loci. Using a branching process model, we calculate the probability distribution of the number of copies of A on the different genetic backgrounds, after it is established but while it is still rare. Then, we use a deterministic model to express the change in frequency of the recombination modifier, due to hitchhiking, as A goes to fixation. We show that this method can give good estimates of selection for recombination. Moreover, it shows that recombination is selected through two different effects: it increases the fixation probability of new alleles, and it accelerates selective sweeps. The relative importance of these two effects depends on the relative times of occurrence of the beneficial alleles. AU - Roze, Denis AU - Nicholas Barton ID - 4248 IS - 3 JF - Genetics TI - The Hill-Robertson effect and the evolution of recombination VL - 173 ER - TY - GEN AB - A recent analysis has shown that divergence between human and chimpanzee varies greatly across the genome. Although this is consistent with ‘hybridisation’ between the diverging human and chimp lineages, such observations can be explained more simply by the null model of allopatric speciation. AU - Nicholas Barton ID - 4250 IS - 16 T2 - Current Biology TI - Evolutionary Biology: How did the human species form? VL - 16 ER - TY - CONF AU - Thomas Wies AU - Kuncak, Viktor AU - Lam,Patrick AU - Podelski,Andreas AU - Rinard,Martin ID - 4359 TI - Field Constraint Analysis ER - TY - CONF AU - Maler, Oded AU - Dejan Nickovic AU - Pnueli,Amir ID - 4373 TI - Real Time Temporal Logic: Past, Present, Future ER - TY - CONF AU - Maler, Oded AU - Dejan Nickovic AU - Pnueli,Amir ID - 4374 TI - From MITL to Timed Automata ER - TY - CONF AB - We propose and evaluate a new algorithm for checking the universality of nondeterministic finite automata. In contrast to the standard algorithm, which uses the subset construction to explicitly determinize the automaton, we keep the determinization step implicit. Our algorithm computes the least fixed point of a monotone function on the lattice of antichains of state sets. We evaluate the performance of our algorithm experimentally using the random automaton model recently proposed by Tabakov and Vardi. We show that on the difficult instances of this probabilistic model, the antichain algorithm outperforms the standard one by several orders of magnitude. We also show how variations of the antichain method can be used for solving the language-inclusion problem for nondeterministic finite automata, and the emptiness problem for alternating finite automata. AU - De Wulf, Martin AU - Doyen, Laurent AU - Thomas Henzinger AU - Raskin, Jean-François ID - 4406 TI - Antichains: A new algorithm for checking universality of finite automata VL - 4144 ER - TY - CONF AU - Alur, Rajeev AU - Pavol Cerny AU - Zdancewic,Steve ID - 4401 TI - Preserving Secrecy Under Refinement ER - TY - CONF AB - The synthesis of reactive systems requires the solution of two-player games on graphs with ω-regular objectives. When the objective is specified by a linear temporal logic formula or nondeterministic Büchi automaton, then previous algorithms for solving the game require the construction of an equivalent deterministic automaton. However, determinization for automata on infinite words is extremely complicated, and current implementations fail to produce deterministic automata even for relatively small inputs. We show how to construct, from a given nondeterministic Büchi automaton, an equivalent nondeterministic parity automaton that is good for solving games with objective . The main insight is that a nondeterministic automaton is good for solving games if it fairly simulates the equivalent deterministic automaton. In this way, we omit the determinization step in game solving and reactive synthesis. The fact that our automata are nondeterministic makes them surprisingly simple, amenable to symbolic implementation, and allows an incremental search for winning strategies. AU - Thomas Henzinger AU - Piterman, Nir ID - 4437 TI - Solving games without determinization VL - 4207 ER - TY - CONF AB - We present an assume-guarantee interface algebra for real-time components. In our formalism a component implements a set of task sequences that share a resource. A component interface consists of an arrival rate function and a latency for each task sequence, and a capacity function for the shared resource. The interface specifies that the component guarantees certain task latencies depending on assumptions about task arrival rates and allocated resource capacities. Our algebra defines compatibility and refinement relations on interfaces. Interface compatibility can be checked on partial designs, even when some component interfaces are yet unknown. In this case interface composition computes as new assumptions the weakest constraints on the unknown components that are necessary to satisfy the specified guarantees. Interface refinement is defined in a way that ensures that compatible interfaces can be refined and implemented independently. Our algebra thus formalizes an interface-based design methodology that supports both the incremental addition of new components and the independent stepwise refinement of existing components. We demonstrate the flexibility and efficiency of the framework through simulation experiments. AU - Thomas Henzinger AU - Matic, Slobodan ID - 4436 TI - An interface algebra for real-time components ER - TY - CONF AB - We add freeze quantifiers to the game logic ATL in order to specify real-time objectives for games played on timed structures. We define the semantics of the resulting logic TATL by restricting the players to physically meaningful strategies, which do not prevent time from diverging. We show that TATL can be model checked over timed automaton games. We also specify timed optimization problems for physically meaningful strategies, and we show that for timed automaton games, the optimal answers can be approximated to within any degree of precision. AU - Thomas Henzinger AU - Prabhu, Vinayak S ID - 4432 TI - Timed alternating-time temporal logic VL - 4202 ER - TY - CONF AB - We summarize some current trends in embedded systems design and point out some of their characteristics, such as the chasm between analytical and computational models, and the gap between safety-critical and best-effort engineering practices. We call for a coherent scientific foundation for embedded systems design, and we discuss a few key demands on such a foundation: the need for encompassing several manifestations of heterogeneity, and the need for constructivity in design. We believe that the development of a satisfactory Embedded Systems Design Science provides a timely challenge and opportunity for reinvigorating computer science. AU - Thomas Henzinger AU - Sifakis, Joseph ID - 4431 TI - The embedded systems design challenge VL - 4085 ER - TY - JOUR AB - One source of complexity in the μ-calculus is its ability to specify an unbounded number of switches between universal (AX) and existential (EX) branching modes. We therefore study the problems of satisfiability, validity, model checking, and implication for the universal and existential fragments of the μ-calculus, in which only one branching mode is allowed. The universal fragment is rich enough to express most specifications of interest, and therefore improved algorithms are of practical importance. We show that while the satisfiability and validity problems become indeed simpler for the existential and universal fragments, this is, unfortunately, not the case for model checking and implication. We also show the corresponding results for the alternation-free fragment of the μ-calculus, where no alternations between least and greatest fixed points are allowed. Our results imply that efforts to find a polynomial-time model-checking algorithm for the μ-calculus can be replaced by efforts to find such an algorithm for the universal or existential fragment. AU - Thomas Henzinger AU - Kupferman, Orna AU - Majumdar, Ritankar S ID - 4451 IS - 2 JF - Theoretical Computer Science TI - On the universal and existential fragments of the mu-calculus VL - 354 ER - TY - CONF AB - We consider the problem if a given program satisfies a specified safety property. Interesting programs have infinite state spaces, with inputs ranging over infinite domains, and for these programs the property checking problem is undecidable. Two broad approaches to property checking are testing and verification. Testing tries to find inputs and executions which demonstrate violations of the property. Verification tries to construct a formal proof which shows that all executions of the program satisfy the property. Testing works best when errors are easy to find, but it is often difficult to achieve sufficient coverage for correct programs. On the other hand, verification methods are most successful when proofs are easy to find, but they are often inefficient at discovering errors. We propose a new algorithm, Synergy, which combines testing and verification. Synergy unifies several ideas from the literature, including counterexample-guided model checking, directed testing, and partition refinement.This paper presents a description of the Synergy algorithm, its theoretical properties, a comparison with related algorithms, and a prototype implementation called Yogi. AU - Gulavani, Bhargav S AU - Thomas Henzinger AU - Kannan, Yamini AU - Nori, Aditya V AU - Rajamani, Sriram K ID - 4523 TI - Synergy: A new algorithm for property checking ER - TY - CONF AB - We designed and implemented a new programming language called Hierarchical Timing Language (HTL) for hard realtime systems. Critical timing constraints are specified within the language,and ensured by the compiler. Programs in HTL are extensible in two dimensions without changing their timing behavior: new program modules can be added, and individual program tasks can be refined. The mechanism supporting time invariance under parallel composition is that different program modules communicate at specified instances of time. Time invariance under refinement is achieved by conservative scheduling of the top level. HTL is a coordination language, in that individual tasks can be implemented in "foreign" languages. As a case study, we present a distributed HTL implementation of an automotive steer-by-wire controller. AU - Ghosal, Arkadeb AU - Thomas Henzinger AU - Iercan, Daniel AU - Kirsch, Christoph M AU - Sangiovanni-Vincentelli, Alberto ID - 4526 TI - A hierarchical coordination language for interacting real-time tasks ER - TY - CONF AB - Computational modeling of biological systems is becoming increasingly common as scientists attempt to understand biological phenomena in their full complexity. Here we distinguish between two types of biological models mathematical and computational - according to their different representations of biological phenomena and their diverse potential. We call the approach of constructing computational models of biological systems executable biology, as it focuses on the design of executable computer algorithms that mimic biological phenomena. We give an overview of the main modeling efforts in this direction, and discuss some of the new challenges that executable biology poses for computer science and biology. We argue that for executable biology to reach its full potential as a mainstream biological technique, formal and algorithmic approaches must be integrated into biological research, driving biology towards a more precise engineering discipline. AU - Fisher, Jasmin AU - Thomas Henzinger ID - 4528 TI - Executable biology ER - TY - CONF AB - Games on graphs with ω-regular objectives provide a model for the control and synthesis of reactive systems. Every ω-regular objective can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens “eventually.” Two main strengths of the classical, infinite-limit formulation of liveness are robustness (independence from the granularity of transitions) and simplicity (abstraction of complicated time bounds). However, the classical liveness formulation suffers from the drawback that the time until something good happens may be unbounded. A stronger formulation of liveness, so-called finitary liveness, overcomes this drawback, while still retaining robustness and simplicity. Finitary liveness requires that there exists an unknown, fixed bound b such that something good happens within b transitions. While for one-shot liveness (reachability) objectives, classical and finitary liveness coincide, for repeated liveness (Büchi) objectives, the finitary formulation is strictly stronger. In this work we study games with finitary parity and Streett (fairness) objectives. We prove the determinacy of these games, present algorithms for solving these games, and characterize the memory requirements of winning strategies. Our algorithms can be used, for example, for synthesizing controllers that do not let the response time of a system increase without bound. AU - Krishnendu Chatterjee AU - Thomas Henzinger ID - 4539 TI - Finitary winning in omega-regular games VL - 3920 ER - TY - CONF AB - A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with ω-regular winning conditions specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy improvement algorithm for stochastic parity games; this is the first non-brute-force algorithm for solving these games. From the strategy improvement algorithm we obtain a randomized subexponential-time algorithm to solve such games. AU - Krishnendu Chatterjee AU - Thomas Henzinger ID - 4538 TI - Strategy improvement and randomized subexponential algorithms for stochastic parity games VL - 3884 ER - TY - CONF AB - We consider Markov decision processes (MDPs) with multiple discounted reward objectives. Such MDPs occur in design problems where one wishes to simultaneously optimize several criteria, for example, latency and power. The possible trade-offs between the different objectives are characterized by the Pareto curve. We show that every Pareto-optimal point can be achieved by a memoryless strategy; however, unlike in the single-objective case, the memoryless strategy may require randomization. Moreover, we show that the Pareto curve can be approximated in polynomial time in the size of the MDP. Additionally, we study the problem if a given value vector is realizable by any strategy, and show that it can be decided in polynomial time; but the question whether it is realizable by a deterministic memoryless strategy is NP-complete. These results provide efficient algorithms for design exploration in MDP models with multiple objectives. This research was supported in part by the AFOSR MURI grant F49620-00-1-0327, and the NSF grants CCR-0225610, CCR-0234690, and CCR-0427202. AU - Krishnendu Chatterjee AU - Majumdar, Ritankar S AU - Thomas Henzinger ID - 4551 TI - Markov decision processes with multiple objectives VL - 3884 ER - TY - JOUR AB - In 2-player non-zero-sum games, Nash equilibria capture the options for rational behavior if each player attempts to maximize her payoff. In contrast to classical game theory, we consider lexicographic objectives: first, each player tries to maximize her own payoff, and then, the player tries to minimize the opponent's payoff. Such objectives arise naturally in the verification of systems with multiple components. There, instead of proving that each component satisfies its specification no matter how the other components behave, it sometimes suffices to prove that each component satisfies its specification provided that the other components satisfy their specifications. We say that a Nash equilibrium is secure if it is an equilibrium with respect to the lexicographic objectives of both players. We prove that in graph games with Borel winning conditions, which include the games that arise in verification, there may be several Nash equilibria, but there is always a unique maximal payoff profile of a secure equilibrium. We show how this equilibrium can be computed in the case of ω-regular winning conditions, and we characterize the memory requirements of strategies that achieve the equilibrium. AU - Krishnendu Chatterjee AU - Thomas Henzinger AU - Jurdziński, Marcin ID - 4550 IS - 1-2 JF - Theoretical Computer Science TI - Games with secure equilibria VL - 365 ER - TY - CONF AB - We present a compositional theory of system verification, where specifications assign real-numbered costs to systems. These costs can express a wide variety of quantitative system properties, such as resource consumption, price, or a measure of how well a system satisfies its specification. The theory supports the composition of systems and specifications, and the hiding of variables. Boolean refinement relations are replaced by real-numbered distances between descriptions of a system at different levels of detail. We show that the classical Boolean rules for compositional reasoning have quantitative counterparts in our setting. While our general theory allows costs to be specified by arbitrary cost functions, we also consider a class of linear cost functions, which give rise to an instance of our framework where all operations are computable in polynomial time. AU - Krishnendu Chatterjee AU - de Alfaro, Luca AU - Faella, Marco AU - Thomas Henzinger AU - Majumdar, Ritankar S AU - Stoelinga, Mariëlle ID - 4549 TI - Compositional quantitative reasoning ER - TY - CONF AB - A concurrent reachability game is a two-player game played on a graph: at each state, the players simultaneously and independently select moves; the two moves determine jointly a probability distribution over the successor states. The objective for player 1 consists in reaching a set of target states; the objective for player 2 is to prevent this, so that the game is zero-sum. Our contributions are two-fold. First, we present a simple proof of the fact that in concurrent reachability games, for all epsilon > 0, memoryless epsilon-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an epsilon-optimal strategy achieves the objective with probability within epsilon of the value of the game. In contrast to previous proofs of this fact, which rely on the limit behavior of discounted games using advanced Puisieux series analysis, our proof is elementary and combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives. AU - Krishnendu Chatterjee AU - de Alfaro, Luca AU - Thomas Henzinger ID - 4552 TI - Strategy improvement for concurrent reachability games ER - TY - CONF AB - Many software model checkers are based on predicate abstraction. If the verification goal depends on pointer structures, the approach does not work well, because it is difficult to find adequate predicate abstractions for the heap. In contrast, shape analysis, which uses graph-based heap abstractions, can provide a compact representation of recursive data structures. We integrate shape analysis into the software model checker Blast. Because shape analysis is expensive, we do not apply it globally. Instead, we ensure that, like predicates, shape graphs are computed and stored locally, only where necessary for proving the verification goal. To achieve this, we extend lazy abstraction refinement, which so far has been used only for predicate abstractions, to three-valued logical structures. This approach does not only increase the precision of model checking, but it also increases the efficiency of shape analysis. We implemented the technique by extending Blast with calls to Tvla. AU - Beyer, Dirk AU - Thomas Henzinger AU - Théoduloz, Grégory ID - 4574 TI - Lazy shape analysis VL - 4144 ER - TY - GEN AB - Mitchison and Jozsa recently suggested that the "chained-Zeno" counterfactual computation protocol recently proposed by Hosten et al. is counterfactual for only one output of the computer. This claim was based on the existing abstract algebraic definition of counterfactual computation, and indeed according to this definition, their argument is correct. However, a more general definition (physically adequate) for counterfactual computation is implicitly assumed by Hosten et. al. Here we explain in detail why the protocol is counterfactual and how the "history tracking" method of the existing description inadequately represents the physics underlying the protocol. Consequently, we propose a modified definition of counterfactual computation. Finally, we comment on one of the most interesting aspects of the error-correcting protocol. AU - Hosten, Onur AU - Rakher, Matthew AU - Barreiro, Julio AU - Peters, Nicholas AU - Kwiat, Paul ID - 573 TI - Counterfactual computation revisited ER - TY - GEN AB - Vaidman, in a recent article adopts the method of 'quantum weak measurements in pre- and postselected ensembles' to ascertain whether or not the chained-Zeno counterfactual computation scheme proposed by Hosten et al. is counterfactual; which has been the topic of a debate on the definition of counterfactuality. We disagree with his conclusion, which brings up some interesting aspects of quantum weak measurements and some concerns about the way they are interpreted. AU - Hosten, Onur AU - Kwiat, Paul ID - 574 TI - Weak measurements and counterfactual computation ER - TY - CONF AB - A source of single photons allows secure quantum key distribution, in addition, to being a critical resource for linear optics quantum computing. We describe our progress on deterministically creating single photons from spontaneous parametric downconversion, an extension of the Pittman, Jacobs and Franson scheme [Phys. Rev A, v66, 042303 (2002)]. Their idea was to conditionally prepare single photons by measuring one member of a spontaneously emitted photon pair and storing the remaining conditionally prepared photon until a predetermined time, when it would be "deterministically" released from storage. Our approach attempts to improve upon this by recycling the pump pulse in order to decrease the possibility of multiple-pair generation, while maintaining a high probability of producing a single pair. Many of the challenges we discuss are central to other quantum information technologies, including the need for low-loss optical storage, switching and detection, and fast feed-forward control. AU - Peters, Nicholas A AU - Arnold, Keith J AU - VanDevender, Aaron P AU - Jeffrey, Evan R AU - Rangarajan, Radhika AU - Onur Hosten AU - Barreiro, Julio T AU - Altepeter, Joseph B AU - Kwiat, Paul G ID - 578 TI - Towards a quasi-deterministic single-photon source VL - 6305 ER - TY - CONF AB - Visible light photon counters (VLPCs) and solid-state photomultipliers (SSPMs) are high-efficiency single-photon detectors which have multi-photon counting capability. While both the VLPCs and the SSPMs have inferred internal quantum efficiencies above 93%, the actual measured values for both the detectors were in fact limited to less than 88%, attributed to in-coupling losses. We are currently improving this overall detection efficiency via a) custom anti-reflection coating the detectors and the in-coupling fibers, b) implementing a novel cryogenic design to reduce transmission losses and, c) using low-noise electronics to obtain a better signal-to-noise ratio. AU - Rangarajan, Radhika AU - Altepeter, Joseph B AU - Jeffrey, Evan R AU - Stoutimore, Micah J AU - Peters, Nicholas A AU - Onur Hosten AU - Kwiat, Paul G ID - 577 TI - High-efficiency single-photon detectors VL - 6372 ER - TY - JOUR AB - The logic underlying the coherent nature of quantum information processing often deviates from intuitive reasoning, leading to surprising effects. Counterfactual computation constitutes a striking example: the potential outcome of a quantum computation can be inferred, even if the computer is not run 1. Relying on similar arguments to interaction-free measurements 2 (or quantum interrogation3), counterfactual computation is accomplished by putting the computer in a superposition of 'running' and 'not running' states, and then interfering the two histories. Conditional on the as-yet-unknown outcome of the computation, it is sometimes possible to counterfactually infer information about the solution. Here we demonstrate counterfactual computation, implementing Grover's search algorithm with an all-optical approach4. It was believed that the overall probability of such counterfactual inference is intrinsically limited1,5, so that it could not perform better on average than random guesses. However, using a novel 'chained' version of the quantum Zeno effect6, we show how to boost the counterfactual inference probability to unity, thereby beating the random guessing limit. Our methods are general and apply to any physical system, as illustrated by a discussion of trapped-ion systems. Finally, we briefly show that, in certain circumstances, counterfactual computation can eliminate errors induced by decoherence. AU - Onur Hosten AU - Rakher, Matthew T AU - Barreiro, Julio T AU - Peters, Nicholas A AU - Kwiat, Paul G ID - 579 IS - 7079 JF - Nature TI - Counterfactual quantum computation through quantum interrogation VL - 439 ER - TY - CONF AB - Visible light photon counters (VLPCs) and solid-state photomultipliers (SSPMs) facilitate efficient single-photon detection. We are attempting to improve their efficiency, previously limited to < 88% by coupling losses, via anti-reflection coatings, better electronics and cryogenics. AU - Rangarajan, Radhika AU - Peters, Nicholas A AU - Onur Hosten AU - Altepeter, Joseph B AU - Jeffrey, Evan R AU - Kwiat, Paul G ID - 583 TI - Improved single-photon detection ER - TY - JOUR AU - Salecker, Iris AU - Häusser, Michael AU - de Bono, Mario ID - 6151 IS - 6 JF - EMBO reports SN - 1469-221X TI - On the axonal road to circuit function and behaviour: Workshop on the assembly and function of neuronal circuits VL - 7 ER - TY - JOUR AU - Rogers, Candida AU - Persson, Annelie AU - Cheung, Benny AU - de Bono, Mario ID - 6152 IS - 7 JF - Current Biology SN - 0960-9822 TI - Behavioral motifs and neural pathways coordinating O2 responses and aggregation in C. elegans VL - 16 ER - TY - JOUR AB - An experimental technique for measuring the current density distribution with a resolution smaller than the channel/rib scale of the flow field in polymer electrolyte fuel cells (PEFCs) is presented. The electron conductors in a plane perpendicular to the channel direction are considered as two-dimensional resistors. Hence, the current density is obtained from the solution of Laplace's equation with the potentials at current collector and reaction layer as boundary conditions. Using ohmic drop for calculating the local current, detailed knowledge of all resistances involved is of prime importance. In particular, the contact resistance between the gas diffusion layer (GDL) and flow field rib, as well as GDL bulk conductivity, are strongly dependent on clamping pressure. They represent a substantial amount of the total ohmic drop and therefore require careful consideration. The detailed experimental setup as well as the concise procedure for quantitative data evaluation is described. Finally, the method is applied successfully to a cell operated on pure oxygen and air up to high current densities. The results show that electrical and ionic resistances seem to govern the current distribution at low current regimes, whereas mass transport limitations locally hamper the current production at high loads. AU - Freunberger, Stefan Alexander AU - Reum, Mathias AU - Evertz, Jörg AU - Wokaun, Alexander AU - Büchi, Felix N. ID - 7328 IS - 11 JF - Journal of The Electrochemical Society SN - 0013-4651 TI - Measuring the current distribution in PEFCs with sub-millimeter resolution VL - 153 ER - TY - JOUR AB - Propagation of performance changes to adjacent cells in polymer electrolyte fuel cell stacks is studied by means of voltage monitoring and local current density measurements in peripheral cells of the stack. A technical fuel cell stack has been modified by implementing two independent reactant and coolant supplies in order to deliberately change the performance of one cell (anomalous cell) and study the coupling phenomena to adjacent cells (coupling cells), while keeping the working conditions of the later cell-group unaltered. Two anomalies are studied: (i) air starvation and (ii) thermal anomaly, in a single anomalous cell in the stack and their coupling to adjacent cells. The results have shown that anomalies inducing considerable changes in the local current density of the anomalous cell (such as air starvation) propagate to adjacent cells affecting their performance. The propagation of local current density changes takes place via the common bipolar plate due to its finite thickness and in-plane conductivity. Consequently, anomalies which do not strongly influence the local current density distribution (such as a thermal anomaly under the studied working conditions) do not propagate to adjacent cells. AU - Santis, Marco AU - Freunberger, Stefan Alexander AU - Papra, Matthias AU - Wokaun, Alexander AU - Büchi, Felix N. ID - 7327 IS - 2 JF - Journal of Power Sources SN - 0378-7753 TI - Experimental investigation of coupling phenomena in polymer electrolyte fuel cell stacks VL - 161 ER - TY - CONF AB - Often the properties of a single cell are considered as representative for a complete polymer electrolyte fuel cell stack or even a fuel cell system. In some cases this comes close, however, in many real cases differences on several scales become important. Cell interaction phenomena in fuel cell stacks that arise from inequalities between adjacent cells are investigated in detail experimentally. For that, a specialized 2-cell stack with advanced localized diagnostics was developed. The results show that inequalities propagate by electrical coupling, inhomogeneous cell polarization and inducing in-plane current in the common bipolar plate. The effects of the different loss-mechanisms are analyzed and quantified. AU - Büchi, Felix N. AU - Freunberger, Stefan Alexander AU - Santis, Marco ID - 7326 IS - 1 T2 - ECS Transactions TI - What is learned beyond the scale of single cells? VL - 3 ER - TY - JOUR AB - A novel measurement principle for measuring the current distribution in polymer electrolyte fuel cells (PEFCs) is introduced. It allows, in contrast to all other known techniques, for the first time for a resolution smaller than the channel/rib scale of the flow field in PEFCs. The current density is obtained by considering the electron conductors in the cell as a two-dimensional resistor with the voltage drop caused by the current. The method was applied to a cell operated on oxygen up to high current densities. The results show that the ohmic resistances govern the current distribution in the low current regime, whereas mass transport limitations hamper the current production under the land at high loads. AU - Freunberger, Stefan Alexander AU - Reum, Mathias AU - Wokaun, Alexander AU - Büchi, Felix N. ID - 7329 IS - 9 JF - Electrochemistry Communications SN - 1388-2481 TI - Expanding current distribution measurement in PEFCs to sub-millimeter resolution VL - 8 ER - TY - JOUR AB - Polymer electrolyte fuel cells (PE fuel cells) working with air at low stoichiometries (<2.0) and standard electrochemical components show a high degree of inhomogeneity in the current density distribution over the active area. An inhomogeneous current density distribution leads to a non-uniform utilization of the active area, which could negatively affect the time of life of the cells. Furthermore, it is also believed to lower cell performance. In this work, the homogenization of the current density, realized by means of tailored cathodes with along-the-air-channel redistributed catalyst loadings, is investigated. The air stoichiometry range for which a homogenization of the current density is achieved depends upon the gradient with which the catalyst is redistributed along the air channel. A gentle increasing catalyst loading profile homogenizes the current density at relatively higher air stoichiometries, while a steeper profile is suited better for lower air stoichiometries. The results show that a homogenization of the current density by means of redistributed catalyst loading has negative effects on cell performance. Model calculations corroborate the experimental findings on homogenization of the current density and deliver an explanation for the decrease in cell performance. AU - Santis, M. AU - Freunberger, Stefan Alexander AU - Reiner, A. AU - Büchi, F.N. ID - 7330 IS - 25 JF - Electrochimica Acta SN - 0013-4686 TI - Homogenization of the current density in polymer electrolyte fuel cells by in-plane cathode catalyst gradients VL - 51 ER - TY - JOUR AB - A quasi-two-dimensional, along-the-channel mass and heat-transfer model for a proton exchange membrane fuel cell (PEFC) is described and validated against experimental current distribution data. The model is formulated in a dimensional manner, i.e., local transport phenomena are treated one-dimensional in through-plane direction and coupled in-plane by convective transport in the gas and coolant channels. Thus, a two-dimensional slice running through the repetitive unit of a cell from the anode channel via membrane-electrode assembly (MEA) and cathode channel to the coolant channel and from inlet to outlet is modeled. The aim of the work is to elucidate the influence of operating conditions such as feed gas humidities and stoichiometric ratios on the along-the-channel current density distribution and to identify the distinct underlying voltage loss mechanisms. Furthermore, a complicated technical flow field is modeled by a combination of co- and counterflow subdomains and compared with experimental current densities. AU - Freunberger, Stefan Alexander AU - Santis, Marco AU - Schneider, Ingo A. AU - Wokaun, Alexander AU - Büchi, Felix N. ID - 7332 IS - 2 JF - Journal of The Electrochemical Society SN - 0013-4651 TI - In-plane effects in large-scale PEMFCs VL - 153 ER - TY - JOUR AB - A previously developed mathematical model for water management and current density distribution in a polymer electrolyte fuel cell (PEFCs) is employed to investigate the effects of cooling strategies on cell performance. The model describes a two-dimensional slice through the cell along the channels and through the entire cell sandwich including the coolant channels and the bipolar plate. Arbitrary flow arrangements of fuel, oxidant, and coolant stream directions can be described. Due to the serious impact of temperature on all processes in the PEFC, both the relative direction of the coolant stream to the gas streams and its mass flow turns out to significantly affect the cell performance. Besides influencing the electrochemical reaction and all kinds of mass transfer temperature, variations predominantly alter the local membrane hydration distribution and subseqently its conductivity. AU - Freunberger, Stefan Alexander AU - Wokaun, Alexander AU - Büchi, Felix N. ID - 7331 IS - 5 JF - Journal of The Electrochemical Society SN - 0013-4651 TI - In-plane effects in large-scale PEFCs: II. The influence of cooling strategy on cell performance VL - 153 ER - TY - JOUR AB - Phylogenetic relationships between the extinct woolly mammoth (Mammuthus primigenius), and the Asian (Elephas maximus) and African savanna (Loxodonta africana) elephants remain unresolved. Here, we report the sequence of the complete mitochondrial genome (16,842 base pairs) of a woolly mammoth extracted from permafrost-preserved remains from the Pleistocene epoch - the oldest mitochondrial genome sequence determined to date. We demonstrate that well-preserved mitochondrial genome fragments, as long as ∼1,600-1700 base pairs, can be retrieved from pre-Holocene remains of an extinct species. Phylogenetic reconstruction of the Elephantinae clade suggests that M. primigenius and E. maximus are sister species that diverged soon after their common ancestor split from the L. africana lineage. Low nucleotide diversity found between independently determined mitochondrial genomic sequences of woolly mammoths separated geographically and in time suggests that north-eastern Siberia was occupied by a relatively homogeneous population of M. primigenius throughout the late Pleistocene. AU - Rogaev, Evgeny I AU - Moliaka, Yuri K AU - Malyarchuk, Boris A AU - Fyodor Kondrashov AU - Derenko, Miroslava V AU - Chumakov, Ilya M AU - Grigorenko, Anastasia P ID - 854 IS - 3 JF - PLoS Biology TI - Complete mitochondrial genome and phylogeny of pleistocene mammoth Mammuthus primigenius VL - 4 ER -