@article{661,
abstract = {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.},
author = {Smutny, Michael and Ákos, Zsuzsa and Grigolon, Silvia and Shamipour, Shayan and Ruprecht, Verena and Capek, Daniel and Behrndt, Martin and Papusheva, Ekaterina and Tada, Masazumi and Hof, Björn and Vicsek, Tamás and Salbreux, Guillaume and Heisenberg, Carl-Philipp J},
issn = {14657392},
journal = {Nature Cell Biology},
pages = {306 -- 317},
publisher = {Nature Publishing Group},
title = {{Friction forces position the neural anlage}},
doi = {10.1038/ncb3492},
volume = {19},
year = {2017},
}
@inproceedings{949,
abstract = {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.},
author = {Chatterjee, Krishnendu and Goharshady, Amir and Pavlogiannis, Andreas},
editor = {D'Souza, Deepak},
issn = {03029743},
location = {Pune, India},
pages = {59 -- 66},
publisher = {Springer},
title = {{JTDec: A tool for tree decompositions in soot}},
doi = {10.1007/978-3-319-68167-2_4},
volume = {10482},
year = {2017},
}
@inproceedings{639,
abstract = {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.},
author = {Chatterjee, Krishnendu and Fu, Hongfei and Goharshady, Amir},
editor = {Majumdar, Rupak and Kunčak, Viktor},
isbn = {978-331963389-3},
location = {Heidelberg, Germany},
pages = {41 -- 63},
publisher = {Springer},
title = {{Non-polynomial worst case analysis of recursive programs}},
doi = {10.1007/978-3-319-63390-9_3},
volume = {10427},
year = {2017},
}
@inproceedings{8094,
abstract = {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.},
author = {Martius, Georg S and Hostettler, Rafael and Knoll, Alois and Der, Ralf},
booktitle = {Proceedings of the Artificial Life Conference 2016},
isbn = {9780262339360},
location = {Cancun, Mexico},
pages = {142--143},
publisher = {MIT Press},
title = {{Self-organized control of an tendon driven arm by differential extrinsic plasticity}},
doi = {10.7551/978-0-262-33936-0-ch029},
volume = {28},
year = {2016},
}
@article{1705,
abstract = {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.},
author = {Bogomolov, Sergiy and Donzé, Alexandre and Frehse, Goran and Grosu, Radu and Johnson, Taylor and Ladan, Hamed and Podelski, Andreas and Wehrle, Martin},
journal = {International Journal on Software Tools for Technology Transfer},
number = {4},
pages = {449 -- 467},
publisher = {Springer},
title = {{Guided search for hybrid systems based on coarse-grained space abstractions}},
doi = {10.1007/s10009-015-0393-y},
volume = {18},
year = {2016},
}
@article{1794,
abstract = {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.},
author = {Kolmogorov, Vladimir and Takhanov, Rustem},
journal = {Algorithmica},
number = {1},
pages = {17 -- 46},
publisher = {Springer},
title = {{Inference algorithms for pattern-based CRFs on sequence data}},
doi = {10.1007/s00453-015-0017-7},
volume = {76},
year = {2016},
}
@article{1833,
abstract = {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. },
author = {Klimova, Anna and Rudas, Tamás},
journal = {Journal of Multivariate Analysis},
pages = {440 -- 452},
publisher = {Elsevier},
title = {{On the closure of relational models}},
doi = {10.1016/j.jmva.2015.10.005},
volume = {143},
year = {2016},
}
@article{1881,
abstract = {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. },
author = {Lee, Jioon and Schnelli, Kevin},
journal = {Probability Theory and Related Fields},
number = {1-2},
pages = {165 -- 241},
publisher = {Springer},
title = {{Extremal eigenvalues and eigenvectors of deformed Wigner matrices}},
doi = {10.1007/s00440-014-0610-8},
volume = {164},
year = {2016},
}
@inproceedings{478,
abstract = {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.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus},
location = {The Hague, Netherlands},
pages = {1432 -- 1439},
publisher = {IOS Press},
title = {{The complexity of deciding legality of a single step of magic: The gathering}},
doi = {10.3233/978-1-61499-672-9-1432},
volume = {285},
year = {2016},
}
@inproceedings{480,
abstract = {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.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
location = {New York, NY, USA},
pages = {247 -- 256},
publisher = {IEEE},
title = {{Perfect-information stochastic games with generalized mean-payoff objectives}},
doi = {10.1145/2933575.2934513},
volume = {05-08-July-2016},
year = {2016},
}