@inproceedings{4432, abstract = {We add freeze quantifiers to the game logic ATL in order to specify real-time objectives for games played on timed structures. We define the semantics of the resulting logic TATL by restricting the players to physically meaningful strategies, which do not prevent time from diverging. We show that TATL can be model checked over timed automaton games. We also specify timed optimization problems for physically meaningful strategies, and we show that for timed automaton games, the optimal answers can be approximated to within any degree of precision.}, author = {Thomas Henzinger and Prabhu, Vinayak S}, pages = {1 -- 17}, publisher = {Springer}, title = {{Timed alternating-time temporal logic}}, doi = {10.1007/11867340_1}, volume = {4202}, year = {2006}, } @inproceedings{4436, abstract = {We present an assume-guarantee interface algebra for real-time components. In our formalism a component implements a set of task sequences that share a resource. A component interface consists of an arrival rate function and a latency for each task sequence, and a capacity function for the shared resource. The interface specifies that the component guarantees certain task latencies depending on assumptions about task arrival rates and allocated resource capacities. Our algebra defines compatibility and refinement relations on interfaces. Interface compatibility can be checked on partial designs, even when some component interfaces are yet unknown. In this case interface composition computes as new assumptions the weakest constraints on the unknown components that are necessary to satisfy the specified guarantees. Interface refinement is defined in a way that ensures that compatible interfaces can be refined and implemented independently. Our algebra thus formalizes an interface-based design methodology that supports both the incremental addition of new components and the independent stepwise refinement of existing components. We demonstrate the flexibility and efficiency of the framework through simulation experiments.}, author = {Thomas Henzinger and Matic, Slobodan}, pages = {253 -- 266}, publisher = {IEEE}, title = {{An interface algebra for real-time components}}, doi = {10.1109/RTAS.2006.11}, year = {2006}, } @inproceedings{4437, abstract = {The synthesis of reactive systems requires the solution of two-player games on graphs with ω-regular objectives. When the objective is specified by a linear temporal logic formula or nondeterministic Büchi automaton, then previous algorithms for solving the game require the construction of an equivalent deterministic automaton. However, determinization for automata on infinite words is extremely complicated, and current implementations fail to produce deterministic automata even for relatively small inputs. We show how to construct, from a given nondeterministic Büchi automaton, an equivalent nondeterministic parity automaton that is good for solving games with objective . The main insight is that a nondeterministic automaton is good for solving games if it fairly simulates the equivalent deterministic automaton. In this way, we omit the determinization step in game solving and reactive synthesis. The fact that our automata are nondeterministic makes them surprisingly simple, amenable to symbolic implementation, and allows an incremental search for winning strategies.}, author = {Thomas Henzinger and Piterman, Nir}, pages = {395 -- 410}, publisher = {Springer}, title = {{Solving games without determinization}}, doi = {10.1007/11874683_26}, volume = {4207}, year = {2006}, } @article{4451, abstract = {One source of complexity in the μ-calculus is its ability to specify an unbounded number of switches between universal (AX) and existential (EX) branching modes. We therefore study the problems of satisfiability, validity, model checking, and implication for the universal and existential fragments of the μ-calculus, in which only one branching mode is allowed. The universal fragment is rich enough to express most specifications of interest, and therefore improved algorithms are of practical importance. We show that while the satisfiability and validity problems become indeed simpler for the existential and universal fragments, this is, unfortunately, not the case for model checking and implication. We also show the corresponding results for the alternation-free fragment of the μ-calculus, where no alternations between least and greatest fixed points are allowed. Our results imply that efforts to find a polynomial-time model-checking algorithm for the μ-calculus can be replaced by efforts to find such an algorithm for the universal or existential fragment.}, author = {Thomas Henzinger and Kupferman, Orna and Majumdar, Ritankar S}, journal = {Theoretical Computer Science}, number = {2}, pages = {173 -- 186}, publisher = {Elsevier}, title = {{On the universal and existential fragments of the mu-calculus}}, doi = {10.1016/j.tcs.2005.11.015}, volume = {354}, year = {2006}, } @inproceedings{4523, abstract = {We consider the problem if a given program satisfies a specified safety property. Interesting programs have infinite state spaces, with inputs ranging over infinite domains, and for these programs the property checking problem is undecidable. Two broad approaches to property checking are testing and verification. Testing tries to find inputs and executions which demonstrate violations of the property. Verification tries to construct a formal proof which shows that all executions of the program satisfy the property. Testing works best when errors are easy to find, but it is often difficult to achieve sufficient coverage for correct programs. On the other hand, verification methods are most successful when proofs are easy to find, but they are often inefficient at discovering errors. We propose a new algorithm, Synergy, which combines testing and verification. Synergy unifies several ideas from the literature, including counterexample-guided model checking, directed testing, and partition refinement.This paper presents a description of the Synergy algorithm, its theoretical properties, a comparison with related algorithms, and a prototype implementation called Yogi.}, author = {Gulavani, Bhargav S and Thomas Henzinger and Kannan, Yamini and Nori, Aditya V and Rajamani, Sriram K}, pages = {117 -- 127}, publisher = {ACM}, title = {{Synergy: A new algorithm for property checking}}, doi = {10.1145/1181775.1181790}, year = {2006}, } @inproceedings{4526, abstract = {We designed and implemented a new programming language called Hierarchical Timing Language (HTL) for hard realtime systems. Critical timing constraints are specified within the language,and ensured by the compiler. Programs in HTL are extensible in two dimensions without changing their timing behavior: new program modules can be added, and individual program tasks can be refined. The mechanism supporting time invariance under parallel composition is that different program modules communicate at specified instances of time. Time invariance under refinement is achieved by conservative scheduling of the top level. HTL is a coordination language, in that individual tasks can be implemented in "foreign" languages. As a case study, we present a distributed HTL implementation of an automotive steer-by-wire controller.}, author = {Ghosal, Arkadeb and Thomas Henzinger and Iercan, Daniel and Kirsch, Christoph M and Sangiovanni-Vincentelli, Alberto}, pages = {132 -- 141}, publisher = {ACM}, title = {{A hierarchical coordination language for interacting real-time tasks}}, doi = {10.1145/1176887.1176907}, year = {2006}, } @inproceedings{4528, abstract = {Computational modeling of biological systems is becoming increasingly common as scientists attempt to understand biological phenomena in their full complexity. Here we distinguish between two types of biological models mathematical and computational - according to their different representations of biological phenomena and their diverse potential. 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 give an overview of the main modeling efforts in this direction, and discuss some of the new challenges that executable biology poses for computer science and biology. We argue that for executable biology to reach its full potential as a mainstream biological technique, formal and algorithmic approaches must be integrated into biological research, driving biology towards a more precise engineering discipline.}, author = {Fisher, Jasmin and Thomas Henzinger}, pages = {1675 -- 1682}, publisher = {IEEE}, title = {{Executable biology}}, doi = {10.1109/WSC.2006.322942}, year = {2006}, } @inproceedings{4538, abstract = {A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with ω-regular winning conditions specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy improvement algorithm for stochastic parity games; this is the first non-brute-force algorithm for solving these games. From the strategy improvement algorithm we obtain a randomized subexponential-time algorithm to solve such games.}, author = {Krishnendu Chatterjee and Thomas Henzinger}, pages = {512 -- 523}, publisher = {Springer}, title = {{Strategy improvement and randomized subexponential algorithms for stochastic parity games}}, doi = {10.1007/11672142_42}, volume = {3884}, year = {2006}, } @inproceedings{4539, abstract = {Games on graphs with ω-regular objectives provide a model for the control and synthesis of reactive systems. Every ω-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 (Büchi) objectives, the finitary formulation is strictly stronger. In this work we study games with finitary parity and Streett (fairness) objectives. We prove the determinacy of these games, present algorithms for solving these games, and characterize the memory requirements of winning strategies. Our algorithms can be used, for example, for synthesizing controllers that do not let the response time of a system increase without bound.}, author = {Krishnendu Chatterjee and Thomas Henzinger}, pages = {257 -- 271}, publisher = {Springer}, title = {{Finitary winning in omega-regular games}}, doi = {10.1007/11691372_17}, volume = {3920}, year = {2006}, } @inproceedings{4549, abstract = {We present a compositional theory of system verification, where specifications assign real-numbered costs to systems. These costs can express a wide variety of quantitative system properties, such as resource consumption, price, or a measure of how well a system satisfies its specification. The theory supports the composition of systems and specifications, and the hiding of variables. Boolean refinement relations are replaced by real-numbered distances between descriptions of a system at different levels of detail. We show that the classical Boolean rules for compositional reasoning have quantitative counterparts in our setting. While our general theory allows costs to be specified by arbitrary cost functions, we also consider a class of linear cost functions, which give rise to an instance of our framework where all operations are computable in polynomial time.}, author = {Krishnendu Chatterjee and de Alfaro, Luca and Faella, Marco and Thomas Henzinger and Majumdar, Ritankar S and Stoelinga, Mariëlle}, pages = {179 -- 188}, publisher = {IEEE}, title = {{Compositional quantitative reasoning}}, doi = {10.1109/QEST.2006.11}, year = {2006}, } @article{4550, abstract = {In 2-player non-zero-sum games, Nash equilibria capture the options for rational behavior if each player attempts to maximize her payoff. In contrast to classical game theory, we consider lexicographic objectives: first, each player tries to maximize her own payoff, and then, the player tries to minimize the opponent's payoff. Such objectives arise naturally in the verification of systems with multiple components. There, instead of proving that each component satisfies its specification no matter how the other components behave, it sometimes suffices to prove that each component satisfies its specification provided that the other components satisfy their specifications. We say that a Nash equilibrium is secure if it is an equilibrium with respect to the lexicographic objectives of both players. We prove that in graph games with Borel winning conditions, which include the games that arise in verification, there may be several Nash equilibria, but there is always a unique maximal payoff profile of a secure equilibrium. We show how this equilibrium can be computed in the case of ω-regular winning conditions, and we characterize the memory requirements of strategies that achieve the equilibrium.}, author = {Krishnendu Chatterjee and Thomas Henzinger and Jurdziński, Marcin}, journal = {Theoretical Computer Science}, number = {1-2}, pages = {67 -- 82}, publisher = {Elsevier}, title = {{Games with secure equilibria}}, doi = {10.1016/j.tcs.2006.07.032}, volume = {365}, year = {2006}, } @inproceedings{4551, abstract = {We consider Markov decision processes (MDPs) with multiple discounted reward objectives. Such MDPs occur in design problems where one wishes to simultaneously optimize several criteria, for example, latency and power. The possible trade-offs between the different objectives are characterized by the Pareto curve. We show that every Pareto-optimal point can be achieved by a memoryless strategy; however, unlike in the single-objective case, the memoryless strategy may require randomization. Moreover, we show that the Pareto curve can be approximated in polynomial time in the size of the MDP. Additionally, we study the problem if a given value vector is realizable by any strategy, and show that it can be decided in polynomial time; but the question whether it is realizable by a deterministic memoryless strategy is NP-complete. These results provide efficient algorithms for design exploration in MDP models with multiple objectives. This research was supported in part by the AFOSR MURI grant F49620-00-1-0327, and the NSF grants CCR-0225610, CCR-0234690, and CCR-0427202. }, author = {Krishnendu Chatterjee and Majumdar, Ritankar S and Thomas Henzinger}, pages = {325 -- 336}, publisher = {Springer}, title = {{Markov decision processes with multiple objectives}}, doi = {10.1007/11672142_26}, volume = {3884}, year = {2006}, } @inproceedings{4552, abstract = {A concurrent reachability game is a two-player game played on a graph: at each state, the players simultaneously and independently select moves; the two moves determine jointly a probability distribution over the successor states. The objective for player 1 consists in reaching a set of target states; the objective for player 2 is to prevent this, so that the game is zero-sum. Our contributions are two-fold. First, we present a simple proof of the fact that in concurrent reachability games, for all epsilon > 0, memoryless epsilon-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an epsilon-optimal strategy achieves the objective with probability within epsilon of the value of the game. In contrast to previous proofs of this fact, which rely on the limit behavior of discounted games using advanced Puisieux series analysis, our proof is elementary and combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives.}, author = {Krishnendu Chatterjee and de Alfaro, Luca and Thomas Henzinger}, pages = {291 -- 300}, publisher = {IEEE}, title = {{Strategy improvement for concurrent reachability games}}, doi = {10.1109/QEST.2006.48}, year = {2006}, } @article{2455, abstract = {Local accumulation of the plant growth regulator auxin mediates pattern formation in Arabidopsis roots and influences outgrowth and development of lateral root- and shoot-derived primordia. However, it has remained unclear how auxin can simultaneously regulate patterning and organ outgrowth and how its distribution is stabilized in a primordium-specif ic manner. Here we show that five PIN genes collectively control auxin distribution to regulate cell division and cell expansion in the primary root. Furthermore, the joint action of these genes has an important role in pattern formation by focusing the auxin maximum and restricting the expression domain of PLETHORA (PLT) genes, major determinants for root stem cell specification. In turn, PLT genes are required for PIN gene transcription to stabilize the auxin maximum at the distal root tip. Our data reveal an interaction network of auxin transport facilitators and root fate determinants that control patterning and growth of the root primordium.}, author = {Billou, Ikram and Xu, Jian and Wildwater, Marjolein and Willemsen, Viola and Paponov, Ivan A and Jirí Friml and Heldstra, Renze and Aida, Mitsuhiro and Palme, Klaus J and Scheres, Ben}, journal = {Nature}, number = {7021}, pages = {39 -- 44}, publisher = {Nature Publishing Group}, title = {{The PIN auxin efflux facilitator network controls growth and patterning in Arabidopsis roots}}, doi = {10.1038/nature03184}, volume = {433}, year = {2005}, } @inbook{2463, author = {Dubová, J and Hejátko, Jan and Jirí Friml}, booktitle = {Encyclopedia of Molecular Cell Biology and Molecular Medicine}, editor = {Meyers, Robert A}, pages = {249 -- 295}, publisher = {Wiley-Blackwell}, title = {{Reproduction, plants}}, doi = {10.1002/3527600906}, volume = {12}, year = {2005}, } @inbook{2464, author = {Jirí Friml and Wiśniewska, Justyna}, booktitle = {Intercellular Communication in Plants}, editor = {Fleming, Andrew J.}, publisher = {Wiley-Blackwell}, title = {{Auxin as an intercellular signal}}, volume = {16}, year = {2005}, } @misc{2647, abstract = {Our understanding of the role played by neurotransmitter receptors in the developing brain has advanced in recent years. The major excitatory and inhibitory neurotransmitters in the brain, glutamate and GABA, activate both ionotropic (ligand-gated ion channels) and metabotropic (G protein-coupled) receptors, and are generally associated with neuronal communication in the mature brain. However, before the emergence of their role in neurotransmission in adulthood, they also act to influence earlier developmental events, some of which occur prior to synapse formation: such as proliferation, migration, differentiation or survival processes during neural development. To fulfill these actions in the constructing of the nervous system, different types of glutamate and GABA receptors need to be expressed both at the right time and at the right place. The identification by molecular cloning of 16 ionotropic glutamate receptor subunits, eight metabotropic glutamate receptor subtypes, 21 ionotropic and two metabotropic GABA receptor subunits, some of which exist in alternatively splice variants, has enriched our appreciation of how molecular diversity leads to functional diversity in the brain. It now appears that many different types of glutamate and GABA receptor subunits have prominent expression in the embryonic and/or postnatal brain, whereas others are mainly present in the adult brain. Although the significance of this differential expression of subunits is not fully understood, it appears that the change in subunit composition is essential for normal development in particular brain regions. This review focuses on emerging information relating to the expression and role of glutamatergic and GABAergic neurotransmitter receptors during prenatal and postnatal development.}, author = {Luján, Rafael and Ryuichi Shigemoto and López-Bendito, Guillermina}, booktitle = {Neuroscience}, number = {3}, pages = {567 -- 580}, publisher = {Elsevier}, title = {{Glutamate and GABA receptor signalling in the developing brain}}, doi = {10.1016/j.neuroscience.2004.09.042}, volume = {130}, year = {2005}, } @article{2648, abstract = {Hyperpolarization-activated and cyclic nucleotide-gated (HCN) channels are involved in the control of neuronal excitability and plasticity. In this study, we used immunoblotting and immunohistochemical techniques to reveal the developmental expression and subcellular distribution of the HCN1 subunit in the cerebellar cortex. During postnatal development, the spatio-temporal expression of HCN1 correlated well with the morphological events occurring during the ontogenesis of cerebellar interneurons. Using immunoblotting techniques, HCN1 was weakly detected during the first postnatal week and continued to increase throughout postnatal development, peaking at postnatal day (P)15. At the light-microscopic level, HCN1 immunoreactivity was very weak until P7 whereas from P10-12 to adulthood it was strongly detected in the lower third of the molecular layer and in the Purkinje cell layer. HCN1 was present in axons running through the molecular layer and in the pericellular basket around Purkinje cells at P12, but in the periaxonal plexus (the pinceau) surrounding their initial segment only after P15. Using immunofluorescence, HCN1 colocalized with GAD65 and synaptophysin, demonstrating that the subunit was present in inhibitory axons and axon terminals. At the electron-microscopic level, in adulthood, HCN1 immunoparticles were detected at postsynaptic sites in basket and Purkinje cells but most immunoparticles were found at presynaptic sites in basket cell axons and in terminals. In the axon terminals, the distribution of HCN1 was relatively uniform along the extrasynaptic plasma membrane; this was confirmed using quantitative techniques. The present findings suggest that HCN1 channels may provide a significant route for modulating co-ordinated cerebellar synaptic transmission through basket cells.}, author = {Luján, Rafael and Albasanz, José L and Ryuichi Shigemoto and Juíz, José M}, journal = {European Journal of Neuroscience}, number = {8}, pages = {2073 -- 2082}, publisher = {Wiley-Blackwell}, title = {{Preferential localization of the hyperpolarization-activated cyclic nucleotide-gated cation channel subunit HCN1 in basket cell terminals of the rat cerebellum}}, doi = {10.1111/j.1460-9568.2005.04043.x}, volume = {21}, year = {2005}, } @article{2649, abstract = {The number of ionotropic receptors in synapses is an essential factor for determining the efficacy of fast transmission. We estimated the number of functional AMPA receptors at single postsynaptic sites by a combination of two-photon uncaging of glutamate and the nonstationary fluctuation analysis in immature rat Purkinje cells (PCs), which receive a single type of excitatory input from climbing fibers. Areas of postsynaptic membrane specialization at the recorded synapses were measured by reconstruction of serial ultrathin sections. The number of functional AMPA receptors was proportional to the synaptic area with a density of ∼ 1280 receptors/μm 2. Moreover, highly sensitive freeze-fracture replica labeling revealed a homogeneous density of immunogold particles for AMPA receptors in synaptic sites (910 ± 36 particles/μm 2) and much lower density in extrasynaptic sites (19 ± 2 particles/μm 2) in the immature PCs. Our results indicate that in this developing synapse, the efficacy of transmission is determined by the synaptic area.}, author = {Tanaka, Junichi and Matsuzaki, Masanori and Tarusawa, Etsuko and Momiyama, Akiko and Molnár, Elek and Kasai, Haruo and Ryuichi Shigemoto}, journal = {Journal of Neuroscience}, number = {4}, pages = {799 -- 807}, publisher = {Society for Neuroscience}, title = {{Number and density of AMPA receptors in single synapses in immature cerebellum}}, doi = {10.1523/JNEUROSCI.4256-04.2005}, volume = {25}, year = {2005}, } @article{2650, abstract = {Septohippocampal cholinergic neurons play key roles in learning and memory processes, and in the generation of hippocampal theta rhythm. The range of receptors for endogenous modulators expressed on these neurons is unclear. Here we describe GABAB 1a/b receptor (GABABR) and type 1 cannabinoid receptor (CB1R) expression in rat septal cholinergic [i.e. choline acetyltransferase (ChAT)-positive] cells. Using double immunofluorescent staining, we found that almost two-thirds of the cholinergic cells in the rat medial septum were GABABR positive, and that these cells had significantly larger somata than did GABABR-negative cholinergic neurons. We detected CB1R labelling in somata after axonal protein transport was blocked by colchicine. In these animals about one-third of the cholinergic cells were CB1R positive. These cells again had larger somata than CB1R-negative cholinergic neurons. The analyses confirmed that the size of GABABR-positive and CB 1R-positive cholinergic cells were alike, and all CB 1R-positive cholinergic cells were GABABR positive as well. CB1R-positive cells were invariably ChAT positive. All retrogradely labelled septohippocampal cholinergic cells were positive for GABABR and at least half of them also for CB1R. These data shed light on the existence of at least two cholinergic cell types in the medial septum: one expresses GABABR and CB1R, has large somata and projects to the hippocampus, whereas the other is negative for GABABR and CB1R and has smaller somata. The results also suggest that cholinergic transmission in the hippocampus is fine-tuned by endocannabinoid signalling.}, author = {Nyíri, Gábor and Szabadits, Eszter and Cserép, Csaba and Mackie, Ken P and Ryuichi Shigemoto and Freund, Tamás F}, journal = {European Journal of Neuroscience}, number = {11}, pages = {3034 -- 3042}, publisher = {Wiley-Blackwell}, title = {{GABAB and CB1 cannabinoid receptor expression identifies two types of septal cholinergic neurons}}, doi = {10.1111/j.1460-9568.2005.04146.x}, volume = {21}, year = {2005}, }