TY - JOUR AB - Although nuclear envelope (NE) assembly is known to require the GTPase Ran, the membrane fusion machinery involved is uncharacterized. NE assembly involves formation of a reticular network on chromatin, fusion of this network into a closed NE and subsequent expansion. Here we show that p97, an AAA-ATPase previously implicated in fusion of Golgi and transitional endoplasmic reticulum (ER) membranes together with the adaptor p47, has two discrete functions in NE assembly. Formation of a closed NE requires the p97–Ufd1–Npl4 complex, not previously implicated in membrane fusion. Subsequent NE growth involves a p97–p47 complex. This study provides the first insights into the molecular mechanisms and specificity of fusion events involved in NE formation. AU - HETZER, Martin W AU - Meyer, Hemmo H. AU - Walther, Tobias C. AU - Bilbao-Cortes, Daniel AU - Warren, Graham AU - Mattaj, Iain W. ID - 11125 IS - 12 JF - Nature Cell Biology KW - Cell Biology SN - 1465-7392 TI - Distinct AAA-ATPase p97 complexes function in discrete steps of nuclear assembly VL - 3 ER - TY - JOUR AB - We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time 𝑜(𝑛√) per operation. To be precise, the algorithm uses O(n1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and bipartiteness in amortized time O(n1/3 log n) per update, with O(1) worst case time per query. AU - Henzinger, Monika H AU - King, Valerie ID - 11892 IS - 2 JF - SIAM Journal on Computing SN - 0097-5397 TI - Maintaining minimum spanning forests in dynamic graphs VL - 31 ER - TY - CONF AB - Previous studies of the Web graph structure have focused on the graph structure at the level of individual pages. In actuality the Web is a hierarchically nested graph, with domains, hosts and Web sites introducing intermediate levels of affiliation and administrative control. To better understand the growth of the Web we need to understand its macro-structure, in terms of the linkage between Web sites. We approximate this by studying the graph of the linkage between hosts on the Web. This was done based on snapshots of the Web taken by Google in Oct 1999, Aug 2000 and Jun 2001. The connectivity between hosts is represented by a directed graph, with hosts as nodes and weighted edges representing the count of hyperlinks between pages on the corresponding hosts. We demonstrate how such a "hostgraph" can be used to study connectivity properties of hosts and domains over time, and discuss a modified "copy model" to explain observed link weight distributions as a function of subgraph size. We discuss changes in the Web over time in the size and connectivity of Web sites and country domains. We also describe a data mining application of the hostgraph: a related host finding algorithm which achieves a precision of 0.65 at rank 3. AU - Bharat, K. AU - Chang, Bay-Wei AU - Henzinger, Monika H AU - Ruhl, M. ID - 11914 SN - 15504786 T2 - 1st IEEE International Conference on Data Mining TI - Who links to whom: Mining linkage between Web sites ER - TY - GEN AB - A molecular classification method is based on a space filling description of a molecule. The three dimensional body corresponding to the space filling molecular structure is divided into Voronoi regions to provide a basis for efficiently processing local structural information. A Delaunay triangulation provides a basis for systematically processing information relating to the Voronoi regions into shape descriptors in the form of topological elements. Preferably, additional shape and/or property descriptors are included in the classification method. The classification methods generally are used to identify similarities between molecules that can be used as property predictors for a variety of applications. Generally, the property predictions are the basis for selection of compounds for incorporation into efficacy evaluations. AU - Liang, Jie AU - Edelsbrunner, Herbert ID - 3507 TI - Molecular classification for property prediction ER - TY - BOOK AB - The book combines topics in mathematics (geometry and topology), computer science (algorithms), and engineering (mesh generation). The original motivation for these topics was the difficulty faced (both conceptually and in the technical execution) in any attempt to combine elements of combinatorial and of numerical algorithms. Mesh generation is a topic where a meaningful combination of these different approaches to problem solving is inevitable. The book develops methods from both areas that are amenable to combination, and explains recent breakthrough solutions to meshing that fit into this category.The book should be an ideal graduate text for courses on mesh generation. The specific material is selected giving preference to topics that are elementary, attractive, lend themselves to teaching, useful, and interesting. AU - Edelsbrunner, Herbert ID - 3586 SN - 0-521-79309-2 TI - Geometry and Topology for Mesh Generation VL - 7 ER - TY - CONF AU - Krishnendu Chatterjee AU - Dasgupta, Pallab AU - Chakrabarti, Partha P ID - 3447 TI - Weighted quantified computation tree logic ER - TY - JOUR AB - For diffeomorphisms of smooth compact manifolds, we consider the problem of how fast the number of periodic points with period $n$grows as a function of $n$. In many familiar cases (e.g., Anosov systems) the growth is exponential, but arbitrarily fast growth is possible; in fact, the first author has shown that arbitrarily fast growth is topologically (Baire) generic for $C^2$ or smoother diffeomorphisms. In the present work we show that, by contrast, for a measure-theoretic notion of genericity we call ``prevalence'', the growth is not much faster than exponential. Specifically, we show that for each $\delta > 0$, there is a prevalent set of ( $C^{1+\rho}$ or smoother) diffeomorphisms for which the number of period $n$ points is bounded above by $\operatorname{exp}(C n^{1+\delta})$ for some $C$ independent of $n$. We also obtain a related bound on the decay of the hyperbolicity of the periodic points as a function of $n$. The contrast between topologically generic and measure-theoretically generic behavior for the growth of the number of periodic points and the decay of their hyperbolicity shows this to be a subtle and complex phenomenon, reminiscent of KAM theory. AU - Kaloshin, Vadim AU - Hunt, Brian R. ID - 8522 IS - 4 JF - Electronic Research Announcements of the American Mathematical Society KW - General Mathematics SN - 1079-6762 TI - A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms I VL - 7 ER - TY - JOUR AB - We continue the previous article's discussion of bounds, for prevalent diffeomorphisms of smooth compact manifolds, on the growth of the number of periodic points and the decay of their hyperbolicity as a function of their period $n$. In that article we reduced the main results to a problem, for certain families of diffeomorphisms, of bounding the measure of parameter values for which the diffeomorphism has (for a given period $n$) an almost periodic point that is almost nonhyperbolic. We also formulated our results for $1$-dimensional endomorphisms on a compact interval. In this article we describe some of the main techniques involved and outline the rest of the proof. To simplify notation, we concentrate primarily on the $1$-dimensional case. AU - Kaloshin, Vadim AU - Hunt, Brian R. ID - 8521 IS - 5 JF - Electronic Research Announcements of the American Mathematical Society KW - General Mathematics SN - 1079-6762 TI - A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms II VL - 7 ER - TY - JOUR AB - A number α∈R is diophantine if it is not well approximable by rationals, i.e. for some C,ε>0 and any relatively prime p,q∈Z we have |αq−p|>Cq−1−ε. It is well-known and is easy to prove that almost every α in R is diophantine. In this paper we address a noncommutative version of the diophantine properties. Consider a pair A,B∈SO(3) and for each n∈Z+ take all possible words in A, A -1, B, and B - 1 of length n, i.e. for a multiindex I=(i1,i1,…,im,jm) define |I|=∑mk=1(|ik|+|jk|)=n and \( W_n(A,B ) = \{W_{\cal I}(A,B) = A^{i_1} B^{j_1} \dots A^{i_m} B^{j_m}\}_{|{\cal I|}=n \).¶Gamburd—Jakobson—Sarnak [GJS] raised the problem: prove that for Haar almost every pair A,B∈SO(3) the closest distance of words of length n to the identity, i.e. sA,B(n)=min|I|=n∥WI(A,B)−E∥, is bounded from below by an exponential function in n. This is the analog of the diophantine property for elements of SO(3). In this paper we prove that s A,B (n) is bounded from below by an exponential function in n 2. We also exhibit obstructions to a “simple” proof of the exponential estimate in n. AU - Kaloshin, Vadim AU - Rodnianski, I. ID - 8524 IS - 5 JF - Geometric And Functional Analysis SN - 1016-443X TI - Diophantine properties of elements of SO(3) VL - 11 ER - TY - JOUR AB - Epigenetic silenced alleles of the Arabidopsis SUPERMANlocus (the clark kent alleles) are associated with dense hypermethylation at noncanonical cytosines (CpXpG and asymmetric sites, where X = A, T, C, or G). A genetic screen for suppressors of a hypermethylated clark kent mutant identified nine loss-of-function alleles of CHROMOMETHYLASE3(CMT3), a novel cytosine methyltransferase homolog. These cmt3 mutants display a wild-type morphology but exhibit decreased CpXpG methylation of the SUP gene and of other sequences throughout the genome. They also show reactivated expression of endogenous retrotransposon sequences. These results show that a non-CpG DNA methyltransferase is responsible for maintaining epigenetic gene silencing. AU - Lindroth, A. M. AU - Cao, Xiaofeng AU - Jackson, James P. AU - Zilberman, Daniel AU - McCallum, Claire M. AU - Henikoff, Steven AU - Jacobsen, Steven E. ID - 9444 IS - 5524 JF - Science KW - Multidisciplinary SN - 0036-8075 TI - Requirement of CHROMOMETHYLASE3 for maintenance of CpXpG methylation VL - 292 ER - TY - CONF AB - A controller is an environment for a system that achieves a particular control objective by providing inputs to the system without constraining the choices of the system. For synchronous systems, where system and controller make simultaneous and interdependent choices, the notion that a controller must not constrain the choices of the system can be formalized by type systems for composability. In a previous paper, we solved the control problem for static and dynamic types: a static type is a dependency relation between inputs and outputs, and composition is well-typed if it does not introduce cyclic dependencies; a dynamic type is a set of static types, one for each state. Static and dynamic types, however, cannot capture many important digital circuits, such as gated clocks, bidirectional buses, and random-access memory. We therefore introduce more general type systems, so-called dependent and bidirectional types, for modeling these situations, and we solve the corresponding control problems. In a system with a dependent type, the dependencies between inputs and outputs are determined gradually through a game of the system against the controller. In a system with a bidirectional type, also the distinction between inputs and outputs is resolved dynamically by such a game. The game proceeds in several rounds. In each round the system and the controller choose to update some variables dependent on variables that have already been updated. The solution of the control problem for dependent and bidirectional types is based on algorithms for solving these games. AU - De Alfaro, Luca AU - Henzinger, Thomas A AU - Mang, Freddy ID - 4634 SN - 9783540424970 T2 - Proceedings of the 12th International Conference on on Concurrency Theory TI - The control of synchronous systems, Part II VL - 2154 ER - TY - CONF AB - A procedure for the analysis of state spaces is called symbolic if it manipulates not individual states, but sets of states that are represented by constraints. Such a procedure can be used for the analysis of infinite state spaces, provided termination is guaranteed. We present symbolic procedures, and corresponding termination criteria, for the solution of infinite-state games, which occur in the control and modular verification of infinite-state systems. To characterize the termination of symbolic procedures for solving infinite-state games, we classify these game structures into four increasingly restrictive categories: 1 Class 1 consists of infinite-state structures for which all safety and reachability games can be solved. 2 Class 2 consists of infinite-state structures for which all ω-regular games can be solved. 3 Class 3 consists of infinite-state structures for which all nested positive boolean combinations of ω-regular games can be solved. 4 Class 4 consists of infinite-state structures for which all nested boolean combinations of ω-regular games can be solved. We give a structural characterization for each class, using equivalence relations on the state spaces of games which range from game versions of trace equivalence to a game version of bisimilarity. We provide infinite-state examples for all four classes of games from control problems for hybrid systems. We conclude by presenting symbolic algorithms for the synthesis of winning strategies (“controller synthesis”) for infinitestate games with arbitrary ω-regular objectives, and prove termination over all class-2 structures. This settles, in particular, the symbolic controller synthesis problem for rectangular hybrid systems. AU - De Alfaro, Luca AU - Henzinger, Thomas A AU - Majumdar, Ritankar ID - 4633 SN - 9783540424970 T2 - Proceedings of the 12th International Conference on on Concurrency Theory TI - Symbolic algorithms for infinite-state games VL - 2154 ER - TY - CONF AB - Abstract. Dynamic programs, or fixpoint iteration schemes, are useful for solving many problems on state spaces, including model checking on Kripke structures (“verification”), computing shortest paths on weighted graphs (“optimization”), computing the value of games played on game graphs (“control”). For Kripke structures, a rich fixpoint theory is available in the form of the µ-calculus. Yet few connections have been made between different interpretations of fixpoint algorithms. We study the question of when a particular fixpoint iteration scheme ϕ for verifying an ω-regular property Ψ on a Kripke structure can be used also for solving a two-player game on a game graph with winning objective Ψ. We provide a sufficient and necessary criterion for the answer to be affirmative in the form of an extremal-model theorem for games: under a game interpretation, the dynamic program ϕ solves the game with objective Ψ if and only if both (1) under an existential interpretation on Kripke structures, ϕ is equivalent to ∃Ψ, and (2) under a universal interpretation on Kripke structures, ϕ is equivalent to ∀Ψ. In other words, ϕ is correct on all two-player game graphs iff it is correct on all extremal game graphs, where one or the other player has no choice of moves. The theorem generalizes to quantitative interpretations, where it connects two-player games with costs to weighted graphs. While the standard translations from ω-regular properties to the µ-calculus violate (1) or (2), we give a translation that satisfies both conditions. Our construction, therefore, yields fixpoint iteration schemes that can be uniformly applied on Kripke structures, weighted graphs, game graphs, and game graphs with costs, in order to meet or optimize a given ω-regular objective. AU - De Alfaro, Luca AU - Henzinger, Thomas A AU - Majumdar, Ritankar ID - 4636 SN - 076951281X T2 - Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science TI - From verification to control: dynamic programs for omega-regular objectives ER - TY - CONF AB - We show how model checking techniques can be applied to the analysis of connectivity and cost-of-traversal properties of Web sites. AU - De Alfaro, Luca AU - Henzinger, Thomas A AU - Mang, Freddy ID - 4635 SN - 9781581133486 T2 - Proceedings of the 10th international conference on World Wide Web TI - MCWEB: A model-checking tool for web-site debugging ER - TY - CONF AB - We present a compositional trace-based model for probabilistic systems. The behavior of a system with probabilistic choice is a stochastic process, namely, a probability distribution on traces, or “bundle.” Consequently, the semantics of a system with both nondeterministic and probabilistic choice is a set of bundles. The bundles of a composite system can be obtained by combining the bundles of the components in a simple mathematical way. Refinement between systems is bundle containment. We achieve assume-guarantee compositionality for bundle semantics by introducing two scoping mechanisms. The first mechanism, which is standard in compositional modeling, distinguishes inputs from outputs and hidden state. The second mechanism, which arises in probabilistic systems, partitions the state into probabilistically independent regions. AU - De Alfaro, Luca AU - Henzinger, Thomas A AU - Jhala, Ranjit ID - 4632 SN - 9783540424970 T2 - Proceedings of the 12th International Conference on on Concurrency Theory TI - Compositional methods for probabilistic systems VL - 2154 ER - TY - CONF AB - Model checking is a practical tool for automated debugging of embedded software. In model checking, a high-level description of a system is compared against a logical correctness requirement to discover inconsistencies. Since model checking is based on exhaustive state-space exploration and the size of the state space of a design grows exponentially with the size of the description, scalability remains a challenge. We have thus developed techniques for exploiting modular design structure during model checking, and the model checker jMocha (Java MOdel-CHecking Algorithm) is based on this theme. Instead of manipulating unstructured state-transition graphs, it supports the hierarchical modeling framework of reactive modules. jMocha is a growing interactive software environment for specification, simulation and verification, and is intended as a vehicle for the development of new verification algorithms and approaches. It is written in Java and uses native C-code BDD libraries from VIS. jMocha offers: (1) a GUI that looks familiar to Windows/Java users; (2) a simulator that displays traces in a message sequence chart fashion; (3) requirements verification both by symbolic and enumerative model checking; (4) implementation verification by checking trace containment; (5) a proof manager that aids compositional and assume-guarantee reasoning; and (6) SLANG (Scripting LANGuage) for the rapid and structured development of new verification algorithms. jMocha is available publicly at ; it is a successor and extension of the original Mocha tool that was entirely written in C. AU - Alur, Rajeev AU - De Alfaro, Luca AU - Grosu, Radu AU - Henzinger, Thomas A AU - Kang, Myong AU - Kirsch, Christoph AU - Majumdar, Ritankar AU - Mang, Freddy AU - Wang, Bow ID - 4600 SN - 0769510507 T2 - Proceedings of the 23rd International Conference on Software Engineering TI - jMocha: A model-checking tool that exploits design structure ER - TY - JOUR AB - State-space explosion is a fundamental obstacle in the formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reduction and symbolic state-space search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable states. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable states as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first search for the analysis of asynchronous network protocols, and symbolic breadth-first search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy. AU - Alur, Rajeev AU - Brayton, Robert AU - Henzinger, Thomas A AU - Qadeer, Shaz AU - Rajamani, Sriram ID - 4599 IS - 2 JF - Formal Methods in System Design SN - 0925-9856 TI - Partial-order reduction in symbolic state-space exploration VL - 18 ER - TY - CONF AB - Conventional type systems specify interfaces in terms of values and domains. We present a light-weight formalism that captures the temporal aspects of software component interfaces. Specifically, we use an automata-based language to capture both input assumptions about the order in which the methods of a component are called, and output guarantees about the order in which the component calls external methods. The formalism supports automatic compatability checks between interface models, and thus constitutes a type system for component interaction. Unlike traditional uses of automata, our formalism is based on an optimistic approach to composition, and on an alternating approach to design refinement. According to the optimistic approach, two components are compatible if there is some environment that can make them work together. According to the alternating approach, one interface refines another if it has weaker input assumptions, and stronger output guarantees. We show that these notions have game-theoretic foundations that lead to efficient algorithms for checking compatibility and refinement. AU - De Alfaro, Luca AU - Henzinger, Thomas A ID - 4622 SN - 9781581133905 T2 - Proceedings of the 8th European software engineering conference TI - Interface automata ER - TY - CONF AB - We classify component-based models of computation into component models and interface models. A component model specifies for each component howthe component behaves in an arbitrary environment; an interface model specifies for each component what the component expects from the environment. Component models support compositional abstraction, and therefore component-based verification. Interface models support compositional refinement, and therefore componentbased design. Many aspects of interface models, such as compatibility and refinement checking between interfaces, are properly viewed in a gametheoretic setting, where the input and output values of an interface are chosen by different players. AU - De Alfaro, Luca AU - Henzinger, Thomas A ID - 4623 SN - 9783540426738 T2 - Proceedings of the 1st International Workshop on Embedded Software TI - Interface theories for component-based design VL - 2211 ER - TY - CONF AB - This paper presents a concept for integrating the embedded programming methodology Giotto and the object-oriented AOCS Framework to create an environment for the rapid development of distributed software for safety-critical embedded control systems with hard real-time requirements of the kind typically found in aerospace applications. AU - Brown, Timothy AU - Pasetti, Alessandro AU - Pree, Wolfgang AU - Henzinger, Thomas A AU - Kirsch, Christoph ID - 4564 SN - 0780370341 T2 - Proceedings of the 20th Digital Avionics Systems Conference TI - A reusable and platform-independent framework for distributed control systems ER -