@inproceedings{4368, author = {Dejan Nickovic and Maler, Oded}, pages = {304 -- 319}, publisher = {Springer}, title = {{AMT: a property-based monitoring tool for analog systems}}, doi = {1567}, year = {2007}, } @inproceedings{4370, author = {Maler, Oded and Dejan Nickovic and Pnueli,Amir}, pages = {95 -- 107}, publisher = {Springer}, title = {{On synthesizing controllers from bounded-response properties}}, doi = {1568}, year = {2007}, } @inproceedings{4394, author = {Bouillaguet,Charles and Kuncak, Viktor and Thomas Wies and Zee,Karen and Rinard,Martin C.}, pages = {74 -- 88}, publisher = {Springer}, title = {{Using First-Order Theorem Provers in the Jahob Data Structure Verification System}}, doi = {1552}, year = {2007}, } @inproceedings{4398, author = {Berdine,Josh and Calcagno,Cristiano and Cook,Byron and Distefano,Dino and O'Hearn,Peter W. and Thomas Wies and Yang,Hongseok}, pages = {178 -- 192}, publisher = {Springer}, title = {{Shape Analysis for Composite Data Structures}}, doi = {1553}, year = {2007}, } @inproceedings{4399, abstract = {A temporal interface for a software component is a finite automaton that specifies the legal sequences of calls to functions that are provided by the component. We compare and evaluate three different algorithms for automatically extracting temporal interfaces from program code: (1) a game algorithm that computes the interface as a representation of the most general environment strategy to avoid a safety violation; (2) a learning algorithm that repeatedly queries the program to construct the minimal interface automaton; and (3) a CEGAR algorithm that iteratively refines an abstract interface hypothesis by adding relevant program variables. For comparison purposes, we present and implement the three algorithms in a unifying formal setting. While the three algorithms compute the same output and have similar worst-case complexities, their actual running times may differ considerably for a given input program. On the theoretical side, we provide for each of the three algorithms a family of input programs on which that algorithm outperforms the two alternatives. On the practical side, we evaluate the three algorithms experimentally on a variety of Java libraries. }, author = {Beyer, Dirk and Thomas Henzinger and Vasu Singh}, pages = {4 -- 19}, publisher = {Springer}, title = {{Algorithms for interface synthesis}}, doi = {10.1007/978-3-540-73368-3_4}, volume = {4590}, year = {2007}, } @inproceedings{4402, author = {Alur, Rajeev and Pavol Cerny and Chaudhuri,Swarat}, pages = {664 -- 678}, publisher = {Springer}, title = {{Model Checking on Trees with Path Equivalences}}, doi = {1544}, year = {2007}, } @article{4405, abstract = {Background A central goal of Systems Biology is to model and analyze biological signaling pathways that interact with one another to form complex networks. Here we introduce Qualitative networks, an extension of Boolean networks. With this framework, we use formal verification methods to check whether a model is consistent with the laboratory experimental observations on which it is based. If the model does not conform to the data, we suggest a revised model and the new hypotheses are tested in-silico. Results We consider networks in which elements range over a small finite domain allowing more flexibility than Boolean values, and add target functions that allow to model a rich set of behaviors. We propose a symbolic algorithm for analyzing the steady state of these networks, allowing us to scale up to a system consisting of 144 elements and state spaces of approximately 1086 states. We illustrate the usefulness of this approach through a model of the interaction between the Notch and the Wnt signaling pathways in mammalian skin, and its extensive analysis. Conclusion We introduce an approach for constructing computational models of biological systems that extends the framework of Boolean networks and uses formal verification methods for the analysis of the model. This approach can scale to multicellular models of complex pathways, and is therefore a useful tool for the analysis of complex biological systems. The hypotheses formulated during in-silico testing suggest new avenues to explore experimentally. Hence, this approach has the potential to efficiently complement experimental studies in biology.}, author = {Schaub, Marc A and Thomas Henzinger and Fisher, Jasmin}, journal = {BMC Systems Biology}, number = {4}, publisher = {BioMed Central}, title = {{Qualitative networks: A symbolic approach to analyze biological signaling networks}}, doi = {10.1186/1752-0509-1-4}, volume = {1}, year = {2007}, } @inbook{4417, abstract = {Counterexample-guided abstraction refinement (CEGAR) is a powerful technique to scale automatic program analysis techniques to large programs. However, so far it has been used primarily for model checking in the context of predicate abstraction. We formalize CEGAR for general powerset domains. If a spurious abstract counterexample needs to be removed through abstraction refinement, there are often several choices, such as which program location(s) to refine, which abstract domain(s) to use at different locations, and which abstract values to compute. We define several plausible preference orderings on abstraction refinements, such as refining as “late” as possible and as “coarse” as possible. We present generic algorithms for finding refinements that are optimal with respect to the different preference orderings. We also compare the different orderings with respect to desirable properties, including the property if locally optimal refinements compose to a global optimum. Finally, we point out some difficulties with CEGAR for non-powerset domains.}, author = {Manevich, Roman and Field, John and Thomas Henzinger and Ramalingam, Ganesan and Sagiv, Mooly}, booktitle = {Program Analysis and Compilation, Theory and Practice: Essays Dedicated to Reinhard Wilhelm on the Occasion of His 60th Birthday}, pages = {273 -- 292}, publisher = {Springer}, title = {{Abstract counterexample-based refinement for powerset domains}}, doi = {10.1007/978-3-540-71322-7_13}, volume = {4444}, year = {2007}, } @article{4446, abstract = {The Embedded Machine is a virtual machine that mediates in real time the interaction between software processes and physical processes. It separates the compilation of embedded programs into two phases. The first phase, the platform-independent compiler phase, generates E code (code executed by the Embedded Machine), which supervises the timing, not the scheduling of, application tasks relative to external events such as clock ticks and sensor interrupts. E code is portable and, given an input behavior, exhibits predictable (i.e., deterministic) timing and output behavior. The second phase, the platform-dependent compiler phase, checks the time safety of the E code, that is, whether platform performance (determined by the hardware) and platform utilization (determined by the scheduler of the operating system) enable its timely execution. We have used the Embedded Machine to compile and execute high-performance control applications written in Giotto, such as the flight control system of an autonomous model helicopter.}, author = {Thomas Henzinger and Kirsch, Christoph M}, journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)}, number = {393}, publisher = {ACM}, title = {{The embedded machine: Predictable, portable real-time code}}, doi = {10.1145/1286821.1286824}, volume = {29}, year = {2007}, } @inproceedings{4511, abstract = {In the traditional view, a language is a set of words, i.e., a function from words to boolean values. We call this view “qualitative,” because each word either belongs to or does not belong to a language. Let Σ be an alphabet, and let us consider infinite words over Σ. Formally, a qualitative language over Σ is a function A: B . There are many applications of qualitative languages. For example, qualitative languages are used to specify the legal behaviors of systems, and zero-sum objectives of games played on graphs. In the former case, each behavior of a system is either legal or illegal; in the latter case, each outcome of a game is either winning or losing. For defining languages, it is convenient to use finite acceptors (or generators). In particular, qualitative languages are often defined using finite-state machines (so-called ω-automata) whose transitions are labeled by letters from Σ. For example, the states of an ω-automaton may represent states of a system, and the transition labels may represent atomic observables of a behavior. There is a rich and well-studied theory of finite-state acceptors of qualitative languages, namely, the theory of theω-regular languages.}, author = {Thomas Henzinger}, pages = {20 -- 22}, publisher = {Springer}, title = {{Quantitative generalizations of languages}}, doi = {10.1007/978-3-540-73208-2_2}, volume = {4588}, year = {2007}, } @inproceedings{4514, abstract = {Digital technology is increasingly deployed in safety-critical situations. This calls for systematic design and verification methodologies that can cope with three major sources of system complexity: concurrency, real time, and uncertainty. We advocate a two-step process: formal modeling followed by algorithmic analysis (or, “model building” followed by “model checking”). We model the concurrent components of a reactive system as potential collaborators or adversaries in a multi-player game with temporal objectives, such as system safety. The real-time aspect of embedded systems requires models that combine discrete state transitions and continuous state evolutions. Uncertainty in the environment is naturally modeled by probabilistic state changes. As a result, we obtain three orthogonal extensions of the basic state-transition graph model for reactive systems —game graphs, timed graphs, and stochastic graphs— as well as combinations thereof. In this short text, we provide a uniform exposition of the underlying definitions. For verification algorithms, we refer the reader to the literature.}, author = {Thomas Henzinger}, pages = {103 -- 110}, publisher = {Springer}, title = {{Games, time, and probability: Graph models for system design and analysis}}, doi = {10.1007/978-3-540-69507-3_7}, volume = {4362}, year = {2007}, } @article{4529, abstract = {Computational modeling of biological systems is becoming increasingly important in efforts to better understand complex biological behaviors. In this review, we distinguish between two types of biological models—mathematical and computational—which differ in their representations of biological phenomena. We call the approach of constructing computational models of biological systems 'executable biology', as it focuses on the design of executable computer algorithms that mimic biological phenomena. We survey the main modeling efforts in this direction, emphasize the applicability and benefits of executable models in biological research and highlight some of the challenges that executable biology poses for biology and computer science. We claim that for executable biology to reach its full potential as a mainstream biological technique, formal and algorithmic approaches must be integrated into biological research. This will drive biology toward a more precise engineering discipline.}, author = {Fisher, Jasmin and Thomas Henzinger}, journal = {Nature Biotechnology}, pages = {1239 -- 1249}, publisher = {Nature Publishing Group}, title = {{Executable cell biology}}, doi = {10.1038/nbt1356}, volume = {25}, year = {2007}, } @proceedings{4530, abstract = {This book constitutes the refereed proceedings of the 21st International Workshop on Computer Science Logic, CSL 2007, held as the 16th Annual Conference of the EACSL in Lausanne, Switzerland. The 36 revised full papers presented together with the abstracts of six invited lectures are organized in topical sections on logic and games, expressiveness, games and trees, logic and deduction, lambda calculus, finite model theory, linear logic, proof theory, and game semantics.}, author = {Duparc, Jacques and Thomas Henzinger}, booktitle = {CSL: Computer Science Logic}, publisher = {Springer}, title = {{CSL: Computer Science Logic }}, doi = {10.1007/978-3-540-74915-8}, volume = {4646}, year = {2007}, } @article{4531, abstract = {Caenorhabditis elegans vulval development provides an important paradigm for studying the process of cell fate determination and pattern formation during animal development. Although many genes controlling vulval cell fate specification have been identified, how they orchestrate themselves to generate a robust and invariant pattern of cell fates is not yet completely understood. Here, we have developed a dynamic computational model incorporating the current mechanistic understanding of gene interactions during this patterning process. A key feature of our model is the inclusion of multiple modes of crosstalk between the epidermal growth factor receptor (EGFR) and LIN-12/Notch signaling pathways, which together determine the fates of the six vulval precursor cells (VPCs). Computational analysis, using the model-checking technique, provides new biological insights into the regulatory network governing VPC fate specification and predicts novel negative feedback loops. In addition, our analysis shows that most mutations affecting vulval development lead to stable fate patterns in spite of variations in synchronicity between VPCs. Computational searches for the basis of this robustness show that a sequential activation of the EGFR-mediated inductive signaling and LIN-12 / Notch-mediated lateral signaling pathways is key to achieve a stable cell fate pattern. We demonstrate experimentally a time-delay between the activation of the inductive and lateral signaling pathways in wild-type animals and the loss of sequential signaling in mutants showing unstable fate patterns; thus, validating two key predictions provided by our modeling work. The insights gained by our modeling study further substantiate the usefulness of executing and analyzing mechanistic models to investigate complex biological behaviors.}, author = {Fisher, Jasmin and Piterman, Nir and Hajnal, Alex and Thomas Henzinger}, journal = {PLoS Computational Biology}, publisher = {Public Library of Science}, title = {{Predictive modeling of signaling crosstalk during C. elegans vulval development}}, doi = {10.1371/journal.pcbi.0030092}, volume = {3(5):e92}, year = {2007}, } @inproceedings{4537, abstract = {The classical synthesis problem for reactive systems asks, given a proponent process A and an opponent process B, to refine A so that the closed-loop system A parallel to B satisfies a given specification Phi. The solution of this problem requires the computation of a winning strategy for proponent A in a game against opponent B. We define and study the co-synthesis problem, where the proponent A consists itself of two independent processes, A = A(1)parallel to A(2), with specifications Phi(1) and Phi(2), and the goal is to refine both A(1) and A(2) so that A(1)parallel to A(2)parallel to B satisfies Phi(1) boolean AND Phi(2). For example, if the opponent B is a fair scheduler for the two processes A(1) and A(2), and Phi(i) specifies the requirements of mutual exclusion for A(i) (e.g., starvation freedom), then the co-synthesis problem asks for the automatic synthesis of a mutual-exclusion protocol. We show that co-synthesis defined classically, with the processes A(1) and A(2) either collaborating or competing, does not capture desirable solutions. Instead, the proper formulation of co-synthesis is the one where process A, competes with A(2) but not at the price of violating Phi(1), and vice versa. We call this assume-guarantee synthesis and show that it can be solved by computing secure-equilibrium strategies. In particular, from mutual-exclusion requirements the assume-guarantee synthesis algorithm automatically computes Peterson's protocol.}, author = {Krishnendu Chatterjee and Thomas Henzinger}, pages = {261 -- 275}, publisher = {Springer}, title = {{Assume-guarantee synthesis}}, doi = {10.1007/978-3-540-71209-1_21}, volume = {4424}, year = {2007}, } @article{4547, abstract = {We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buechi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.}, author = {Krishnendu Chatterjee and Doyen, Laurent and Thomas Henzinger and Raskin, Jean-François}, journal = {Logical Methods in Computer Science}, number = {184}, pages = {1 -- 23}, publisher = {International Federation of Computational Logic}, title = {{Algorithms for omega-regular games with imperfect information}}, doi = {10.2168/LMCS-3(3:4)2007}, volume = {3}, year = {2007}, } @article{2657, abstract = {The highest densities of the two metabotropic GABA subunits, GABA B1 and GABAB2, have been reported as occurring around the glutamatergic synapses between Purkinje cell spines and parallel fibre varicosities. In order to determine how this distribution is achieved during development, we investigated the expression pattern and the cellular and subcellular localization of the GABAB1 and GABAB2 subunits in the rat cerebellum during postnatal development. At the light microscopic level, immunoreactivity for the GABAB1 and GABAB2 subunits was very prominent in the developing molecular layer, especially in Purkinje cells. Using double immunofluorescence, we demonstrated that GABAB1 was transiently expressed in glial cells. At the electron microscopic level, immunoreactivity for GABAB receptors was always detected both pre- and postsynaptically. Presynaptically, GABAB1 and GABAB2 were localized in the extrasynaptic membrane of parallel fibres at all ages, and only rarely in GABAergic axons. Postsynaptically, GABAB receptors were localized to the extrasynaptic and perisynaptic plasma membrane of Purkinje cell dendrites and spines throughout development. Quantitative analysis and three-dimensional reconstructions further revealed a progressive developmental movement of the GABAB1 subunit on the surface of Purkinje cells from dendritic shafts to its final destination, the dendritic spines. Together, these results indicate that GABAB receptors undergo dynamic regulation during cerebellar development in association with the establishment and maturation of glutamatergic synapses to Purkinje cells.}, author = {Luján, Rafael and Ryuichi Shigemoto}, journal = {European Journal of Neuroscience}, number = {6}, pages = {1479 -- 1490}, publisher = {Wiley-Blackwell}, title = {{Localization of metabotropic GABA receptor subunits GABAB1 and GABAB2 relative to synaptic sites in the rat developing cerebellum}}, doi = {10.1111/j.1460-9568.2006.04669.x}, volume = {23}, year = {2006}, } @article{2659, abstract = {Transmembrane AMPA receptor regulatory proteins (TARPs), including stargazin/γ-2, are associated with AMPA receptors and participate in their surface delivery and anchoring at the postsynaptic membrane. TARPs may also act as a positive modulator of the AMPA receptor ion channel function; however, little is known about other TARP members except for stargazin/γ-2. We examined the synaptic localization of stargazin/γ-2 and γ-8 by immunoelectron microscopy and biochemical analysis. The analysis of sodium dodecyl sulfate-digested freeze-fracture replica labeling revealed that stargazin/γ-2 was concentrated in the postsynaptic area, whereas γ-8 was distributed both in synaptic and extra-synaptic plasma membranes of the hippocampal neuron. When a synaptic plasma membrane-enriched brain fraction was treated with Triton X-100 and separated by sucrose density gradient ultracentrifugation, a large proportion of NMDA receptor and stargazin/γ-2 was accumulated in raft-enriched fractions, whereas AMPA receptor and γ-8 were distributed in both the raft-enriched fractions and other Triton-insoluble fractions. Phosphorylation of stargazin/γ-2 and γ-8 was regulated by different sets of kinases and phosphatases in cultured cortical neurons. These results suggested that stargazin/γ-2 and γ-8 have distinct roles in postsynaptic membranes under the regulation of different intracellular signaling pathways.}, author = {Inamura, Mihoko and Itakura, Makoto and Okamoto, Hirotsugu and Hoka, Sumio and Mizoguchi, Akira and Fukazawa, Yugo and Ryuichi Shigemoto and Yamamori, Saori and Takahashi, Masami}, journal = {Neuroscience Research}, number = {1}, pages = {45 -- 53}, publisher = {Elsevier}, title = {{ Differential localization and regulation of stargazin-like protein, γ-8 and stargazin in the plasma membrane of hippocampal and cortical neurons}}, doi = {10.1016/j.neures.2006.01.004}, volume = {55}, year = {2006}, } @article{2660, abstract = {Pavlovian fear conditioning, a simple form of associative learning, is thought to involve the induction of associative, NMDA receptor-dependent long-term potentiation (LTP) in the lateral amygdala. Using a combined genetic and electrophysiological approach, we show here that lack of a specific GABAB receptor subtype, GABAB(1a,2), unmasks a nonassociative, NMDA receptor-independent form of presynaptic LTP at cortico-amygdala afferents. Moreover, the level of presynaptic GABA B(1a,2) receptor activation, and hence the balance between associative and nonassociative forms of LTP, can be dynamically modulated by local inhibitory activity. At the behavioral level, genetic loss of GABA B(1a) results in a generalization of conditioned fear to nonconditioned stimuli. Our findings indicate that presynaptic inhibition through GABAB(1a,2) receptors serves as an activity-dependent constraint on the induction of homosynaptic plasticity, which may be important to prevent the generalization of conditioned fear.}, author = {Shaban, Hamdy and Humeau, Yann and Herry, Cyril and Cassasus, Guillaume and Ryuichi Shigemoto and Ciocchi, Stéphane and Barbieri, Samuel and Van Der Putten, Herman V and Kaupmann, Klemens and Bettler, Bernhard and Lüthi, Andreas}, journal = {Nature Neuroscience}, number = {8}, pages = {1028 -- 1035}, publisher = {Nature Publishing Group}, title = {{Generalization of amygdala LTP and conditioned fear in the absence of presynaptic inhibition}}, doi = {10.1038/nn1732}, volume = {9}, year = {2006}, } @article{2661, abstract = {GABAB receptors are the G protein-coupled receptors for the main inhibitory neurotransmitter in the brain, γ-aminobutyric acid (GABA). Molecular diversity in the GABAB system arises from the GABAB1a and GABAB1b subunit isoforms that solely differ in their ectodomains by a pair of sushi repeats that is unique to GABAB1a. Using a combined genetic, physiological, and morphological approach, we now demonstrate that GABAB1 isoforms localize to distinct synaptic sites and convey separate functions in vivo. At hippocampal CA3-to-CA1 synapses, GABAB1a assembles heteroreceptors inhibiting glutamate release, while predominantly GABAB1b mediates postsynaptic inhibition. Electron microscopy reveals a synaptic distribution of GABAB1 isoforms that agrees with the observed functional differences. Transfected CA3 neurons selectively express GABAB1a in distal axons, suggesting that the sushi repeats, a conserved protein interaction motif, specify heteroreceptor localization. The constitutive absence of GABAB1a but not GABAB1b results in impaired synaptic plasticity and hippocampus-dependent memory, emphasizing molecular differences in synaptic GABAB functions.}, author = {Vigot, Réjan and Barbieri, Samuel and Bräuner-Osborne, Hans and Tureček, Rostislav and Ryuichi Shigemoto and Zhang, Yan Ping and Luján, Rafael and Jacobson, Laura H and Biermann, Barbara and Fritschy, Jean-Marc and Vacher, Claire-Marie and Müller, Matthias P and Sansig, Gilles and Guetg, Nicole and Cryan, John F and Kaupmann, Klemens and Gassmann, Martin and Oertner, Thomas G and Bettler, Bernhard}, journal = {Neuron}, number = {4}, pages = {589 -- 601}, publisher = {Elsevier}, title = {{Differential Compartmentalization and Distinct Functions of GABAB Receptor Variants}}, doi = {10.1016/j.neuron.2006.04.014}, volume = {50}, year = {2006}, }