TY - JOUR AB - We study algorithmic questions wrt algebraic path properties in concurrent systems, where the transitions of the system are labeled from a complete, closed semiring. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus AU - Goharshady, Amir Kafshdar AU - Pavlogiannis, Andreas ID - 6009 IS - 3 JF - ACM Transactions on Programming Languages and Systems SN - 0164-0925 TI - Algorithms for algebraic path properties in concurrent systems of constant treewidth components VL - 40 ER - TY - CONF AB - We consider the stochastic shortest path (SSP)problem for succinct Markov decision processes(MDPs), where the MDP consists of a set of vari-ables, and a set of nondeterministic rules that up-date the variables. First, we show that several ex-amples from the AI literature can be modeled assuccinct MDPs. Then we present computationalapproaches for upper and lower bounds for theSSP problem: (a) for computing upper bounds, ourmethod is polynomial-time in the implicit descrip-tion of the MDP; (b) for lower bounds, we present apolynomial-time (in the size of the implicit descrip-tion) reduction to quadratic programming. Our ap-proach is applicable even to infinite-state MDPs.Finally, we present experimental results to demon-strate the effectiveness of our approach on severalclassical examples from the AI literature. AU - Chatterjee, Krishnendu AU - Fu, Hongfei AU - Goharshady, Amir AU - Okati, Nastaran ID - 5977 SN - 10450823 T2 - Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence TI - Computational approaches for stochastic shortest path on succinct MDPs VL - 2018 ER - TY - JOUR AB - We show that a rather simple, steady modification of the streamwise velocity profile in a pipe can lead to a complete collapse of turbulence and the flow fully relaminarizes. Two different devices, a stationary obstacle (inset) and a device which injects fluid through an annular gap close to the wall, are used to control the flow. Both devices modify the streamwise velocity profile such that the flow in the center of the pipe is decelerated and the flow in the near wall region is accelerated. We present measurements with stereoscopic particle image velocimetry to investigate and capture the development of the relaminarizing flow downstream these devices and the specific circumstances responsible for relaminarization. We find total relaminarization up to Reynolds numbers of 6000, where the skin friction in the far downstream distance is reduced by a factor of 3.4 due to relaminarization. In a smooth straight pipe the flow remains completely laminar downstream of the control. Furthermore, we show that transient (temporary) relaminarization in a spatially confined region right downstream the devices occurs also at much higher Reynolds numbers, accompanied by a significant local skin friction drag reduction. The underlying physical mechanism of relaminarization is attributed to a weakening of the near-wall turbulence production cycle. AU - Kühnen, Jakob AU - Scarselli, Davide AU - Schaner, Markus AU - Hof, Björn ID - 422 IS - 4 JF - Flow Turbulence and Combustion TI - Relaminarization by steady modification of the streamwise velocity profile in a pipe VL - 100 ER - TY - JOUR AB - Turbulence is the major cause of friction losses in transport processes and it is responsible for a drastic drag increase in flows over bounding surfaces. While much effort is invested into developing ways to control and reduce turbulence intensities, so far no methods exist to altogether eliminate turbulence if velocities are sufficiently large. We demonstrate for pipe flow that appropriate distortions to the velocity profile lead to a complete collapse of turbulence and subsequently friction losses are reduced by as much as 90%. Counterintuitively, the return to laminar motion is accomplished by initially increasing turbulence intensities or by transiently amplifying wall shear. Since neither the Reynolds number nor the shear stresses decrease (the latter often increase), these measures are not indicative of turbulence collapse. Instead, an amplification mechanism measuring the interaction between eddies and the mean shear is found to set a threshold below which turbulence is suppressed beyond recovery. AU - Kühnen, Jakob AU - Song, Baofang AU - Scarselli, Davide AU - Budanur, Nazmi B AU - Riedl, Michael AU - Willis, Ashley AU - Avila, Marc AU - Hof, Björn ID - 461 JF - Nature Physics TI - Destabilizing turbulence in pipe flow VL - 14 ER - TY - JOUR AB - Auxin is unique among plant hormones due to its directional transport that is mediated by the polarly distributed PIN auxin transporters at the plasma membrane. The canalization hypothesis proposes that the auxin feedback on its polar flow is a crucial, plant-specific mechanism mediating multiple self-organizing developmental processes. Here, we used the auxin effect on the PIN polar localization in Arabidopsis thaliana roots as a proxy for the auxin feedback on the PIN polarity during canalization. We performed microarray experiments to find regulators of this process that act downstream of auxin. We identified genes that were transcriptionally regulated by auxin in an AXR3/IAA17- and ARF7/ARF19-dependent manner. Besides the known components of the PIN polarity, such as PID and PIP5K kinases, a number of potential new regulators were detected, among which the WRKY23 transcription factor, which was characterized in more detail. Gain- and loss-of-function mutants confirmed a role for WRKY23 in mediating the auxin effect on the PIN polarity. Accordingly, processes requiring auxin-mediated PIN polarity rearrangements, such as vascular tissue development during leaf venation, showed a higher WRKY23 expression and required the WRKY23 activity. Our results provide initial insights into the auxin transcriptional network acting upstream of PIN polarization and, potentially, canalization-mediated plant development. AU - Prat, Tomas AU - Hajny, Jakub AU - Grunewald, Wim AU - Vasileva, Mina K AU - Molnar, Gergely AU - Tejos, Ricardo AU - Schmid, Markus AU - Sauer, Michael AU - Friml, Jirí ID - 449 IS - 1 JF - PLoS Genetics TI - WRKY23 is a component of the transcriptional network mediating auxin feedback on PIN polarity VL - 14 ER - TY - JOUR AB - Intercellular distribution of the plant hormone auxin largely depends on the polar subcellular distribution of the plasma membrane PIN-FORMED (PIN) auxin transporters. PIN polarity switches in response to different developmental and environmental signals have been shown to redirect auxin fluxes mediating certain developmental responses. PIN phosphorylation at different sites and by different kinases is crucial for PIN function. Here we investigate the role of PIN phosphorylation during gravitropic response. Loss- and gain-of-function mutants in PINOID and related kinases but not in D6PK kinase as well as mutations mimicking constitutive dephosphorylated or phosphorylated status of two clusters of predicted phosphorylation sites partially disrupted PIN3 phosphorylation and caused defects in gravitropic bending in roots and hypocotyls. In particular, they impacted PIN3 polarity rearrangements in response to gravity and during feed-back regulation by auxin itself. Thus PIN phosphorylation, besides regulating transport activity and apical-basal targeting, is also important for the rapid polarity switches in response to environmental and endogenous signals. AU - Grones, Peter AU - Abas, Melinda F AU - Hajny, Jakub AU - Jones, Angharad AU - Waidmann, Sascha AU - Kleine Vehn, Jürgen AU - Friml, Jirí ID - 191 IS - 1 JF - Scientific Reports TI - PID/WAG-mediated phosphorylation of the Arabidopsis PIN3 auxin transporter mediates polarity switches during gravitropism VL - 8 ER - TY - JOUR AB - Plant hormones as signalling molecules play an essential role in the control of plant growth and development. Typically, sites of hormonal action are usually distant from the site of biosynthesis thus relying on efficient transport mechanisms. Over the last decades, molecular identification of proteins and protein complexes involved in hormonal transport has started. Advanced screens for genes involved in hormonal transport in combination with transport assays using heterologous systems such as yeast, insect, or tobacco BY2 cells or Xenopus oocytes provided important insights into mechanisms underlying distribution of hormones in plant body and led to identification of principal transporters for each hormone. This review gives a short overview of the mechanisms of hormonal transport and transporters identified in Arabidopsis thaliana. AU - Abualia, Rashed AU - Benková, Eva AU - Lacombe, Benoît ID - 47 JF - Advances in Botanical Research TI - Transporters and mechanisms of hormone transport in arabidopsis VL - 87 ER - TY - JOUR AB - Although much is known about the physiological framework of T cell motility, and numerous rate-limiting molecules have been identified through loss-of-function approaches, an integrated functional concept of T cell motility is lacking. Here, we used in vivo precision morphometry together with analysis of cytoskeletal dynamics in vitro to deconstruct the basic mechanisms of T cell migration within lymphatic organs. We show that the contributions of the integrin LFA-1 and the chemokine receptor CCR7 are complementary rather than positioned in a linear pathway, as they are during leukocyte extravasation from the blood vasculature. Our data demonstrate that CCR7 controls cortical actin flows, whereas integrins mediate substrate friction that is sufficient to drive locomotion in the absence of considerable surface adhesions and plasma membrane flux. AU - Hons, Miroslav AU - Kopf, Aglaja AU - Hauschild, Robert AU - Leithner, Alexander F AU - Gärtner, Florian R AU - Abe, Jun AU - Renkawitz, Jörg AU - Stein, Jens AU - Sixt, Michael K ID - 15 IS - 6 JF - Nature Immunology TI - Chemokines and integrins independently tune actin flow and substrate friction during intranodal migration of T cells VL - 19 ER - TY - JOUR AB - This scientific commentary refers to ‘NEGR1 and FGFR2 cooperatively regulate cortical development and core behaviours related to autism disorders in mice’ by Szczurkowska et al. AU - Contreras, Ximena AU - Hippenmeyer, Simon ID - 28 IS - 9 JF - Brain a journal of neurology TI - Incorrect trafficking route leads to autism VL - 141 ER - TY - JOUR AB - The rapid auxin-triggered growth of the Arabidopsis hypocotyls involves the nuclear TIR1/AFB-Aux/IAA signaling and is accompanied by acidification of the apoplast and cell walls (Fendrych et al., 2016). Here, we describe in detail the method for analysis of the elongation and the TIR1/AFB-Aux/IAA-dependent auxin response in hypocotyl segments as well as the determination of relative values of the cell wall pH. AU - Li, Lanxin AU - Krens, Gabriel AU - Fendrych, Matyas AU - Friml, Jirí ID - 442 IS - 1 JF - Bio-protocol TI - Real-time analysis of auxin response, cell wall pH and elongation in Arabidopsis thaliana Hypocotyls VL - 8 ER -