TY - CONF
AB - Depth-bounded processes form the most expressive known fragment of the π-calculus for which interesting verification problems are still decidable. In this paper we develop an adequate domain of limits for the well-structured transition systems that are induced by depth-bounded processes. An immediate consequence of our result is that there exists a forward algorithm that decides the covering problem for this class. Unlike backward algorithms, the forward algorithm terminates even if the depth of the process is not known a priori. More importantly, our result suggests a whole spectrum of forward algorithms that enable the effective verification of a large class of mobile systems.
AU - Wies, Thomas
AU - Zufferey, Damien
AU - Henzinger, Thomas A
ED - Ong, Luke
ID - 4361
TI - Forward analysis of depth-bounded processes
VL - 6014
ER -
TY - CONF
AB - In this paper we propose a novel technique for constructing timed automata from properties expressed in the logic mtl, under bounded-variability assumptions. We handle full mtl and include all future operators. Our construction is based on separation of the continuous time monitoring of the input sequence and discrete predictions regarding the future. The separation of the continuous from the discrete allows us to determinize our automata in an exponential construction that does not increase the number of clocks. This leads to a doubly exponential construction from mtl to deterministic timed automata, compared with triply exponential using existing approaches. We offer an alternative to the existing approach to linear real-time model checking, which has never been implemented. It further offers a unified framework for model checking, runtime monitoring, and synthesis, in an approach that can reuse tools, implementations, and insights from the discrete setting.
AU - Nickovic, Dejan
AU - Piterman, Nir
ED - Henzinger, Thomas A.
ED - Chatterjee, Krishnendu
ID - 4369
TI - From MTL to deterministic timed automata
VL - 6246
ER -
TY - CONF
AB - Techniques such as verification condition generation, predicate abstraction, and expressive type systems reduce software verification to proving formulas in expressive logics. Programs and their specifications often make use of data structures such as sets, multisets, algebraic data types, or graphs. Consequently, formulas generated from verification also involve such data structures. To automate the proofs of such formulas we propose a logic (a “calculus”) of such data structures. We build the calculus by starting from decidable logics of individual data structures, and connecting them through functions and sets, in ways that go beyond the frameworks such as Nelson-Oppen. The result are new decidable logics that can simultaneously specify properties of different kinds of data structures and overcome the limitations of the individual logics. Several of our decidable logics include abstraction functions that map a data structure into its more abstract view (a tree into a multiset, a multiset into a set), into a numerical quantity (the size or the height), or into the truth value of a candidate data structure invariant (sortedness, or the heap property). For algebraic data types, we identify an asymptotic many-to-one condition on the abstraction function that guarantees the existence of a decision procedure. In addition to the combination based on abstraction functions, we can combine multiple data structure theories if they all reduce to the same data structure logic. As an instance of this approach, we describe a decidable logic whose formulas are propositional combinations of formulas in: weak monadic second-order logic of two successors, two-variable logic with counting, multiset algebra with Presburger arithmetic, the Bernays-Schönfinkel-Ramsey class of first-order logic, and the logic of algebraic data types with the set content function. The subformulas in this combination can share common variables that refer to sets of objects along with the common set algebra operations. Such sound and complete combination is possible because the relations on sets definable in the component logics are all expressible in Boolean Algebra with Presburger Arithmetic. Presburger arithmetic and its new extensions play an important role in our decidability results. In several cases, when we combine logics that belong to NP, we can prove the satisfiability for the combined logic is still in NP.
AU - Kuncak, Viktor
AU - Piskac, Ruzica
AU - Suter, Philippe
AU - Wies, Thomas
ED - Barthe, Gilles
ED - Hermenegildo, Manuel
ID - 4378
TI - Building a calculus of data structures
VL - 5944
ER -
TY - JOUR
AB - The formal specification component of verification can be exported to simulation through the idea of property checkers. The essence of this approach is the automatic construction of an observer from the specification in the form of a program that can be interfaced with a simulator and alert the user if the property is violated by a simulation trace. Although not complete, this lighter approach to formal verification has been effectively used in software and digital hardware to detect errors. Recently, the idea of property checkers has been extended to analog and mixed-signal systems.
In this paper, we apply the property-based checking methodology to an industrial and realistic example of a DDR2 memory interface. The properties describing the DDR2 analog behavior are expressed in the formal specification language stl/psl in form of assertions. The simulation traces generated from an actual DDR2 interface design are checked with respect to the stl/psl assertions using the amt tool. The focus of this paper is on the translation of the official (informal and descriptive) specification of two non-trivial DDR2 properties into stl/psl assertions. We study both the benefits and the current limits of such approach.
AU - Jones, Kevin D
AU - Konrad,Victor
AU - Dejan Nickovic
ID - 4379
IS - 2
JF - Formal Methods in System Design
TI - Analog property checkers: a DDR2 case study
VL - 36
ER -
TY - CONF
AB - Cloud computing is an emerging paradigm aimed to offer users pay-per-use computing resources, while leaving the burden of managing the computing infrastructure to the cloud provider. We present a new programming and pricing model that gives the cloud user the flexibility of trading execution speed and price on a per-job basis. We discuss the scheduling and resource management challenges for the cloud provider that arise in the implementation of this model. We argue that techniques from real-time and embedded software can be useful in this context.
AU - Henzinger, Thomas A
AU - Tomar, Anmol
AU - Singh, Vasu
AU - Wies, Thomas
AU - Zufferey, Damien
ID - 4380
TI - A marketplace for cloud resources
ER -
TY - CONF
AB - Cloud computing aims to give users virtually unlimited pay-per-use computing resources without the burden of managing the underlying infrastructure. We claim that, in order to realize the full potential of cloud computing, the user must be presented with a pricing model that offers flexibility at the requirements level, such as a choice between different degrees of execution speed and the cloud provider must be presented with a programming model that offers flexibility at the execution level, such as a choice between different scheduling policies. In such a flexible framework, with each job, the user purchases a virtual computer with the desired speed and cost characteristics, and the cloud provider can optimize the utilization of resources across a stream of jobs from different users. We designed a flexible framework to test our hypothesis, which is called FlexPRICE (Flexible Provisioning of Resources in a Cloud Environment) and works as follows. A user presents a job to the cloud. The cloud finds different schedules to execute the job and presents a set of quotes to the user in terms of price and duration for the execution. The user then chooses a particular quote and the cloud is obliged to execute the job according to the chosen quote. FlexPRICE thus hides the complexity of the actual scheduling decisions from the user, but still provides enough flexibility to meet the users actual demands. We implemented FlexPRICE in a simulator called PRICES that allows us to experiment with our framework. We observe that FlexPRICE provides a wide range of execution options-from fast and expensive to slow and cheap-- for the whole spectrum of data-intensive and computation-intensive jobs. We also observe that the set of quotes computed by FlexPRICE do not vary as the number of simultaneous jobs increases.
AU - Henzinger, Thomas A
AU - Tomar, Anmol
AU - Singh, Vasu
AU - Wies, Thomas
AU - Zufferey, Damien
ID - 4381
TI - FlexPRICE: Flexible provisioning of resources in a cloud environment
ER -
TY - CONF
AB - Transactional memory (TM) has shown potential to simplify the task of writing concurrent programs. Inspired by classical work on databases, formal definitions of the semantics of TM executions have been proposed. Many of these definitions assumed that accesses to shared data are solely performed through transactions. In practice, due to legacy code and concurrency libraries, transactions in a TM have to share data with non-transactional operations. The semantics of such interaction, while widely discussed by practitioners, lacks a clear formal specification. Those interactions can vary, sometimes in subtle ways, between TM implementations and underlying memory models. We propose a correctness condition for TMs, parametrized opacity, to formally capture the now folklore notion of strong atomicity by stipulating the two following intuitive requirements: first, every transaction appears as if it is executed instantaneously with respect to other transactions and non-transactional operations, and second, non-transactional operations conform to the given underlying memory model. We investigate the inherent cost of implementing parametrized opacity. We first prove that parametrized opacity requires either instrumenting non-transactional operations (for most memory models) or writing to memory by transactions using potentially expensive read-modify-write instructions (such as compare-and-swap). Then, we show that for a class of practical relaxed memory models, parametrized opacity can indeed be implemented with constant-time instrumentation of non-transactional writes and no instrumentation of non-transactional reads. We show that, in practice, parametrizing the notion of correctness allows developing more efficient TM implementations.
AU - Guerraoui, Rachid
AU - Henzinger, Thomas A
AU - Kapalka, Michal
AU - Singh, Vasu
ID - 4382
TI - Transactions in the jungle
ER -
TY - CONF
AB - GIST is a tool that (a) solves the qualitative analysis problem of turn-based probabilistic games with ω-regular objectives; and (b) synthesizes reasonable environment assumptions for synthesis of unrealizable specifications. Our tool provides the first and efficient implementations of several reduction-based techniques to solve turn-based probabilistic games, and uses the analysis of turn-based probabilistic games for synthesizing environment assumptions for unrealizable specifications.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Jobstmann, Barbara
AU - Radhakrishna, Arjun
ID - 4388
TI - GIST: A solver for probabilistic games
VL - 6174
ER -
TY - CONF
AB - Digital components play a central role in the design of complex embedded systems. These components are interconnected with other, possibly analog, devices and the physical environment. This environment cannot be entirely captured and can provide inaccurate input data to the component. It is thus important for digital components to have a robust behavior, i.e. the presence of a small change in the input sequences should not result in a drastic change in the output sequences. In this paper, we study a notion of robustness for sequential circuits. However, since sequential circuits may have parts that are naturally discontinuous (e.g., digital controllers with switching behavior), we need a flexible framework that accommodates this fact and leaves discontinuous parts of the circuit out from the robustness analysis. As a consequence, we consider sequential circuits that have their input variables partitioned into two disjoint sets: control and disturbance variables. Our contributions are (1) a definition of robustness for sequential circuits as a form of continuity with respect to disturbance variables, (2) the characterization of the exact class of sequential circuits that are robust according to our definition, (3) an algorithm to decide whether a sequential circuit is robust or not.
AU - Doyen, Laurent
AU - Henzinger, Thomas A
AU - Legay, Axel
AU - Nickovic, Dejan
ID - 4389
TI - Robustness of sequential circuits
ER -
TY - CONF
AB - Concurrent data structures with fine-grained synchronization are notoriously difficult to implement correctly. The difficulty of reasoning about these implementations does not stem from the number of variables or the program size, but rather from the large number of possible interleavings. These implementations are therefore prime candidates for model checking. We introduce an algorithm for verifying linearizability of singly-linked heap-based concurrent data structures. We consider a model consisting of an unbounded heap where each vertex stores an element from an unbounded data domain, with a restricted set of operations for testing and updating pointers and data elements. Our main result is that linearizability is decidable for programs that invoke a fixed number of methods, possibly in parallel. This decidable fragment covers many of the common implementation techniques — fine-grained locking, lazy synchronization, and lock-free synchronization. We also show how the technique can be used to verify optimistic implementations with the help of programmer annotations. We developed a verification tool CoLT and evaluated it on a representative sample of Java implementations of the concurrent set data structure. The tool verified linearizability of a number of implementations, found a known error in a lock-free implementation and proved that the corrected version is linearizable.
AU - Cerny, Pavol
AU - Radhakrishna, Arjun
AU - Zufferey, Damien
AU - Chaudhuri, Swarat
AU - Alur, Rajeev
ID - 4390
TI - Model checking of linearizability of concurrent list implementations
VL - 6174
ER -
TY - CONF
AB - Boolean notions of correctness are formalized by preorders on systems. Quantitative measures of correctness can be formalized by real-valued distance functions between systems, where the distance between implementation and specification provides a measure of “fit” or “desirability.” We extend the simulation preorder to the quantitative setting, by making each player of a simulation game pay a certain price for her choices. We use the resulting games with quantitative objectives to define three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the implementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. We consider these distances for safety as well as liveness specifications. The distances can be computed in polynomial time for safety specifications, and for liveness specifications given by weak fairness constraints. We show that the distance functions satisfy the triangle inequality, that the distance between two systems does not increase under parallel composition with a third system, and that the distance between two systems can be bounded from above and below by distances between abstractions of the two systems. These properties suggest that our simulation distances provide an appropriate basis for a quantitative theory of discrete systems. We also demonstrate how the robustness distance can be used to measure how many transmission errors are tolerated by error correcting codes.
AU - Cerny, Pavol
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
ID - 4393
TI - Simulation distances
VL - 6269
ER -
TY - CONF
AB - Shape analysis is a promising technique to prove program properties about recursive data structures. The challenge is to automatically determine the data-structure type, and to supply the shape analysis with the necessary information about the data structure. We present a stepwise approach to the selection of instrumentation predicates for a TVLA-based shape analysis, which takes us a step closer towards the fully automatic verification of data structures. The approach uses two techniques to guide the refinement of shape abstractions: (1) during program exploration, an explicit heap analysis collects sample instances of the heap structures, which are used to identify the data structures that are manipulated by the program; and (2) during abstraction refinement along an infeasible error path, we consider different possible heap abstractions and choose the coarsest one that eliminates the infeasible path. We have implemented this combined approach for automatic shape refinement as an extension of the software model checker BLAST. Example programs from a data-structure library that manipulate doubly-linked lists and trees were successfully verified by our tool.
AU - Beyer, Dirk
AU - Henzinger, Thomas A
AU - Théoduloz, Grégory
AU - Zufferey, Damien
ED - Rosenblum, David
ED - Taenzer, Gabriele
ID - 4396
TI - Shape refinement through explicit heap analysis
VL - 6013
ER -
TY - CONF
AB - We present ABC, a software tool for automatically computing symbolic upper bounds on the number of iterations of nested program loops. The system combines static analysis of programs with symbolic summation techniques to derive loop invariant relations between program variables. Iteration bounds are obtained from the inferred invariants, by replacing variables with bounds on their greatest values. We have successfully applied ABC to a large number of examples. The derived symbolic bounds express non-trivial polynomial relations over loop variables. We also report on results to automatically infer symbolic expressions over harmonic numbers as upper bounds on loop iteration counts.
AU - Blanc, Régis
AU - Henzinger, Thomas A
AU - Hottelier, Thibaud
AU - Kovács, Laura
ED - Clarke, Edmund M
ED - Voronkov, Andrei
ID - 10908
SN - 0302-9743
T2 - Logic for Programming, Artificial Intelligence, and Reasoning
TI - ABC: Algebraic Bound Computation for loops
VL - 6355
ER -
TY - JOUR
AB - Nuclear pore complexes have recently been shown to play roles in gene activation; however their potential involvement in metazoan transcription remains unclear. Here we show that the nucleoporins Sec13, Nup98, and Nup88, as well as a group of FG-repeat nucleoporins, bind to the Drosophila genome at functionally distinct loci that often do not represent nuclear envelope contact sites. Whereas Nup88 localizes to silent loci, Sec13, Nup98, and a subset of FG-repeat nucleoporins bind to developmentally regulated genes undergoing transcription induction. Strikingly, RNAi-mediated knockdown of intranuclear Sec13 and Nup98 specifically inhibits transcription of their target genes and prevents efficient reactivation of transcription after heat shock, suggesting an essential role of NPC components in regulating complex gene expression programs of multicellular organisms.
AU - Capelson, Maya
AU - Liang, Yun
AU - Schulte, Roberta
AU - Mair, William
AU - Wagner, Ulrich
AU - HETZER, Martin W
ID - 11102
IS - 3
JF - Cell
KW - General Biochemistry
KW - Genetics and Molecular Biology
SN - 0092-8674
TI - Chromatin-bound nuclear pore components regulate gene expression in higher eukaryotes
VL - 140
ER -
TY - JOUR
AB - In metazoa, nuclear pore complexes (NPCs) assemble from disassembled precursors into a reforming nuclear envelope (NE) at the end of mitosis and into growing intact NEs during interphase. Here, we show via RNAi-mediated knockdown that ELYS, a nucleoporin critical for the recruitment of the essential Nup107/160 complex to chromatin, is required for NPC assembly at the end of mitosis but not during interphase. Conversely, the transmembrane nucleoporin POM121 is critical for the incorporation of the Nup107/160 complex into new assembly sites specifically during interphase. Strikingly, recruitment of the Nup107/160 complex to an intact NE involves a membrane curvature-sensing domain of its constituent Nup133, which is not required for postmitotic NPC formation. Our results suggest that in organisms with open mitosis, NPCs assemble via two distinct mechanisms to accommodate cell cycle-dependent differences in NE topology.
AU - Doucet, Christine M.
AU - Talamas, Jessica A.
AU - HETZER, Martin W
ID - 11101
IS - 6
JF - Cell
KW - General Biochemistry
KW - Genetics and Molecular Biology
SN - 0092-8674
TI - Cell cycle-dependent differences in nuclear pore complex assembly in metazoa
VL - 141
ER -
TY - JOUR
AU - HETZER, Martin W
ID - 11098
IS - 2
JF - Aging
KW - Cell Biology
KW - Aging
SN - 1945-4589
TI - The role of the nuclear pore complex in aging of post-mitotic cells
VL - 2
ER -
TY - CONF
AB - Inspired by online ad allocation, we study online stochastic packing integer programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing integer programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple dual training-based algorithm achieves a (1 − o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1−1𝑒 for online ad allocation, and log(m) for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based algorithms on real data sets, and also indicates an intrinsic trade-off between fairness and efficiency.
AU - Feldman, Jon
AU - Henzinger, Monika H
AU - Korula, Nitish
AU - Mirrokni, Vahab S.
AU - Stein, Cliff
ID - 11797
SN - 1611-3349
T2 - 18th Annual European Symposium on Algorithms
TI - Online stochastic packing applied to display ad allocation
VL - 6346
ER -
TY - JOUR
AU - Weijers, Dolf
AU - Friml, Jirí
ID - 3051
IS - 6
JF - Cell
TI - SnapShot: Auxin signaling and transport
VL - 136
ER -
TY - JOUR
AB - The dynamic, differential distribution of the hormone auxin within plant tissues controls an impressive variety of developmental processes, which tailor plant growth and morphology to environmental conditions. Various environmental and endogenous signals can be integrated into changes in auxin distribution through their effects on local auxin biosynthesis and intercellular auxin transport. Individual cells interpret auxin largely by a nuclear signaling pathway that involves the F box protein TIR1 acting as an auxin receptor. Auxin-dependent TIR1 activity leads to ubiquitination-based degradation of transcriptional repressors and complex transcriptional reprogramming. Thus, auxin appears to be a versatile trigger of preprogrammed developmental changes in plant cells.
AU - Vanneste, Steffen
AU - Friml, Jirí
ID - 3052
IS - 6
JF - Cell
TI - Auxin: A trigger for change in plant development
VL - 136
ER -
TY - JOUR
AB - The differential distribution of the plant signaling molecule auxin is required for many aspects of plant development. Local auxin maxima and gradients arise as a result of local auxin metabolism and, predominantly, from directional cell-to-cell transport. In this primer, we discuss how the coordinated activity of several auxin influx and efflux systems, which transport auxin across the plasma membrane, mediates directional auxin flow. This activity crucially contributes to the correct setting of developmental cues in embryogenesis, organogenesis, vascular tissue formation and directional growth in response to environmental stimuli.
AU - Petrášek, Jan
AU - Friml, Jirí
ID - 3057
IS - 16
JF - Development
TI - Auxin transport routes in plant development
VL - 136
ER -
TY - JOUR
AB - The PIN-FORMED (PIN) proteins are secondary transporters acting in the efflux of the plant signal molecule auxin from cells. They are asymmetrically localized within cells and their polarity determines the directionality of intercellular auxin flow. PIN genes are found exclusively in the genomes of multicellular plants and play an important role in regulating asymmetric auxin distribution in multiple developmental processes, including embryogenesis, organogenesis, tissue differentiation and tropic responses. All PIN proteins have a similar structure with amino- and carboxy-terminal hydrophobic, membrane-spanning domains separated by a central hydrophilic domain. The structure of the hydrophobic domains is well conserved. The hydrophilic domain is more divergent and it determines eight groups within the protein family. The activity of PIN proteins is regulated at multiple levels, including transcription, protein stability, subcellular localization and transport activity. Different endogenous and environmental signals can modulate PIN activity and thus modulate auxin-distribution-dependent development. A large group of PIN proteins, including the most ancient members known from mosses, localize to the endoplasmic reticulum and they regulate the subcellular compartmentalization of auxin and thus auxin metabolism. Further work is needed to establish the physiological importance of this unexpected mode of auxin homeostasis regulation. Furthermore, the evolution of PIN-based transport, PIN protein structure and more detailed biochemical characterization of the transport function are important topics for further studies.
AU - Křeček, Pavel
AU - Skůpa, Petr
AU - Libus, Jiří
AU - Naramoto, Satoshi
AU - Tejos, Ricardo
AU - Friml, Jirí
AU - Zažímalová, Eva
ID - 3061
IS - 12
JF - Genome Biology
TI - The PIN-FORMED (PIN) protein family of auxin transporters
VL - 10
ER -
TY - JOUR
AB - The problem of obtaining the maximum a posteriori estimate of a general discrete Markov random field (i.e., a Markov random field defined using a discrete set of labels) is known to be NP-hard. However, due to its central importance in many applications, several approximation algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) LP-S: the linear programming (LP) relaxation proposed by Schlesinger (1976) for a special case and independently in Chekuri et al. (2001), Koster et al. (1998), and Wainwright et al. (2005) for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation of Ravikumar and Lafferty (2006); and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki (2003) for two label problems and later extended by Kumar et al. (2006) for a general label set.
We show that the SOCP-MS and the QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LP-S relaxation strictly dominates (i.e., provides a better approximation than) QP-RL and SOCP-MS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LP-S relaxation. Based on these results we propose some novel SOCP relaxations which define constraints using random variables that form cycles or cliques in the graphical model representation of the random field. Using some examples we show that the new SOCP relaxations strictly dominate the previous approaches.
AU - Kumar, M Pawan
AU - Vladimir Kolmogorov
AU - Torr, Philip H
ID - 3197
JF - Journal of Machine Learning Research
TI - An analysis of convex relaxations for MAP estimation of discrete MRFs
VL - 10
ER -
TY - JOUR
AB - Recent theoretical work has provided a basic understanding of signal propagation in networks of spiking neurons, but mechanisms for gating and controlling these signals have not been investigated previously. Here we introduce an idea for the gating of multiple signals in cortical networks that combines principles of signal propagation with aspects of balanced networks. Specifically, we studied networks in which incoming excitatory signals are normally cancelled by locally evoked inhibition, leaving the targeted layer unresponsive. Transmission can be gated 'on' by modulating excitatory and inhibitory gains to upset this detailed balance. We illustrate gating through detailed balance in large networks of integrate-and-fire neurons. We show successful gating of multiple signals and study failure modes that produce effects reminiscent of clinically observed pathologies. Provided that the individual signals are detectable, detailed balance has a large capacity for gating multiple signals.
AU - Vogels, Tim P
AU - Abbott, L F
ID - 8026
IS - 4
JF - Nature Neuroscience
SN - 1097-6256
TI - Gating multiple signals through detailed balance of excitation and inhibition in spiking networks
VL - 12
ER -
TY - CONF
AB - We present an on-the-fly abstraction technique for infinite-state continuous -time Markov chains. We consider Markov chains that are specified by a finite set of transition classes. Such models naturally represent biochemical reactions and therefore play an important role in the stochastic modeling of biological systems. We approximate the transient probability distributions at various time instances by solving a sequence of dynamically constructed abstract models, each depending on the previous one. Each abstract model is a finite Markov chain that represents the behavior of the original, infinite chain during a specific time interval. Our approach provides complete information about probability distributions, not just about individual parameters like the mean. The error of each abstraction can be computed, and the precision of the abstraction refined when desired. We implemented the algorithm and demonstrate its usefulness and efficiency on several case studies from systems biology.
AU - Thomas Henzinger
AU - Maria Mateescu
AU - Wolf, Verena
ID - 4453
TI - Sliding-window abstraction for infinite Markov chains
VL - 5643
ER -
TY - CONF
AB - Weighted automata are finite automata with numerical weights on transitions. Nondeterministic weighted automata define quantitative languages L that assign to each word w a real number L(w) computed as the maximal value of all runs over w, and the value of a run r is a function of the sequence of weights that appear along r. There are several natural functions to consider such as Sup, LimSup, LimInf, limit average, and discounted sum of transition weights.
We introduce alternating weighted automata in which the transitions of the runs are chosen by two players in a turn-based fashion. Each word is assigned the maximal value of a run that the first player can enforce regardless of the choices made by the second player. We survey the results about closure properties, expressiveness, and decision problems for nondeterministic weighted automata, and we extend these results to alternating weighted automata.
For quantitative languages L 1 and L 2, we consider the pointwise operations max(L 1,L 2), min(L 1,L 2), 1 − L 1, and the sum L 1 + L 2. We establish the closure properties of all classes of alternating weighted automata with respect to these four operations.
We next compare the expressive power of the various classes of alternating and nondeterministic weighted automata over infinite words. In particular, for limit average and discounted sum, we show that alternation brings more expressive power than nondeterminism.
Finally, we present decidability results and open questions for the quantitative extension of the classical decision problems in automata theory: emptiness, universality, language inclusion, and language equivalence.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
ID - 4542
TI - Alternating weighted automata
VL - 5699
ER -
TY - CONF
AB - We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. We present in this paper a strategy improvement algorithm for computing the value of a concurrent safety game, that is, the maximal probability with which player 1 can enforce the safety objective. The algorithm yields a sequence of player-1 strategies which ensure probabilities of winning that converge monotonically to the value of the safety game. Our result is significant because the strategy improvement algorithm provides, for the first time, a way to approximate the value of a concurrent safety game from below. Since a value iteration algorithm, or a strategy improvement algorithm for reachability games, can be used to approximate the same value from above, the combination of both algorithms yields a method for computing a converging sequence of upper and lower bounds for the values of concurrent reachability and safety games. Previous methods could approximate the values of these games only from one direction, and as no rates of convergence are known, they did not provide a practical way to solve these games.
AU - Krishnendu Chatterjee
AU - de Alfaro, Luca
AU - Thomas Henzinger
ID - 4544
TI - Termination criteria for solving concurrent safety and reachability games
ER -
TY - CONF
AB - A stochastic game is a two-player game played oil a graph, where in each state the successor is chosen either by One of the players, or according to a probability distribution. We Survey Stochastic games with limsup and liminf objectives. A real-valued re-ward is assigned to each state, and the value of all infinite path is the limsup (resp. liminf) of all rewards along the path. The value of a stochastic game is the maximal expected value of an infinite path that call he achieved by resolving the decisions of the first player. We present the complexity of computing values of Stochastic games and their subclasses, and the complexity, of optimal strategies in such games.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
ID - 4545
TI - A survey of stochastic games with limsup and liminf objectives
VL - 5556
ER -
TY - CONF
AB - Most specification languages express only qualitative constraints. However, among two implementations that satisfy a given specification, one may be preferred to another. For example, if a specification asks that every request is followed by a response, one may prefer an implementation that generates responses quickly but does not generate unnecessary responses. We use quantitative properties to measure the “goodness” of an implementation. Using games with corresponding quantitative objectives, we can synthesize “optimal” implementations, which are preferred among the set of possible implementations that satisfy a given specification.
In particular, we show how automata with lexicographic mean-payoff conditions can be used to express many interesting quantitative properties for reactive systems. In this framework, the synthesis of optimal implementations requires the solution of lexicographic mean-payoff games (for safety requirements), and the solution of games with both lexicographic mean-payoff and parity objectives (for liveness requirements). We present algorithms for solving both kinds of novel graph games.
AU - Bloem, Roderick
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Jobstmann, Barbara
ID - 4569
TI - Better quality in synthesis through quantitative objectives
VL - 5643
ER -
TY - CONF
AB - Alpaga is a solver for two-player parity games with imperfect information. Given the description of a game, it determines whether the first player can ensure to win and, if so, it constructs a winning strategy. The tool provides a symbolic implementation of a recent algorithm based on antichains.
AU - Berwanger, Dietmar
AU - Krishnendu Chatterjee
AU - De Wulf, Martin
AU - Doyen, Laurent
AU - Thomas Henzinger
ID - 4580
TI - Alpaga: A tool for solving parity games with imperfect information
VL - 5505
ER -
TY - GEN
AB - We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs of [GO09] and present a precise characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems.
AU - Chatterjee, Krishnendu
ID - 5392
SN - 2664-1690
TI - Probabilistic automata on infinite words: Decidability and undecidability results
ER -
TY - GEN
AB - Gist is a tool that (a) solves the qualitative analysis problem of turn-based probabilistic games with ω-regular objectives; and (b) synthesizes reasonable environment assumptions for synthesis of unrealizable specifications. Our tool provides efficient implementations of several reduction based techniques to solve turn-based probabilistic games, and uses the analysis of turn-based probabilistic games for synthesizing environment assumptions for unrealizable specifications.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Jobstmann, Barbara
AU - Radhakrishna, Arjun
ID - 5393
SN - 2664-1690
TI - Gist: A solver for probabilistic games
ER -
TY - GEN
AB - We consider two-player games played on graphs with request-response and finitary Streett objectives. We show these games are PSPACE-hard, improving the previous known NP-hardness. We also improve the lower bounds on memory required by the winning strategies for the players.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Horn, Florian
ID - 5394
SN - 2664-1690
TI - Improved lower bounds for request-response and finitary Streett games
ER -
TY - GEN
AB - We study observation-based strategies for partially-observable Markov decision processes (POMDPs) with omega-regular objectives. An observation-based strategy relies on partial information about the history of a play, namely, on the past sequence of observa- tions. We consider the qualitative analysis problem: given a POMDP with an omega-regular objective, whether there is an observation-based strategy to achieve the objective with probability 1 (almost-sure winning), or with positive probability (positive winning). Our main results are twofold. First, we present a complete picture of the computational complexity of the qualitative analysis of POMDPs with parity objectives (a canonical form to express omega-regular objectives) and its subclasses. Our contribution consists in establishing several upper and lower bounds that were not known in literature. Second, we present optimal bounds (matching upper and lower bounds) on the memory required by pure and randomized observation-based strategies for the qualitative analysis of POMDPs with parity objectives and its subclasses.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
ID - 5395
SN - 2664-1690
TI - Qualitative analysis of partially-observable Markov decision processes
ER -
TY - JOUR
AB - The human CDK8 subcomplex (CDK8, cyclin C, Med12, and Med13) negatively regulates transcription in ways not completely defined; past studies suggested CDK8 kinase activity was required for its repressive function. Using a reconstituted transcription system together with recombinant or endogenous CDK8 subcomplexes, we demonstrate that, in fact, Med12 and Med13 are critical for subcomplex-dependent repression, whereas CDK8 kinase activity is not. A hallmark of activated transcription is efficient reinitiation from promoter-bound scaffold complexes that recruit a series of pol II enzymes to the gene. Notably, the CDK8 submodule strongly represses even reinitiation events, suggesting a means to fine tune transcript levels. Structural and biochemical studies confirm the CDK8 submodule binds the Mediator leg/tail domain via the Med13 subunit, and this submodule-Mediator association precludes pol II recruitment. Collectively, these results reveal the CDK8 subcomplex functions as a simple switch that controls the Mediator-pol II interaction to help regulate transcription initiation and reinitiation events. As Mediator is generally required for expression of protein-coding genes, this may reflect a common mechanism by which activated transcription is shut down in human cells.
AU - Knuesel, Matthew
AU - Meyer, Krista
AU - Bernecky, Carrie A
AU - Taatjes, Dylan
ID - 599
IS - 4
JF - Genes and Development
TI - The human CDK8 subcomplex is a molecular switch that controls Mediator coactivator function
VL - 23
ER -
TY - CHAP
AB - Let g be a cubic polynomial with integer coefficients and n>9 variables, and assume that the congruence g=0 modulo p^k is soluble for all prime powers p^k. We show that the equation g=0 has infinitely many integer solutions when the cubic part of g defines a projective hypersurface with singular locus of dimension <n-10. The proof is based on the Hardy-Littlewood circle method.
AU - Browning, Timothy D
AU - Heath Brown, Roger
ID - 164
T2 - Analytic Number Theory: Essays in honour of Klaus Roth
TI - Integral points on cubic hypersurfaces
ER -
TY - JOUR
AB - We demonstrate the time-resolved driving of two-photon blue sideband transitions between superconducting qubits and a transmission line resonator. As an example of using these sideband transitions for a two-qubit operation, we implement a pulse sequence that first entangles one qubit with the resonator and subsequently distributes the entanglement between two qubits. We show the generation of 75% fidelity Bell states by this method. The full density matrix of the two-qubit system is extracted using joint measurement and quantum state tomography and shows close agreement with numerical simulation.
AU - Leek, Peter J
AU - Filipp, Stefan
AU - Maurer, Patrick
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Johannes Fink
AU - Göppl, M
AU - Steffen, L. Kraig
AU - Wallraff, Andreas
ID - 1766
IS - 18
JF - Physical Review B - Condensed Matter and Materials Physics
TI - Using sideband transitions for two-qubit operations in superconducting circuits
VL - 79
ER -
TY - JOUR
AB - We present spectroscopic measurements of the Autler-Townes doublet and the sidebands of the Mollow triplet in a driven superconducting qubit. The ground to first excited state transition of the qubit is strongly pumped while the resulting dressed qubit spectrum is probed with a weak tone. The corresponding transitions are detected using dispersive readout of the qubit coupled off resonantly to a microwave transmission line resonator. The observed frequencies of the Autler-Townes and Mollow spectral lines are in good agreement with a dispersive Jaynes-Cummings model taking into account higher excited qubit states and dispersive level shifts due to off-resonant drives.
AU - Baur, Matthias P
AU - Filipp, Stefan
AU - Bianchetti, R
AU - Johannes Fink
AU - Göppl, M
AU - Steffen, L. Kraig
AU - Leek, Peter J
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1767
IS - 24
JF - Physical Review Letters
TI - Measurement of autler-townes and mollow transitions in a strongly driven superconducting qubit
VL - 102
ER -
TY - JOUR
AB - Quantum state tomography is an important tool in quantum information science for complete characterization of multiqubit states and their correlations. Here we report a method to perform a joint simultaneous readout of two superconducting qubits dispersively coupled to the same mode of a microwave transmission line resonator. The nonlinear dependence of the resonator transmission on the qubit state dependent cavity frequency allows us to extract the full two-qubit correlations without the need for single-shot readout of individual qubits. We employ standard tomographic techniques to reconstruct the density matrix of two-qubit quantum states.
AU - Filipp, Stefan
AU - Maurer, Patrick
AU - Leek, Peter J
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Johannes Fink
AU - Göppl, M
AU - Steffen, L. Kraig
AU - Gambetta, Jay M
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1768
IS - 20
JF - Physical Review Letters
TI - Two-qubit state tomography using a joint dispersive readout
VL - 102
ER -
TY - JOUR
AB - We present an ideal realization of the Tavis-Cummings model in the absence of atom number and coupling fluctuations by embedding a discrete number of fully controllable superconducting qubits at fixed positions into a transmission line resonator. Measuring the vacuum Rabi mode splitting with one, two, and three qubits strongly coupled to the cavity field, we explore both bright and dark dressed collective multiqubit states and observe the discrete N scaling of the collective dipole coupling strength. Our experiments demonstrate a novel approach to explore collective states, such as the W state, in a fully globally and locally controllable quantum system. Our scalable approach is interesting for solid-state quantum information processing and for fundamental multiatom quantum optics experiments with fixed atom numbers.
AU - Johannes Fink
AU - Bianchetti, R
AU - Baur, Matthias P
AU - Göppl, M
AU - Steffen, L. Kraig
AU - Filipp, Stefan
AU - Leek, Peter J
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1769
IS - 8
JF - Physical Review Letters
TI - Dressed collective qubit states and the Tavis-Cummings model in circuit QED
VL - 103
ER -
TY - JOUR
AB - The quantum state of a superconducting qubit nonresonantly coupled to a transmission line resonator can be determined by measuring the quadrature amplitudes of an electromagnetic field transmitted through the resonator. We present experiments in which we analyze in detail the dynamics of the transmitted field as a function of the measurement frequency for both weak continuous and pulsed measurements. We find excellent agreement between our data and calculations based on a set of Bloch-type differential equations for the cavity field derived from the dispersive Jaynes-Cummings Hamiltonian including dissipation. We show that the measured system response can be used to construct a measurement operator from which the qubit population can be inferred accurately. Such a measurement operator can be used in tomographic methods to reconstruct single and multiqubit states in ensemble-averaged measurements.
AU - Bianchetti, R
AU - Filipp, Stefan
AU - Baur, Matthias P
AU - Johannes Fink
AU - Göppl, M
AU - Leek, Peter J
AU - Steffen, L. Kraig
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1770
IS - 4
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Dynamics of dispersive single-qubit readout in circuit quantum electrodynamics
VL - 80
ER -
TY - JOUR
AB - The exceptionally strong coupling realizable between superconducting qubits and photons stored in an on-chip microwave resonator allows for the detailed study of matter-light interactions in the realm of circuit quantum electrodynamics (QED). Here we investigate the resonant interaction between a single transmon-type multilevel artificial atom and weak thermal and coherent fields. We explore up to three photon dressed states of the coupled system in a linear response heterodyne transmission measurement. The results are in good quantitative agreement with a generalized Jaynes-Cummings model. Our data indicate that the role of thermal fields in resonant cavity QED can be studied in detail using superconducting circuits.
AU - Johannes Fink
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Filipp, Stefan
AU - Göppl, M
AU - Leek, Peter J
AU - Steffen, L. Kraig
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1771
JF - Physica Scripta T
TI - Thermal excitation of multi-photon dressed states in circuit quantum electrodynamics
VL - T137
ER -
TY - JOUR
AB - Many membrane channels and receptors exhibit adaptive, or desensitized, response to a strong sustained input stimulus. A key mechanism that underlies this response is the slow, activity-dependent removal of responding molecules to a pool which is unavailable to respond immediately to the input. This mechanism is implemented in different ways in various biological systems and has traditionally been studied separately for each. Here we highlight the common aspects of this principle, shared by many biological systems, and suggest a unifying theoretical framework. We study theoretically a class of models which describes the general mechanism and allows us to distinguish its universal from system-specific features. We show that under general conditions, regardless of the details of kinetics, molecule availability encodes an averaging over past activity and feeds back multiplicatively on the system output. The kinetics of recovery from unavailability determines the effective memory kernel inside the feedback branch, giving rise to a variety of system-specific forms of adaptive response—precise or input-dependent, exponential or power-law—as special cases of the same model.
AU - Tamar Friedlander
AU - Brenner, Naama
ID - 1825
IS - 52
JF - PNAS
TI - Adaptive response by state-dependent inactivation
VL - 106
ER -
TY - JOUR
AB - We have developed a tunable source of Mie scale microdroplet aerosols that can be used for the generation of energetic ions. To demonstrate this potential, a terawatt Ti: Al2 O3 laser focused to 2×10 19 W/cm2 was used to irradiate heavy water (D2 O) aerosols composed of micron-scale droplets. Energetic deuterium ions, which were generated in the laser-droplet interaction, produced deuterium-deuterium fusion with approximately 2×10^3 fusion neutrons measured per joule of incident laser energy.
AU - Higginbotham, Andrew P
AU - Semonin, Octavi
AU - Bruce, S
AU - Chan, C
AU - Maindi, M
AU - Donnelly, Tom
AU - Maurer, M
AU - Bang, Woosuk
AU - Churina, I.V
AU - Osterholz, Jens
AU - Kim, I
AU - Bernstein, Aaron
AU - Ditmire, Todd
ID - 88
IS - 6
JF - Review of Scientific Instruments
TI - Generation of Mie size microdroplet aerosols with applications in laser-driven fusion experiments
VL - 80
ER -
TY - JOUR
AB - As part of an ongoing effort to develop a parameterization of wave-induced abyssal mixing, the authors derive an heuristic model for nonlinear wave breaking and energy dissipation associated with internal tides. Then the saturation and dissipation of internal tides for idealized and observed topography samples are investigated. One of the main results is that the wave-induced mixing could be more intense and more confined to the bottom than previously assumed in numerical models. Furthermore, in this model wave breaking and mixing clearly depend on the small scales of the topography below 10 km or so, which is below the current resolution of global bathymetry. This motivates the use of a statistical approach to represent the unresolved topography when addressing the role of internal tides in mixing the deep ocean.
AU - Muller, Caroline J
AU - Bühler, Oliver
ID - 9147
IS - 9
JF - Journal of Physical Oceanography
KW - Oceanography
SN - 1520-0485
TI - Saturation of the internal tides and induced mixing in the abyssal ocean
VL - 39
ER -
TY - JOUR
AB - Several observational studies have shown a tight relationship between tropical precipitation and column‐integrated water vapor. We show that the observed relationship in the tropics between column‐integrated water vapor, precipitation, and its variance can be qualitatively reproduced by a simple and physically motivated two‐layer model. It has previously been argued that features of this relationship could be explained by analogy with the theory of continuous phase transitions. Instead, our model explicitly assumes that the onset of precipitation is governed by a stability threshold involving boundary‐layer water vapor. This allows us to explain the precipitation‐humidity relationship over a broader range of water vapor values, and may explain the observed temperature dependence of the relationship.
AU - Muller, Caroline J
AU - Back, Larissa E.
AU - O'Gorman, Paul A.
AU - Emanuel, Kerry A.
ID - 9148
IS - 16
JF - Geophysical Research Letters
KW - General Earth and Planetary Sciences
KW - Geophysics
SN - 0094-8276
TI - A model for the relationship between tropical precipitation and column water vapor
VL - 36
ER -
TY - JOUR
AB - One possible way to produce ultra-cold, high-phase-space-density quantum gases of molecules in the rovibronic ground state is given by molecule association from quantum-degenerate atomic gases on a Feshbach resonance and subsequent coherent optical multi-photon transfer into the rovibronic ground state. In ultra-cold samples of Cs2 molecules, we observe two-photon dark resonances that connect the intermediate rovibrational level |v=73,J=2 with the rovibrational ground state |v=0,J=0 of the singlet X 1 ∑ g + ground-state potential. For precise dark resonance spectroscopy we exploit the fact that it is possible to efficiently populate the level |v=73,J=2 by two-photon transfer from the dissociation threshold with the stimulated Raman adiabatic passage (STIRAP) technique. We find that at least one of the two-photon resonances is sufficiently strong to allow future implementation of coherent STIRAP transfer of a molecular quantum gas to the rovibrational ground state |v=0,J=0.
AU - Mark, Manfred
AU - Danzl, Johann G
AU - Haller, Elmar
AU - Gustavsson, Mattias
AU - Bouloufa, Nadia
AU - Dulieu, Olivier
AU - Salami, Houssam
AU - Bergeman, Thomas
AU - Ritsch, Helmut
AU - Hart, Russell
AU - Nägerl, Hanns
ID - 1038
IS - 2
JF - Applied Physics B: Lasers and Optics
TI - Dark resonances for ground-state transfer of molecular quantum gases
VL - 95
ER -
TY - JOUR
AB - Ultracold atomic physics offers myriad possibilities to study strongly correlated many-body systems in lower dimensions. Typically, only ground-state phases are accessible. Using a tunable quantum gas of bosonic cesium atoms, we realized and controlled in one-dimensional geometry a highly excited quantum phase that is stabilized in the presence of attractive interactions by maintaining and strengthening quantum correlations across a confinement-induced resonance. We diagnosed the crossover from repulsive to attractive interactions in terms of the stiffness and energy of the system. Our results open up the experimental study of metastable, excited, many-body phases with strong correlations and their dynamical properties.
AU - Haller, Elmar
AU - Gustavsson, Mattias
AU - Mark, Manfred
AU - Danzl, Johann G
AU - Hart, Russell
AU - Pupillo, Guido
AU - Nägerl, Hanns
ID - 1040
IS - 5945
JF - Science
TI - Realization of an excited, strongly correlated quantum gas Phase
VL - 325
ER -
TY - JOUR
AB - We demonstrate efficient transfer of ultracold molecules into a deeply bound rovibrational level of the singlet ground state potential in the presence of an optical lattice. The overall molecule creation efficiency is 25%, and the transfer efficiency to the rovibrational level |v = 73, J = 2) is above 80%. We find that the molecules in |v = 73, J = 2) are trapped in the optical lattice, and that the lifetime in the lattice is limited by optical excitation by the lattice light. The molecule trapping time for a lattice depth of 15 atomic recoil energies is about 20 ms. We determine the trapping frequency by the lattice phase and amplitude modulation technique. It will now be possible to transfer the molecules to the rovibrational ground state |v = 0, J = 0) in the presence of the optical lattice.
AU - Danzl, Johann G
AU - Mark, Manfred
AU - Haller, Elmar
AU - Gustavsson, Mattias
AU - Hart, Russell
AU - Liem, Andreas
AU - Zellmer, Holger
AU - Nägerl, Hanns
ID - 1041
JF - New Journal of Physics
TI - Deeply bound ultracold molecules in an optical lattice
VL - 11
ER -
TY - JOUR
AB - One possibility for the creation of ultracold, high phase space density quantum gases of molecules in the rovibronic ground state relies on first associating weakly-bound molecules from quantum-degenerate atomic gases on a Feshbach resonance and then transferring the molecules via several steps of coherent two-photon stimulated Raman adiabatic passage (STIRAP) into the rovibronic ground state. Here, in ultracold samples of Cs2 Feshbach molecules produced out of ultracold samples of Cs atoms, we observe several optical transitions to deeply-bound rovibrational levels of the excited 0 u+ molecular potentials with high resolution. At least one of these transitions, although rather weak, allows efficient STIRAP transfer into the deeply-bound vibrational level v = 73> of the singlet X 1Σg+ ground state potential, as recently demonstrated (J. G. Danzl, E. Haller, M. Gustavsson, M. J. Mark, R. Hart, N. Bouloufa, O. Dulieu, H. Ritsch, and H.-C. Nägerl, Science, 2008, 321, 1062). From this level, the rovibrational ground state v = 0, J = 0> can be reached with one more transfer step. In total, our results show that coherent ground state transfer for Cs2 is possible using a maximum of two successive two-photon STIRAP processes or one single four-photon STIRAP process.
AU - Danzl, Johann G
AU - Mark, Manfred
AU - Haller, Elmar
AU - Gustavsson, Mattias
AU - Bouloufa, Nadia
AU - Dulieu, Olivier
AU - Ritsch, Helmut
AU - Hart, Russell
AU - Nägerl, Hanns
ID - 1043
JF - Faraday Discussions
TI - Precision molecular spectroscopy for ground state transfer of molecular quantum gases
VL - 142
ER -
TY - JOUR
AB - Let (E, H, μ) be an abstract Wiener space and let DV : = V D, where D denotes the Malliavin derivative and V is a closed and densely defined operator from H into another Hilbert space under(H, {combining low line}). Given a bounded operator B on under(H, {combining low line}), coercive on the range over(R (V), -), we consider the operators A : = V* B V in H and under(A, {combining low line}) : = V V* B in under(H, {combining low line}), as well as the realisations of the operators L : = DV* B DV and under(L, {combining low line}) : = DV DV* B in Lp (E, μ) and Lp (E, μ ; under(H, {combining low line})) respectively, where 1 < p < ∞. Our main result asserts that the following four assertions are equivalent: (1)D (sqrt(L)) = D (DV) with {norm of matrix} sqrt(L) f {norm of matrix}p {minus tilde} {norm of matrix} DV f {norm of matrix}p for f ∈ D (sqrt(L));(2)under(L, {combining low line}) admits a bounded H∞-functional calculus on over(R (DV), -);(3)D (sqrt(A)) = D (V) with {norm of matrix} sqrt(A) h {norm of matrix} {minus tilde} {norm of matrix} V h {norm of matrix} for h ∈ D (sqrt(A));(4)under(A, {combining low line}) admits a bounded H∞-functional calculus on over(R (V), -). Moreover, if these conditions are satisfied, then D (L) = D (DV2) ∩ D (DA). The equivalence (1)-(4) is a non-symmetric generalisation of the classical Meyer inequalities of Malliavin calculus (where under(H, {combining low line}) = H, V = I, B = frac(1, 2) I). A one-sided version of (1)-(4), giving Lp-boundedness of the Riesz transform DV / sqrt(L) in terms of a square function estimate, is also obtained. As an application let -A generate an analytic C0-contraction semigroup on a Hilbert space H and let -L be the Lp-realisation of the generator of its second quantisation. Our results imply that two-sided bounds for the Riesz transform of L are equivalent with the Kato square root property for A. The boundedness of the Riesz transform is used to obtain an Lp-domain characterisation for the operator L.
AU - Jan Maas
AU - van Neerven, Jan M
ID - 2119
IS - 8
JF - Journal of Functional Analysis
TI - Boundedness of Riesz transforms for elliptic operators on abstract Wiener spaces
VL - 257
ER -
TY - JOUR
AB - Relying on the quantization rule of Raab and Friedrich [Phys. Rev. A (2009) in press], we derive simple and accurate formulae for the number of rotational states supported by a weakly bound vibrational level of a diatomic molecular ion. We also provide analytic estimates of the rotational constants of any such levels up to threshold for dissociation and obtain a criterion for determining whether a given weakly bound vibrational level is rotationless. The results depend solely on the long-range part of the molecular potential.
AU - Mikhail Lemeshko
AU - Frierich, Bretislav
ID - 2137
IS - 1
JF - Journal of Atomic and Molecular Sciences
TI - Rotational structure of weakly bound molecular ions
VL - 1
ER -
TY - JOUR
AB - We investigate the effects of a magnetic field on the dynamics of rotationally inelastic collisions of open-shell molecules (Σ2, Σ3, and Π2) with closed-shell atoms. Our treatment makes use of the Fraunhofer model of matter wave scattering and its recent extension to collisions in electric [M. Lemeshko and B. Friedrich, J. Chem. Phys. 129, 024301 (2008)] and radiative fields [M. Lemeshko and B. Friedrich, Int. J. Mass. Spec. 280, 19 (2009)]. A magnetic field aligns the molecule in the space-fixed frame and thereby alters the effective shape of the diffraction target. This significantly affects the differential and integral scattering cross sections. We exemplify our treatment by evaluating the magnetic-field-dependent scattering characteristics of the He-CaH (XΣ+2), He-O2 (XΣ–3), and He-OH (XΠΩ2) systems at thermal collision energies. Since the cross sections can be obtained for different orientations of the magnetic field with respect to the relative velocity vector, the model also offers predictions about the frontal-versus-lateral steric asymmetry of the collisions. The steric asymmetry is found to be almost negligible for the He-OH system, weak for the He-CaH collisions, and strong for the He-O2. While odd ΔM transitions dominate the He-OH [J=3/2,f→J′,e/f] integral cross sections in a magnetic field parallel to the relative velocity vector, even ΔM transitions prevail in the case of the He-CaH (X2Σ+) and He-O2 (XΣ−3) collision systems. For the latter system, the magnetic field opens inelastic channels that are closed in the absence of the field. These involve the transitions N=1,J=0→N′, J′ with J′=N′.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2149
IS - 1
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Collisions of paramagnetic molecules in magnetic fields: An analytic model based on Fraunhofer diffraction of matter waves
VL - 79
ER -
TY - JOUR
AB - We examine the effects of a linearly polarized nonresonant radiative field on the dynamics of rotationally inelastic Na+ + N2 collisions at eV collision energies. Our treatment is based on the Fraunhofer model of matter wave scattering and its recent extension to collisions in electric fields [M. Lemeshko, B. Friedrich, J. Chem. Phys. 129 (2008) 024301]. The nonresonant radiative field changes the effective shape of the target molecule by aligning it in the space-fixed frame. This markedly alters the differential and integral scattering cross-sections. As the cross-sections can be evaluated for a polarization of the radiative field collinear or perpendicular to the relative velocity vector, the model also offers predictions about steric asymmetry of the collisions.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2150
IS - 1-3
JF - International Journal of Mass Spectrometry
TI - The effect of a nonresonant radiative field on low-energy rotationally inelastic Na+ + N2 collisions
VL - 280
ER -
TY - JOUR
AB - By making use of the quantization rule of Raab and Friedrich [Phys. Rev. A 78, 022707 (2008)], we derive simple and accurate formulae for the number of rotational states supported by a weakly bound vibrational level of a diatomic molecule and the rotational constants of any such levels up to the threshold, and provide a criterion for determining whether a given weakly bound vibrational level is rotationless. The results depend solely on the long-range part of the molecular potential and are applicable to halo molecules.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2191
IS - 5
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Rotational and rotationless states of weakly bound molecules
VL - 79
ER -
TY - JOUR
AB - We develop an analytic model of thermal state-to-state rotationally inelastic collisions of asymmetric-top molecules with closed-shell atoms in electric fields and apply it to the Ar-H2O collision system. The predicted cross sections as well as the steric asymmetry of the collisions show at fields up to 150 kV/cm characteristic field-dependent features which can be experimentally tested. Particularly suitable candidates for such tests are the 000 → 220 and 101→ 221 channels, arising from the relaxation of the field-free selection rules due to the hybridization of J states by the field. Averaging over the M' product channels is found to largely obliterate the orientation effects brought about by the field.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2192
IS - 52
JF - Journal of Physical Chemistry A
TI - Model analysis of rotationally inelastic Ar + H2O scattering in an electric field
VL - 113
ER -
TY - JOUR
AB - We show that weakly bound molecules can be probed by "shaking" in a pulsed nonresonant laser field. The field introduces a centrifugal term which expels the highest vibrational level from the potential that binds it. Our numerical simulations applied to the Rb2 and KRb Feshbach molecules indicate that shaking by feasible laser pulses can be used to accurately recover the square of the vibrational wave function and, by inversion, also the long-range part of the molecular potential.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2193
IS - 5
JF - Physical Review Letters
TI - Probing weakly bound molecules with nonresonant light
VL - 103
ER -
TY - JOUR
AB - Let X be a projective non-singular quartic hypersurface of dimension 39 or more, which is defined over . We show that X() is non-empty provided that X() is non-empty and X has p-adic points for every prime p.
AU - Timothy Browning
AU - Heath-Brown, Roger
ID - 228
IS - 629
JF - Journal fur die Reine und Angewandte Mathematik
TI - Rational points on quartic hypersurfaces
ER -
TY - JOUR
AB - An upper bound of the expected order of magnitude is established for the number of ℚ-rational points of bounded height on Châtelet surfaces defined over ℚ.
AU - Timothy Browning
ID - 229
IS - 1
JF - Mathematische Annalen
TI - Linear growth for Châtelet surfaces
VL - 346
ER -
TY - JOUR
AB - We prove the Lee-Huang-Yang formula for the ground state energy of the 3D Bose gas with repulsive interactions described by the exponential function, in a simultaneous limit of weak coupling and high density. In particular, we show that the Bogoliubov approximation is exact in an appropriate parameter regime, as far as the ground state energy is concerned.
AU - Giuliani, Alessandro
AU - Robert Seiringer
ID - 2384
IS - 5-6
JF - Journal of Statistical Physics
TI - The ground state energy of the weakly interacting Bose gas at high density
VL - 135
ER -
TY - JOUR
AB - We consider an ultracold rotating Bose gas in a harmonic trap close to the critical angular velocity, so that the system can be considered to be confined to the lowest Landau level. With this assumption we prove that the Gross-Pitaevskii energy functional accurately describes the ground-state energy of the corresponding N -body Hamiltonian with contact interaction provided the total angular momentum L is much less than N2. While the Gross-Pitaevskii energy is always an obvious variational upper bound to the ground-state energy, a more refined analysis is needed to establish it as an exact lower bound. We also discuss the question of Bose-Einstein condensation in the parameter range considered. Coherent states together with inequalities in spaces of analytic functions are the main technical tools.
AU - Lieb, Élliott H
AU - Robert Seiringer
AU - Yngvason, Jakob
ID - 2385
IS - 6
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Yrast line of a rapidly rotating Bose gas: Gross-Pitaevskii regime
VL - 79
ER -
TY - JOUR
AB - We prove exponential decay of the off-diagonal correlation function in the two-dimensional homogeneous Bose gas when a2 ρ is small and the temperature T satisfies T> 4πρ ln | ln (a2 ρ) |. Here, a is the scattering length of the repulsive interaction potential and ρ is the density. To the leading order in a2 ρ, this bound agrees with the expected critical temperature for superfluidity. In the three-dimensional Bose gas, exponential decay is proved when T- Tc (0) Tc (0) >5 a ρ1/3, where Tc (0) is the critical temperature of the ideal gas. While this condition is not expected to be sharp, it gives a rigorous upper bound on the critical temperature for Bose-Einstein condensation.
AU - Robert Seiringer
AU - Ueltschi, Daniel
ID - 2386
IS - 1
JF - Physical Review B - Condensed Matter and Materials Physics
TI - Rigorous upper bound on the critical temperature of dilute Bose gases
VL - 80
ER -
TY - JOUR
AB - We consider a system of trapped spinless bosons interacting with a repulsive potential and subject to rotation. In the limit of rapid rotation and small scattering length, we rigorously show that the ground state energy converges to that of a simplified model Hamiltonian with contact interaction projected onto the Lowest Landau Level. This effective Hamiltonian models the bosonic analogue of the Fractional Quantum Hall Effect (FQHE). For a fixed number of particles, we also prove convergence of states; in particular, in a certain regime we show convergence towards the bosonic Laughlin wavefunction. This is the first rigorous justification of the effective FQHE Hamiltonian for rapidly rotating Bose gases. We review previous results on this effective Hamiltonian and outline open problems.
AU - Lewin, Mathieu
AU - Robert Seiringer
ID - 2387
IS - 5
JF - Journal of Statistical Physics
TI - Strongly correlated phases in rapidly rotating Bose gases
VL - 137
ER -
TY - JOUR
AB - This paper provides self-contained proof of a theorem relating probabilistic coherence of forecasts to their non-domination by rival forecasts with respect to any proper scoring rule. The theorem recapitulates insights achieved by other investigators, and clarifies the connection of coherence and proper scoring rules to Bregman divergence.
AU - Predd, Joel B
AU - Robert Seiringer
AU - Lieb, Élliott H
AU - Osherson, Daniel N
AU - Poor, Harold V
AU - Kulkarni, Sanjeev R
ID - 2388
IS - 10
JF - IEEE Transactions on Information Theory
TI - Probabilistic coherence and proper scoring rules
VL - 55
ER -
TY - CONF
AB - Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into ℝd? Known results easily imply polynomiality of EMBEDk→2 (k = 1, 2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3 (even if k is not considered fixed). We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED d→d and EMBED(d-1)→d are undecidable for each d ≥ 5. Our main result is NP-hardness of EMBED2→4 and, more generally, of EMBEDk→d for all k, d with d ≥ 4 and d ≥ k ≥ (2d - 2)/3.
AU - Matoušek, Jiří
AU - Martin Tancer
AU - Uli Wagner
ID - 2433
TI - Hardness of embedding simplicial complexes in ℝd
ER -
TY - JOUR
AB - G protein-coupled receptors (GPCRs) have critical functions in intercellular communication. Although a wide range of different receptors have been identified in the same cells, the mechanism by which signals are integrated remains elusive. The ability of GPCRs to form dimers or larger hetero-oligomers is thought to generate such signal integration. We examined the molecular mechanisms responsible for the GABAB receptor-mediated potentiation of the mGlu receptor signalling reported in Purkinje neurons. We showed that this effect does not require a physical interaction between both receptors. Instead, it is the result of a more general mechanism in which the βγ subunits produced by the Gi-coupled GABAB receptor enhance the mGlu-mediated Gq response. Most importantly, this mechanism could be generally applied to other pairs of Gi- and Gq-coupled receptors and the signal integration varied depending on the time delay between activation of each receptor. Such a mechanism helps explain specific properties of cells expressing two different Gi- and Gq-coupled receptors activated by a single transmitter, or properties of GPCRs naturally coupled to both types of the G protein.
AU - Rives, Marie L
AU - Vol, Claire
AU - Fukazawa, Yugo
AU - Tinel, Norbert
AU - Trinquet, Eric
AU - Ayoub, Mohammed A
AU - Ryuichi Shigemoto
AU - Pin, Jean-Philippe
AU - Prezèau, Laurent
ID - 2499
IS - 15
JF - EMBO Journal
TI - Crosstalk between GABAB and mGlu1a receptors reveals new insight into GPCR signal integration
VL - 28
ER -
TY - JOUR
AB - Parent-of-origin-specific (imprinted) gene expression is regulated in Arabidopsis thaliana endosperm by cytosine demethylation of the maternal genome mediated by the DNA glycosylase DEMETER, but the extent of the methylation changes is not known. Here, we show that virtually the entire endosperm genome is demethylated, coupled with extensive local non-CG hypermethylation of small interfering RNA–targeted sequences. Mutation of DEMETER partially restores endosperm CG methylation to levels found in other tissues, indicating that CG demethylation is specific to maternal sequences. Endosperm demethylation is accompanied by CHH hypermethylation of embryo transposable elements. Our findings demonstrate extensive reconfiguration of the endosperm methylation landscape that likely reinforces transposon silencing in the embryo.
AU - Hsieh, Tzung-Fu
AU - Ibarra, Christian A.
AU - Silva, Pedro
AU - Zemach, Assaf
AU - Eshed-Williams, Leor
AU - Fischer, Robert L.
AU - Zilberman, Daniel
ID - 9453
IS - 5933
JF - Science
KW - Multidisciplinary
SN - 0036-8075
TI - Genome-wide demethylation of Arabidopsis endosperm
VL - 324
ER -
TY - CONF
AB - We give polynomial-time algorithms for computing the values of Markov decision processes (MDPs) with limsup and liminf objectives. A real-valued reward is assigned to each state, and the value of an infinite path in the MDP is the limsup (resp. liminf) of all rewards along the path. The value of an MDP is the maximal expected value of an infinite path that can be achieved by resolving the decisions of the MDP. Using our result on MDPs, we show that turn-based stochastic games with limsup and liminf objectives can be solved in NP ∩ coNP.
AU - Krishnendu Chatterjee
AU - Thomas Henzinger
ID - 3503
TI - Probabilistic systems with limsup and liminf objectives
VL - 5489
ER -
TY - GEN
AB - Ising models with pairwise interactions are the least structured, or maximum-entropy, probability distributions that exactly reproduce measured pairwise correlations between spins. Here we use this equivalence to construct Ising models that describe the correlated spiking activity of populations of 40 neurons in the salamander retina responding to natural movies. We show that pairwise interactions between neurons account for observed higher-order correlations, and that for groups of 10 or more neurons pairwise interactions can no longer be regarded as small perturbations in an independent system. We then construct network ensembles that generalize the network instances observed in the experiment, and study their thermodynamic behavior and coding capacity. Based on this construction, we can also create synthetic networks of 120 neurons, and find that with increasing size the networks operate closer to a critical point and start exhibiting collective behaviors reminiscent of spin glasses. We examine closely two such behaviors that could be relevant for neural code: tuning of the network to the critical point to maximize the ability to encode diverse stimuli, and using the metastable states of the Ising Hamiltonian as neural code words.
AU - Gasper Tkacik
AU - Schneidman, Elad
AU - Berry, Michael J
AU - Bialek, William S
ID - 3732
T2 - ArXiv
TI - Spin glass models for a network of real neurons
VL - q-bio.NC
ER -
TY - JOUR
AB - There is a close analogy between statistical thermodynamics and the evolution of allele frequencies under mutation, selection and random drift. Wright's formula for the stationary distribution of allele frequencies is analogous to the Boltzmann distribution in statistical physics. Population size, 2N, plays the role of the inverse temperature, 1/kT, and determines the magnitude of random fluctuations. Log mean fitness, View the MathML source, tends to increase under selection, and is analogous to a (negative) energy; a potential function, U, increases under mutation in a similar way. An entropy, SH, can be defined which measures the deviation from the distribution of allele frequencies expected under random drift alone; the sum View the MathML source gives a free fitness that increases as the population evolves towards its stationary distribution. Usually, we observe the distribution of a few quantitative traits that depend on the frequencies of very many alleles. The mean and variance of such traits are analogous to observable quantities in statistical thermodynamics. Thus, we can define an entropy, SΩ, which measures the volume of allele frequency space that is consistent with the observed trait distribution. The stationary distribution of the traits is View the MathML source; this applies with arbitrary epistasis and dominance. The entropies SΩ, SH are distinct, but converge when there are so many alleles that traits fluctuate close to their expectations. Populations tend to evolve towards states that can be realised in many ways (i.e., large SΩ), which may lead to a substantial drop below the adaptive peak; we illustrate this point with a simple model of genetic redundancy. This analogy with statistical thermodynamics brings together previous ideas in a general framework, and justifies a maximum entropy approximation to the dynamics of quantitative traits.
AU - Barton, Nicholas H
AU - Coe, Jason
ID - 3775
IS - 2
JF - Journal of Theoretical Biology
TI - On the application of statistical physics to evolutionary biology
VL - 259
ER -
TY - JOUR
AB - Why are sinistral snails so rare? Two main hypotheses are that selection acts against the establishment of new coiling morphs, because dextral and sinistral snails have trouble mating, or else a developmental constraint prevents the establishment of sinistrals. We therefore used an isolate of the snail Lymnaea stagnalis, in which sinistrals are rare, and populations of Partula suturalis, in which sinistrals are common, as well as a mathematical model, to understand the circumstances by which new morphs evolve. The main finding is that the sinistral genotype is associated with reduced egg viability in L. stagnalis, but in P. suturalis individuals of sinistral and dextral genotype appear equally fecund, implying a lack of a constraint. As positive frequency-dependent selection against the rare chiral morph in P. suturalis also operates over a narrow range (< 3%), the results suggest a model for chiral evolution in snails in which weak positive frequency-dependent selection may be overcome by a negative frequency-dependent selection, such as reproductive character displacement. In snails, there is not always a developmental constraint. As the direction of cleavage, and thus the directional asymmetry of the entire body, does not generally vary in other Spiralia (annelids, echiurans, vestimentiferans, sipunculids and nemerteans), it remains an open question as to whether this is because of a constraint and/or because most taxa do not have a conspicuous external asymmetry (like a shell) upon which selection can act.
AU - Davison, Angus
AU - Barton, Nicholas H
AU - Clarke, Bryan
ID - 3780
IS - 8
JF - Journal of Evolutionary Biology
TI - The effect of chirality phenotype and genotype on the fecundity and viability of Partula suturalis and Lymnaea stagnalis: Implications for the evolution of sinistral snails
VL - 22
ER -
TY - CONF
AB - In this paper we extend the work of Alfaro, Henzinger et al. on interface theories for component-based design. Existing interface theories often fail to capture functional relations between the inputs and outputs of an interface. For example, a simple synchronous interface that takes as input a number n ≥ 0 and returns, at the same time, as output n + 1, cannot be expressed in existing theories. In this paper we provide a theory of relational interfaces, where such input-output relations can be captured. Our theory supports synchronous interfaces, both stateless and stateful. It includes explicit notions of environments and pluggability, and satisfies fundamental properties such as preservation of refinement by composition, and characterization of pluggability by refinement. We achieve these properties by making reasonable restrictions on feedback loops in interface compositions.
AU - Tripakis, Stavros
AU - Lickly, Ben
AU - Henzinger, Thomas A
AU - Lee, Edward
ID - 3837
T2 - EMSOFT '09 Proceedings of the seventh ACM international conference on Embedded software
TI - On relational interfaces
ER -
TY - CONF
AB - We compare several languages for specifying Markovian population models such as queuing networks and chemical reaction networks. These languages —matrix descriptions, stochastic Petri nets, stoichiometric equations, stochastic process algebras, and guarded command models— all describe continuous-time Markov chains, but they differ according to important properties, such as compositionality, expressiveness and succinctness, executability, ease of use, and the support they provide for checking the well-formedness of a model and for analyzing a model.
AU - Henzinger, Thomas A
AU - Jobstmann, Barbara
AU - Wolf, Verena
ID - 3841
TI - Formalisms for specifying Markovian population models
VL - 5797
ER -
TY - CONF
AB - Within systems biology there is an increasing interest in the stochastic behavior of biochemical reaction networks. An appropriate stochastic description is provided by the chemical master equation, which represents a continuous- time Markov chain (CTMC).
Standard Uniformization (SU) is an efficient method for the transient analysis of CTMCs. For systems with very different time scales, such as biochemical reaction networks, SU is computationally expensive. In these cases, a variant of SU, called adaptive uniformization (AU), is known to reduce the large number of iterations needed by SU. The additional difficulty of AU is that it requires the solution of a birth process.
In this paper we present an on-the-fly variant of AU, where we improve the original algorithm for AU at the cost of a small approximation error. By means of several examples, we show that our approach is particularly well-suited for biochemical reaction networks.
AU - Didier, Frédéric
AU - Henzinger, Thomas A
AU - Mateescu, Maria
AU - Wolf, Verena
ID - 3843
IS - 6
TI - Fast adaptive uniformization of the chemical master equation
VL - 4
ER -
TY - CONF
AB - The Hierarchical Timing Language (HTL) is a real-time coordination language for distributed control systems. HTL programs must be checked for well-formedness, race freedom, transmission safety (schedulability of inter-host communication), and time safety (schedulability of host computation). We present a modular abstract syntax and semantics for HTL, modular checks of well-formedness, race freedom, and transmission safety, and modular code distribution. Our contributions here complement previous results on HTL time safety and modular code generation. Modularity in HTL can be utilized in easy program composition as well as fast program analysis and code generation, but also in so-called runtime patching, where program components may be modified at runtime.
AU - Henzinger, Thomas A
AU - Kirsch, Christoph
AU - Marques, Eduardo
AU - Sokolova, Ana
ID - 3844
TI - Distributed, modular HTL
ER -
TY - JOUR
AB - Games on graphs with omega-regular objectives provide a model for the control and synthesis of reactive systems. Every omega-regular objective can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens “eventually.” Two main strengths of the classical, infinite-limit formulation of liveness are robustness (independence from the granularity of transitions) and simplicity (abstraction of complicated time bounds). However, the classical liveness formulation suffers from the drawback that the time until something good happens may be unbounded. A stronger formulation of liveness, so-called finitary liveness, overcomes this drawback, while still retaining robustness and simplicity. Finitary liveness requires that there exists an unknown, fixed bound b such that something good happens within b transitions. While for one-shot liveness (reachability) objectives, classical and finitary liveness coincide, for repeated liveness (Buchi) objectives, the finitary formulation is strictly stronger. In this work we study games with finitary parity and Streett objectives. We prove the determinacy of these games, present algorithms for solving these games, and characterize the memory requirements of winning strategies. We show that finitary parity games can be solved in polynomial time, which is not known for infinitary parity games. For finitary Streett games, we give an EXPTIME algorithm and show that the problem is NP-hard. Our algorithms can be used, for example, for synthesizing controllers that do not let the response time of a system increase without bound.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Horn, Florian
ID - 3870
IS - 1
JF - ACM Transactions on Computational Logic (TOCL)
TI - Finitary winning in omega-regular games
VL - 11
ER -
TY - CONF
AB - Nondeterministic weighted automata are finite automata with numerical weights oil transitions. They define quantitative languages 1, that assign to each word v; a real number L(w). The value of ail infinite word w is computed as the maximal value of all runs over w, and the value of a run as the supremum, limsup liminf, limit average, or discounted sum of the transition weights. We introduce probabilistic weighted antomata, in which the transitions are chosen in a randomized (rather than nondeterministic) fashion. Under almost-sure semantics (resp. positive semantics), the value of a word v) is the largest real v such that the runs over w have value at least v with probability I (resp. positive probability). We study the classical questions of automata theory for probabilistic weighted automata: emptiness and universality, expressiveness, and closure under various operations oil languages. For quantitative languages, emptiness university axe defined as whether the value of some (resp. every) word exceeds a given threshold. We prove some, of these questions to he decidable, and others undecidable. Regarding expressive power, we show that probabilities allow its to define a wide variety of new classes of quantitative languages except for discounted-sum automata, where probabilistic choice is no more expressive than nondeterminism. Finally we live ail almost complete picture of the closure of various classes of probabilistic weighted automata for the following, provide, is operations oil quantitative languages: maximum, sum. and numerical complement.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
ID - 3871
TI - Probabilistic weighted automata
VL - 5710
ER -
TY - JOUR
AB - We compare anti-parasite defences at the level of multicellular organisms and insect societies, and find that selection by parasites at these two organisational levels is often very similar and has created a number of parallel evolutionary solutions in the host's immune response. The defence mechanisms of both individuals and insect colonies start with border defences to prevent parasite intake and are followed by soma defences that prevent the establishment and spread of the parasite between the body's cells or the social insect workers. Lastly, germ line defences are employed to inhibit infection of the reproductive tissue of organisms or the reproductive individuals in colonies. We further find sophisticated self/non-self-recognition systems operating at both levels, which appear to be vital in maintaining the integrity of the body or colony as a reproductive entity. We then expand on the regulation of immune responses and end with a contemplation of how evolution may shape the different immune components, both within and between levels. The aim of this review is to highlight common evolutionary principles acting in disease defence at the level of both individual organisms and societies, thereby linking the fields of physiological and ecological immunology.
AU - Cremer, Sylvia
AU - Sixt, Michael K
ID - 3946
IS - 1513
JF - Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences
TI - Analogies in the evolution of individual and social immunity
VL - 364
ER -
TY - CONF
AB - We describe an algorithm for segmenting three-dimensional medical imaging data modeled as a continuous function on a 3-manifold. It is related to watershed algorithms developed in image processing but is closer to its mathematical roots, which are Morse theory and homological algebra. It allows for the implicit treatment of an underlying mesh, thus combining the structural integrity of its mathematical foundations with the computational efficiency of image processing.
AU - Edelsbrunner, Herbert
AU - Harer, John
ID - 3968
TI - The persistent Morse complex segmentation of a 3-manifold
VL - 5903
ER -
TY - JOUR
AB - Populations living in a spatially and temporally changing environment can adapt to the changing optimum and/or migrate toward favorable habitats. Here we extend previous analyses with a static optimum to allow the environment to vary in time as well as in space. The model follows both population dynamics and the trait mean under stabilizing selection, and the outcomes can be understood by comparing the loads due to genetic variance, dispersal, and temporal change. With fixed genetic variance, we obtain two regimes: (1) adaptation that is uniform along the environmental gradient and that responds to the moving optimum as expected for panmictic populations and when the spatial gradient is sufficiently steep, and (2) a population with limited range that adapts more slowly than the environmental optimum changes in both time and space; the population therefore becomes locally extinct and migrates toward suitable habitat. We also use a population‐genetic model with many loci to allow genetic variance to evolve, and we show that the only solution now has uniform adaptation.
AU - Polechova, Jitka
AU - Barton, Nicholas H
AU - Marion, Glenn
ID - 4136
IS - 5
JF - American Naturalist
TI - Species' range: Adaptation in space and time
VL - 174
ER -
TY - JOUR
AB - Felsenstein distinguished two ways by which selection can directly strengthen isolation. First, a modifier that strengthens prezygotic isolation can be favored everywhere. This fits with the traditional view of reinforcement as an adaptation to reduce deleterious hybridization by strengthening assortative mating. Second, selection can favor association between different incompatibilities, despite recombination. We generalize this “two allele” model to follow associations among any number of incompatibilities, which may include both assortment and hybrid inviability. Our key argument is that this process, of coupling between incompatibilities, may be quite different from the usual view of reinforcement: strong isolation can evolve through the coupling of any kind of incompatibility, whether prezygotic or postzygotic. Single locus incompatibilities become coupled because associations between them increase the variance in compatibility, which in turn increases mean fitness if there is positive epistasis. Multiple incompatibilities, each maintained by epistasis, can become coupled in the same way. In contrast, a single-locus incompatibility can become coupled with loci that reduce the viability of haploid hybrids because this reduces harmful recombination. We obtain simple approximations for the limits of tight linkage, and strong assortment, and show how assortment alleles can invade through associations with other components of reproductive isolation.
AU - Barton, Nicholas H
AU - De Cara, Maria
ID - 4242
IS - 5
JF - Evolution; International Journal of Organic Evolution
TI - The evolution of strong reproductive isolation
VL - 63
ER -
TY - CONF
AB - Pseudo-code descriptions of STMs assume sequentially consistent program execution and atomicity of high-level STM operations like read, write, and commit. These assumptions are often violated in realistic settings, as STM implementations run on relaxed memory models, with the atomicity of operations as provided by the hardware. This paper presents the first approach to verify STMs under relaxed memory models with atomicity of 32 bit loads and stores, and read-modify-write operations. We present RML, a new high-level language for expressing concurrent algorithms with a hardware-level atomicity of instructions, and whose semantics is parametrized by various relaxed memory models. We then present our tool, FOIL, which takes as input the RML description of an STM algorithm and the description of a memory model, and automatically determines the locations of fences, which if inserted, ensure the correctness of the STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and McRT STM under the memory models of sequential consistency, total store order, partial store order, and relaxed memory order.
AU - Guerraoui, Rachid
AU - Thomas Henzinger
AU - Vasu Singh
ID - 4383
TI - Software transactional memory on relaxed memory models
VL - 5643
ER -
TY - CONF
AB - For programs whose data variables range over boolean or finite domains, program verification is decidable, and this forms the basis of recent tools for software model checking. In this paper, we consider algorithmic verification of programs that use boolean variables, and in addition, access a single read-only array whose length is potentially unbounded, and whose elements range over a potentially unbounded data domain. We show that the reachability problem, while undecidable in general, is (1) Pspace-complete for programs in which the array-accessing for-loops are not nested, (2) decidable for a restricted class of programs with doubly-nested loops. The second result establishes connections to automata and logics defining languages over data words.
AU - Alur, Rajeev
AU - Cerny, Pavol
AU - Weinstein, Scott
ID - 4403
TI - Algorithmic analysis of array-accessing programs
VL - 5771
ER -
TY - JOUR
AB - Nuclear-pore complexes (NPCs) are large protein channels that span the nuclear envelope (NE), which is a double membrane that encloses the nuclear genome of eukaryotes. Each of the typically 2,000–4,000 pores in the NE of vertebrate cells is composed of multiple copies of 30 different proteins known as nucleoporins. The evolutionarily conserved NPC proteins have the well-characterized function of mediating the transport of molecules between the nucleoplasm and the cytoplasm. Mutations in nucleoporins are often linked to specific developmental defects and disease, and the resulting phenotypes are usually interpreted as the consequences of perturbed nuclear transport activity. However, recent evidence suggests that NPCs have additional functions in chromatin organization and gene regulation, some of which might be independent of nuclear transport. Here, we review the transport-dependent and transport-independent roles of NPCs in the regulation of nuclear function and gene expression.
AU - Capelson, Maya
AU - HETZER, Martin W
ID - 11105
IS - 7
JF - EMBO reports
KW - Genetics
KW - Molecular Biology
KW - Biochemistry
SN - 1469-221X
TI - The role of nuclear pores in gene regulation, development and disease
VL - 10
ER -
TY - JOUR
AB - Nucleocytoplasmic transport occurs exclusively through nuclear pore complexes (NPCs) embedded in pores formed by inner and outer nuclear membrane fusion. The mechanism for de novo pore and NPC biogenesis remains unclear. Reticulons (RTNs) and Yop1/DP1 are conserved membrane protein families required to form and maintain the tubular endoplasmic reticulum (ER) and the postmitotic nuclear envelope. In this study, we report that members of the RTN and Yop1/DP1 families are required for nuclear pore formation. Analysis of Saccharomyces cerevisiae prp20-G282S and nup133Δ NPC assembly mutants revealed perturbations in Rtn1–green fluorescent protein (GFP) and Yop1-GFP ER distribution and colocalization to NPC clusters. Combined deletion of RTN1 and YOP1 resulted in NPC clustering, nuclear import defects, and synthetic lethality with the additional absence of Pom34, Pom152, and Nup84 subcomplex members. We tested for a direct role in NPC biogenesis using Xenopus laevis in vitro assays and found that anti-Rtn4a antibodies specifically inhibited de novo nuclear pore formation. We hypothesize that these ER membrane–bending proteins mediate early NPC assembly steps.
AU - Dawson, T. Renee
AU - Lazarus, Michelle D.
AU - HETZER, Martin W
AU - Wente, Susan R.
ID - 11107
IS - 5
JF - Journal of Cell Biology
KW - Cell Biology
SN - 0021-9525
TI - ER membrane–bending proteins are necessary for de novo nuclear pore formation
VL - 184
ER -
TY - JOUR
AB - Over the last decade, the nuclear envelope (NE) has emerged as a key component in the organization and function of the nuclear genome. As many as 100 different proteins are thought to specifically localize to this double membrane that separates the cytoplasm and the nucleoplasm of eukaryotic cells. Selective portals through the NE are formed at sites where the inner and outer nuclear membranes are fused, and the coincident assembly of ∼30 proteins into nuclear pore complexes occurs. These nuclear pore complexes are essential for the control of nucleocytoplasmic exchange. Many of the NE and nuclear pore proteins are thought to play crucial roles in gene regulation and thus are increasingly linked to human diseases.
AU - HETZER, Martin W
AU - Wente, Susan R.
ID - 11103
IS - 5
JF - Developmental Cell
KW - Developmental Biology
KW - Cell Biology
KW - General Biochemistry
KW - Genetics and Molecular Biology
KW - Molecular Biology
SN - 1534-5807
TI - Border control at the nucleus: Biogenesis and organization of the nuclear membrane and pore complexes
VL - 17
ER -
TY - JOUR
AB - In dividing cells, nuclear pore complexes (NPCs) disassemble during mitosis and reassemble into the newly forming nuclei. However, the fate of nuclear pores in postmitotic cells is unknown. Here, we show that NPCs, unlike other nuclear structures, do not turn over in differentiated cells. While a subset of NPC components, like Nup153 and Nup50, are continuously exchanged, scaffold nucleoporins, like the Nup107/160 complex, are extremely long-lived and remain incorporated in the nuclear membrane during the entire cellular life span. Besides the lack of nucleoporin expression and NPC turnover, we discovered an age-related deterioration of NPCs, leading to an increase in nuclear permeability and the leaking of cytoplasmic proteins into the nucleus. Our finding that nuclear “leakiness” is dramatically accelerated during aging and that a subset of nucleoporins is oxidatively damaged in old cells suggests that the accumulation of damage at the NPC might be a crucial aging event.
AU - D'Angelo, Maximiliano A.
AU - Raices, Marcela
AU - Panowski, Siler H.
AU - HETZER, Martin W
ID - 11108
IS - 2
JF - Cell
KW - General Biochemistry
KW - Genetics and Molecular Biology
SN - 0092-8674
TI - Age-dependent deterioration of nuclear pore complexes causes a loss of nuclear integrity in postmitotic cells
VL - 136
ER -
TY - JOUR
AB - Formation of the nuclear envelope (NE) around segregated chromosomes occurs by the reshaping of the endoplasmic reticulum (ER), a reservoir for disassembled nuclear membrane components during mitosis. In this study, we show that inner nuclear membrane proteins such as lamin B receptor (LBR), MAN1, Lap2β, and the trans-membrane nucleoporins Ndc1 and POM121 drive the spreading of ER membranes into the emerging NE via their capacity to bind chromatin in a collaborative manner. Despite their redundant functions, decreasing the levels of any of these trans-membrane proteins by RNAi-mediated knockdown delayed NE formation, whereas increasing the levels of any of them had the opposite effect. Furthermore, acceleration of NE formation interferes with chromosome separation during mitosis, indicating that the time frame over which chromatin becomes membrane enclosed is physiologically relevant and regulated. These data suggest that functionally distinct classes of chromatin-interacting membrane proteins, which are present at nonsaturating levels, collaborate to rapidly reestablish the nuclear compartment at the end of mitosis.
AU - Anderson, Daniel J.
AU - Vargas, Jesse D.
AU - Hsiao, Joshua P.
AU - HETZER, Martin W
ID - 11106
IS - 2
JF - Journal of Cell Biology
KW - Cell Biology
SN - 0021-9525
TI - Recruitment of functionally distinct membrane proteins to chromatin mediates nuclear envelope formation in vivo
VL - 186
ER -
TY - JOUR
AU - Feraru, Elena
AU - Friml, Jirí
ID - 3037
IS - 4
JF - Plant Physiology
TI - PIN polar targeting
VL - 147
ER -
TY - JOUR
AB - A complete mitochondrial (mt) genome sequence was reconstructed from a 38,000 year-old Neandertal individual with 8341 mtDNA sequences identified among 4.8 Gb of DNA generated from ∼0.3 g of bone. Analysis of the assembled sequence unequivocally establishes that the Neandertal mtDNA falls outside the variation of extant human mtDNAs, and allows an estimate of the divergence date between the two mtDNA lineages of 660,000 ± 140,000 years. Of the 13 proteins encoded in the mtDNA, subunit 2 of cytochrome c oxidase of the mitochondrial electron transport chain has experienced the largest number of amino acid substitutions in human ancestors since the separation from Neandertals. There is evidence that purifying selection in the Neandertal mtDNA was reduced compared with other primate lineages, suggesting that the effective population size of Neandertals was small.
AU - Green, Richard E
AU - Malaspinas, Anna-Sapfo
AU - Krause, Johannes
AU - Briggs, Adrian W
AU - Johnson, Philip L
AU - Caroline Uhler
AU - Meyer, Matthias
AU - Good, Jeffrey M
AU - Maricic, Tomislav
AU - Stenzel, Udo
AU - Prüfer, Kay
AU - Siebauer, Michael F
AU - Burbano, Hernän A
AU - Ronan, Michael T
AU - Rothberg, Jonathan M
AU - Egholm, Michael
AU - Rudan, Pavao
AU - Brajković, Dejana
AU - Kućan, Željko
AU - Gušić, Ivan
AU - Wikström, Mårten K
AU - Laakkonen, Liisa J
AU - Kelso, Janet F
AU - Slatkin, Montgomery
AU - Pääbo, Svante H
ID - 3307
JF - Cell
TI - A complete neandertal mitochondrial genome sequence determined by highhhroughput sequencing
VL - 134
ER -
TY - JOUR
AB - The field of cavity quantum electrodynamics (QED), traditionally studied in atomic systems, has gained new momentum by recent reports of quantum optical experiments with solid-state semiconducting and superconducting systems. In cavity QED, the observation of the vacuum Rabi mode splitting is used to investigate the nature of matter-light interaction at a quantum-mechanical level. However, this effect can, at least in principle, be explained classically as the normal mode splitting of two coupled linear oscillators. It has been suggested that an observation of the scaling of the resonant atom-photon coupling strength in the Jaynes-Cummings energy ladder with the square root of photon number n is sufficient to prove that the system is quantum mechanical in nature. Here we report a direct spectroscopic observation of this characteristic quantum nonlinearity. Measuring the photonic degree of freedom of the coupled system, our measurements provide unambiguous spectroscopic evidence for the quantum nature of the resonant atom-field interaction in cavity QED. We explore atom-photon superposition states involving up to two photons, using a spectroscopic pump and probe technique. The experiments have been performed in a circuit QED set-up, in which very strong coupling is realized by the large dipole coupling strength and the long coherence time of a superconducting qubit embedded in a high-quality on-chip microwave cavity. Circuit QED systems also provide a natural quantum interface between flying qubits (photons) and stationary qubits for applications in quantum information processing and communication.
AU - Johannes Fink
AU - Göppl, M
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Leek, Peter J
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1763
IS - 7202
JF - Nature
TI - Climbing the Jaynes-Cummings ladder and observing its √n nonlinearity in a cavity QED system
VL - 454
ER -
TY - JOUR
AB - High quality on-chip microwave resonators have recently found prominent new applications in quantum optics and quantum information processing experiments with superconducting electronic circuits, a field now known as circuit quantum electrodynamics (QED). They are also used as single photon detectors and parametric amplifiers. Here we analyze the physical properties of coplanar waveguide resonators and their relation to the materials properties for use in circuit QED. We have designed and fabricated resonators with fundamental frequencies from 2 to 9 GHz and quality factors ranging from a few hundreds to a several hundred thousands controlled by appropriately designed input and output coupling capacitors. The microwave transmission spectra measured at temperatures of 20 mK are shown to be in good agreement with theoretical lumped element and distributed element transmission matrix models. In particular, the experimentally determined resonance frequencies, quality factors, and insertion losses are fully and consistently explained by the two models for all measured devices. The high level of control and flexibility in design renders these resonators ideal for storing and manipulating quantum electromagnetic fields in integrated superconducting electronic circuits.
AU - Göppl, M
AU - Fragner, A
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Filipp, Stefan
AU - Johannes Fink
AU - Leek, Peter J
AU - Puebla, G
AU - Steffen, L. Kraig
AU - Wallraff, Andreas
ID - 1765
IS - 11
JF - Journal of Applied Physics
TI - Coplanar waveguide resonators for circuit quantum electrodynamics
VL - 104
ER -
TY - JOUR
AB - Homeostasis of internal carbon dioxide (CO2) and oxygen (O2) levels is fundamental to all animals. Here we examine the CO2 response of the nematode Caenorhabditis elegans. This species inhabits rotting material, which typically has a broad CO2 concentration range. We show that well fed C. elegans avoid CO2 levels above 0.5%. Animals can respond to both absolute CO2 concentrations and changes in CO2 levels within seconds. Responses to CO2 do not reflect avoidance of acid pH but appear to define a new sensory response. Sensation of CO2 is promoted by the cGMP-gated ion channel subunits TAX-2 and TAX-4, but other pathways are also important. Robust CO2 avoidance in well fed animals requires inhibition of the DAF-16 forkhead transcription factor by the insulin-like receptor DAF-2. Starvation, which activates DAF-16, strongly suppresses CO2 avoidance. Exposure to hypoxia (<1% O2) also suppresses CO2 avoidance via activation of the hypoxia-inducible transcription factor HIF-1. The npr-1 215V allele of the naturally polymorphic neuropeptide receptor npr-1, besides inhibiting avoidance of high ambient O2 in feeding C. elegans, also promotes avoidance of high CO2. C. elegans integrates competing O2 and CO2 sensory inputs so that one response dominates. Food and allelic variation at NPR-1 regulate which response prevails. Our results suggest that multiple sensory inputs are coordinated by C. elegans to generate different coherent foraging strategies.
AU - Bretscher, A. J.
AU - Busch, K. E.
AU - de Bono, Mario
ID - 6146
IS - 23
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - A carbon dioxide avoidance behavior is integrated with responses to ambient oxygen and food in Caenorhabditis elegans
VL - 105
ER -
TY - JOUR
AB - We calculate the E-polynomials of certain twisted GL(n,ℂ)-character varieties Mn of Riemann surfaces by counting points over finite fields using the character table of the finite group of Lie-type GL(n, q) and a theorem proved in the appendix by N. Katz. We deduce from this calculation several geometric results, for example, the value of the topological Euler characteristic of the associated PGL(n,ℂ)-character variety. The calculation also leads to several conjectures about the cohomology of Mn: an explicit conjecture for its mixed Hodge polynomial; a conjectured curious hard Lefschetz theorem and a conjecture relating the pure part to absolutely indecomposable representations of a certain quiver. We prove these conjectures for n=2.
AU - Tamas Hausel
AU - Rodríguez Villegas, Fernando
ID - 1460
IS - 3
JF - Inventiones Mathematicae
TI - Mixed Hodge polynomials of character varieties: With an appendix by Nicholas M. Katz
VL - 174
ER -
TY - JOUR
AB - We report on the control of interaction-induced dephasing of Bloch oscillations for an atomic Bose-Einstein condensate in an optical lattice. We quantify the dephasing in terms of the width of the quasimomentum distribution and measure its dependence on time for different interaction strengths which we control by means of a Feshbach resonance. For minimal interaction, the dephasing time is increased from a few to more than 20 thousand Bloch oscillation periods, allowing us to realize a BEC-based atom interferometer in the noninteracting limit.
AU - Gustavsson, Mattias
AU - Haller, Elmar
AU - Mark, Manfred
AU - Danzl, Johann G
AU - Rojas Kopeinig, Gabriel
AU - Nägerl, Hanns
ID - 1036
IS - 8
JF - Physical Review Letters
TI - Control of interaction-induced dephasing of bloch oscillations
VL - 100
ER -
TY - JOUR
AB - We experimentally demonstrate Cs2 Feshbach molecules well above the dissociation threshold, which are stable against spontaneous decay on the time scale of 1s. An optically trapped sample of ultracold dimers is prepared in a high rotational state and magnetically tuned into a region with a negative binding energy. The metastable character of these molecules arises from the large centrifugal barrier in combination with negligible coupling to states with low rotational angular momentum. A sharp onset of dissociation with increasing magnetic field is mediated by a crossing with a lower rotational dimer state and facilitates dissociation on demand with a well-defined energy.
AU - Knoop, Steven
AU - Mark, Michael
AU - Ferlaino, Francesca
AU - Danzl, Johann G
AU - Kraemer, Tobias
AU - Nägerl, Hanns
AU - Grimm, Rudolf
ID - 1037
IS - 8
JF - Physical Review Letters
TI - Metastable feshbach molecules in high rotational states
VL - 100
ER -
TY - JOUR
AB - Molecular cooling techniques face the hurdle of dissipating translational as well as internal energy in the presence of a rich electronic, vibrational, and rotational energy spectrum. In our experiment, we create a translationally ultracold, dense quantum gas of molecules bound by more than 1000 wave numbers in the electronic ground state. Specifically, we stimulate with 80% efficiency, a two-photon transfer of molecules associated on a Feshbach resonance from a Bose-Einstein condensate of cesium atoms. In the process, the initial loose, long-range electrostatic bond of the Feshbach molecule is coherently transformed into a tight chemical bond. We demonstrate coherence of the transfer in a Ramsey-type experiment and show that the molecular sample is not heated during the transfer. Our results show that the preparation of a quantum gas of molecules in specific rovibrational states is possible and that the creation of a Bose-Einstein condensate of molecules in their rovibronic ground state is within reach.
AU - Danzl, Johann G
AU - Haller, Elmar
AU - Gustavsson, Mattias
AU - Mark, Manfred
AU - Hart, Russell
AU - Bouloufa, Nadia
AU - Dulieu, Olivier
AU - Ritsch, Helmut
AU - Nägerl, Hanns
ID - 1039
IS - 5892
JF - Science
TI - Quantum gas of deeply bound ground state molecules
VL - 321
ER -
TY - JOUR
AB - We consider the linear stochastic Cauchy problem dX (t) =AX (t) dt +B dWH (t), t≥ 0, where A generates a C0-semigroup on a Banach space E, WH is a cylindrical Brownian motion over a Hilbert space H, and B: H → E is a bounded operator. Assuming the existence of a unique minimal invariant measure μ∞, let Lp denote the realization of the Ornstein-Uhlenbeck operator associated with this problem in Lp (E, μ∞). Under suitable assumptions concerning the invariance of the range of B under the semigroup generated by A, we prove the following domain inclusions, valid for 1 < p ≤ 2: Image omitted. Here WHk, p (E, μinfin; denotes the kth order Sobolev space of functions with Fréchet derivatives up to order k in the direction of H. No symmetry assumptions are made on L p.
AU - Jan Maas
AU - van Neerven, Jan M
ID - 2120
IS - 4
JF - Infinite Dimensional Analysis, Quantum Probability and Related Topics
TI - On the domain of non-symmetric Ornstein-Uhlenbeck operators in banach spaces
VL - 11
ER -
TY - JOUR
AB - Let H be a separable real Hubert space and let double struck F sign = (ℱt)t∈[0,T] be the augmented filtration generated by an H-cylindrical Brownian motion (WH(t))t∈[0,T] on a probability space (Ω, ℱ ℙ). We prove that if E is a UMD Banach space, 1 ≤ p < ∞, and F ∈ double struck D sign1,p(Ω E) is ℱT-measurable, then F = double struck E sign(F) + ∫0T Pdouble struck F sign(DF) dW H, where D is the Malliavin derivative of F and P double struck F sign is the projection onto the F-adapted elements in a suitable Banach space of Lp-stochastically integrable ℒ(H, E)-valued processes.
AU - van Neerven, Jan M
AU - Jan Maas
ID - 2121
JF - Electronic Communications in Probability
TI - A Clark-Ocone formula in UMD Banach spaces
VL - 13
ER -
TY - JOUR
AB - We present an analytic model of thermal state-to-state rotationally inelastic collisions of polar molecules in electric fields. The model is based on the Fraunhofer scattering of matter waves and requires Legendre moments characterizing the “shape” of the target in the body-fixed frame as its input. The electric field orients the target in the space-fixed frame and thereby effects a striking alteration of the dynamical observables: both the phase and amplitude of the oscillations in the partial differential cross sections undergo characteristic field-dependent changes that transgress into the partial integral cross sections. As the cross sections can be evaluated for a field applied parallel or perpendicular to the relative velocity, the model also offers predictions about steric asymmetry. We exemplify the field-dependent quantum collision dynamics with the behavior of the Ne–OCS(Σ1) and Ar–NO(Π2) systems. A comparison with the close-coupling calculations available for the latter system [Chem. Phys. Lett.313, 491 (1999)] demonstrates the model’s ability to qualitatively explain the field dependence of all the scattering features observed.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2146
IS - 2
JF - Journal of Chemical Physics
TI - An analytic model of rotationally inelastic collisions of polar molecules in electric fields
VL - 129
ER -
TY - CONF
AB - We present a review of recent work on the mathematical aspects of the BCS gap equation, covering our results of Ref. 9 as well our recent joint work with Hamza and Solovej and with Frank and Naboko, respectively. In addition, we mention some related new results.
AU - Hainzl, Christian
AU - Robert Seiringer
ID - 2331
TI - Spectral properties of the BCS gap equation of superfluidity
ER -