TY - JOUR
AB - During embryonic development, mechanical forces are essential for cellular rearrangements driving tissue morphogenesis. Here, we show that in the early zebrafish embryo, friction forces are generated at the interface between anterior axial mesoderm (prechordal plate, ppl) progenitors migrating towards the animal pole and neurectoderm progenitors moving in the opposite direction towards the vegetal pole of the embryo. These friction forces lead to global rearrangement of cells within the neurectoderm and determine the position of the neural anlage. Using a combination of experiments and simulations, we show that this process depends on hydrodynamic coupling between neurectoderm and ppl as a result of E-cadherin-mediated adhesion between those tissues. Our data thus establish the emergence of friction forces at the interface between moving tissues as a critical force-generating process shaping the embryo.
AU - Smutny, Michael
AU - Ákos, Zsuzsa
AU - Grigolon, Silvia
AU - Shamipour, Shayan
AU - Ruprecht, Verena
AU - Capek, Daniel
AU - Behrndt, Martin
AU - Papusheva, Ekaterina
AU - Tada, Masazumi
AU - Hof, Björn
AU - Vicsek, Tamás
AU - Salbreux, Guillaume
AU - Heisenberg, Carl-Philipp J
ID - 661
JF - Nature Cell Biology
SN - 14657392
TI - Friction forces position the neural anlage
VL - 19
ER -
TY - CONF
AB - The notion of treewidth of graphs has been exploited for faster algorithms for several problems arising in verification and program analysis. Moreover, various notions of balanced tree decompositions have been used for improved algorithms supporting dynamic updates and analysis of concurrent programs. In this work, we present a tool for constructing tree-decompositions of CFGs obtained from Java methods, which is implemented as an extension to the widely used Soot framework. The experimental results show that our implementation on real-world Java benchmarks is very efficient. Our tool also provides the first implementation for balancing tree-decompositions. In summary, we present the first tool support for exploiting treewidth in the static analysis problems on Java programs.
AU - Chatterjee, Krishnendu
AU - Goharshady, Amir
AU - Pavlogiannis, Andreas
ED - D'Souza, Deepak
ID - 949
SN - 03029743
TI - JTDec: A tool for tree decompositions in soot
VL - 10482
ER -
TY - CONF
AB - We study the problem of developing efficient approaches for proving worst-case bounds of non-deterministic recursive programs. Ranking functions are sound and complete for proving termination and worst-case bounds of non-recursive programs. First, we apply ranking functions to recursion, resulting in measure functions, and show that they provide a sound and complete approach to prove worst-case bounds of non-deterministic recursive programs. Our second contribution is the synthesis of measure functions in non-polynomial forms. We show that non-polynomial measure functions with logarithm and exponentiation can be synthesized through abstraction of logarithmic or exponentiation terms, Farkas’ Lemma, and Handelman’s Theorem using linear programming. While previous methods obtain worst-case polynomial bounds, our approach can synthesize bounds of the form O(n log n) as well as O(nr) where r is not an integer. We present experimental results to demonstrate that our approach can efficiently obtain worst-case bounds of classical recursive algorithms such as Merge-Sort, Closest-Pair, Karatsuba’s algorithm and Strassen’s algorithm.
AU - Chatterjee, Krishnendu
AU - Fu, Hongfei
AU - Goharshady, Amir
ED - Majumdar, Rupak
ED - Kunčak, Viktor
ID - 639
SN - 978-331963389-3
TI - Non-polynomial worst case analysis of recursive programs
VL - 10427
ER -
TY - CONF
AB - With the accelerated development of robot technologies, optimal control becomes one of the central themes of research. In traditional approaches, the controller, by its internal functionality, finds appropriate actions on the basis of the history of sensor values, guided by the goals, intentions, objectives, learning schemes, and so forth. The idea is that the controller controls the world---the body plus its environment---as reliably as possible. This paper focuses on new lines of self-organization for developmental robotics. We apply the recently developed differential extrinsic synaptic plasticity to a muscle-tendon driven arm-shoulder system from the Myorobotics toolkit. In the experiments, we observe a vast variety of self-organized behavior patterns: when left alone, the arm realizes pseudo-random sequences of different poses. By applying physical forces, the system can be entrained into definite motion patterns like wiping a table. Most interestingly, after attaching an object, the controller gets in a functional resonance with the object's internal dynamics, starting to shake spontaneously bottles half-filled with water or sensitively driving an attached pendulum into a circular mode. When attached to the crank of a wheel the neural system independently discovers how to rotate it. In this way, the robot discovers affordances of objects its body is interacting with.
AU - Martius, Georg S
AU - Hostettler, Rafael
AU - Knoll, Alois
AU - Der, Ralf
ID - 8094
SN - 9780262339360
T2 - Proceedings of the Artificial Life Conference 2016
TI - Self-organized control of an tendon driven arm by differential extrinsic plasticity
VL - 28
ER -
TY - JOUR
AB - Hybrid systems represent an important and powerful formalism for modeling real-world applications such as embedded systems. A verification tool like SpaceEx is based on the exploration of a symbolic search space (the region space). As a verification tool, it is typically optimized towards proving the absence of errors. In some settings, e.g., when the verification tool is employed in a feedback-directed design cycle, one would like to have the option to call a version that is optimized towards finding an error trajectory in the region space. A recent approach in this direction is based on guided search. Guided search relies on a cost function that indicates which states are promising to be explored, and preferably explores more promising states first. In this paper, we propose an abstraction-based cost function based on coarse-grained space abstractions for guiding the reachability analysis. For this purpose, a suitable abstraction technique that exploits the flexible granularity of modern reachability analysis algorithms is introduced. The new cost function is an effective extension of pattern database approaches that have been successfully applied in other areas. The approach has been implemented in the SpaceEx model checker. The evaluation shows its practical potential.
AU - Bogomolov, Sergiy
AU - Donzé, Alexandre
AU - Frehse, Goran
AU - Grosu, Radu
AU - Johnson, Taylor
AU - Ladan, Hamed
AU - Podelski, Andreas
AU - Wehrle, Martin
ID - 1705
IS - 4
JF - International Journal on Software Tools for Technology Transfer
TI - Guided search for hybrid systems based on coarse-grained space abstractions
VL - 18
ER -
TY - JOUR
AB - We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.
AU - Kolmogorov, Vladimir
AU - Takhanov, Rustem
ID - 1794
IS - 1
JF - Algorithmica
TI - Inference algorithms for pattern-based CRFs on sequence data
VL - 76
ER -
TY - JOUR
AB - Relational models for contingency tables are generalizations of log-linear models, allowing effects associated with arbitrary subsets of cells in the table, and not necessarily containing the overall effect, that is, a common parameter in every cell. Similarly to log-linear models, relational models can be extended to non-negative distributions, but the extension requires more complex methods. An extended relational model is defined as an algebraic variety, and it turns out to be the closure of the original model with respect to the Bregman divergence. In the extended relational model, the MLE of the cell parameters always exists and is unique, but some of its properties may be different from those of the MLE under log-linear models. The MLE can be computed using a generalized iterative scaling procedure based on Bregman projections.
AU - Klimova, Anna
AU - Rudas, Tamás
ID - 1833
JF - Journal of Multivariate Analysis
TI - On the closure of relational models
VL - 143
ER -
TY - JOUR
AB - We consider random matrices of the form H=W+λV, λ∈ℝ+, where W is a real symmetric or complex Hermitian Wigner matrix of size N and V is a real bounded diagonal random matrix of size N with i.i.d.\ entries that are independent of W. We assume subexponential decay for the matrix entries of W and we choose λ∼1, so that the eigenvalues of W and λV are typically of the same order. Further, we assume that the density of the entries of V is supported on a single interval and is convex near the edges of its support. In this paper we prove that there is λ+∈ℝ+ such that the largest eigenvalues of H are in the limit of large N determined by the order statistics of V for λ>λ+. In particular, the largest eigenvalue of H has a Weibull distribution in the limit N→∞ if λ>λ+. Moreover, for N sufficiently large, we show that the eigenvectors associated to the largest eigenvalues are partially localized for λ>λ+, while they are completely delocalized for λ<λ+. Similar results hold for the lowest eigenvalues.
AU - Lee, Jioon
AU - Schnelli, Kevin
ID - 1881
IS - 1-2
JF - Probability Theory and Related Fields
TI - Extremal eigenvalues and eigenvectors of deformed Wigner matrices
VL - 164
ER -
TY - CONF
AB - Magic: the Gathering is a game about magical combat for any number of players. Formally it is a zero-sum, imperfect information stochastic game that consists of a potentially unbounded number of steps. We consider the problem of deciding if a move is legal in a given single step of Magic. We show that the problem is (a) coNP-complete in general; and (b) in P if either of two small sets of cards are not used. Our lower bound holds even for single-player Magic games. The significant aspects of our results are as follows: First, in most real-life game problems, the task of deciding whether a given move is legal in a single step is trivial, and the computationally hard task is to find the best sequence of legal moves in the presence of multiple players. In contrast, quite uniquely our hardness result holds for single step and with only one-player. Second, we establish efficient algorithms for important special cases of Magic.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
ID - 478
TI - The complexity of deciding legality of a single step of magic: The gathering
VL - 285
ER -
TY - CONF
AB - Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for -approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 480
TI - Perfect-information stochastic games with generalized mean-payoff objectives
VL - 05-08-July-2016
ER -