@article{3882, abstract = {We study infinite stochastic games played by two players over a finite state space, with objectives specified by sets of infinite traces. The games are concurrent (players make moves simultaneously and independently), stochastic (the next state is determined by a probability distribution that depends on the current state and chosen moves of the players) and infinite (proceed for an infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game and epsilon-optimal strategies that ensure values within epsilon of the optimum value; and qualitative analysis, analyzing the set of states with optimum value 1 and epsilon-optimal strategies for the states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finite-prefix of traces, and show that the class of tail objectives is strictly richer than that of the omega-regular objectives. We develop new proof techniques to extend several properties of concurrent games with omega-regular objectives to concurrent games with tail objectives. We prove the positive limit-one property for tail objectives. The positive limit-one property states that for all concurrent games if the optimum value for a player is positive for a tail objective Phi at some state, then there is a state where the optimum value is 1 for the player for the objective Phi. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzerosum (not strictly conflicting objectives) games with simpler reachability objectives. A consequence of our analysis presents a polynomial time reduction of the quantitative analysis of tail objectives to the qualitative analysis for the subclass of one-player stochastic games (Markov decision processes). }, author = {Krishnendu Chatterjee}, journal = {Theoretical Computer Science}, number = {1-3}, pages = {181 -- 198}, publisher = {Elsevier}, title = {{Concurrent games with tail objectives}}, doi = {10.1016/j.tcs.2007.07.047}, volume = {388}, year = {2007}, } @inproceedings{3883, abstract = {We consider games where the winning conditions are disjunctions (or dually, conjunctions) of parity conditions; we call them generalized parity games. These winning conditions, while omega-regular, arise naturally when considering fair simulation between parity automata, secure equilibria for parity conditions, and determinization of Rabin automata. We show that these games retain the computational complexity of Rabin and Streett conditions; i.e., they are NP-complete and co-NP-complete, respectively. The (co-) NP-hardness is proved for the special case of a conjunction/disjunction of two parity conditions, which is the case that arises in fair simulation and secure equilibria. However, considering these games as Rabin or Streett games is not optimal. We give an exposition of Zielonka's algorithm when specialized to this kind of games. The complexity of solving these games for k parity objectives with d priorities, n states, and m edges is O(n(2kd) (.) m) (.) (k(.)d)!/ d!(k), as compared to O(n(2kd .) m) - (k (.) d)! when these games are solved as Rabin/Streett games. We also extend the subexponential algorithm for solving parity games recently introduced by Jurdzinski, Paterson, and Zwick to generalized parity games. The resulting complexity of solving generalized parity games is n(O(root n)) (.) (k(.)d)!/d!(k). As a corollary we obtain an improved ald!k gorithm for Rabin and Streett games with d pairs, with time complexity n(O(root n)) (.) d!.}, author = {Krishnendu Chatterjee and Thomas Henzinger and Piterman, Nir}, pages = {153 -- 167}, publisher = {Springer}, title = {{Generalized parity games}}, doi = {10.1007/978-3-540-71389-0_12}, volume = {4423}, year = {2007}, } @inproceedings{3884, abstract = {We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL*, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula).}, author = {Krishnendu Chatterjee and Thomas Henzinger and Piterman, Nir}, pages = {59 -- 73}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Strategy logic}}, doi = {10.1007/978-3-540-74407-8_5}, volume = {4703}, year = {2007}, } @inproceedings{3885, abstract = {The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also present improved memory bounds for randomized almost-sure winning and optimal strategies.}, author = {Krishnendu Chatterjee}, pages = {138 -- 152}, publisher = {Springer}, title = {{Optimal strategy synthesis in stochastic Müller games}}, doi = {10.1007/978-3-540-71389-0_11}, volume = {4423}, year = {2007}, } @inproceedings{3886, abstract = {The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We show that both the qualitative and quantitative problem for stochastic Müller games are PSPACE-complete. We also consider two well-known sub-classes of Müller objectives, namely, upward-closed and union-closed objectives, and show that both the qualitative and quantitative problem for these sub-classes are coNP-complete.}, author = {Krishnendu Chatterjee}, pages = {436 -- 448}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Stochastic Müller games are PSPACE-complete}}, doi = {10.1007/978-3-540-77050-3_36}, volume = {4855}, year = {2007}, } @inproceedings{3887, abstract = {We consider Markov decision processes (MDPs) with multiple long-run average 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 epsilon-approximated by a memoryless strategy, for all epsilon > 0. In contrast to the single-objective case, the memoryless strategy may require randomization. We show that the Pareto curve can be approximated (a) in polynomial time in the size of the MDP for irreducible MDPs; and (b) in polynomial space in the size of the MDP for all MDPs. 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 for irreducible MDPs and in NP for all MDPs. These results provide algorithms for design exploration in MDP models with multiple long-run average objectives.}, author = {Krishnendu Chatterjee}, pages = {473 -- 484}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Markov decision processes with multiple long-run average objectives}}, doi = {10.1007/978-3-540-77050-3_39}, volume = {4855}, year = {2007}, } @article{3909, abstract = {Social insect colonies have evolved collective immune defences against parasites. These ‘social immune systems’ result from the cooperation of the individual group members to combat the increased risk of disease transmission that arises from sociality and group living. In this review we illustrate the pathways that parasites can take to infect a social insect colony and use these pathways as a framework to predict colony defence mechanisms and present the existing evidence. We find that the collective defences can be both prophylactic and activated on demand and consist of behavioural, physiological and organisational adaptations of the colony that prevent parasite entrance, establishment and spread. We discuss the regulation of collective immunity, which requires complex integration of information about both the parasites and the internal status of the insect colony. Our review concludes with an examination of the evolution of social immunity, which is based on the consequences of selection at both the individual and the colony level.}, author = {Cremer, Sylvia and Armitage, Sophie and Schmid Hempel, Paul}, journal = {Current Biology}, number = {16}, pages = {R693 -- R702}, publisher = {Cell Press}, title = {{Social immunity}}, doi = {10.1016/j.cub.2007.06.008}, volume = {17}, year = {2007}, } @article{3910, author = {Hughes, David and Cremer, Sylvia}, journal = {Animal Behaviour}, number = {5}, pages = {1593 -- 1599}, publisher = {Elsevier}, title = {{Plasticity in anti-parasite behaviours and its suggested role in invasion biology}}, doi = {10.1016/j.anbehav.2006.12.025}, volume = {74}, year = {2007}, } @article{3911, abstract = {Life in a social group increases the risk of disease transmission. To counteract this threat, social insects have evolved manifold antiparasite defenses, ranging from social exclusion of infected group members to intensive care. It is generally assumed that individuals performing hygienic behaviors risk infecting themselves, suggesting a high direct cost of helping. Our work instead indicates the opposite for garden ants. Social contact with individual workers, which were experimentally exposed to a fungal parasite, provided a clear survival benefit to nontreated, naive group members upon later challenge with the same parasite. This first demonstration of contact immunity in Social Hymenoptera and complementary results from other animal groups and plants suggest its general importance in both antiparasite and antiherbivore defense. In addition to this physiological prophylaxis of adult ants, infection of the brood was prevented in our experiment by behavioral changes of treated and naive workers. Parasite-treated ants stayed away from the brood chamber, whereas their naive nestmates increased brood-care activities. Our findings reveal a direct benefit for individuals to perform hygienic behaviors toward others, and this might explain the widely observed maintenance of social cohesion under parasite attack in insect societies.}, author = {Ugelvig, Line V and Cremer, Sylvia}, journal = {Current Biology}, number = {22}, pages = {1967 -- 1971}, publisher = {Cell Press}, title = {{Social prophylaxis: group interaction promotes collective immunity in ant colonies}}, doi = {10.1016/j.cub.2007.10.029}, volume = {17}, year = {2007}, } @article{3937, abstract = {Lymphocyte motility in lymph nodes is regulated by chemokines, but the contribution of integrins to this motility remains obscure. Here we examined lymphocyte migration over CCR7-binding chemokines that 'decorate' lymph node stroma. In a shear-free environment, surface-bound lymph node chemokines but not their soluble counterparts promoted robust and sustained T lymphocyte motility. The chemokine CCL21 induced compartmentalized clustering of the integrins LFA-1 and VLA-4 in motile lymphocytes, but both integrins remained nonadhesive to ligands on lymphocytes, dendritic cells and stroma. The application of shear stress to lymphocytes interacting with CCL21 and integrin ligands promoted robust integrin-mediated adhesion. Thus, lymph node chemokines that promote motility and strongly activate lymphocyte integrins under shear forces fail to stimulate stable integrin adhesiveness in extravascular shear-free environments.}, author = {Woolf, Eilon and Grigorova, Irina and Sagiv, Adi and Grabovsky, Valentin and Feigelson, Sara W and Shulman, Ziv and Hartmann, Tanja and Michael Sixt and Cyster, Jason G and Alon, Ronen}, journal = {Nature Immunology}, number = {10}, pages = {1076 -- 1085}, publisher = {Nature Publishing Group}, title = {{Lymph node chemokines promote sustained T lymphocyte motility without triggering stable integrin adhesiveness in the absence of shear forces}}, doi = {10.1038/ni1499}, volume = {8}, year = {2007}, } @article{3938, abstract = {RhoH is a small GTPase expressed only in the hematopoietic system. With the use of mice with targeted disruption of the RhoH gene, we demonstrated that RhoH is crucial for thymocyte maturation during DN3 to DN4 transition and during positive selection. Furthermore, the differentiation and expansion of DN3 and DN4 thymocytes in vitro were severely impaired. These defects corresponded to defective TCR signaling. Although RhoH is not required for TCR-induced activation of ZAP70 and ZAP70-mediated activation of p38, it is crucial for the tyrosine phosphorylation of LAT, PLCgamma1, and Vav1 and for the activation of Erk and calcium influx. These data suggest that RhoH is important for pre-TCR and TCR signaling because it allows the efficient interaction of ZAP70 with the LAT signalosome, thus regulating thymocyte development.}, author = {Dorn, Tatjana and Kuhn, Ursula and Bungartz, Gerd and Stiller, Sebastian and Bauer, Martina and Ellwart, Joachim and Peters, Thorsten and Scharffetter-Kochanek, Karin and Semmrich, Monika and Laschinger, Melanie and Holzmann, Bernhard and Klinkert, Wolfgang E and Straten, Per Thor and Køllgaard, Tania and Michael Sixt and Brakebusch, Cord}, journal = {Blood}, number = {6}, pages = {2346 -- 2355}, publisher = {American Society of Hematology}, title = {{RhoH is important for positive thymocyte selection and T-cell receptor signaling}}, doi = {10.1182/blood-2006-04-019034}, volume = {109}, year = {2007}, } @article{3972, abstract = {The persistence diagram of a real-valued function on a topological space is a multiset of points in the extended plane. We prove that under mild assumptions on the function, the persistence diagram is stable: small changes in the function imply only small changes in the diagram. We apply this result to estimating the homology of sets in a metric space and to comparing and classifying geometric shapes.}, author = {Cohen-Steiner, David and Herbert Edelsbrunner and Harer, John}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {103 -- 120}, publisher = {Springer}, title = {{Stability of persistence diagrams}}, doi = {10.1007/s00454-006-1276-5}, volume = {37}, year = {2007}, } @article{3973, abstract = {In this paper we bound the difference between the total mean curvatures of two closed surfaces in R-3 in terms of their total absolute curvatures and the Frechet distance between the volumes they enclose. The proof relies on a combination of methods from algebraic topology and integral geometry. We also bound the difference between the lengths of two curves using the same methods.}, author = {Cohen-Steiner, David and Herbert Edelsbrunner}, journal = {Foundations of Computational Mathematics}, number = {4}, pages = {391 -- 404}, publisher = {Springer}, title = {{Inequalities for the curvature of curves and surfaces}}, doi = {10.1007/s10208-005-0200-3}, volume = {7}, year = {2007}, } @inproceedings{3975, abstract = {We study the reconstruction of a stratified space from a possibly noisy point sample. Specifically, we use the vineyard of the distance function restricted to a I-parameter family of neighborhoods of a point to assess the local homology of the stratified space at that point. We prove the correctness of this assessment under the assumption of a sufficiently dense sample. We also give an algorithm that constructs the vineyard and makes the local assessment in time at most cubic in the size of the Delaunay triangulation of the point sample.}, author = {Paul Bendich and Cohen-Steiner, David and Herbert Edelsbrunner and Harer, John and Morozov, Dmitriy}, pages = {536 -- 546}, publisher = {IEEE}, title = {{Inferring local homology from sampled stratified spaces}}, doi = {10.1109/FOCS.2007.33}, year = {2007}, } @article{3976, abstract = {Herein, we study the interfaces of a set of 146 transient protein-protein interfaces in order to better understand the principles of their interactions. We define and generate the protein interface using tools from computational geometry and topology and then apply statistical analysis to its residue composition. In addition to counting individual occurrences, we evaluate pairing preferences, both across and as neighbors on one side of an interface. Likelihood correction emphasizes novel and unexpected pairs, such as the His-Cys pair found in most complexes of serine proteases with their diverse inhibitors and the Met-Met neighbor pair found in unrelated protein interfaces. We also present a visualization of the protein interface that allows for facile identification of residue-residue contacts and other biochemical properties.}, author = {Headd, Jeffrey J and Ban, Y E Andrew and Brown, Paul and Herbert Edelsbrunner and Vaidya, Madhuwanti and Rudolph, Johannes}, journal = {Journal of Proteome Research}, number = {7}, pages = {2576 -- 2586}, publisher = {American Chemical Society}, title = {{Protein-protein interfaces: Properties, preferences, and projections}}, doi = {10.1021/pr070018+}, volume = {6}, year = {2007}, } @article{3977, abstract = {Using inclusion-exclusion, we can write the indicator function of a union of finitely many balls as an alternating sum of indicator functions of common intersections of balls. We exhibit abstract simplicial complexes that correspond to minimal inclusion-exclusion formulas. They include the dual complex, as defined in [3], and are characterized by the independence of their simplices and by geometric realizations with the same underlying space as the dual complex.}, author = {Attali, Dominique and Herbert Edelsbrunner}, journal = {Discrete & Computational Geometry}, number = {1}, pages = {59 -- 77}, publisher = {Springer}, title = {{Inclusion-exclusion formulas from independent complexes}}, doi = {10.1007/s00454-006-1274-7}, volume = {37}, year = {2007}, } @inproceedings{3981, abstract = {Building on the work of Martinetz, Schulten and de Silva, Carlsson, we introduce a 2-parameter family of witness complexes and algorithms for constructing them. This family can be used to determine the gross topology of point cloud data in R-d or other metric spaces. The 2-parameter family is sensitive to differences in sampling density and thus amenable to detecting patterns within the data set. It also lends itself to theoretical analysis. For example, we can prove that in the limit, when the witnesses cover the entire domain, witness complexes in the family that share the first, scale parameter have the same homotopy type.}, author = {Attali, Dominique and Herbert Edelsbrunner and Harer, John and Mileyko, Yuriy}, pages = {386 -- 397}, publisher = {Springer}, title = {{Alpha-beta witness complexes}}, doi = {10.1007/978-3-540-73951-7_34}, volume = {4619}, year = {2007}, } @article{4152, abstract = {Gastrulation is a morphogenetic process that results in the formation of the embryonic germ layers. Here we detail the major cell movements that occur during zebrafish gastrulation: epiboly, internalization, and convergent extension. Although gastrulation is known to be regulated by signaling pathways such as the Wnt/planar cell polarity pathway, many questions remain about the underlying molecular and cellular mechanisms. Key factors that may play a role in gastrulation cell movements are cell adhesion and cytoskeletal rearrangement. In addition, some of the driving force for gastrulation may derive from tissue interactions such as those described between the enveloping layer and the yolk syncytial layer. Future exploration of gastrulation mechanisms relies on the development of sensitive and quantitative techniques to characterize embryonic germ-layer properties.}, author = {Rohde, Laurel and Heisenberg, Carl-Philipp J}, journal = {International Review of Cytology - A Survey of Cell Biology}, pages = {159 -- 192}, publisher = {Academic Press}, title = {{Zebrafish gastrulation: Cell movements, signals, and mechanisms}}, doi = {10.1016/S0074-7696(07)61004-3}, volume = {261}, year = {2007}, } @article{4182, abstract = {We are interested in the cellular and molecular mechanisms underlying tissue morphogenesis during zebrafish gastrulation. Both differential cell adhesion and contractility have been proposed to be key mechanisms by which tissues form and rearrange in development. To obtain insight into the potential roles of differential cell adhesion and contraction for germ layer morphogenesis during gastrulation, we are analyzing cell adhesion and contraction of germ layer progenitor cells using atomic force microscopy, primary tissue culture and transplantation assays. I will present and discuss data about the differential adhesiveness and contractility of germ layer progenitor cells in the context of germ layer formation during vertebrate gastrulation.}, author = {Krieg, Michael and Arboleda, Yohanna and Müller, Daniel and Heisenberg, Carl-Philipp J}, journal = {European Journal of Cell Biology}, number = {Supplement 1}, pages = {39 -- 39}, publisher = {Elsevier}, title = {{The role of cell adhesion and contractility for germ layer morphogenesis during zebrafish gastrulation}}, doi = {10.1016/j.ejcb.2007.02.002}, volume = {86}, year = {2007}, } @article{4205, abstract = {Background: Bone morphogenetic proteins (Bmps) are required for the specification of ventrolateral cell fates during embryonic dorsoventral patterning and for proper convergence and extension gastrulation movements, but the mechanisms underlying the latter role remained elusive. Results: Via bead implantations, we show that the Bmp gradient determines the direction of lateral mesodermal cell migration during dorsal convergence in the zebrafish gastrula. This effect is independent of its role during dorsoventral patterning and of noncanonical Wnt signaling. However, it requires Bmp signal transduction through AIk8 and Smad5 to negatively regulate Ca2+/Cadherin-dependent cell-cell adhesiveness. In vivo, converging mesodermal cells form lamellipodia that attach to adjacent cells. Bmp signaling diminishes the Cadherin-dependent stability of such contact points, thereby abrogating subsequent cell displacement during lamellipodial retraction. Conclusions: We propose that the ventral-to-dorsal Bmp gradient has an instructive role to establish a reverse gradient of cell-cell adhesiveness, thereby defining different migratory zones and directing lamellipodia-driven cell migrations during dorsal convergence in lateral regions of the zebrafish gastrula.}, author = {Von Der Hardt, Sophia and Bakkers, Jeroen and Inbal, Adi and Carvalho, Lara and Solnica Krezel, Lilianna and Heisenberg, Carl-Philipp J and Hammerschmidt, Matthias}, journal = {Current Biology}, number = {6}, pages = {475 -- 487}, publisher = {Cell Press}, title = {{The Bmp gradient of the zebrafish gastrula guides migrating lateral cells by regulating cell-cell adhesion}}, doi = {10.1016/j.cub.2007.02.013}, volume = {17}, year = {2007}, }