@inproceedings{4375, author = {Lahiri,Shuvendu K. and Qadeer,Shaz and Galeotti,Juan P. and Voung,Jan W. and Thomas Wies}, pages = {493 -- 508}, publisher = {Springer}, title = {{Intra-module Inference}}, doi = {1555}, year = {2009}, } @inproceedings{4376, author = {Lublinerman,Roberto and Chaudhuri,Swarat and Pavol Cerny}, pages = {61 -- 80}, publisher = {ACM}, title = {{Parallel programming with object assemblies}}, doi = {1546}, year = {2009}, } @inproceedings{4377, author = {Hoenicke,Jochen and Leino, K Rustan and Podelski,Andreas and Schäf,Martin and Thomas Wies}, pages = {338 -- 353}, publisher = {Springer}, title = {{It's Doomed; We Can Prove It}}, doi = {1557}, year = {2009}, } @inproceedings{4383, abstract = {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.}, author = {Guerraoui, Rachid and Thomas Henzinger and Vasu Singh}, pages = {321 -- 336}, publisher = {Springer}, title = {{Software transactional memory on relaxed memory models}}, doi = {10.1007/978-3-642-02658-4_26}, volume = {5643}, year = {2009}, } @inproceedings{4385, author = {Dragojevic,Aleksandar and Guerraoui, Rachid and Singh, Anmol V and Vasu Singh}, pages = {7 -- 16}, publisher = {ACM}, title = {{Preventing versus curing: avoiding conflicts in transactional memories}}, doi = {1533}, year = {2009}, } @inproceedings{4391, author = {Pavol Cerny and Alur, Rajeev}, pages = {173 -- 187}, publisher = {Springer}, title = {{Automated Analysis of Java Methods for Confidentiality}}, doi = {1548}, year = {2009}, } @inproceedings{4403, abstract = {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.}, author = {Alur, Rajeev and Cerny, Pavol and Weinstein, Scott}, location = {Coimbra, Portugal}, pages = {86 -- 101}, publisher = {Springer}, title = {{Algorithmic analysis of array-accessing programs}}, doi = {10.1007/978-3-642-04027-6_9}, volume = {5771}, year = {2009}, } @inproceedings{4453, abstract = {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.}, author = {Thomas Henzinger and Maria Mateescu and Wolf, Verena}, pages = {337 -- 352}, publisher = {Springer}, title = {{Sliding-window abstraction for infinite Markov chains}}, doi = {10.1007/978-3-642-02658-4_27}, volume = {5643}, year = {2009}, } @inproceedings{4535, abstract = {Molecular noise, which arises from the randomness of the discrete events in the cell, significantly influences fundamental biological processes. Discrete -state continuous-time stochastic models (CTMC) can be used to describe such effects, but the calculation of the probabilities of certain events is computationally expensive. We present a comparison of two analysis approaches for CTMC. On one hand, we estimate the probabilities of interest using repeated Gillespie simulation and determine the statistical accuracy that we obtain. On the other hand, we apply a numerical reachability analysis that approximates the probability distributions of the system at several time instances. We use examples of cellular processes to demonstrate the superiority of the reachability analysis if accurate results are required.}, author = {Didier, Frédéric and Thomas Henzinger and Maria Mateescu and Wolf, Verena}, pages = {173 -- 188}, publisher = {Springer}, title = {{Approximation of event probabilities in noisy cellular processes}}, doi = {10.1007/978-3-642-03845-7_12}, volume = {5688}, year = {2009}, } @inproceedings{4540, abstract = {Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the maximum, limsup, liminf, limit average, or discounted sum of the transition weights. We study expressiveness and closure questions about these quantitative languages. We first show that the set of words with value greater than a threshold can be non-w-regular for deterministic limit-average and discounted-sum automata, while this set is always w-regular when the threshold is isolated (i.e., some neighborhood around the threshold contains no word). In the latter case, we prove that the w-regular language is robust against small perturbations of the transition weights. We next consider automata with transition weights 0 or 1 and show that they are as expressive as general weighted automata in the limit-average case, but not in the discounted-sum case. Third, for quantitative languages L-1 and L-2, we consider the operations max(L-1, L-2), min(L-1, L-2), and 1-L-1, which generalize the boolean operations on languages, as well as the sum L-1 + L-2. We establish the closure properties of all classes of quantitative languages with respect to these four operations.}, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, pages = {199 -- 208}, publisher = {IEEE}, title = {{Expressiveness and closure properties for quantitative languages}}, doi = {10.1109/LICS.2009.16}, year = {2009}, } @inproceedings{4542, abstract = {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.}, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, location = {Wroclaw, Poland}, pages = {3 -- 13}, publisher = {Springer}, title = {{Alternating weighted automata}}, doi = {10.1007/978-3-642-03409-1_2}, volume = {5699}, year = {2009}, } @inproceedings{4543, abstract = {The synthesis of a reactive system with respect to all omega-regular specification requires the solution of a graph game. Such games have been extended in two natural ways. First, a game graph can be equipped with probabilistic choices between alternative transitions, thus allowing the, modeling of uncertain behaviour. These are called stochastic games. Second, a liveness specification can he strengthened to require satisfaction within all unknown but bounded amount of time. These are called finitary objectives. We study. for the first time, the, combination of Stochastic games and finitary objectives. We characterize the requirements on optimal strategies and provide algorithms for Computing the maximal achievable probability of winning stochastic games with finitary parity or Street, objectives. Most notably the set of state's from which a player can win with probability . for a finitary parity objective can he computed in polynomial time even though no polynomial-time algorithm is known in the nonfinitary case.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Horn, Florian}, location = {High Tatras, Slovakia}, pages = {34 -- 54}, publisher = {Springer}, title = {{Stochastic games with finitary objectives}}, doi = {10.1007/978-3-642-03816-7_4}, volume = {5734}, year = {2009}, } @inproceedings{4544, abstract = {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.}, author = {Krishnendu Chatterjee and de Alfaro, Luca and Thomas Henzinger}, pages = {197 -- 206}, publisher = {SIAM}, title = {{Termination criteria for solving concurrent safety and reachability games}}, doi = {10.1137/1.9781611973068.23}, year = {2009}, } @inproceedings{4545, abstract = {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. }, author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A}, location = {Rhodos, Greece}, pages = {1 -- 15}, publisher = {Springer}, title = {{A survey of stochastic games with limsup and liminf objectives}}, doi = {10.1007/978-3-642-02930-1_1}, volume = {5556}, year = {2009}, } @inproceedings{4569, abstract = {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.}, author = {Bloem, Roderick and Chatterjee, Krishnendu and Henzinger, Thomas A and Jobstmann, Barbara}, location = {Grenoble, France}, pages = {140 -- 156}, publisher = {Springer}, title = {{Better quality in synthesis through quantitative objectives}}, doi = {10.1007/978-3-642-02658-4_14}, volume = {5643}, year = {2009}, } @inproceedings{4580, abstract = {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.}, author = {Berwanger, Dietmar and Krishnendu Chatterjee and De Wulf, Martin and Doyen, Laurent and Thomas Henzinger}, pages = {58 -- 61}, publisher = {Springer}, title = {{Alpaga: A tool for solving parity games with imperfect information}}, doi = {10.1007/978-3-642-00768-2_7}, volume = {5505}, year = {2009}, } @article{12656, abstract = {We use meteorological data from two automatic weather stations (AWS) on Juncal Norte Glacier, central Chile, to investigate the glacier–climate interaction and to test ablation models of different complexity. The semi-arid Central Andes are characterized by dry summers, with precipitation close to zero, low relative humidity and intense solar radiation. We show that katabatic forcing is dominant both on the glacier tongue and in the fore field, and that low humidity and absence of clouds cause strong radiative cooling of the glacier surface. Surface albedo is basically constant for snow and ice, because of the scarcity of solid precipitation. The energy balance of the glacier is simulated for a 2-month period in austral summer using two models of different complexity, which differ in the inclusion of the heat conduction flux into the snowpack and in the parameterization of the incoming longwave radiation. Net shortwave radiation is the dominant component of the energy balance. The sensible heat flux is always positive, while both the net longwave radiation and latent heat flux are negative. Neglecting the subsurface heat flux and corresponding variations in surface temperature leads to an overestimation of ablation of 2% over a total of 3695 mm water equivalent (w.e.) at the end of the season. Correct modelling of incoming longwave radiation is crucial, and we suggest that parameterizations based on vapour pressure and air temperature should be used rather than on computed cloud amount. We also used an enhanced temperature-index model incorporating the shortwave radiation flux, which has two empirical parameters. We apply it both with values of parameters obtained for Alpine glaciers and recalibrated on Juncal Norte. The model recalibrated against the correct energy balance simulations performs very well. The model parameters respond to the meteorological conditions typical of this climatic setting.}, author = {Pellicciotti, Francesca and Helbing, Jakob and Rivera, Andrés and Favier, Vincent and Corripio, Javier and Araos, José and Sicart, Jean-Emmanuel and Carenzo, Marco}, issn = {1099-1085}, journal = {Hydrological Processes}, keywords = {Water Science and Technology}, number = {19}, pages = {3980--3997}, publisher = {Wiley}, title = {{A study of the energy balance and melt regime on Juncal Norte Glacier, semi-arid Andes of central Chile, using melt models of different complexity}}, doi = {10.1002/hyp.7085}, volume = {22}, year = {2008}, } @article{1296, abstract = {The crystalline-like structure of the optic lobes of the fruit fly Drosophila melanogaster has made them a model system for the study of neuronal cell-fate determination, axonal path finding, and target selection. For functional studies, however, the small size of the constituting visual interneurons has so far presented a formidable barrier. We have overcome this problem by establishing in vivo whole-cell recordings [1] from genetically targeted visual interneurons of Drosophila. Here, we describe the response properties of six motion-sensitive large-field neurons in the lobula plate that form a network consisting of individually identifiable, directionally selective cells most sensitive to vertical image motion (VS cells [2, 3]). Individual VS cell responses to visual motion stimuli exhibit all the characteristics that are indicative of presynaptic input from elementary motion detectors of the correlation type [4, 5]. Different VS cells possess distinct receptive fields that are arranged sequentially along the eye's azimuth, corresponding to their characteristic cellular morphology and position within the retinotopically organized lobula plate. In addition, lateral connections between individual VS cells cause strongly overlapping receptive fields that are wider than expected from their dendritic input. Our results suggest that motion vision in different dipteran fly species is accomplished in similar circuitries and according to common algorithmic rules. The underlying neural mechanisms of population coding within the VS cell network and of elementary motion detection, respectively, can now be analyzed by the combination of electrophysiology and genetic intervention in Drosophila.}, author = {Maximilian Jösch and Plett, Johannes and Borst, Alexander and Reiff, Dierk F}, journal = {Current Biology}, number = {5}, pages = {368 -- 374}, publisher = {Cell Press}, title = {{Response properties of motion sensitive visual interneurons in the Lobula plate of Drosophila melanogaster}}, doi = {10.1016/j.cub.2008.02.022}, volume = {18}, year = {2008}, } @article{844, abstract = {Mutation rate varies greatly between nucleotide sites of the human genome and depends both on the global genomic location and the local sequence context of a site. In particular, CpG context elevates the mutation rate by an order of magnitude. Mutations also vary widely in their effect on the molecular function, phenotype, and fitness. Independence of the probability of occurrence of a new mutation's effect has been a fundamental premise in genetics. However, highly mutable contexts may be preserved by negative selection at important sites but destroyed by mutation at sites under no selection. Thus, there may be a positive correlation between the rate of mutations at a nucleotide site and the magnitude of their effect on fitness. We studied the impact of CpG context on the rate of human-chimpanzee divergence and on intrahuman nucleotide diversity at non-synonymous coding sites. We compared nucleotides that occupy identical positions within codons of identical amino acids and only differ by being within versus outside CpG context. Nucleotides within CpG context are under a stronger negative selection, as revealed by their lower, proportionally to the mutation rate, rate of evolution and nucleotide diversity. In particular, the probability of fixation of a non-synonymous transition at a CpG site is two times lower than at a CpG site. Thus, sites with different mutation rates are not necessarily selectively equivalent. This suggests that the mutation rate may complement sequence conservation as a characteristic predictive of functional importance of nucleotide sites.}, author = {Schmidt, Steffen and Gerasimova, Anna and Fyodor Kondrashov and Adzuhbei, Ivan A and Kondrashov, Alexey S and Sunyaev, Shamil R}, journal = {PLoS Genetics}, number = {11}, publisher = {Public Library of Science}, title = {{Hypermutable non-synonymous sites are under stronger negative selection}}, doi = {10.1371/journal.pgen.1000281}, volume = {4}, year = {2008}, } @article{8480, abstract = {The KIX domain of the transcription co-activator CBP is a three-helix bundle protein that folds via rapid accumulation of an intermediate state, followed by a slower folding phase. Recent NMR relaxation dispersion studies revealed the presence of a low-populated (excited) state of KIX that exists in equilibrium with the natively folded form under non-denaturing conditions, and likely represents the equilibrium analog of the folding intermediate. Here, we combine amide hydrogen/deuterium exchange measurements using rapid NMR data acquisition techniques with backbone 15N and 13C relaxation dispersion experiments to further investigate the equilibrium folding of the KIX domain. Residual structure within the folding intermediate is detected by both methods, and their combination enables reliable quantification of the amount of persistent residual structure. Three well-defined folding subunits are found, which display variable stability and correspond closely to the individual helices in the native state. While two of the three helices (α2 and α3) are partially formed in the folding intermediate (to ∼ 50% and ∼ 80%, respectively, at 20 °C), the third helix is disordered. The observed helical content within the excited state exceeds the helical propensities predicted for the corresponding peptide regions, suggesting that the two helices are weakly mutually stabilized, while methyl 13C relaxation dispersion data indicate that a defined packing arrangement is unlikely. Temperature-dependent experiments reveal that the largest enthalpy and entropy changes along the folding reaction occur during the final transition from the intermediate to the native state. Our experimental data are consistent with a folding mechanism where helices α2 and α3 form rapidly, although to different extents, while helix α1 consolidates only as folding proceeds to complete the native state-structure.}, author = {Schanda, Paul and Brutscher, Bernhard and Konrat, Robert and Tollinger, Martin}, issn = {0022-2836}, journal = {Journal of Molecular Biology}, keywords = {Molecular Biology}, number = {4}, pages = {726--741}, publisher = {Elsevier}, title = {{Folding of the KIX domain: Characterization of the equilibrium analog of a folding intermediate using 15N/13C relaxation dispersion and fast 1H/2H amide exchange NMR spectroscopy}}, doi = {10.1016/j.jmb.2008.05.040}, volume = {380}, year = {2008}, }