TY - CONF AB - We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (players interact simultaneously); and (b) turn-based (players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. We present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function (probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Gimbert, Hugo AU - Henzinger, Thomas A ID - 3856 TI - Randomness for free VL - 6281 ER - TY - GEN AB - This book constitutes the proceedings of the 8th International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS 2010, held in Klosterneuburg, Austria in September 2010. The 14 papers presented were carefully reviewed and selected from 31 submissions. In addition, the volume contains 3 invited talks and 2 invited tutorials.The aim of FORMATS is to promote the study of fundamental and practical aspects of timed systems, and to bring together researchers from different disciplines that share an interest in the modeling and analysis of timed systems. Typical topics include foundations and semantics, methods and tools, and applications. ED - Chatterjee, Krishnendu ED - Henzinger, Thomas A ID - 3859 TI - Formal modeling and analysis of timed systems VL - 6246 ER - TY - CONF AB - Systems ought to behave reasonably even in circumstances that are not anticipated in their specifications. We propose a definition of robustness for liveness specifications which prescribes, for any number of environment assumptions that are violated, a minimal number of system guarantees that must still be fulfilled. This notion of robustness can be formulated and realized using a Generalized Reactivity formula. We present an algorithm for synthesizing robust systems from such formulas. For the important special case of Generalized Reactivity formulas of rank 1, our algorithm improves the complexity of [PPS06] for large specifications with a small number of assumptions and guarantees. AU - Bloem, Roderick AU - Chatterjee, Krishnendu AU - Greimel, Karin AU - Henzinger, Thomas A AU - Jobstmann, Barbara ED - Touili, Tayssir ED - Cook, Byron ED - Jackson, Paul ID - 3866 TI - Robustness in the presence of liveness VL - 6174 ER - TY - JOUR AB - Simulation and bisimulation metrics for stochastic systems provide a quantitative generalization of the classical simulation and bisimulation relations. These metrics capture the similarity of states with respect to quantitative specifications written in the quantitative mu-calculus and related probabilistic logics. We first show that the metrics provide a bound for the difference in long-run average and discounted average behavior across states, indicating that the metrics can be used both in system verification, and in performance evaluation. For turn-based games and MDPs, we provide a polynomial-time algorithm for the computation of the one-step metric distance between states. The algorithm is based on linear programming; it improves on the previous known exponential-time algorithm based on a reduction to the theory of reals. We then present PSPACE algorithms for both the decision problem and the problem of approximating the metric distance between two states, matching the best known algorithms for Markov chains. For the bisimulation kernel of the metric our algorithm works in time O(n(4)) for both turn-based games and MDPs; improving the previously best known O(n(9).log(n)) time algorithm for MDPs. For a concurrent game G, we show that computing the exact distance be tween states is at least as hard as computing the value of concurrent reachability games and the square-root-sum problem in computational geometry. We show that checking whether the metric distance is bounded by a rational r, can be done via a reduction to the theory of real closed fields, involving a formula with three quantifier alternations, yielding O(vertical bar G vertical bar(O(vertical bar G vertical bar 5))) time complexity, improving the previously known reduction, which yielded O(vertical bar G vertical bar(O(vertical bar G vertical bar 7))) time complexity. These algorithms can be iterated to approximate the metrics using binary search AU - Chatterjee, Krishnendu AU - De Alfaro, Luca AU - Majumdar, Ritankar AU - Raman, Vishwanath ID - 3868 IS - 3 JF - Logical Methods in Computer Science TI - Algorithms for game metrics VL - 6 ER - TY - BOOK AB - Combining concepts from topology and algorithms, this book delivers what its title promises: an introduction to the field of computational topology. Starting with motivating problems in both mathematics and computer science and building up from classic topics in geometric and algebraic topology, the third part of the text advances to persistent homology. This point of view is critically important in turning a mostly theoretical field of mathematics into one that is relevant to a multitude of disciplines in the sciences and engineering. The main approach is the discovery of topology through algorithms. The book is ideal for teaching a graduate or advanced undergraduate course in computational topology, as it develops all the background of both the mathematical and algorithmic aspects of the subject from first principles. Thus the text could serve equally well in a course taught in a mathematics department or computer science department. AU - Edelsbrunner, Herbert AU - Harer, John ID - 3899 SN - 978-0-8218-4925-5 TI - Computational Topology: An Introduction VL - 69 ER - TY - JOUR AB - Almost all species of the orchid genus Ophrys are pollinated by sexual deception. The orchids mimic the sex pheromone of receptive female insects, mainly hymenopterans, in order to attract males seeking to copulate. Most Ophrys species have achromatic flowers, but some exhibit a coloured perianth and a bright, conspicuous labellum pattern. We recently showed that the pink perianth of Ophrys heldreichii flowers increases detectability by its pollinator, males of the long-horned bee Eucera berlandi. Here we tested the hypothesis that the bright, complex labellum pattern mimics the female of the pollinator to increase attractiveness toward males. In a dual-choice test we offered E. berlandi males an O. heldreichii flower and a flower from O. dictynnae, which also exhibits a pinkish perianth but no conspicuous labellum pattern. Both flowers were housed in UV-transmitting acrylic glass boxes to exclude olfactory signals. Males significantly preferred O. heldreichii to O. dictynnae flowers. In a second experiment, we replaced the perianth of both flowers with identical artificial perianths made from pink card, so that only the labellum differed between the two flower stimuli. Males then chose between both stimuli at random, suggesting that the presence of a labellum pattern does not affect their choice. Spectral measurements revealed higher colour contrast with the background of the perianth of O. heldreichii compared to O. dictynnae, but no difference in green receptor-specific contrast or brightness. Our results show that male choice is guided by the chromatic contrast of the perianth during the initial flower approach but is not affected by the presence of a labellum pattern. Instead, we hypothesise that the labellum pattern is involved in aversive learning during post-copulatory behaviour and used by the orchid as a strategy to increase outcrossing. AU - Streinzer, M. AU - Ellis, Thomas AU - Paulus, H. AU - Spaethe, J. ID - 3963 IS - 3 JF - Arthropod-Plant Interactions TI - Visual discrimination between two sexually deceptive Ophrys species by a bee pollinator VL - 4 ER - TY - JOUR AB - Chemokines orchestrate immune cell trafficking by eliciting either directed or random migration and by activating integrins in order to induce cell adhesion. Analyzing dendritic cell (DC) migration, we showed that these distinct cellular responses depended on the mode of chemokine presentation within tissues. The surface-immobilized form of the chemokine CCL21, the heparan sulfate-anchoring ligand of the CC-chemokine receptor 7 (CCR7), caused random movement of DCs that was confined to the chemokine-presenting surface because it triggered integrin-mediated adhesion. Upon direct contact with CCL21, DCs truncated the anchoring residues of CCL21, thereby releasing it from the solid phase. Soluble CCL21 functionally resembles the second CCR7 ligand, CCL19, which lacks anchoring residues and forms soluble gradients. Both soluble CCR7 ligands triggered chemotactic movement, but not surface adhesion. Adhesive random migration and directional steering cooperate to produce dynamic but spatially restricted locomotion patterns closely resembling the cellular dynamics observed in secondary lymphoid organs. AU - Schumann, Kathrin AU - Lämmermann, Tim AU - Bruckner, Markus AU - Legler, Daniel AU - Polleux, Julien AU - Spatz, Joachim AU - Schuler, Gerold AU - Förster, Reinhold AU - Lutz, Manfred AU - Sorokin, Lydia AU - Sixt, Michael K ID - 3959 IS - 5 JF - Immunity TI - Immobilized chemokine fields and soluble chemokine gradients cooperatively shape migration patterns of dendritic cells VL - 32 ER - TY - JOUR AB - Extracellular matrix (ECM) proteins can modify immune reactions, e.g. by sequestering or displaying growth factors and by interacting with immune and glial cells. Here we quantified by quantitative polymerase chain reaction (qPCR) expression of 50 ECM components and 34 ECM degrading enzymes in multiple sclerosis (MS) active and inactive white matter lesions. COL1A1, COL3A1, COL5A1 and COL5A2 chains were induced strongly in active lesions and even more in inactive lesions. These chains interact to form collagen types I, III and V, which are fibrillar collagens. Biglycan and decorin, which can decorate fibrillar collagens, were also induced strongly. The fibrillar collagens, biglycan and decorin were largely found between the endothelium and astrocytic glia limitans in the perivascular space where they formed a meshwork which was closely associated with infiltrating immune cells. In active lesions collagen V was also seen in the heavily infiltrated parenchyma. Fibrillar collagens I and III inhibited in vitro human monocyte production of CCL2 (MCP-1), an inflammatory chemokine involved in recruitment of immune cells. Together, ECM changes in lesions with different activities were quantified and proteins forming a perivascular fibrosis were identified. Induced fibrillar collagens may contribute to limiting enlargement of MS lesions by inhibiting the production of CCL2 by monocytes. AU - Mohan, Hema AU - Krumbholz, Markus AU - Sharma, Rakhi AU - Eisele, Sylvia AU - Junker, Andreas AU - Michael Sixt AU - Newcombe, Jia AU - Wekerle, Hartmut AU - Hohlfeld, Reinhard AU - Lassmann, Hans AU - Meinl, Edgar ID - 3958 IS - 5 JF - Brain Pathology TI - Extracellular matrix in multiple sclerosis lesions: fibrillar collagens, biglycan and decorin are upregulated and associated with infiltrating immune cells VL - 20 ER - TY - JOUR AB - For innate and adaptive immune responses it is essential that inflammatory cells use quick and flexible locomotion strategies. Accordingly, most leukocytes can efficiently infiltrate and traverse almost every physiological or artificial environment. Here, we review how leukocytes might achieve this task mechanistically, and summarize recent findings on the principles of cytoskeletal force generation and transduction at the leading edge of leukocytes. We propose a model in which the cells switch between adhesion-receptor-mediated force transmission and locomotion modes that are based on cellular deformations, but independent of adhesion receptors. This plasticity in migration strategies allows leukocytes to adapt to the geometry and molecular composition of their environment. AU - Jörg Renkawitz AU - Michael Sixt ID - 3961 IS - 10 JF - EMBO Reports TI - Mechanisms of force generation and force transmission during interstitial leukocyte migration VL - 11 ER - TY - JOUR AB - When lymphocytes follow chemotactic cues, they can adopt different migratory modes depending on the geometry and molecular composition of their extracellular environment. In this issue of The EMBO Journal, Klemke et al (2010) describe a novel Ras-dependent chemokine receptor signalling pathway that leads to activation of cofilin, which in turn amplifies actin turnover. This signalling module is exclusively required for lymphocyte migration in three-dimensional (3D) environments, but not for locomotion on two-dimensional (2D) surfaces. AU - Michele Weber AU - Michael Sixt ID - 3960 IS - 17 JF - EMBO Journal TI - MEK signalling tunes actin treadmilling for interstitial lymphocyte migration VL - 29 ER -