TY - JOUR
AB - Background and aims Angiosperms display remarkable diversity in flower colour, implying that transitions between pigmentation phenotypes must have been common. Despite progress in understanding transitions between anthocyanin (blue, purple, pink or red) and unpigmented (white) flowers, little is known about the evolutionary patterns of flower-colour transitions in lineages with both yellow and anthocyanin-pigmented flowers. This study investigates the relative rates of evolutionary transitions between different combinations of yellow- and anthocyanin-pigmentation phenotypes in the tribe Antirrhineae. Methods We surveyed taxonomic literature for data on anthocyanin and yellow floral pigmentation for 369 species across the tribe. We then reconstructed the phylogeny of 169 taxa and used phylogenetic comparative methods to estimate transition rates among pigmentation phenotypes across the phylogeny. Key Results In contrast to previous studies we found a bias towards transitions involving a gain in pigmentation, although transitions to phenotypes with both anthocyanin and yellow taxa are nevertheless extremely rare. Despite the dominance of yellow and anthocyanin-pigmented taxa, transitions between these phenotypes are constrained to move through a white intermediate stage, whereas transitions to double-pigmentation are very rare. The most abundant transitions are between anthocyanin-pigmented and unpigmented flowers, and similarly the most abundant polymorphic taxa were those with anthocyanin-pigmented and unpigmented flowers. Conclusions Our findings show that pigment evolution is limited by the presence of other floral pigments. This interaction between anthocyanin and yellow pigments constrains the breadth of potential floral diversity observed in nature. In particular, they suggest that selection has repeatedly acted to promote the spread of single-pigmented phenotypes across the Antirrhineae phylogeny. Furthermore, the correlation between transition rates and polymorphism suggests that the forces causing and maintaining variance in the short term reflect evolutionary processes on longer time scales.
AU - Ellis, Thomas
AU - Field, David
ID - 1382
IS - 7
JF - Annals of Botany
TI - Repeated gains in yellow and anthocyanin pigmentation in flower colour transitions in the Antirrhineae
VL - 117
ER -
TY - CONF
AB - The continuous evolution of a wide variety of systems, including continous-time Markov chains and linear hybrid automata, can be
described in terms of linear differential equations. In this paper we study the decision problem of whether the solution x(t) of a system of linear differential equations dx/dt = Ax reaches a target halfspace infinitely often. This recurrent reachability problem can
equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function f:R≥0 --> R satisfying a given linear
differential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most 7, then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order 9 (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.
AU - Chonev, Ventsislav K
AU - Ouaknine, Joël
AU - Worrell, James
ID - 1389
T2 - LICS '16
TI - On recurrent reachability for continuous linear dynamical systems
ER -
TY - CONF
AB - The goal of automatic program repair is to identify a set of syntactic changes that can turn a program that is incorrect with respect
to a given specification into a correct one. Existing program repair techniques typically aim to find any program that meets the given specification. Such “best-effort” strategies can end up generating a program that is quite different from the original one. Novel techniques have been proposed to compute syntactically minimal program fixes, but the smallest syntactic fix to a program can still significantly alter the original program’s behaviour. We propose a new approach to program repair based on program distances, which can quantify changes not only to the program syntax but also to the program semantics. We call this the quantitative program repair problem where the “optimal” repair is derived using multiple distances. We implement a solution to the quantitative repair
problem in a prototype tool called Qlose
(Quantitatively close), using the program synthesizer Sketch. We evaluate the effectiveness of different distances in obtaining desirable repairs by evaluating
Qlose on programs taken from educational tools such as CodeHunt and edX.
AU - D'Antoni, Loris
AU - Samanta, Roopsha
AU - Singh, Rishabh
ID - 1390
TI - QLOSE: Program repair with quantitative objectives
VL - 9780
ER -
TY - CONF
AB - We present an extension to the quantifier-free theory of integer arrays which allows us to express counting. The properties expressible in Array Folds Logic (AFL) include statements such as "the first array cell contains the array length," and "the array contains equally many minimal and maximal elements." These properties cannot be expressed in quantified fragments of the theory of arrays, nor in the theory of concatenation. Using reduction to counter machines, we show that the satisfiability problem of AFL is PSPACE-complete, and with a natural restriction the complexity decreases to NP. We also show that adding either universal quantifiers or concatenation leads to undecidability.
AFL contains terms that fold a function over an array. We demonstrate that folding, a well-known concept from functional languages, allows us to concisely summarize loops that count over arrays, which occurs frequently in real-life programs. We provide a tool that can discharge proof obligations in AFL, and we demonstrate on practical examples that our decision procedure can solve a broad range of problems in symbolic testing and program verification.
AU - Daca, Przemyslaw
AU - Henzinger, Thomas A
AU - Kupriyanov, Andrey
ID - 1391
TI - Array folds logic
VL - 9780
ER -
TY - JOUR
AB - The solution space of genome-scale models of cellular metabolism provides a map between physically
viable flux configurations and cellular metabolic phenotypes described, at the most basic level, by the
corresponding growth rates. By sampling the solution space of E. coliʼs metabolic network, we show
that empirical growth rate distributions recently obtained in experiments at single-cell resolution can
be explained in terms of a trade-off between the higher fitness of fast-growing phenotypes and the
higher entropy of slow-growing ones. Based on this, we propose a minimal model for the evolution of
a large bacterial population that captures this trade-off. The scaling relationships observed in
experiments encode, in such frameworks, for the same distance from the maximum achievable growth
rate, the same degree of growth rate maximization, and/or the same rate of phenotypic change. Being
grounded on genome-scale metabolic network reconstructions, these results allow for multiple
implications and extensions in spite of the underlying conceptual simplicity.
AU - De Martino, Daniele
AU - Capuani, Fabrizio
AU - De Martino, Andrea
ID - 1394
IS - 3
JF - Physical Biology
TI - Growth against entropy in bacterial metabolism: the phenotypic trade-off behind empirical growth rate distributions in E. coli
VL - 13
ER -
TY - THES
AB - We study partially observable Markov decision processes (POMDPs) with objectives used in verification and artificial intelligence. The qualitative analysis problem given a POMDP and an objective asks whether there is a strategy (policy) to ensure that the objective is satisfied almost surely (with probability 1), resp. with positive probability (with probability greater than 0). For POMDPs with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards, we consider two types of path constraints: (i) a quantitative limit-average constraint defines the set of paths where the payoff is at least a given threshold L1 = 1. Our main results for qualitative limit-average constraint under almost-sure winning are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative limit-average constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We present a prototype implementation of our EXPTIME algorithm. For POMDPs with w-regular conditions specified as parity objectives, while the qualitative analysis problems are known to be undecidable even for very special case of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. Based on our theoretical algorithms we also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of well-known POMDP examples for robotics applications. For POMDPs with a set of target states and an integer cost associated with every transition, we study the optimization objective that asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely. We show that for general integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double and exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms that extend existing algorithms for POMDPs with finite-horizon objectives. We show experimentally that it performs well in many examples of interest. We study more deeply the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a strategy to ensure that the target set is reached almost surely. While in general the problem EXPTIME-complete, in many practical cases strategies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. We first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. Decentralized POMDPs (DEC-POMDPs) extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. In this work we consider Goal DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the real-time dynamic programming approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. In the end we present a short summary of a few other results related to verification of MDPs and POMDPs.
AU - Chmelik, Martin
ID - 1397
TI - Algorithms for partially observable markov decision processes
ER -
TY - THES
AB - Hybrid zones represent evolutionary laboratories, where recombination brings together alleles in combinations which have not previously been tested by selection. This provides an excellent opportunity to test the effect of molecular variation on fitness, and how this variation is able to spread through populations in a natural context. The snapdragon Antirrhinum majus is polymorphic in the wild for two loci controlling the distribution of yellow and magenta floral pigments. Where the yellow A. m. striatum and the magenta A. m. pseudomajus meet along a valley in the Spanish Pyrenees they form a stable hybrid zone Alleles at these loci recombine to give striking transgressive variation for flower colour. The sharp transition in phenotype over ~1km implies strong selection maintaining the hybrid zone. An indirect assay of pollinator visitation in the field found that pollinators forage in a positive-frequency dependent manner on Antirrhinum, matching previous data on fruit set. Experimental arrays and paternity analysis of wild-pollinated seeds demonstrated assortative mating for pigmentation alleles, and that pollinator behaviour alone is sufficient to explain this pattern. Selection by pollinators should be sufficiently strong to maintain the hybrid zone, although other mechanisms may be at work. At a broader scale I examined evolutionary transitions between yellow and anthocyanin pigmentation in the tribe Antirrhinae, and found that selection has acted strate that pollinators are a major determinant of reproductive success and mating patterns in wild Antirrhinum.
AU - Ellis, Thomas
ID - 1398
TI - The role of pollinator-mediated selection in the maintenance of a flower color polymorphism in an Antirrhinum majus hybrid zone
ER -
TY - JOUR
AB - The concept of well group in a special but important case captures homological properties of the zero set of a continuous map (Formula presented.) on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within (Formula presented.) distance r from f for a given (Formula presented.). The main drawback of the approach is that the computability of well groups was shown only when (Formula presented.) or (Formula presented.). Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of (Formula presented.) by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and (Formula presented.), our approximation of the (Formula presented.)th well group is exact. For the second part, we find examples of maps (Formula presented.) with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status.
AU - Franek, Peter
AU - Krcál, Marek
ID - 1408
IS - 1
JF - Discrete & Computational Geometry
TI - On computability and triviality of well groups
VL - 56
ER -
TY - JOUR
AU - Abbott, Richard
AU - Barton, Nicholas H
AU - Good, Jeffrey
ID - 1409
IS - 11
JF - Molecular Ecology
TI - Genomics of hybridization and its evolutionary consequences
VL - 25
ER -
TY - JOUR
AB - The pollen grains arise after meiosis of pollen mother cells within the anthers. A series of complex structural changes follows, generating mature pollen grains capable of performing the double fertilization of the female megasporophyte. Several signaling molecules, including hormones and lipids, have been involved in the regulation and appropriate control of pollen development. Phosphatidylinositol 4-phophate 5-kinases (PIP5K), which catalyze the biosynthesis of the phosphoinositide PtdIns(4,5)P2, are important for tip polar growth of root hairs and pollen tubes, embryo development, vegetative plant growth, and responses to the environment. Here, we report a role of PIP5Ks during microgametogenesis. PIP5K1 and PIP5K2 are expressed during early stages of pollen development and their transcriptional activity respond to auxin in pollen grains. Early male gametophytic lethality to certain grade was observed in both pip5k1-/- and pip5k2-/- single mutants. The number of pip5k mutant alleles is directly related to the frequency of aborted pollen grains suggesting the two genes are involved in the same function. Indeed PIP5K1 and PIP5K2 are functionally redundant since homozygous double mutants did not render viable pollen grains. The loss of function of PIP5K1 and PIP5K2results in defects in vacuole morphology in pollen at the later stages and epidermal root cells. Our results show that PIP5K1, PIP5K2 and phosphoinositide signaling are important cues for early developmental stages and vacuole formation during microgametogenesis.
AU - Ugalde, José
AU - Rodríguez Furlán, Cecilia
AU - De Rycke, Riet
AU - Norambuena, Lorena
AU - Friml, Jirí
AU - León, Gabriel
AU - Tejos, Ricardo
ID - 1410
JF - Plant Science
TI - Phosphatidylinositol 4-phosphate 5-kinases 1 and 2 are involved in the regulation of vacuole morphology during Arabidopsis thaliana pollen development
VL - 250
ER -
TY - JOUR
AB - We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov.
AU - Matoušek, Jiří
AU - Sedgwick, Eric
AU - Tancer, Martin
AU - Wagner, Uli
ID - 1411
IS - 1
JF - Israel Journal of Mathematics
TI - Untangling two systems of noncrossing curves
VL - 212
ER -
TY - JOUR
AB - Combining high-resolution level set surface tracking with lower resolution physics is an inexpensive method for achieving highly detailed liquid animations. Unfortunately, the inherent resolution mismatch introduces several types of disturbing visual artifacts. We identify the primary sources of these artifacts and present simple, efficient, and practical solutions to address them. First, we propose an unconditionally stable filtering method that selectively removes sub-grid surface artifacts not seen by the fluid physics, while preserving fine detail in dynamic splashing regions. It provides comparable results to recent error-correction techniques at lower cost, without substepping, and with better scaling behavior. Second, we show how a modified narrow-band scheme can ensure accurate free surface boundary conditions in the presence of large resolution mismatches. Our scheme preserves the efficiency of the narrow-band methodology, while eliminating objectionable stairstep artifacts observed in prior work. Third, we demonstrate that the use of linear interpolation of velocity during advection of the high-resolution level set surface is responsible for visible grid-aligned kinks; we therefore advocate higher-order velocity interpolation, and show that it dramatically reduces this artifact. While these three contributions are orthogonal, our results demonstrate that taken together they efficiently address the dominant sources of visual artifacts arising with high-resolution embedded liquid surfaces; the proposed approach offers improved visual quality, a straightforward implementation, and substantially greater scalability than competing methods.
AU - Goldade, Ryan
AU - Batty, Christopher
AU - Wojtan, Christopher J
ID - 1412
IS - 2
JF - Computer Graphics Forum
TI - A practical method for high-resolution embedded liquid surfaces
VL - 35
ER -
TY - JOUR
AB - This paper generalizes the well-known Diffusion Curves Images (DCI), which are composed of a set of Bezier curves with colors specified on either side. These colors are diffused as Laplace functions over the image domain, which results in smooth color gradients interrupted by the Bezier curves. Our new formulation allows for more color control away from the boundary, providing a similar expressive power as recent Bilaplace image models without introducing associated issues and computational costs. The new model is based on a special Laplace function blending and a new edge blur formulation. We demonstrate that given some user-defined boundary curves over an input raster image, fitting colors and edge blur from the image to the new model and subsequent editing and animation is equally convenient as with DCIs. Numerous examples and comparisons to DCIs are presented.
AU - Jeschke, Stefan
ID - 1413
IS - 2
JF - Computer Graphics Forum
TI - Generalized diffusion curves: An improved vector representation for smooth-shaded images
VL - 35
ER -
TY - JOUR
AB - In this paper, we present a method to model hyperelasticity that is well suited for representing the nonlinearity of real-world objects, as well as for estimating it from deformation examples. Previous approaches suffer several limitations, such as lack of integrability of elastic forces, failure to enforce energy convexity, lack of robustness of parameter estimation, or difficulty to model cross-modal effects. Our method avoids these problems by relying on a general energy-based definition of elastic properties. The accuracy of the resulting elastic model is maximized by defining an additive model of separable energy terms, which allow progressive parameter estimation. In addition, our method supports efficient modeling of extreme nonlinearities thanks to energy-limiting constraints. We combine our energy-based model with an optimization method to estimate model parameters from force-deformation examples, and we show successful modeling of diverse deformable objects, including cloth, human finger skin, and internal human anatomy in a medical imaging application.
AU - Miguel Villalba, Eder
AU - Miraut, David
AU - Otaduy, Miguel
ID - 1414
IS - 2
JF - Computer Graphics Forum
TI - Modeling and estimation of energy-based hyperelastic objects
VL - 35
ER -
TY - JOUR
AB - The Fluid Implicit Particle method (FLIP) for liquid simulations uses particles to reduce numerical dissipation and provide important visual cues for events like complex splashes and small-scale features near the liquid surface. Unfortunately, FLIP simulations can be computationally expensive, because they require a dense sampling of particles to fill the entire liquid volume. Furthermore, the vast majority of these FLIP particles contribute nothing to the fluid's visual appearance, especially for larger volumes of liquid. We present a method that only uses FLIP particles within a narrow band of the liquid surface, while efficiently representing the remaining inner volume on a regular grid. We show that a naïve realization of this idea introduces unstable and uncontrollable energy fluctuations, and we propose a novel coupling scheme between FLIP particles and regular grid which overcomes this problem. Our method drastically reduces the particle count and simulation times while yielding results that are nearly indistinguishable from regular FLIP simulations. Our approach is easy to integrate into any existing FLIP implementation.
AU - Ferstl, Florian
AU - Ando, Ryoichi
AU - Wojtan, Christopher J
AU - Westermann, Rüdiger
AU - Thuerey, Nils
ID - 1415
IS - 2
JF - Computer Graphics Forum
TI - Narrow band FLIP for liquid simulations
VL - 35
ER -
TY - JOUR
AB - Anisotropic dipole-dipole interactions between ultracold dipolar fermions break the symmetry of the Fermi surface and thereby deform it. Here we demonstrate that such a Fermi surface deformation induces a topological phase transition - the so-called Lifshitz transition - in the regime accessible to present-day experiments. We describe the impact of the Lifshitz transition on observable quantities such as the Fermi surface topology, the density-density correlation function, and the excitation spectrum of the system. The Lifshitz transition in ultracold atoms can be controlled by tuning the dipole orientation and, in contrast to the transition studied in crystalline solids, is completely interaction driven.
AU - Van Loon, Erik
AU - Katsnelson, Mikhail
AU - Chomaz, Lauriane
AU - Lemeshko, Mikhail
ID - 1416
IS - 19
JF - Physical Review B - Condensed Matter and Materials Physics
TI - Interaction-driven Lifshitz transition with dipolar fermions in optical lattices
VL - 93
ER -
TY - JOUR
AB - Plant development mediated by the phytohormone auxin depends on tightly controlled cellular auxin levels at its target tissue that are largely established by intercellular and intracellular auxin transport mediated by PIN auxin transporters. Among the eight members of the Arabidopsis PIN family, PIN6 is the least characterized candidate. In this study we generated functional, fluorescent protein-tagged PIN6 proteins and performed comprehensive analysis of their subcellular localization and also performed a detailed functional characterization of PIN6 and its developmental roles. The localization study of PIN6 revealed a dual localization at the plasma membrane (PM) and endoplasmic reticulum (ER). Transport and metabolic profiling assays in cultured cells and Arabidopsis strongly suggest that PIN6 mediates both auxin transport across the PM and intracellular auxin homeostasis, including the regulation of free auxin and auxin conjugates levels. As evidenced by the loss- and gain-of-function analysis, the complex function of PIN6 in auxin transport and homeostasis is required for auxin distribution during lateral and adventitious root organogenesis and for progression of these developmental processes. These results illustrate a unique position of PIN6 within the family of PIN auxin transporters and further add complexity to the developmentally crucial process of auxin transport.
AU - Simon, Sibu
AU - Skůpa, Petr
AU - Viaene, Tom
AU - Zwiewka, Marta
AU - Tejos, Ricardo
AU - Klíma, Petr
AU - Čarná, Mária
AU - Rolčík, Jakub
AU - De Rycke, Riet
AU - Moreno, Ignacio
AU - Dobrev, Petre
AU - Orellana, Ariel
AU - Zažímalová, Eva
AU - Friml, Jirí
ID - 1417
IS - 1
JF - New Phytologist
TI - PIN6 auxin transporter at endoplasmic reticulum and plasma membrane mediates auxin homeostasis and organogenesis in Arabidopsis
VL - 211
ER -
TY - JOUR
AB - We study the superconducting phase of the Hubbard model using the Gutzwiller variational wave function (GWF) and the recently proposed diagrammatic expansion technique (DE-GWF). The DE-GWF method works on the level of the full GWF and in the thermodynamic limit. Here, we consider a finite-size system to study the accuracy of the results as a function of the system size (which is practically unrestricted). We show that the finite-size scaling used, e.g. in the variational Monte Carlo method can lead to significant, uncontrolled errors. The presented research is the first step towards applying the DE-GWF method in studies of inhomogeneous situations, including systems with impurities, defects, inhomogeneous phases, or disorder.
AU - Tomski, Andrzej
AU - Kaczmarczyk, Jan
ID - 1419
IS - 17
JF - Journal of Physics: Condensed Matter
TI - Gutzwiller wave function for finite systems: Superconductivity in the Hubbard model
VL - 28
ER -
TY - JOUR
AB - Selection, mutation, and random drift affect the dynamics of allele frequencies and consequently of quantitative traits. While the macroscopic dynamics of quantitative traits can be measured, the underlying allele frequencies are typically unobserved. Can we understand how the macroscopic observables evolve without following these microscopic processes? This problem has been studied previously by analogy with statistical mechanics: the allele frequency distribution at each time point is approximated by the stationary form, which maximizes entropy. We explore the limitations of this method when mutation is small (4Nμ < 1) so that populations are typically close to fixation, and we extend the theory in this regime to account for changes in mutation strength. We consider a single diallelic locus either under directional selection or with overdominance and then generalize to multiple unlinked biallelic loci with unequal effects. We find that the maximum-entropy approximation is remarkably accurate, even when mutation and selection change rapidly.
AU - Bod'ová, Katarína
AU - Tkacik, Gasper
AU - Barton, Nicholas H
ID - 1420
IS - 4
JF - Genetics
TI - A general approximation for the dynamics of quantitative traits
VL - 202
ER -
TY - CONF
AB - Hybridization methods enable the analysis of hybrid automata with complex, nonlinear dynamics through a sound abstraction process. Complex dynamics are converted to simpler ones with added noise, and then analysis is done using a reachability method for the simpler dynamics. Several such recent approaches advocate that only "dynamic" hybridization techniquesi.e., those where the dynamics are abstracted on-The-fly during a reachability computation are effective. In this paper, we demonstrate this is not the case, and create static hybridization methods that are more scalable than earlier approaches. The main insight in our approach is that quick, numeric simulations can be used to guide the process, eliminating the need for an exponential number of hybridization domains. Transitions between domains are generally timetriggered, avoiding accumulated error from geometric intersections. We enhance our static technique by combining time-Triggered transitions with occasional space-Triggered transitions, and demonstrate the benefits of the combined approach in what we call mixed-Triggered hybridization. Finally, error modes are inserted to confirm that the reachable states stay within the hybridized regions. The developed techniques can scale to higher dimensions than previous static approaches, while enabling the parallelization of the main performance bottleneck for many dynamic hybridization approaches: The nonlinear optimization required for sound dynamics abstraction. We implement our method as a model transformation pass in the HYST tool, and perform reachability analysis and evaluation using an unmodified version of SpaceEx on nonlinear models with up to six dimensions.
AU - Bak, Stanley
AU - Bogomolov, Sergiy
AU - Henzinger, Thomas A
AU - Johnson, Taylor
AU - Prakash, Pradyot
ID - 1421
TI - Scalable static hybridization methods for analysis of nonlinear systems
ER -