@inproceedings{4545, abstract = {A stochastic game is a two-player game played oil a graph, where in each state the successor is chosen either by One of the players, or according to a probability distribution. We Survey Stochastic games with limsup and liminf objectives. A real-valued re-ward is assigned to each state, and the value of all infinite path is the limsup (resp. liminf) of all rewards along the path. The value of a stochastic game is the maximal expected value of an infinite path that call he achieved by resolving the decisions of the first player. We present the complexity of computing values of Stochastic games and their subclasses, and the complexity, of optimal strategies in such games. }, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, location = {Rhodos, Greece}, pages = {1 -- 15}, publisher = {Springer}, title = {{A survey of stochastic games with limsup and liminf objectives}}, doi = {10.1007/978-3-642-02930-1_1}, volume = {5556}, year = {2009}, } @inproceedings{4569, abstract = {Most specification languages express only qualitative constraints. However, among two implementations that satisfy a given specification, one may be preferred to another. For example, if a specification asks that every request is followed by a response, one may prefer an implementation that generates responses quickly but does not generate unnecessary responses. We use quantitative properties to measure the “goodness” of an implementation. Using games with corresponding quantitative objectives, we can synthesize “optimal” implementations, which are preferred among the set of possible implementations that satisfy a given specification. In particular, we show how automata with lexicographic mean-payoff conditions can be used to express many interesting quantitative properties for reactive systems. In this framework, the synthesis of optimal implementations requires the solution of lexicographic mean-payoff games (for safety requirements), and the solution of games with both lexicographic mean-payoff and parity objectives (for liveness requirements). We present algorithms for solving both kinds of novel graph games.}, author = {Bloem, Roderick and Chatterjee, Krishnendu and Henzinger, Thomas A and Jobstmann, Barbara}, location = {Grenoble, France}, pages = {140 -- 156}, publisher = {Springer}, title = {{Better quality in synthesis through quantitative objectives}}, doi = {10.1007/978-3-642-02658-4_14}, volume = {5643}, year = {2009}, } @inproceedings{4580, abstract = {Alpaga is a solver for two-player parity games with imperfect information. Given the description of a game, it determines whether the first player can ensure to win and, if so, it constructs a winning strategy. The tool provides a symbolic implementation of a recent algorithm based on antichains.}, author = {Berwanger, Dietmar and Krishnendu Chatterjee and De Wulf, Martin and Doyen, Laurent and Thomas Henzinger}, pages = {58 -- 61}, publisher = {Springer}, title = {{Alpaga: A tool for solving parity games with imperfect information}}, doi = {10.1007/978-3-642-00768-2_7}, volume = {5505}, year = {2009}, } @misc{5392, abstract = {We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs of [GO09] and present a precise characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems.}, author = {Chatterjee, Krishnendu}, issn = {2664-1690}, pages = {17}, publisher = {IST Austria}, title = {{Probabilistic automata on infinite words: Decidability and undecidability results}}, doi = {10.15479/AT:IST-2009-0004}, year = {2009}, } @misc{5393, abstract = {Gist is a tool that (a) solves the qualitative analysis problem of turn-based probabilistic games with ω-regular objectives; and (b) synthesizes reasonable environment assumptions for synthesis of unrealizable specifications. Our tool provides efficient implementations of several reduction based techniques to solve turn-based probabilistic games, and uses the analysis of turn-based probabilistic games for synthesizing environment assumptions for unrealizable specifications.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Jobstmann, Barbara and Radhakrishna, Arjun}, issn = {2664-1690}, pages = {12}, publisher = {IST Austria}, title = {{Gist: A solver for probabilistic games}}, doi = {10.15479/AT:IST-2009-0003}, year = {2009}, } @misc{5394, abstract = {We consider two-player games played on graphs with request-response and finitary Streett objectives. We show these games are PSPACE-hard, improving the previous known NP-hardness. We also improve the lower bounds on memory required by the winning strategies for the players.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Horn, Florian}, issn = {2664-1690}, pages = {11}, publisher = {IST Austria}, title = {{Improved lower bounds for request-response and finitary Streett games}}, doi = {10.15479/AT:IST-2009-0002}, year = {2009}, } @misc{5395, abstract = {We study observation-based strategies for partially-observable Markov decision processes (POMDPs) with omega-regular objectives. An observation-based strategy relies on partial information about the history of a play, namely, on the past sequence of observa- tions. We consider the qualitative analysis problem: given a POMDP with an omega-regular objective, whether there is an observation-based strategy to achieve the objective with probability 1 (almost-sure winning), or with positive probability (positive winning). Our main results are twofold. First, we present a complete picture of the computational complexity of the qualitative analysis of POMDPs with parity objectives (a canonical form to express omega-regular objectives) and its subclasses. Our contribution consists in establishing several upper and lower bounds that were not known in literature. Second, we present optimal bounds (matching upper and lower bounds) on the memory required by pure and randomized observation-based strategies for the qualitative analysis of POMDPs with parity objectives and its subclasses.}, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, issn = {2664-1690}, pages = {20}, publisher = {IST Austria}, title = {{Qualitative analysis of partially-observable Markov decision processes}}, doi = {10.15479/AT:IST-2009-0001}, year = {2009}, } @article{2868, abstract = {Plants exhibit an amazing developmental flexibility. Plant embryogenesis results in the establishment of a simple apical-basal axis represented by apical shoot and basal root meristems. Later, during postembryonic growth, shaping of the plant body continues by the formation and activation of numerous adjacent meristems that give rise to lateral shoot branches, leaves, flowers, or lateral roots. This developmental plasticity reflects an important feature of the plant's life strategy based on the rapid reaction to different environmental stimuli, such as temperature fluctuations, availability of nutrients, light or water and response resulting in modulation of developmental programs. Plant hormones are important endogenous factors for the integration of these environmental inputs and regulation of plant development. After a period of studies focused primarily on single hormonal pathways that enabled us to understand the hormone perception and signal transduction mechanisms, it became obvious that the developmental output mediated by a single hormonal pathway is largely modified through a whole network of interactions with other hormonal pathways. In this review, we will summarize recent knowledge on hormonal networks that regulate the development and growth of root with focus on the hormonal interactions that shape the root apical meristem. }, author = {Eva Benková and Hejátko, Jan}, journal = {Plant Molecular Biology}, number = {4}, pages = {383 -- 396}, publisher = {Springer}, title = {{Hormone interactions at the root apical meristem}}, doi = {10.1007/s11103-008-9393-6}, volume = {69}, year = {2009}, } @article{2869, abstract = {Lateral root formation is a major determinant of root systems architecture. The degree of root branching impacts the efficiency of water uptake, acquisition of nutrients and anchorage by plants. Understanding the regulation of lateral root development is therefore of vital agronomic importance. The molecular and cellular basis of lateral root formation has been most extensively studied in the plant model Arabidopsis thaliana (Arabidopsis). Significant progress has recently been made in identifying many new Arabidopsis genes that regulate lateral root initiation, patterning and emergence processes. We review how these studies have revealed that the plant hormone auxin represents a common signal that integrates these distinct yet interconnected developmental processes.}, author = {Péret, Benjamin and De Rybel, Bert and Casimiro, Ilda and Eva Benková and Swarup, Ranjan and Laplaze, Laurent and Beeckman, Tom and Bennett, Malcolm J}, journal = {Trends in Plant Science}, number = {7}, pages = {399 -- 408}, publisher = {Cell Press}, title = {{Arabidopsis lateral root development: an emerging story}}, doi = {10.1016/j.tplants.2009.05.002}, volume = {14}, year = {2009}, } @article{2932, abstract = {We describe a new implementation of the Edmonds’s algorithm for computing a perfect matching of minimum cost, to which we refer as Blossom V. A key feature of our implementation is a combination of two ideas that were shown to be effective for this problem: the “variable dual updates” approach of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and the use of priority queues. We achieve this by maintaining an auxiliary graph whose nodes correspond to alternating trees in the Edmonds’s algorithm. While our use of priority queues does not improve the worst-case complexity, it appears to lead to an efficient technique. In the majority of our tests Blossom V outperformed previous implementations of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and Mehlhorn and Schäfer (J Algorithmics Exp (JEA) 7:4, 2002), sometimes by an order of magnitude. We also show that for large VLSI instances it is beneficial to update duals by solving a linear program, contrary to a conjecture by Cook and Rohe. }, author = {Vladimir Kolmogorov}, journal = {Mathematical Programming Computation}, number = {1}, pages = {43 -- 67}, publisher = {Springer}, title = {{Blossom V: A new implementation of a minimum cost perfect matching algorithm}}, doi = {10.1007/s12532-009-0002-8}, volume = {1}, year = {2009}, } @article{3046, abstract = {Plant-parasitic nematodes are destructive plant pathogens that cause significant yield losses. They induce highly specialized feeding sites (NFS) in infected plant roots from which they withdraw nutrients. In order to establish these NFS, it is thought that the nematodes manipulate the molecular and physiological pathways of their hosts. Evidence is accumulating that the plant signalling molecule auxin is involved in the initiation and development of the feeding sites of sedentary plant-parasitic nematodes. Intercellular transport of auxin is essential for various aspects of plant growth and development. Here, we analysed the spatial and temporal expression of PIN auxin transporters during the early events of NFS establishment using promoter-GUS/GFP fusion lines. Additionally, single and double pin mutants were used in infection studies to analyse the role of the different PIN proteins during cyst nematode infection. Based on our results, we postulate a model in which PIN1-mediated auxin transport is needed to deliver auxin to the initial syncytial cell, whereas PIN3 and PIN4 distribute the accumulated auxin laterally and are involved in the radial expansion of the NFS. Our data demonstrate that cyst nematodes are able to hijack the auxin distribution network in order to facilitate the infection process. © 2009 Grunewald et al}, author = {Grunewald, Wim and Cannoot, Bernard and Jirí Friml and Gheysen, Godelieve}, journal = {PLoS Pathogens}, number = {1}, publisher = {Public Library of Science}, title = {{Parasitic nematodes modulate PIN mediated auxin transport to facilitate infection}}, doi = { 10.1371/journal.ppat.1000266}, volume = {5}, year = {2009}, } @article{3047, abstract = { Auxin transport is mediated at the cellular level by three independent mechanisms that are characterised by the PIN-formed (PIN), P-glycoprotein (ABCB/PGP) and AUX/LAX transport proteins. The PIN and ABCB transport proteins, best represented by PIN1 and ABCB19 (PGP19), have been shown to coordinately regulate auxin efflux. When PIN1 and ABCB19 coincide on the plasma membrane, their interaction enhances the rate and specificity of auxin efflux and the dynamic cycling of PIN1 is reduced. However, ABCB19 function is not regulated by the dynamic cellular trafficking mechanisms that regulate PIN1 in apical tissues, as localisation of ABCB19 on the plasma membrane was not inhibited by short-term treatments with latrunculin B, oryzalin, brefeldin A (BFA) or wortmannin - all of which have been shown to alter PIN1 and/or PIN2 plasma membrane localisation. When taken up by endocytosis, the styryl dye FM4-64 labels diffuse rather than punctuate intracellular bodies in abcb19 (pgp19), and some aggregations of PIN1 induced by short-term BFA treatment did not disperse after BFA washout in abcb19. Although the subcellular localisations of ABCB19 and PIN1 in the reciprocal mutant backgrounds were like those in wild type, PIN1 plasma membrane localisation in abcb19 roots was more easily perturbed by the detergent Triton X-100, but not other non-ionic detergents. ABCB19 is stably associated with sterol/sphingolipid-enriched membrane fractions containing BIG/TIR3 and partitions into Triton X-100 detergent-resistant membrane (DRM) fractions. In the wild type, PIN1 was also present in DRMs, but was less abundant in abcb19 DRMs. These observations suggested a rationale for the observed lack of auxin transport activity when PIN1 is expressed in a non-plant heterologous system. PIN1 was therefore expressed in Schizosaccharomyces pombe, which has plant-like sterol-enriched microdomains, and catalysed auxin transport in these cells. These data suggest that ABCB19 stabilises PIN1 localisation at the plasma membrane in discrete cellular subdomains where PIN1 and ABCB19 expression overlaps. }, author = {Titapiwatanakun, Boosaree and Blakeslee, Joshua and Bandyopadhyay, Anindita and Yang, Haibing and Mravec, Jozef and Sauer, Michael and Cheng, Yan and Adamec, Jiří and Nagashima, Akitomo and Geisler, Markus and Sakai, Tatsuya and Jirí Friml and Peer, Wendy A and Murphy, Angus S}, journal = {Plant Journal}, number = {1}, pages = {27 -- 44}, publisher = {Wiley-Blackwell}, title = {{ABCB19 PGP19 stabilises PIN1 in membrane microdomains in Arabidopsis}}, doi = {10.1111/j.1365-313X.2008.03668.x}, volume = {57}, year = {2009}, } @article{3048, abstract = {Endocytic vesicle trafficking is crucial for regulating activity and localization of plasma membrane components, but the process is still poorly genetically defined in plants. Membrane proteins of the PIN-FORMED (PIN) family exhibit polar localization in plant cells and facilitate cellular efflux of the plant hormone auxin, thereby regulating multiple developmental processes [1, 2]. PIN proteins undergo constitutive endocytosis and GNOM ARF GEF-dependent recycling [3-5], and their localization is under extensive regulation by developmental and environmental cues [6-9]. We designed a fluorescence imaging-based screen to identify Arabidopsis thaliana mutants defective in internalization of proteins including PINs from the plasma membrane. We identified three mutant loci, BFA-visualized endocytic trafficking defective1 (ben1) through ben3 that do not efficiently accumulate PIN1-GFP in intracellular compartments after inhibition of recycling and secretion by fungal toxin brefeldin A (BFA). Fine mapping revealed that BEN1 encodes an ARF GEF vesicle trafficking regulator from the functionally uncharacterized BIG class. ben1 mutant has been previously implicated in pathogen response [10] and shows cell polarity, BFA sensitivity, and growth defects. BEN1 is involved in endocytosis of plasma membrane proteins and localizes to early endocytic compartments distinct from GNOM-positive endosomes. Our results identify BEN1 as the ARF GEF mediating early endosomal traffic.}, author = {Tanaka, Hirokazu and Kitakura, Saeko and De Rycke, Riet M and De Groodt, Ruth and Jirí Friml}, journal = {Current Biology}, number = {5}, pages = {391 -- 397}, publisher = {Cell Press}, title = {{Fluorescence imaging based screen identifies ARF GEF component of early endosomal trafficking}}, doi = {10.1016/j.cub.2009.01.057}, volume = {19}, year = {2009}, } @article{3049, abstract = {Postembryonic de novo organogenesis represents an important competence evolved in plants that allows their physiological and developmental adaptation to changing environmental conditions. The phytohormones auxin and cytokinin (CK) are important regulators of the developmental fate of pluripotent plant cells. However, the molecular nature of their interaction(s) in control of plant organogenesis is largely unknown. Here, we show that CK modulates auxin-induced organogenesis (AIO) via regulation of the efflux-dependent intercellular auxin distribution. We used the hypocotyl explants-based in vitro system to study the mechanism underlying de novo organogenesis. We show that auxin, but not CK, is capable of triggering organogenesis in hypocotyl explants. The AIO is accompanied by endogenous CK production and tissue-specific activation of CK signaling. CK affects differential auxin distribution, and the CK-mediated modulation of organogenesis is simulated by inhibition of polar auxin transport. CK reduces auxin efflux from cultured tobacco cells and regulates expression of auxin efflux carriers from the PIN family in hypocotyl explants. Moreover, endogenous CK levels influence PIN transcription and are necessary to maintain intercellular auxin distribution in planta. Based on these findings, we propose a model in which auxin acts as a trigger of the organogenic processes, whose output is modulated by the endogenously produced CKs. We propose that an important mechanism of this CK action is its effect on auxin distribution via regulation of expression of auxin efflux carriers.}, author = {Pernisová, Markéta and Klíma, Petr and Horák, Jakub and Válková, Martina and Malbeck, Jiří and Souček, Přemysl and Reichman, Pavel and Hoyerová, Klára and Dubová, Jaroslava and Jirí Friml and Zažímalová, Eva and Hejátko, Jan}, journal = {PNAS}, number = {9}, pages = {3609 -- 3614}, publisher = {National Academy of Sciences}, title = {{Cytokinins modulate auxin induced organogenesis in plants via regulation of the auxin efflux}}, doi = {10.1073/pnas.0811539106}, volume = {106}, year = {2009}, } @article{3050, abstract = {Plant development is governed by signaling molecules called phytohormones. Typically, in certain developmental processes more than 1 hormone is implicated and, thus, coordination of their overlapping activities is crucial for correct plant development. However, molecular mechanisms underlying the hormonal crosstalk are only poorly understood. Multiple hormones including cytokinin and auxin have been implicated in the regulation of root development. Here we dissect the roles of cytokinin in modulating growth of the primary root. We show that cytokinin effect on root elongation occurs through ethylene signaling whereas cytokinin effect on the root meristem size involves ethylene-independent modulation of transport-dependent asymmetric auxin distribution. Exogenous or endogenous modification of cytokinin levels and cytokinin signaling lead to specific changes in transcription of several auxin efflux carrier genes from the PIN family having a direct impact on auxin efflux from cultured cells and on auxin distribution in the root apex. We propose a novel model for cytokinin action in regulating root growth: Cytokinin influences cell-to-cell auxin transport by modification of expression of several auxin transport components and thus modulates auxin distribution important for regulation of activity and size of the root meristem.}, author = {Růžička, Kamil and Šimášková, Mária and Duclercq, Jérôme and Petrášek, Jan and Zažímalová, Eva and Sibu Simon and Jirí Friml and Van Montagu, Marc C and Eva Benková}, journal = {PNAS}, number = {11}, pages = {4284 -- 4289}, publisher = {National Academy of Sciences}, title = {{Cytokinin regulates root meristem activity via modulation of the polar auxin transport}}, doi = {10.1073/pnas.0900060106}, volume = {106}, year = {2009}, } @article{3051, author = {Weijers, Dolf and Friml, Jirí}, journal = {Cell}, number = {6}, pages = {1172 -- 1172}, publisher = {Cell Press}, title = {{SnapShot: Auxin signaling and transport}}, doi = {10.1016/j.cell.2009.03.009}, volume = {136}, year = {2009}, } @article{3052, abstract = {The dynamic, differential distribution of the hormone auxin within plant tissues controls an impressive variety of developmental processes, which tailor plant growth and morphology to environmental conditions. Various environmental and endogenous signals can be integrated into changes in auxin distribution through their effects on local auxin biosynthesis and intercellular auxin transport. Individual cells interpret auxin largely by a nuclear signaling pathway that involves the F box protein TIR1 acting as an auxin receptor. Auxin-dependent TIR1 activity leads to ubiquitination-based degradation of transcriptional repressors and complex transcriptional reprogramming. Thus, auxin appears to be a versatile trigger of preprogrammed developmental changes in plant cells.}, author = {Vanneste, Steffen and Friml, Jirí}, journal = {Cell}, number = {6}, pages = {1005 -- 1016}, publisher = {Cell Press}, title = {{Auxin: A trigger for change in plant development}}, doi = {10.1016/j.cell.2009.03.001}, volume = {136}, year = {2009}, } @article{3053, author = {Benková, Eva and Ivanchenko, Maria and Friml, Jirí and Shishkova, Svetlana and Dubrovsky, Joseph}, journal = {Trends in Plant Science}, number = {4}, pages = {189 -- 193}, publisher = {Cell Press}, title = {{A morphogenetic trigger: Is there an emerging concept in plant developmental biology?}}, doi = {10.1016/j.tplants.2009.01.006}, volume = {14}, year = {2009}, } @article{3054, abstract = {As multicellular organisms, plants, like animals, use endogenous signaling molecules to coordinate their own physiology and development. To compensate for the absence of a cardiovascular system, plants have evolved specialized transport pathways to distribute signals and nutrients. The main transport streams include the xylem flow of the nutrients from the root to the shoot and the phloem flow of materials from the photosynthetic active tissues. These long-distance transport processes are complemented by several intercellular transport mechanisms (apoplastic, symplastic and transcellular transport). A prominent example of transcellular flow is transport of the phytohormone auxin within tissues. The process is mediated by influx and efflux carriers, whose polar localization in the plasma membrane determines the directionality of the flow. This polar auxin transport generates auxin maxima and gradients within tissues that are instrumental in the diverse regulation of various plant developmental processes, including embryogenesis, organogenesis, vascular tissue formation and tropisms.}, author = {Robert, Hélène and Friml, Jirí}, journal = {Nature Chemical Biology}, number = {5}, pages = {325 -- 332}, publisher = {Nature Publishing Group}, title = {{Auxin and other signals on the move in plants}}, doi = {10.1038/nchembio.170}, volume = {5}, year = {2009}, } @article{3055, abstract = {ACAP-type ARF GTPase activating proteins (ARF-GAPs) regulate multiple cellular processes, including endocytosis, secretion, phagocytosis, cell adhesion and cell migration. However, the regulation of ACAP functions by other cellular proteins is poorly understood. We have reported previously that a plant ACAP, VAN3, plays a pivotal role in plant venation continuity. Here, we report on newly identified VAN3 regulators: the CVP2 (cotyledon vascular pattern 2) 5 PTase, which is considered to degrade IP3 and also to produce PtdIns(4)P from PtdIns(4,5)P2; and a PH domain-containing protein, VAB (VAN3 binding protein). Combinational mutations of both CVP2 and its closest homologue CVL1 (CVP2 like 1) phenocopied the strong allele of van3 mutants, showing severe vascular continuity. The phenotype of double mutants between van3, cvp2 and vab suggested that VAN3, CVP2 and VAB function in vascular pattern formation in the same pathway. Localization analysis revealed that both CVP2 and VAB colocalize with VAN3 in the trans- Golgi network (TGN), supporting their functions in the same pathway. The subcellular localization of VAN3 was dependent on its PH domain, and mislocalization of VAN3 was induced in cvp2 or vab mutants. These results suggest that CVP2 and VAB cooperatively regulate the subcellular localization of VAN3 through the interaction between its PH domain and phosphoinositides and/or inositol phosphates. In addition, PtdIns(4)P, to which VAN3 binds preferentially, enhanced the ARF-GAP activity of VAN3, whereas IP3 inhibited it. These results suggest the existence of PtdIns(4)P and/or IP3-dependent subcellular targeting and regulation of VAN3 ACAP activity that governs plant vascular tissue continuity.}, author = {Naramoto, Satoshi and Sawa, Shinichiro and Koizumi, Koji and Uemura, Tomohiro and Ueda, Takashi and Jirí Friml and Nakano, Akihiko and Fukuda, Hiroo}, journal = {Development}, number = {9}, pages = {1529 -- 1538}, publisher = {Company of Biologists}, title = {{Phosphoinositide-dependent regulation of VAN3 ARF-GAP localization and activity essential for vascular tissue continuity in plants}}, doi = {10.1242/dev.030098}, volume = {136}, year = {2009}, }