TY - JOUR
AB - Synapses are the key elements for signal processing and plasticity in the brain. To determine the structural factors underlying the unique functional properties of the hippocampal mossy fiber synapse, the complete quantitative geometry was investigated, using electron microscopy of serial ultrathin sections followed by computer-assisted three-dimensional reconstruction. In particular, parameters relevant for transmitter release and synaptic plasticity were examined. Two membrane specializations were found: active zones (AZs), transmitter release sites, and puncta adherentia, putative adhesion complexes. Individual boutons had, on average, 25 AZs (range, 7-45) that varied in shape and size (mean, 0.1 microm2; range, 0.07-0.17 microm2). The mean distance between individual AZs was 0.45 microm. Mossy fiber boutons and their target structures were mostly ensheathed by astrocytes, but fine glial processes never reached the active zones. Two structural factors are likely to promote synaptic cross talk: the short distance between AZs and the absence of fine glial processes at AZs. Thus, synaptic cross talk may contribute to the efficacy of hippocampal mossy fiber synapses. On average, a bouton contained 20,400 synaptic vesicles; approximately 900 vesicles were located within 60 nm from the active zone, approximately 4400 between 60 and 200 nm, and the remaining beyond 200 nm, suggesting large readily releasable, recycling, and reserve pools. The organization of the different pools may be a key structural correlate of presynaptic plasticity at this synapse. Thus, the mossy fiber bouton differs fundamentally in structure and function from the calyx of Held and other central synapses.
AU - Rollenhagen, Astrid
AU - Satzler, Kurt
AU - Rodriguez, E Patricia
AU - Peter Jonas
AU - Frotscher, Michael
AU - Lubke, Joachim H
ID - 3820
IS - 39
JF - Journal of Neuroscience
TI - Structural determinants of transmission at large hippocampal mossy fiber synapses
VL - 27
ER -
TY - JOUR
AB - Although dendritic signal processing has been extensively investigated in hippocampal pyramidal cells, only little is known about dendritic integration of synaptic potentials in dentate gyrus granule cells, the first stage in the hippocampal trisynaptic circuit. Here we combined dual whole-cell patch-clamp recordings with high-resolution two-photon microscopy to obtain detailed passive cable models of hippocampal granule cells from adult mice. Passive cable properties were determined by direct fitting of the compartmental model to the experimentally measured voltage responses to short and long current pulses. The data are best fit by a cable model with homogenously distributed parameters, including an average specific membrane resistance (R(m)) of 38.0 kohms cm2, a membrane capacitance (C(m)) of 1.0 microF cm(-2), and an intracellular resistivity (R(i)) of 194 ohms cm. Computational analysis shows that signal propagation from somata into dendrites is more efficient in granule cells compared with CA1 pyramidal cells for both steady-state and sinusoidal voltage waveforms up to the gamma frequency range (f50% of 74 Hz). Similarly, distal synaptic inputs from entorhinal fibers can efficiently depolarize the somatic membrane of granule cells. Furthermore, the time course of distal dendritic synaptic potentials is remarkably fast, and temporal summation is restricted to a narrow time window in the range of approximately 10 ms attributable to the rapid dendritic charge redistribution during transient voltage signals. Therefore, the structure of the granule cell dendritic tree may be critically important for precise dendritic signal processing and coincidence detection during hippocampus-dependent memory formation and retrieval.
AU - Schmidt-Hieber, Christoph
AU - Peter Jonas
AU - Bischofberger, Josef
ID - 3821
IS - 31
JF - Journal of Neuroscience
TI - Subthreshold dendritic signal processing and coincidence detection in dentate gyrus granule cells
VL - 27
ER -
TY - CONF
AB - We present Qualitative Randomized CTL (QRCTL), a qualitative version of pCTL, for specifying properties of Markov Decision Processes (MDPs). QRCTL formulas can express the fact that certain temporal properties hold with probability 0 or 1, but they do not distinguish other probabilities values. We present a symbolic, polynomial time model-checking algorithm for QRCTL on MDPs. Then, we study the equivalence relation induced by QRCTL, called qualitative equivalence. We show that for finite alternating MDPs, where nondeterministic and probabilistic choice occur in different states, qualitative equivalence coincides with alternating bisimulation, and can thus be computed via efficient partition-refinement algorithms. Surprisingly, the result does not hold for non-alternating MDPs. Indeed, we show that no local partition refinement algorithm can compute qualitative equivalence on non-alternating MDPs. Finally, we consider QRCTL*, that is the “star extension” of QRCTL. We show that QRCTL and QRCTL* induce the same qualitative equivalence on alternating MDPs, while on non-alternating MDPs, the equivalence, arising from QRCTL* can be strictly finer We also provide a full characterization of the relation between qualitative equivalence, bisimulation, and alternating bisimulation, according to whether the MDPs are finite, and to whether their transition relations are finite-branching.
AU - de Alfaro, Luca
AU - Krishnendu Chatterjee
AU - Faella, Marco
AU - Legay, Axel
ID - 3881
TI - Qualitative logics and equivalences for probabilistic systems
ER -
TY - JOUR
AB - We study infinite stochastic games played by two players over a finite state space, with objectives specified by sets of infinite traces. The games are concurrent (players make moves simultaneously and independently), stochastic (the next state is determined by a probability distribution that depends on the current state and chosen moves of the players) and infinite (proceed for an infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game and epsilon-optimal strategies that ensure values within epsilon of the optimum value; and qualitative analysis, analyzing the set of states with optimum value 1 and epsilon-optimal strategies for the states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finite-prefix of traces, and show that the class of tail objectives is strictly richer than that of the omega-regular objectives. We develop new proof techniques to extend several properties of concurrent games with omega-regular objectives to concurrent games with tail objectives. We prove the positive limit-one property for tail objectives. The positive limit-one property states that for all concurrent games if the optimum value for a player is positive for a tail objective Phi at some state, then there is a state where the optimum value is 1 for the player for the objective Phi. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzerosum (not strictly conflicting objectives) games with simpler reachability objectives. A consequence of our analysis presents a polynomial time reduction of the quantitative analysis of tail objectives to the qualitative analysis for the subclass of one-player stochastic games (Markov decision processes).
AU - Krishnendu Chatterjee
ID - 3882
IS - 1-3
JF - Theoretical Computer Science
TI - Concurrent games with tail objectives
VL - 388
ER -
TY - CONF
AB - We consider games where the winning conditions are disjunctions (or dually, conjunctions) of parity conditions; we call them generalized parity games. These winning conditions, while omega-regular, arise naturally when considering fair simulation between parity automata, secure equilibria for parity conditions, and determinization of Rabin automata. We show that these games retain the computational complexity of Rabin and Streett conditions; i.e., they are NP-complete and co-NP-complete, respectively. The (co-) NP-hardness is proved for the special case of a conjunction/disjunction of two parity conditions, which is the case that arises in fair simulation and secure equilibria. However, considering these games as Rabin or Streett games is not optimal. We give an exposition of Zielonka's algorithm when specialized to this kind of games. The complexity of solving these games for k parity objectives with d priorities, n states, and m edges is O(n(2kd) (.) m) (.) (k(.)d)!/ d!(k), as compared to O(n(2kd .) m) - (k (.) d)! when these games are solved as Rabin/Streett games. We also extend the subexponential algorithm for solving parity games recently introduced by Jurdzinski, Paterson, and Zwick to generalized parity games. The resulting complexity of solving generalized parity games is n(O(root n)) (.) (k(.)d)!/d!(k). As a corollary we obtain an improved ald!k gorithm for Rabin and Streett games with d pairs, with time complexity n(O(root n)) (.) d!.
AU - Krishnendu Chatterjee
AU - Thomas Henzinger
AU - Piterman, Nir
ID - 3883
TI - Generalized parity games
VL - 4423
ER -
TY - CONF
AB - We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL*, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula).
AU - Krishnendu Chatterjee
AU - Thomas Henzinger
AU - Piterman, Nir
ID - 3884
TI - Strategy logic
VL - 4703
ER -
TY - CONF
AB - The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also present improved memory bounds for randomized almost-sure winning and optimal strategies.
AU - Krishnendu Chatterjee
ID - 3885
TI - Optimal strategy synthesis in stochastic Müller games
VL - 4423
ER -
TY - CONF
AB - The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We show that both the qualitative and quantitative problem for stochastic Müller games are PSPACE-complete. We also consider two well-known sub-classes of Müller objectives, namely, upward-closed and union-closed objectives, and show that both the qualitative and quantitative problem for these sub-classes are coNP-complete.
AU - Krishnendu Chatterjee
ID - 3886
TI - Stochastic Müller games are PSPACE-complete
VL - 4855
ER -
TY - CONF
AB - We consider Markov decision processes (MDPs) with multiple long-run average 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 epsilon-approximated by a memoryless strategy, for all epsilon > 0. In contrast to the single-objective case, the memoryless strategy may require randomization. We show that the Pareto curve can be approximated (a) in polynomial time in the size of the MDP for irreducible MDPs; and (b) in polynomial space in the size of the MDP for all MDPs. 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 for irreducible MDPs and in NP for all MDPs. These results provide algorithms for design exploration in MDP models with multiple long-run average objectives.
AU - Krishnendu Chatterjee
ID - 3887
TI - Markov decision processes with multiple long-run average objectives
VL - 4855
ER -
TY - JOUR
AB - Social insect colonies have evolved collective immune defences against parasites. These ‘social immune systems’ result from the cooperation of the individual group members to combat the increased risk of disease transmission that arises from sociality and group living. In this review we illustrate the pathways that parasites can take to infect a social insect colony and use these pathways as a framework to predict colony defence mechanisms and present the existing evidence. We find that the collective defences can be both prophylactic and activated on demand and consist of behavioural, physiological and organisational adaptations of the colony that prevent parasite entrance, establishment and spread. We discuss the regulation of collective immunity, which requires complex integration of information about both the parasites and the internal status of the insect colony. Our review concludes with an examination of the evolution of social immunity, which is based on the consequences of selection at both the individual and the colony level.
AU - Cremer, Sylvia
AU - Armitage, Sophie
AU - Schmid Hempel, Paul
ID - 3909
IS - 16
JF - Current Biology
TI - Social immunity
VL - 17
ER -