TY - JOUR AB - Podoplanin, a mucin-like plasma membrane protein, is expressed by lymphatic endothelial cells and responsible for separation of blood and lymphatic circulation through activation of platelets. Here we show that podoplanin is also expressed by thymic fibroblastic reticular cells (tFRC), a novel thymic medulla stroma cell type associated with thymic conduits, and involved in development of natural regulatory T cells (nTreg). Young mice deficient in podoplanin lack nTreg owing to retardation of CD4+CD25+ thymocytes in the cortex and missing differentiation of Foxp3+ thymocytes in the medulla. This might be due to CCL21 that delocalizes upon deletion of the CCL21-binding podoplanin from medullar tFRC to cortex areas. The animals do not remain devoid of nTreg but generate them delayed within the first month resulting in Th2-biased hypergammaglobulinemia but not in the death-causing autoimmune phenotype of Foxp3-deficient Scurfy mice. AU - Fuertbauer, Elke AU - Zaujec, Jan AU - Uhrin, Pavel AU - Raab, Ingrid AU - Weber, Michele AU - Schachner, Helga AU - Bauer, Miroslav AU - Schütz, Gerhard AU - Binder, Bernd AU - Sixt, Michael K AU - Kerjaschki, Dontscho AU - Stockinger, Hannes ID - 522 IS - 1-2 JF - Immunology Letters TI - Thymic medullar conduits-associated podoplanin promotes natural regulatory T cells VL - 154 ER - TY - CONF AB - We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Randour, Mickael AU - Raskin, Jean ID - 2279 TI - Looking at mean-payoff and total-payoff through windows VL - 8172 ER - TY - JOUR AB - Establishment of the embryonic axis foreshadows the main body axis of adults both in plants and in animals, but underlying mechanisms are considered distinct. Plants utilize directional, cell-to-cell transport of the growth hormone auxin [1, 2] to generate an asymmetric auxin response that specifies the embryonic apical-basal axis [3-6]. The auxin flow directionality depends on the polarized subcellular localization of PIN-FORMED (PIN) auxin transporters [7, 8]. It remains unknown which mechanisms and spatial cues guide cell polarization and axis orientation in early embryos. Herein, we provide conceptually novel insights into the formation of embryonic axis in Arabidopsis by identifying a crucial role of localized tryptophan-dependent auxin biosynthesis [9-12]. Local auxin production at the base of young embryos and the accompanying PIN7-mediated auxin flow toward the proembryo are required for the apical auxin response maximum and the specification of apical embryonic structures. Later in embryogenesis, the precisely timed onset of localized apical auxin biosynthesis mediates PIN1 polarization, basal auxin response maximum, and specification of the root pole. Thus, the tight spatiotemporal control of distinct local auxin sources provides a necessary, non-cell-autonomous trigger for the coordinated cell polarization and subsequent apical-basal axis orientation during embryogenesis and, presumably, also for other polarization events during postembryonic plant life [13, 14]. AU - Robert, Hélène AU - Grones, Peter AU - Stepanova, Anna AU - Robles, Linda AU - Lokerse, Annemarie AU - Alonso, Jose AU - Weijers, Dolf AU - Friml, Jirí ID - 528 IS - 24 JF - Current Biology TI - Local auxin sources orient the apical basal axis in arabidopsis embryos VL - 23 ER - TY - JOUR AB - The apical-basal axis of the early plant embryo determines the body plan of the adult organism. To establish a polarized embryonic axis, plants evolved a unique mechanism that involves directional, cell-to-cell transport of the growth regulator auxin. Auxin transport relies on PIN auxin transporters [1], whose polar subcellular localization determines the flow directionality. PIN-mediated auxin transport mediates the spatial and temporal activity of the auxin response machinery [2-7] that contributes to embryo patterning processes, including establishment of the apical (shoot) and basal (root) embryo poles [8]. However, little is known of upstream mechanisms guiding the (re)polarization of auxin fluxes during embryogenesis [9]. Here, we developed a model of plant embryogenesis that correctly generates emergent cell polarities and auxin-mediated sequential initiation of apical-basal axis of plant embryo. The model relies on two precisely localized auxin sources and a feedback between auxin and the polar, subcellular PIN transporter localization. Simulations reproduced PIN polarity and auxin distribution, as well as previously unknown polarization events during early embryogenesis. The spectrum of validated model predictions suggests that our model corresponds to a minimal mechanistic framework for initiation and orientation of the apical-basal axis to guide both embryonic and postembryonic plant development. AU - Wabnik, Krzysztof T AU - Robert, Hélène AU - Smith, Richard AU - Friml, Jirí ID - 527 IS - 24 JF - Current Biology TI - Modeling framework for the establishment of the apical-basal embryonic axis in plants VL - 23 ER - TY - GEN AB - In this work we present a flexible tool for tumor progression, which simulates the evolutionary dynamics of cancer. Tumor progression implements a multi-type branching process where the key parameters are the fitness landscape, the mutation rate, and the average time of cell division. The fitness of a cancer cell depends on the mutations it has accumulated. The input to our tool could be any fitness landscape, mutation rate, and cell division time, and the tool produces the growth dynamics and all relevant statistics. AU - Reiter, Johannes AU - Bozic, Ivana AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 5399 SN - 2664-1690 TI - TTP: Tool for Tumor Progression ER - TY - CONF AB - We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal EXPTIME-complete complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite-memory strategies. We also establish asymptotically optimal (exponential) memory bounds. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Tracol, Mathieu ID - 2295 TI - What is decidable about partially observable Markov decision processes with omega-regular objectives VL - 23 ER - TY - GEN AB - We consider concurrent games played by two-players on a finite state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to every transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of mean-payoff games) that is not known to be in polynomial time. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus ID - 5403 SN - 2664-1690 TI - Qualitative analysis of concurrent mean-payoff games ER - TY - GEN AB - Linearizability requires that the outcome of calls by competing threads to a concurrent data structure is the same as some sequential execution where each thread has exclusive access to the data structure. In an ordered data structure, such as a queue or a stack, linearizability is ensured by requiring threads commit in the order dictated by the sequential semantics of the data structure; e.g., in a concurrent queue implementation a dequeue can only remove the oldest element. In this paper, we investigate the impact of this strict ordering, by comparing what linearizability allows to what existing implementations do. We first give an operational definition for linearizability which allows us to build the most general linearizable implementation as a transition system for any given sequential specification. We then use this operational definition to categorize linearizable implementations based on whether they are bound or free. In a bound implementation, whenever all threads observe the same logical state, the updates to the logical state and the temporal order of commits coincide. All existing queue implementations we know of are bound. We then proceed to present, to the best of our knowledge, the first ever free queue implementation. Our experiments show that free implementations have the potential for better performance by suffering less from contention. AU - Henzinger, Thomas A AU - Sezgin, Ali ID - 5402 SN - 2664-1690 TI - How free is your linearizable concurrent data structure? ER - TY - GEN AB - We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish asymptotically optimal (exponential) memory bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Tracol, Mathieu ID - 5400 SN - 2664-1690 TI - What is decidable about partially observable Markov decision processes with ω-regular objectives ER - TY - GEN AB - We study finite-state two-player (zero-sum) concurrent mean-payoff games played on a graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lie in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP and coNP is the long-standing best known bound). We show that the exact value can be expressed in the existential theory of the reals, and also establish square-root sum hardness for a related class of games. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus ID - 5404 SN - 2664-1690 TI - The complexity of ergodic games ER -