TY - CONF
AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m=O(n)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of ϵ in time O(n⋅log(n/ϵ)) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O(n⋅log(|a⋅b|))=O(n⋅log(n⋅W)), when the output is ab, as compared to the previously best known algorithm with running time O(n2⋅log(n⋅W)). Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O(n2⋅m) time and the associated decision problem can be solved in O(n⋅m) time, improving the previous known O(n3⋅m⋅log(n⋅W)) and O(n2⋅m) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O(n⋅logn) time, improving the previous known O(n4⋅log(n⋅W)) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 1607
TI - Faster algorithms for quantitative verification in constant treewidth graphs
VL - 9206
ER -
TY - JOUR
AB - Genomic imprinting, an inherently epigenetic phenomenon defined by parent of origin-dependent gene expression, is observed in mammals and flowering plants. Genome-scale surveys of imprinted expression and the underlying differential epigenetic marks have led to the discovery of hundreds of imprinted plant genes and confirmed DNA and histone methylation as key regulators of plant imprinting. However, the biological roles of the vast majority of imprinted plant genes are unknown, and the evolutionary forces shaping plant imprinting remain rather opaque. Here, we review the mechanisms of plant genomic imprinting and discuss theories of imprinting evolution and biological significance in light of recent findings.
AU - Rodrigues, Jessica A.
AU - ZILBERMAN, Daniel
ID - 9532
IS - 24
JF - Genes and Development
SN - 0890-9369
TI - Evolution and function of genomic imprinting in plants
VL - 29
ER -
TY - JOUR
AB - We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a dense k-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.
AU - Krivelevich, Michael
AU - Kwan, Matthew Alan
AU - Sudakov, Benny
ID - 9575
JF - Electronic Notes in Discrete Mathematics
SN - 1571-0653
TI - Cycles and matchings in randomly perturbed digraphs and hypergraphs
VL - 49
ER -
TY - JOUR
AB - Current strategies of computational crystal plasticity that focus on individual atoms or dislocations are impractical for real-scale, large-strain problems even with today’s computing power. Dislocation-density based approaches are a way forward but a critical issue to address is a realistic description of the interactions between dislocations. In this paper, a new scheme for computational dynamics of dislocation-density functions is proposed, which takes full consideration of the mutual elastic interactions between dislocations based on the Hirth–Lothe formulation. Other features considered include (i) the continuity nature of the movements of dislocation densities, (ii) forest hardening, (iii) generation according to high spatial gradients in dislocation densities, and (iv) annihilation. Numerical implementation by the finite-volume method, which is well suited for flow problems with high gradients, is discussed. Numerical examples performed for a single-crystal aluminum model show typical strength anisotropy behavior comparable to experimental observations. Furthermore, a detailed case study on small-scale crystal plasticity successfully captures a number of key experimental features, including power-law relation between strength and size, low dislocation storage and jerky deformation.
AU - Leung, H.S.
AU - Leung, P.S.S.
AU - Cheng, Bingqing
AU - Ngan, A.H.W.
ID - 9673
JF - International Journal of Plasticity
SN - 0749-6419
TI - A new dislocation-density-function dynamics scheme for computational crystal plasticity by explicit consideration of dislocation elastic interactions
VL - 67
ER -
TY - JOUR
AB - The properties of the interface between solid and melt are key to solidification and melting, as the interfacial free energy introduces a kinetic barrier to phase transitions. This makes solidification happen below the melting temperature, in out-of-equilibrium conditions at which the interfacial free energy is ill defined. Here we draw a connection between the atomistic description of a diffuse solid-liquid interface and its thermodynamic characterization. This framework resolves the ambiguities in defining the solid-liquid interfacial free energy above and below the melting temperature. In addition, we introduce a simulation protocol that allows solid-liquid interfaces to be reversibly created and destroyed at conditions relevant for experiments. We directly evaluate the value of the interfacial free energy away from the melting point for a simple but realistic atomic potential, and find a more complex temperature dependence than the constant positive slope that has been generally assumed based on phenomenological considerations and that has been used to interpret experiments. This methodology could be easily extended to the study of other phase transitions, from condensation to precipitation. Our analysis can help reconcile the textbook picture of classical nucleation theory with the growing body of atomistic studies and mesoscale models of solidification.
AU - Cheng, Bingqing
AU - Tribello, Gareth A.
AU - Ceriotti, Michele
ID - 9688
IS - 18
JF - Physical Review B - Condensed Matter and Materials Physics
SN - 1098-0121
TI - Solid-liquid interfacial free energy out of equilibrium
VL - 92
ER -