@article{6148, author = {Kammenga, Jan E. and Phillips, Patrick C. and de Bono, Mario and Doroszuk, Agnieszka}, issn = {0168-9525}, journal = {Trends in Genetics}, number = {4}, pages = {178--185}, publisher = {Elsevier}, title = {{Beyond induced mutants: using worms to study natural variation in genetic pathways}}, doi = {10.1016/j.tig.2008.01.001}, volume = {24}, year = {2008}, } @article{6149, author = {Olofsson, Birgitta and de Bono, Mario}, issn = {0960-9822}, journal = {Current Biology}, number = {5}, pages = {R204--R206}, publisher = {Elsevier}, title = {{Sleep: dozy worms and sleepy flies}}, doi = {10.1016/j.cub.2008.01.002}, volume = {18}, year = {2008}, } @article{1036, abstract = {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.}, author = {Gustavsson, Mattias and Haller, Elmar and Mark, Manfred and Danzl, Johann G and Rojas Kopeinig, Gabriel and Nägerl, Hanns}, journal = {Physical Review Letters}, number = {8}, publisher = {American Physical Society}, title = {{Control of interaction-induced dephasing of bloch oscillations}}, doi = {10.1103/PhysRevLett.100.080404}, volume = {100}, year = {2008}, } @article{1037, abstract = {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.}, author = {Knoop, Steven and Mark, Michael and Ferlaino, Francesca and Danzl, Johann G and Kraemer, Tobias and Nägerl, Hanns and Grimm, Rudolf}, journal = {Physical Review Letters}, number = {8}, publisher = {American Physical Society}, title = {{Metastable feshbach molecules in high rotational states}}, doi = {10.1103/PhysRevLett.100.083002}, volume = {100}, year = {2008}, } @article{1039, abstract = {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.}, author = {Danzl, Johann G and Haller, Elmar and Gustavsson, Mattias and Mark, Manfred and Hart, Russell and Bouloufa, Nadia and Dulieu, Olivier and Ritsch, Helmut and Nägerl, Hanns}, journal = {Science}, number = {5892}, pages = {1062 -- 1066}, publisher = {American Association for the Advancement of Science}, title = {{Quantum gas of deeply bound ground state molecules}}, doi = {10.1126/science.1159909}, volume = {321}, year = {2008}, } @article{10392, abstract = {Protonated formylmetallocenes [M(C5H5)(C5H4-CHOH)]+ (M = Fe, Ru) and their isomers have been studied at the BP86 and B3LYP levels of density functional theory. Oxygen-protonated isomers are the most stable forms in each case, with a plethora of ring- or metal-protonated species at least ca. 14 and 10 kcal/mol higher in energy for M = Fe and Ru, respectively. The computed rotational barriers around the C−C bond connecting the cyclopentadienyl and protonated formyl moieties, ca. 18 kcal/mol, are indicative of substantial conjugation between these moieties. Some of the ring- and iron-protonated species are models for possible intermediates in Friedel–Crafts acylation of ferrocene, and the computations provide further evidence that exo attack is clearly favored over endo attack of the electrophile in this reaction. The structures of the most stable mono- and diprotonated formylferrocenes are corroborated by the good agreement between GIAO-B3LYP-computed and experimental NMR chemical shifts.}, author = {Šarić, Anđela and Vrček, Valerije and Bühl, Michael}, issn = {1520-6041}, journal = {Organometallics}, keywords = {Inorganic Chemistry, Organic Chemistry, Physical and Theoretical Chemistry}, number = {3}, pages = {394--401}, publisher = {American Chemical Society}, title = {{Density functional study of protonated formylmetallocenes}}, doi = {10.1021/om700916f}, volume = {27}, year = {2008}, } @article{9457, abstract = {Eukaryotic chromatin is separated into functional domains differentiated by posttranslational histone modifications, histone variants, and DNA methylation1–6. Methylation is associated with repression of transcriptional initiation in plants and animals, and is frequently found in transposable elements. Proper methylation patterns are critical for eukaryotic development4,5, and aberrant methylation-induced silencing of tumor suppressor genes is a common feature of human cancer7. In contrast to methylation, the histone variant H2A.Z is preferentially deposited by the Swr1 ATPase complex near 5′ ends of genes where it promotes transcriptional competence8–20. How DNA methylation and H2A.Z influence transcription remains largely unknown. Here we show that in the plant Arabidopsis thaliana, regions of DNA methylation are quantitatively deficient in H2A.Z. Exclusion of H2A.Z is seen at sites of DNA methylation in the bodies of actively transcribed genes and in methylated transposons. Mutation of the MET1 DNA methyltransferase, which causes both losses and gains of DNA methylation4,5, engenders opposite changes in H2A.Z deposition, while mutation of the PIE1 subunit of the Swr1 complex that deposits H2A.Z17 leads to genome-wide hypermethylation. Our findings indicate that DNA methylation can influence chromatin structure and effect gene silencing by excluding H2A.Z, and that H2A.Z protects genes from DNA methylation.}, author = {Zilberman, Daniel and Coleman-Derr, Devin and Ballinger, Tracy and Henikoff, Steven}, issn = {1476-4687}, journal = {Nature}, keywords = {Multidisciplinary}, number = {7218}, pages = {125--129}, publisher = {Springer Nature}, title = {{Histone H2A.Z and DNA methylation are mutually antagonistic chromatin marks}}, doi = {10.1038/nature07324}, volume = {456}, year = {2008}, } @article{9537, abstract = {DNA methylation is an ancient process found in all domains of life. Although the enzymes that mediate methylation have remained highly conserved, DNA methylation has been adapted for a variety of uses throughout evolution, including defense against transposable elements and control of gene expression. Defects in DNA methylation are linked to human diseases, including cancer. Methylation has been lost several times in the course of animal and fungal evolution, thus limiting the opportunity for study in common model organisms. In the past decade, plants have emerged as a premier model system for genetic dissection of DNA methylation. A recent combination of plant genetics with powerful genomic approaches has led to a number of exciting discoveries and promises many more.}, author = {Zilberman, Daniel}, issn = {1369-5266}, journal = {Current Opinion in Plant Biology}, number = {5}, pages = {554--559}, publisher = {Elsevier }, title = {{The evolving functions of DNA methylation}}, doi = {10.1016/j.pbi.2008.07.004}, volume = {11}, year = {2008}, } @article{965, abstract = {We give many examples of applying Bogoliubov's forest formula to iterative solutions of various nonlinear equations. The same formula describes an extremely wide class of objects, from an ordinary quadratic equation to renormalization in quantum field theory.}, author = {Morozov, Alexei Y and Maksym Serbyn}, journal = {Theoretical and Mathematical Physics}, number = {2}, pages = {270 -- 293}, publisher = {Elsevier}, title = {{Nonlinear algebra and Bogoliubov's recursion}}, doi = {10.1007/s11232-008-0026-7}, volume = {154}, year = {2008}, } @article{3822, abstract = {Dentate gyrus granule cells transmit action potentials (APs) along their unmyelinated mossy fibre axons to the CA3 region. Although the initiation and propagation of APs are fundamental steps during neural computation, little is known about the site of AP initiation and the speed of propagation in mossy fibre axons. To address these questions, we performed simultaneous somatic and axonal whole-cell recordings from granule cells in acute hippocampal slices of adult mice at approximately 23 degrees C. Injection of short current pulses or synaptic stimulation evoked axonal and somatic APs with similar amplitudes. By contrast, the time course was significantly different, as axonal APs had a higher maximal rate of rise (464 +/- 30 V s(-1) in the axon versus 297 +/- 12 V s(-1) in the soma, mean +/- s.e.m.). Furthermore, analysis of latencies between the axonal and somatic signals showed that APs were initiated in the proximal axon at approximately 20-30 mum distance from the soma, and propagated orthodromically with a velocity of 0.24 m s(-1). Qualitatively similar results were obtained at a recording temperature of approximately 34 degrees C. Modelling of AP propagation in detailed cable models of granule cells suggested that a approximately 4 times higher Na(+) channel density ( approximately 1000 pS mum(-2)) in the axon might account for both the higher rate of rise of axonal APs and the robust AP initiation in the proximal mossy fibre axon. This may be of critical importance to separate dendritic integration of thousands of synaptic inputs from the generation and transmission of a common AP output.}, author = {Schmidt Hieber, Christoph and Jonas, Peter M and Bischofberger, Josef}, issn = {1469-7793}, journal = {The Journal of Physiology}, number = {7}, pages = {1849 -- 57}, publisher = {Wiley-Blackwell}, title = {{Action potential initiation and propagation in hippocampal mossy fibre axons}}, doi = {10.1113/jphysiol.2007.150151 }, volume = {586}, year = {2008}, } @article{3823, abstract = {Two studies in this issue of Neuron (Kwon and Castillo and Rebola et al.) show that the mossy fiber-CA3 pyramidal neuron synapse, a hippocampal synapse well known for its presynaptic plasticity, exhibits a novel form of long-term potentiation of NMDAR-mediated currents, which is induced and expressed postsynaptically.}, author = {Kerr, Angharad and Jonas, Peter M}, issn = {1097-4199}, journal = {Neuron}, number = {1}, pages = {5 -- 7}, publisher = {Elsevier}, title = {{The two sides of hippocampal mossy fiber plasticity (Review)}}, doi = {10.1016/j.neuron.2007.12.015}, volume = {57}, year = {2008}, } @article{3824, abstract = {It is generally thought that transmitter release at mammalian central synapses is triggered by Ca2+ microdomains, implying loose coupling between presynaptic Ca2+ channels and Ca2+ sensors of exocytosis. Here we show that Ca2+ channel subunit immunoreactivity is highly concentrated in the active zone of GABAergic presynaptic terminals of putative parvalbumin-containing basket cells in the hippocampus. Paired recording combined with presynaptic patch pipette perfusion revealed that GABA release at basket cell-granule cell synapses is sensitive to millimolar concentrations of the fast Ca2+ chelator BAPTA but insensitive to the slow Ca2+ chelator EGTA. These results show that Ca2+ source and Ca2+ sensor are tightly coupled at this synapse, with distances in the range of 10-20 nm. Models of Ca2+ inflow-exocytosis coupling further reveal that the tightness of coupling increases efficacy, speed, and temporal precision of transmitter release. Thus, tight coupling contributes to fast feedforward and feedback inhibition in the hippocampal network.}, author = {Bucurenciu, Iancu and Kulik, Ákos and Schwaller, Beat and Frotscher, Michael and Jonas, Peter M}, issn = {1097-4199}, journal = {Neuron}, number = {4}, pages = {536 -- 45}, publisher = {Elsevier}, title = {{Nanodomain coupling between Ca(2+) channels and Ca2+ sensors promotes fast and efficient transmitter release at a cortical GABAergic synapse}}, doi = {10.1016/j.neuron.2007.12.026}, volume = {57}, year = {2008}, } @article{3825, abstract = {Fast-spiking parvalbumin-expressing basket cells (BCs) represent a major type of inhibitory interneuron in the hippocampus. These cells inhibit principal cells in a temporally precise manner and are involved in the generation of network oscillations. Although BCs show a unique expression profile of Ca(2+)-permeable receptors, Ca(2+)-binding proteins and Ca(2+)-dependent signalling molecules, physiological Ca(2+) signalling in these interneurons has not been investigated. To study action potential (AP)-induced dendritic Ca(2+) influx and buffering, we combined whole-cell patch-clamp recordings with ratiometric Ca(2+) imaging from the proximal apical dendrites of rigorously identified BCs in acute slices, using the high-affinity Ca(2+) indicator fura-2 or the low-affinity dye fura-FF. Single APs evoked dendritic Ca(2+) transients with small amplitude. Bursts of APs evoked Ca(2+) transients with amplitudes that increased linearly with AP number. Analysis of Ca(2+) transients under steady-state conditions with different fura-2 concentrations and during loading with 200 microm fura-2 indicated that the endogenous Ca(2+)-binding ratio was approximately 200 (kappa(S) = 202 +/- 26 for the loading experiments). The peak amplitude of the Ca(2+) transients measured directly with 100 microm fura-FF was 39 nm AP(-1). At approximately 23 degrees C, the decay time constant of the Ca(2+) transients was 390 ms, corresponding to an extrusion rate of approximately 600 s(-1). At 34 degrees C, the decay time constant was 203 ms and the corresponding extrusion rate was approximately 1100 s(-1). At both temperatures, continuous theta-burst activity with three to five APs per theta cycle, as occurs in vivo during exploration, led to a moderate increase in the global Ca(2+) concentration that was proportional to AP number, whereas more intense stimulation was required to reach micromolar Ca(2+) concentrations and to shift Ca(2+) signalling into a non-linear regime. In conclusion, dentate gyrus BCs show a high endogenous Ca(2+)-binding ratio, a small AP-induced dendritic Ca(2+) influx, and a relatively slow Ca(2+) extrusion. These specific buffering properties of BCs will sharpen the time course of local Ca(2+) signals, while prolonging the decay of global Ca(2+) signals.}, author = {Aponte, Yexica and Bischofberger, Josef and Jonas, Peter M}, issn = {1469-7793}, journal = {The Journal of Physiology}, number = {8}, pages = {2061 -- 75}, publisher = {Wiley-Blackwell}, title = {{Efficient Ca(2+) buffering in fast-spiking basket cells of rat hippocampus}}, doi = {10.1113/jphysiol.2007.147298}, volume = {586}, year = {2008}, } @article{3826, abstract = {Gamma frequency (30-100 Hz) oscillations in the mature cortex underlie higher cognitive functions. Fast signaling in GABAergic interneuron networks plays a key role in the generation of these oscillations. During development of the rodent brain, gamma activity appears at the end of the first postnatal week, but frequency and synchrony reach adult levels only by the fourth week. However, the mechanisms underlying the maturation of gamma activity are unclear. Here we demonstrate that hippocampal basket cells (BCs), the proposed cellular substrate of gamma oscillations, undergo marked changes in their morphological, intrinsic, and synaptic properties between postnatal day 6 (P6) and P25. During maturation, action potential duration, propagation time, duration of the release period, and decay time constant of IPSCs decreases by approximately 30-60%. Thus, postnatal development converts BCs from slow into fast signaling devices. Computational analysis reveals that BC networks with young intrinsic and synaptic properties as well as reduced connectivity generate oscillations with moderate coherence in the lower gamma frequency range. In contrast, BC networks with mature properties and increased connectivity generate highly coherent activity in the upper gamma frequency band. Thus, late postnatal maturation of BCs enhances coherence in neuronal networks and will thereby contribute to the development of cognitive brain functions.}, author = {Doischer, Daniel and Hosp, Jonas and Yanagawa, Yuchio and Obata, Kunihiko and Jonas, Peter M and Vida, Imre and Bartos, Marlene}, issn = {1529-2401}, journal = {The Journal of Neuroscience}, number = {48}, pages = {12956 -- 68}, publisher = {Society for Neuroscience}, title = {{Postnatal differentiation of basket cells from slow to fast signaling devices}}, doi = {10.1523/JNEUROSCI.2890-08.2008}, volume = {28}, year = {2008}, } @article{3827, abstract = {Previous studies revealed that synaptotagmin 1 is the major Ca(2+) sensor for fast synchronous transmitter release at excitatory synapses. However, the molecular identity of the Ca(2+) sensor at hippocampal inhibitory synapses has not been determined. To address the functional role of synaptotagmin 1 at identified inhibitory terminals, we made paired recordings from synaptically connected basket cells (BCs) and granule cells (GCs) in the dentate gyrus in organotypic slice cultures from wild-type and synaptotagmin 1-deficient mice. As expected, genetic elimination of synaptotagmin 1 abolished synchronous transmitter release at excitatory GC-BC synapses. However, synchronous release at inhibitory BC-GC synapses was maintained. Quantitative analysis revealed that elimination of synaptotagmin 1 reduced release probability and depression but maintained the synchrony of transmitter release at BC-GC synapses. Elimination of synaptotagmin 1 also increased the frequency of both miniature excitatory postsynaptic currents (measured in BCs) and miniature inhibitory postsynaptic currents (recorded in GCs), consistent with a clamping function of synaptotagmin 1 at both excitatory and inhibitory terminals. Single-cell reverse-transcription quantitative PCR analysis revealed that single BCs coexpressed multiple synaptotagmin isoforms, including synaptotagmin 1-5, 7, and 11-13. Our results indicate that, in contrast to excitatory synapses, synaptotagmin 1 is not absolutely required for synchronous release at inhibitory BC-GC synapses. Thus, alternative fast Ca(2+) sensors contribute to synchronous release of the inhibitory transmitter GABA in cortical circuits.}, author = {Kerr, Angharad and Reisinger, Ellen and Jonas, Peter M}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {40}, pages = {15581 -- 6}, publisher = {National Academy of Sciences}, title = {{Differential dependence of phasic transmitter release on synaptotagmin 1 at GABAergic and glutamatergic hippocampal synapses}}, doi = {10.1073/pnas.0800621105}, volume = {105}, year = {2008}, } @inbook{3872, abstract = {We survey value iteration algorithms on graphs. Such algorithms can be used for determining the existence of certain paths (model checking), the existence of certain strategies (game solving), and the probabilities of certain events (performance analysis). We classify the algorithms according to the value domain (boolean, probabilistic, or quantitative); according to the graph structure (nondeterministic, probabilistic, or multi-player); according to the desired property of paths (Borel level 1, 2, or 3); and according to the alternation depth and convergence rate of fixpoint computations.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A}, booktitle = {25 Years in Model Checking}, isbn = {9783540698494}, pages = {107 -- 138}, publisher = {Springer Nature}, title = {{Value iteration}}, doi = {10.1007/978-3-540-69850-0_7}, volume = {5000}, year = {2008}, } @inproceedings{3873, abstract = {We study the controller synthesis problem under budget constraints. In this problem, there is a cost associated with making an observation, and a controller can make only a limited number of observations in each round so that the total cost of the observations does not exceed a given fixed budget. The controller must ensure some omega-regular requirement subject to the budget constraint. Budget constraints arise in designing and implementing controllers for resource-constrained embedded systems, where a controller may not have enough power, time, or bandwidth to obtain data from all sensors in each round. They lead to games of imperfect information, where the unknown information is not fixed a priori, but can vary from round to round, based on the choices made by the controller how to allocate its budget. We show that the budget-constrained synthesis problem for W-regular objectives is complete for exponential time. In addition to studying synthesis under a fixed budget constraint, we study the budget optimization problem, where given a plant, an objective, and observation costs, we have to find a controller that achieves the objective with minimal average accumulated cost (or minimal peak cost). We show that this problem is reducible to a game of imperfect information where the winning objective is a conjunction of an omega-regular condition and a long-run average condition (or a least max-cost condition), and this again leads to an exponential-time algorithm. Finally, we extend our results to games over infinite state spaces, and show that the budget-constrained synthesis problem is decidable for infinite state games with stable quotients of finite index. Consequently, the discrete time budget-constrained synthesis problem is decidable for rectangular hybrid automata.}, author = {Chatterjee, Krishnendu and Majumdar, Ritankar and Henzinger, Thomas A}, booktitle = {11th Workshop on Hybrid Systems: Computation and Control}, issn = {1611-3349}, location = {St. Louis, MO, United States}, pages = {72 -- 86}, publisher = {Springer Nature}, title = {{Controller synthesis with budget constraints}}, doi = {DOI: 10.1007/978-3-540-78929-1_6}, volume = {4981}, year = {2008}, } @inproceedings{3874, abstract = {We consider concurrent two-player timed automaton games with omega-regular objectives specified as parity conditions. These games offer an appropriate model for the synthesis of real-time controllers. Earlier works on timed games focused on pure strategies for each player. We study, for the first time, the use of randomized strategies in such games. While pure (i.e., nonrandomized) strategies in timed games require infinite memory for winning even with respect to reachability objectives, we show that randomized strategies can win with finite memory with respect to all parity objectives. Also, the synthesized randomized real-time controllers are much simpler in structure than the corresponding pure controllers, and therefore easier to implement. For safety objectives we prove the existence of pure finite-memory winning strategies. Finally, while randomization helps in simplifying the strategies required for winning timed parity games, we prove that randomization does not help in winning at more states.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Prabhu, Vinayak}, booktitle = {11th Workshop on Hybrid Systems: Computation and Control}, issn = {1611-3349}, location = {St. Louis, MO, United States}, pages = {87 -- 100}, publisher = {Springer Nature}, title = {{Trading infinite memory for uniform randomness in timed games}}, doi = {10.1007/978-3-540-78929-1_7}, volume = {4981}, year = {2008}, } @inproceedings{3875, abstract = {We study the problem of model checking Interval-valued Discrete-time Markov Chains (IDTMC). IDTMCs are discrete-time finite Markov Chains for which the exact transition probabilities are riot known. Instead in IDTMCs, each transition is associated with an interval in which the actual transition probability must lie. We consider two semantic interpretations for the uncertainty in the transition probabilities of an IDTMC. In the first interpretation, we think of an IDTMC as representing a (possibly uncountable) family of (classical) discrete-time Markov Chains, where each member of the family is a Markov Chain whose transition probabilities lie within the interval range given in the IDTMC. We call this semantic interpretation Uncertain Markov Chains (UMC). In the second semantics for an IDTMC, which we call Interval Markov Decision Process (IMDP), we view the uncertainty as being resolved through non-determinism. In other words, each time a state is visited, we adversarially pick a transition distribution that respects the interval constraints, and take a probabilistic step according to the chosen distribution. We introduce a logic omega-PCTL that can express liveness, strong fairness, and omega-regular properties (such properties cannot be expressed in PCTL). We show that the omega-PCTL model checking problem for Uncertain Markov Chain semantics is decidable in PSPACE (same as the best known upper bound for PCTL) and for Interval Markov Decision Process semantics is decidable in coNP (improving the previous known PSPACE bound for PCTL). We also show that the qualitative fragment of the logic can lie solved in coNP for the UMC interpretation, and can be solved in polynomial time for a sub-class of UMCs. We also prove lower bounds for these model checking problems. We show that the model checking problem of IDTMCs with LTL formulas can be solved for both UMC and IMDP semantics by reduction to the model checking problem of IDTMC with omega-PcTL formulas.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Sen, Koushik}, booktitle = {Foundations of Software Science and Computational Structures - 11th International Conference}, issn = {1611-3349}, location = {Budapest, Hungary}, pages = {302 -- 317}, publisher = {Springer Nature}, title = {{Model-checking omega-regular properties of interval Markov chains}}, doi = {10.1007/978-3-540-78499-9_22}, volume = {4962}, year = {2008}, } @inproceedings{3876, abstract = {We consider two-player games played in real time on game structures with clocks and parity objectives. The games are concurrent in that at each turn, both players independently propose a time delay and an action, and the action with the shorter delay is chosen. To prevent a player from winning by blocking time, we restrict each player to strategies that ensure that the player cannot be responsible for causing a zeno run. First, we present an efficient reduction of these games to turn-based (i.e., nonconcurrent) finite-state (i.e., untimed) parity games. The states of the resulting game are pairs of clock regions of the original game. Our reduction improves the best known complexity for solving timed parity games. Moreover, the rich class of algorithms for classical parity games can now be applied to timed parity games. Second, we consider two restricted classes of strategies for the player that represents the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust strategies. Using a limit-robust strategy, the controller cannot choose an exact real-valued time delay but must allow for some nonzero jitter in each of its actions. If there is a given lower bound on the jitter, then the strategy is bounded-robust. We show that exact strategies are more powerful than limit-robust strategies, which are more powerful than bounded-robust strategies for any bound. For both kinds of robust strategies, we present efficient reductions to standard timed automaton games. These reductions provide algorithms for the synthesis of robust real-time controllers.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Prabhu, Vinayak}, booktitle = {Proceedings of the 6th international conference on Formal Modeling and Analysis of Timed Systems}, isbn = {9783540857778}, issn = {1611-3349}, location = {Saint Malo, France}, pages = {124 -- 140}, publisher = {Springer Nature}, title = {{Timed parity games: complexity and robustness}}, doi = {10.1007/978-3-540-85778-5_10}, volume = {5215}, year = {2008}, }