@inproceedings{3856, abstract = {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. }, author = {Chatterjee, Krishnendu and Doyen, Laurent and Gimbert, Hugo and Henzinger, Thomas A}, location = {Brno, Czech Republic}, pages = {246 -- 257}, publisher = {Springer}, title = {{Randomness for free}}, doi = {10.1007/978-3-642-15155-2_23}, volume = {6281}, year = {2010}, } @proceedings{3859, abstract = {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.}, editor = {Chatterjee, Krishnendu and Henzinger, Thomas A}, location = {Klosterneuburg, Austria}, publisher = {Springer}, title = {{Formal modeling and analysis of timed systems}}, doi = {10.1007/978-3-642-15297-9}, volume = {6246}, year = {2010}, } @inproceedings{3866, abstract = {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.}, author = {Bloem, Roderick and Chatterjee, Krishnendu and Greimel, Karin and Henzinger, Thomas A and Jobstmann, Barbara}, editor = {Touili, Tayssir and Cook, Byron and Jackson, Paul}, location = {Edinburgh, UK}, pages = {410 -- 424}, publisher = {Springer}, title = {{Robustness in the presence of liveness}}, doi = {10.1007/978-3-642-14295-6_36}, volume = {6174}, year = {2010}, } @article{3868, abstract = {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}, author = {Chatterjee, Krishnendu and De Alfaro, Luca and Majumdar, Ritankar and Raman, Vishwanath}, journal = {Logical Methods in Computer Science}, number = {3}, pages = {1 -- 27}, publisher = {International Federation of Computational Logic}, title = {{Algorithms for game metrics}}, doi = {10.2168/LMCS-6(3:13)2010}, volume = {6}, year = {2010}, } @book{3899, abstract = {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.}, author = {Edelsbrunner, Herbert and Harer, John}, isbn = {978-0-8218-4925-5}, pages = {XII, 241}, publisher = {American Mathematical Society}, title = {{Computational Topology: An Introduction}}, doi = {10.1090/mbk/069}, volume = {69}, year = {2010}, } @article{3963, abstract = {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.}, author = {Streinzer, M. and Ellis, Thomas and Paulus, H. and Spaethe, J.}, journal = {Arthropod-Plant Interactions}, number = {3}, pages = {141 -- 148}, publisher = {Springer}, title = {{Visual discrimination between two sexually deceptive Ophrys species by a bee pollinator}}, doi = {10.1007/s11829-010-9093-4}, volume = {4}, year = {2010}, } @article{3959, abstract = {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.}, author = {Schumann, Kathrin and Lämmermann, Tim and Bruckner, Markus and Legler, Daniel and Polleux, Julien and Spatz, Joachim and Schuler, Gerold and Förster, Reinhold and Lutz, Manfred and Sorokin, Lydia and Sixt, Michael K}, journal = {Immunity}, number = {5}, pages = {703 -- 713}, publisher = {Cell Press}, title = {{Immobilized chemokine fields and soluble chemokine gradients cooperatively shape migration patterns of dendritic cells}}, doi = {10.1016/j.immuni.2010.04.017}, volume = {32}, year = {2010}, } @article{3958, abstract = {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.}, author = {Mohan, Hema and Krumbholz, Markus and Sharma, Rakhi and Eisele, Sylvia and Junker, Andreas and Michael Sixt and Newcombe, Jia and Wekerle, Hartmut and Hohlfeld, Reinhard and Lassmann, Hans and Meinl, Edgar}, journal = {Brain Pathology}, number = {5}, pages = {966 -- 975}, publisher = {Wiley-Blackwell}, title = {{Extracellular matrix in multiple sclerosis lesions: fibrillar collagens, biglycan and decorin are upregulated and associated with infiltrating immune cells}}, doi = {10.1111/j.1750-3639.2010.00399.x}, volume = {20}, year = {2010}, } @article{3961, abstract = {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.}, author = {Jörg Renkawitz and Michael Sixt}, journal = {EMBO Reports}, number = {10}, pages = {744 -- 750}, publisher = {Wiley-Blackwell}, title = {{Mechanisms of force generation and force transmission during interstitial leukocyte migration}}, doi = {10.1038/embor.2010.147}, volume = {11}, year = {2010}, } @article{3960, abstract = {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.}, author = {Michele Weber and Michael Sixt}, journal = {EMBO Journal}, number = {17}, pages = {2861 -- 2863}, publisher = {Wiley-Blackwell}, title = {{MEK signalling tunes actin treadmilling for interstitial lymphocyte migration}}, doi = {10.1038/emboj.2010.183}, volume = {29}, year = {2010}, } @article{3964, abstract = {We prove two stability results for Lipschitz functions on triangulable, compact metric spaces and consider applications of both to problems in systems biology. Given two functions, the first result is formulated in terms of the Wasserstein distance between their persistence diagrams and the second in terms of their total persistence.}, author = {Cohen-Steiner, David and Herbert Edelsbrunner and Harer, John and Mileyko, Yuriy}, journal = {Foundations of Computational Mathematics}, number = {2}, pages = {127 -- 139}, publisher = {Springer}, title = {{Lipschitz functions have L_p-stable persistence}}, doi = {10.1007/s10208-010-9060-6}, volume = {10}, year = {2010}, } @article{3957, author = {Riedl, Julia and Flynn, Kevin C and Raducanu, Aurelia and Florian Gärtner and Beck, Gisela and Bosl, Michael and Bradke, Frank and Massberg, Steffen and Aszodi, Attila and Michael Sixt and Wedlich-Söldner, Roland}, journal = {Nature Methods}, number = {3}, pages = {168 -- 169}, publisher = {Nature Publishing Group}, title = {{Lifeact mice for studying F-actin dynamics}}, doi = {10.1038/nmeth0310-168}, volume = {7}, year = {2010}, } @article{4134, abstract = {All species are restricted in their distribution. Currently, ecological models can only explain such limits if patches vary in quality, leading to asymmetrical dispersal, or if genetic variation is too low at the margins for adaptation. However, population genetic models suggest that the increase in genetic variance resulting from dispersal should allow adaptation to almost any ecological gradient. Clearly therefore, these models miss something that prevents evolution in natural populations. We developed an individual-based simulation to explore stochastic effects in these models. At high carrying capacities, our simulations largely agree with deterministic predictions. However, when carrying capacity is low, the population fails to establish for a wide range of parameter values where adaptation was expected from previous models. Stochastic or transient effects appear critical around the boundaries in parameter space between simulation behaviours. Dispersal, gradient steepness, and population density emerge as key factors determining adaptation on an ecological gradient. }, author = {Bridle, Jon and Polechova, Jitka and Kawata, Masakado and Butlin, Roger}, journal = {Ecology Letters}, number = {4}, pages = {485 -- 494}, publisher = {Wiley-Blackwell}, title = {{Why is adaptation prevented at ecological margins? New insights from individual-based simulations}}, doi = {10.1111/j.1461-0248.2010.01442.x}, volume = {13}, year = {2010}, } @article{4163, abstract = {Organ formation requires the precise assembly of progenitor cells into a functional multicellular structure. Mechanical forces probably participate in this process but how they influence organ morphogenesis is still unclear. Here, we show that Wnt11- and Prickle1a-mediated planar cell polarity (PCP) signalling coordinates the formation of the zebrafish ciliated laterality organ (Kupffer's vesicle) by regulating adhesion properties between organ progenitor cells (the dorsal forerunner cells, DFCs). Combined inhibition of Wnt11 and Prickle1a reduces DFC cell-cell adhesion and impairs their compaction and arrangement during vesicle lumen formation. This leads to the formation of a mis-shapen vesicle with small fragmented lumina and shortened cilia, resulting in severely impaired organ function and, as a consequence, randomised laterality of both molecular and visceral asymmetries. Our results reveal a novel role for PCP-dependent cell adhesion in coordinating the supracellular organisation of progenitor cells during vertebrate laterality organ formation.}, author = {Oteíza, Pablo and Koeppen, Mathias and Krieg, Michael and Pulgar, Eduardo and Farias, Cecilia and Melo, Cristina and Preibisch, Steffen and Mueller, Daniel and Tada, Masazumi and Hartel, Steffen and Heisenberg, Carl-Philipp J and Concha, Miguel}, journal = {Development}, number = {20}, pages = {3459 -- 3468}, publisher = {Company of Biologists}, title = {{Planar cell polarity signalling regulates cell adhesion properties in progenitors of the zebrafish laterality organ}}, doi = {10.1242/dev.049981}, volume = {137}, year = {2010}, } @article{4243, abstract = {We investigate a new model for populations evolving in a spatial continuum. This model can be thought of as a spatial version of the Lambda-Fleming-Viot process. It explicitly incorporates both small scale reproduction events and large scale extinction-recolonisation events. The lineages ancestral to a sample from a population evolving according to this model can be described in terms of a spatial version of the Lambda-coalescent. Using a technique of Evans (1997), we prove existence and uniqueness in law for the model. We then investigate the asymptotic behaviour of the genealogy of a finite number of individuals sampled uniformly at random (or more generally `far enough apart') from a two-dimensional torus of sidelength L as L tends to infinity. Under appropriate conditions (and on a suitable timescale) we can obtain as limiting genealogical processes a Kingman coalescent, a more general Lambda-coalescent or a system of coalescing Brownian motions (with a non-local coalescence mechanism).}, author = {Barton, Nicholas H and Etheridge, Alison and Véber, Amandine}, journal = {Electronic Journal of Probability}, number = {7}, pages = {162 -- 216}, publisher = {Institute of Mathematical Statistics}, title = {{A new model for evolution in a spatial continuum}}, doi = {10.1214/EJP.v15-741}, volume = {15}, year = {2010}, } @misc{4340, abstract = {More and more libraries starting semantic web projects. The question about the license of the data is not discussed or the discussion is deferred to the end of project. in this paper is discussed why the question of the license is so important in context of the semantic web that is should be one of the first aspects in a semantic web project. Also it will be shown why a public domain weaver is the only solution that fulfill the the special requirements of the semantic web and that guaranties the reuseablitly of semantic library data for a sustainability of the projects. }, author = {Danowski, Patrick}, booktitle = {European Library Automation Group (ELAG) 2010}, publisher = {Elsevier}, title = {{Open bibliographic data}}, year = {2010}, } @book{4346, abstract = {With the term "Library 2.0" the editors mean an institution which applies the principles of the Web 2.0 such as openness, re-use, collaboration and interaction in the entire organization. Libraries are extending their service offerings and work processes to include the potential of Web 2.0 technologies. This changes the job description and self-image of librarians. The collective volume offers a complete overview of the topic Library 2.0 and the current state of developments from a technological, sociological, information theoretical and practice-oriented perspective.}, editor = {Danowski, Patrick and Bergmann, Julia}, isbn = {9-783-1102-3209-7}, pages = {405}, publisher = {De Gruyter}, title = {{Handbuch Bibliothek 2.0}}, doi = {10.1515/9783110232103}, volume = { 41}, year = {2010}, } @inproceedings{4341, abstract = {More and more libraries starting semantic web projects. The question about the license of the data is not discussed or the discussion is deferred to the end of project. in this paper is discussed why the question of the license is so important in context of the semantic web that is should be one of the first aspects in a semantic web project. Also it will be shown why a public domain weaver is the only solution that fulfill the the special requirements of the semantic web and that guaranties the reuseablitly of semantic library data for a sustainability of the projects.}, author = {Patrick Danowski}, publisher = {IFLA}, title = {{Step one: blow up the silo! - Open bibliographic data, the first step towards Linked Open Data}}, year = {2010}, } @inproceedings{4369, abstract = {In this paper we propose a novel technique for constructing timed automata from properties expressed in the logic mtl, under bounded-variability assumptions. We handle full mtl and include all future operators. Our construction is based on separation of the continuous time monitoring of the input sequence and discrete predictions regarding the future. The separation of the continuous from the discrete allows us to determinize our automata in an exponential construction that does not increase the number of clocks. This leads to a doubly exponential construction from mtl to deterministic timed automata, compared with triply exponential using existing approaches. We offer an alternative to the existing approach to linear real-time model checking, which has never been implemented. It further offers a unified framework for model checking, runtime monitoring, and synthesis, in an approach that can reuse tools, implementations, and insights from the discrete setting.}, author = {Nickovic, Dejan and Piterman, Nir}, editor = {Henzinger, Thomas A. and Chatterjee, Krishnendu}, location = {Klosterneuburg, Austria}, pages = {152 -- 167}, publisher = {Springer}, title = {{From MTL to deterministic timed automata}}, doi = {10.1007/978-3-642-15297-9_13}, volume = {6246}, year = {2010}, } @inproceedings{4364, author = {Podelski,Andreas and Thomas Wies}, pages = {249 -- 260}, publisher = {ACM}, title = {{Counterexample-guided focus}}, doi = {10.1145/1707801.1706330}, year = {2010}, }