@article{890, abstract = {Recent discovery of the Large-billed Reed Warbler (Acrocephalus orinus) in museums and in the wild significantly expanded our knowledge of its morphological traits and genetic variability, and revealed new data on geographical distribution of the breeding grounds, migration routes and wintering locations of this species. It is now certain that A. orinus is breeding in Central Asia; however, the precise area of distribution remains unclear. The difficulty in the further study of this species lies in the small number of known specimens, with only 13 currently available in museums, and in the relative uncertainty of the breeding area and habitat of this species. Following morphological and genetic analyses from Svensson, et al, we describe 14 new A. orinus specimens from collections of Zoological Museums of the former USSR from the territory of Central Asian states. All of these specimens were erroneously labeled as Blyth's Reed Warbler (A. dumetorum), which is thought to be a breeding species in these areas. The 14 new A. orinus specimens were collected during breeding season while most of the 85 A. dumetorum specimens from the same area were collected during the migration period. Our data indicate that the Central Asian territory previously attributed as breeding grounds of A. dumetorum is likely to constitute the breeding territory of A. orinus. This rare case of a re-description of the breeding territory of a lost species emphasizes the importance of maintenance of museum collections around the world. If the present data on the breeding grounds of A. orinus are confirmed with field observations and collections, the literature on the biology of A. dumetorum from the southern part of its range may have to be reconsidered.}, author = {Koblik, Evgeniy A and Red'Kin, Yaroslav A and Meer, Margarita S and Derelle, Romain and Golenkina, Sofia A and Fyodor Kondrashov and Arkhipov, Vladimir Y}, journal = {PLoS One}, number = {4}, publisher = {Public Library of Science}, title = {{Acrocephalus orinus: A case of Mistaken identity}}, doi = {10.1371/journal.pone.0017716}, volume = {6}, year = {2011}, } @article{90, abstract = {A popular method for generating micron-sized aerosols is to submerge ultrasonic (ω ∼ MHz) piezoelectric oscillators in a water bath. The submerged oscillator atomizes the fluid, creating droplets with radii proportional to the wavelength of the standing wave at the fluid surface. Classical theory for the Faraday instability predicts a parametric instability driving a capillary wave at the subharmonic (ω / 2) frequency. For many applications it is desirable to reduce the size of the droplets; however, using higher frequency oscillators becomes impractical beyond a few MHz. Observations are presented that demonstrate that smaller droplets may also be created by increasing the driving amplitude of the oscillator, and that this effect becomes more pronounced for large driving frequencies. It is shown that these observations are consistent with a transition from droplets associated with subharmonic (ω/2) capillary waves to harmonic (ω) capillary waves induced by larger driving frequencies and amplitudes, as predicted by a stability analysis of the capillary waves.}, author = {Higginbotham, Andrew P and Guillen, A and Jones, Nick and Donnelly, Tom and Bernoff, Andrew}, journal = {Journal of the Acoustical Society of America}, number = {5}, pages = {2694 -- 2699}, publisher = {Acoustical Society of America}, title = {{Evidence of the harmonic Faraday instability in ultrasonic atomization experiments with a deep, inviscid fluid}}, doi = {10.1121/1.3643816}, volume = {130}, year = {2011}, } @article{9143, abstract = {Understanding and predicting the response of the hydrological cycle to climate change is a major challenge with important societal implications. Much progress has been made in understanding the response of global average precipitation by considering the energy balances of the atmosphere and the surface1,2,3,4,5,6. This energetic perspective reveals that changes in temperature, greenhouse gases, aerosols, solar forcing and cloud feedbacks can all affect the global average rate of precipitation5,7,8,9,10,11. Local precipitation changes have conventionally been analysed using the water vapour budget, but here we show that the energetic approach can be extended to local changes in precipitation by including changes in horizontal energy transport. In simulations of twenty-first century climate change, this energy transport accounts for much of the spatial variability in precipitation change. We show that changes in radiative and surface sensible heat fluxes are a guide to the local precipitation response over land and at large scales, but not at small scales over the ocean, where cloud and water vapour radiative feedbacks dampen the response. The energetic approach described here helps bridge the gap between our understanding of global and regional precipitation changes. It could be applied to better understand the response of regional precipitation to different radiative forcings, including geo-engineering schemes, as well as to understand the differences between the fast and slow responses of regional precipitation to such forcings.}, author = {Muller, Caroline J and O’Gorman, P. A.}, issn = {1758-678X}, journal = {Nature Climate Change}, number = {5}, pages = {266--271}, publisher = {Springer Nature}, title = {{An energetic perspective on the regional response of precipitation to climate change}}, doi = {10.1038/nclimate1169}, volume = {1}, year = {2011}, } @article{9144, abstract = {A cloud-resolving model is used to investigate the effect of warming on high percentiles of precipitation (precipitation extremes) in the idealized setting of radiative-convective equilibrium. While this idealized setting does not allow for several factors that influence precipitation in the tropics, it does allow for an evaluation of the response of precipitation extremes to warming in simulations with resolved rather than parameterized convection. The methodology developed should also be applicable to less idealized simulations. Modeled precipitation extremes are found to increase in magnitude in response to an increase in sea surface temperature. A dry static energy budget is used to relate the changes in precipitation extremes to changes in atmospheric temperature, vertical velocity, and precipitation efficiency. To first order, the changes in precipitation extremes are captured by changes in the mean temperature structure of the atmosphere. Changes in vertical velocities play a secondary role and tend to weaken the strength of precipitation extremes, despite an intensification of updraft velocities in the upper troposphere. The influence of changes in condensate transports on precipitation extremes is quantified in terms of a precipitation efficiency; it does not change greatly with warming. Tropical precipitation extremes have previously been found to increase at a greater fractional rate than the amount of atmospheric water vapor in observations of present-day variability and in some climate model simulations with parameterized convection. But the fractional increases in precipitation extremes in the cloud-resolving simulations are comparable in magnitude to those in surface water vapor concentrations (owing to a partial cancellation between dynamical and thermodynamical changes), and are substantially less than the fractional increases in column water vapor.}, author = {Muller, Caroline J and O’Gorman, Paul A. and Back, Larissa E.}, issn = {1520-0442}, journal = {Journal of Climate}, keywords = {Atmospheric Science}, number = {11}, pages = {2784--2800}, publisher = {American Meteorological Society}, title = {{Intensification of precipitation extremes with warming in a cloud-resolving model}}, doi = {10.1175/2011jcli3876.1}, volume = {24}, year = {2011}, } @article{918, abstract = {We study theoretically the shapes of a dividing epithelial monolayer of cells lying on top of an elastic stroma. The negative tension created by cell division provokes a buckling instability at a finite wave vector leading to the formation of periodic arrays of villi and crypts. The instability is similar to the buckling of a metallic plate under compression. We use the results to rationalize the various structures of the intestinal lining observed in vivo. Taking into account the coupling between cell division and local curvature, we obtain different patterns of villi and crypts, which could explain the different morphologies of the small intestine and the colon.}, author = {Hannezo, Edouard B and Prost, Jacques and Joanny, Jean}, journal = {Physical Review Letters}, number = {7}, publisher = {American Physical Society}, title = {{Instabilities of monolayered epithelia Shape and structure of villi and crypts}}, doi = {10.1103/PhysRevLett.107.078104}, volume = {107}, year = {2011}, } @article{919, abstract = {Collective cell migration in tissues occurs throughout embryonic development, during wound healing, and in cancerous tumor invasion, yet most detailed knowledge of cell migration comes from single-cell studies. As single cells migrate, the shape of the cell body fluctuates dramatically through cyclic processes of extension, adhesion, and retraction, accompanied by erratic changes in migration direction. Within confluent cell layers, such subcellular motions must be coupled between neighbors, yet the influence of these subcellular motions on collective migration is not known. Here we study motion within a confluent epithelial cell sheet, simultaneously measuring collective migration and subcellular motions, covering a broad range of length scales, time scales, and cell densities. At large length scales and time scales collective migration slows as cell density rises, yet the fastest cells move in large, multicell groups whose scale grows with increasing cell density. This behavior has an intriguing analogy to dynamic heterogeneities found in particulate systems as they become more crowded and approach a glass transition. In addition we find a diminishing self-diffusivity of short-wavelength motions within the cell layer, and growing peaks in the vibrational density of states associated with cooperative cell-shape fluctuations. Both of these observations are also intriguingly reminiscent of a glass transition. Thus, these results provide a broad and suggestive analogy between cell motion within a confluent layer and the dynamics of supercooled colloidal and molecular fluids approaching a glass transition.}, author = {Angelini, Thomas and Hannezo, Edouard B and Trepatc, Xavier and Marquez, Manuel and Fredberg, Jeffrey and Weitz, David}, journal = {Proceedings of the National Academy of Sciences of the United States of America}, number = {12}, pages = {4714 -- 4719}, publisher = {PNAS}, title = {{Glass-like dynamics of collective cell migration}}, doi = {10.1073/pnas.1010059108}, volume = {108}, year = {2011}, } @article{923, abstract = {The conserved role of Notch signaling in controlling intestinal cell fate specification and homeostasis has been extensively studied. Nevertheless, the precise identity of the cells in which Notch signaling is active and the role of different Notch receptor paralogues in the intestine remain ambiguous, due to the lack of reliable tools to investigate Notch expression and function in vivo. We generated a new series of transgenic mice that allowed us, by lineage analysis, to formally prove that Notch1 and Notch2 are specifically expressed in crypt stem cells. In addition, a novel Notch reporter mouse, Hes1-EmGFP SAT, demonstrated exclusive Notch activity in crypt stem cells and absorptive progenitors. This roster of knock-in and reporter mice represents a valuable resource to functionally explore the Notch pathway in vivo in virtually all tissues.}, author = {Fré, Silvia and Hannezo, Edouard B and Šale, Sanja and Huyghe, Mathilde and Lafkas, Daniel and Kissel, Holger and Louvi, Angeliki and Greve, Jeffrey and Louvard, Daniel and Artavanis Tsakonas, Spyros}, journal = {PLoS One}, number = {10}, publisher = {Public Library of Science}, title = {{Notch lineages and activity in intestinal stem cells determined by a new set of knock in mice}}, doi = {10.1371/journal.pone.0025785}, volume = {6}, year = {2011}, } @article{9483, abstract = {Imprinted genes are expressed primarily or exclusively from either the maternal or paternal allele, a phenomenon that occurs in flowering plants and mammals. Flowering plant imprinted gene expression has been described primarily in endosperm, a terminal nutritive tissue consumed by the embryo during seed development or after germination. Imprinted expression in Arabidopsis thaliana endosperm is orchestrated by differences in cytosine DNA methylation between the paternal and maternal genomes as well as by Polycomb group proteins. Currently, only 11 imprinted A. thaliana genes are known. Here, we use extensive sequencing of cDNA libraries to identify 9 paternally expressed and 34 maternally expressed imprinted genes in A. thaliana endosperm that are regulated by the DNA-demethylating glycosylase DEMETER, the DNA methyltransferase MET1, and/or the core Polycomb group protein FIE. These genes encode transcription factors, proteins involved in hormone signaling, components of the ubiquitin protein degradation pathway, regulators of histone and DNA methylation, and small RNA pathway proteins. We also identify maternally expressed genes that may be regulated by unknown mechanisms or deposited from maternal tissues. We did not detect any imprinted genes in the embryo. Our results show that imprinted gene expression is an extensive mechanistically complex phenomenon that likely affects multiple aspects of seed development.}, author = {Hsieh, Tzung-Fu and Shin, Juhyun and Uzawa, Rie and Silva, Pedro and Cohen, Stephanie and Bauer, Matthew J. and Hashimoto, Meryl and Kirkbride, Ryan C. and Harada, John J. and Zilberman, Daniel and Fischer, Robert L.}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {5}, pages = {1755--1762}, publisher = {National Academy of Sciences}, title = {{Regulation of imprinted gene expression in Arabidopsis endosperm}}, doi = {10.1073/pnas.1019273108}, volume = {108}, year = {2011}, } @misc{9522, abstract = {Little is known about chromatin remodeling events immediately after fertilization. A recent report by Autran et al. (2011) in Cell now shows that chromatin regulatory pathways that silence transposable elements are responsible for global delayed activation of gene expression in the early Arabidopsis embryo.}, author = {Zilberman, Daniel}, booktitle = {Developmental Cell}, issn = {1878-1551}, number = {6}, pages = {735--736}, publisher = {Elsevier}, title = {{Balancing parental contributions in plant embryonic gene activation}}, doi = {10.1016/j.devcel.2011.05.018}, volume = {20}, year = {2011}, } @article{967, abstract = {Motivated by recent experiments on the material Ba3NiSb 2O9, we consider a spin-one quantum antiferromagnet on a triangular lattice with the Heisenberg bilinear and biquadratic exchange interactions and a single-ion anisotropy. Using a fermionic "triplon" representation for spins, we study the phase diagram within mean-field theory. In addition to a fully gapped spin-liquid ground state, we find a state where one gapless triplon mode with a Fermi surface coexists with d+id topological pairing of the other triplons. Despite the existence of a Fermi surface, this ground state has fully gapped bulk spin excitations. Such a state has linear in-temperature specific heat and constant in-plane spin susceptibility, with an unusually high Wilson ratio.}, author = {Maksym Serbyn and Senthil, Todadri S and Lee, Patrick}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {18}, publisher = {American Physical Society}, title = {{Exotic S=1 spin-liquid state with fermionic excitations on the triangular lattice}}, doi = {10.1103/PhysRevB.84.180403}, volume = {84}, year = {2011}, } @article{968, abstract = {A Reply to the Comment by Andrei Sergeev, M. Reizer, and V. Mitin.}, author = {Maksym Serbyn and Skvortsov, Mikhail A and Varlamov, Andrei A and Galitski, Victor M}, journal = {Physical Review Letters}, number = {13}, publisher = {American Physical Society}, title = {{Serbyn et al. Reply:}}, doi = {10.1103/PhysRevLett.106.139702}, volume = {106}, year = {2011}, } @article{969, abstract = {We investigate the isotope effect on the London penetration depth of a superconductor which measures n S/m*, the ratio of superfluid density to effective mass. We use a simplified model of electrons weakly coupled to a single phonon frequency ω E, but assume that the energy gap Δ does not have any isotope effect. Nevertheless, we find an isotope effect for n S/m* which is significant if Δ is sufficiently large that it becomes comparable to ω E, a regime of interest to high-T c cuprate superconductors and possibly other families of unconventional superconductors with relatively high T c. Our model is too simple to describe the cuprates and it gives the wrong sign of the isotope effect when compared with experiment, but it is a proof of principle that the isotope effect exists for n S/m* in materials where the pairing gap and T c are not of phonon origin and have no isotope effect.}, author = {Maksym Serbyn and Lee, Patrick}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {2}, publisher = {American Physical Society}, title = {{Isotope effect on the superfluid density in conventional and high-temperature superconductors}}, doi = {10.1103/PhysRevB.83.024506}, volume = {83}, year = {2011}, } @misc{9762, abstract = {Defining population structure and genetic diversity levels is of the utmost importance for developing efficient conservation strategies. Overfishing has caused mean annual catches of the European spiny lobster (Palinurus elephas) to decrease alarmingly along its distribution area. In this context, there is a need for comprehensive studies to evaluate the genetic health of the exploited populations. The present work is based on a set of 10 nuclear markers amplified in 331 individuals from 10 different localities covering most of P. elephas distribution area. Samples from Atlantic and Mediterranean basins showed small but significant differences, indicating that P. elephas populations do not behave as a single panmictic unit but form two partially-overlapping groups. Despite intense overfishing, our dataset did not recover a recent bottleneck signal, and showed a large and stable historical effective size instead. This result could be accounted for by specific life history traits (reproduction and longevity) and the limitations of molecular markers in covering very recent timescales for non temporal samples. Our study emphasizes the necessity of integrating information on effective population sizes and life history parameters when evaluating population connectivity levels from genetic data.}, author = {Palero, Ferran and Abello, Pere and Macpherson, Enrique and Beaumont, Mark and Pascual, Marta}, publisher = {IST Austria}, title = {{Data from: Effect of oceanographic barriers and overfishing on the population genetic structure of the European spiny lobster (Palinurus elephas)}}, doi = {10.5061/dryad.299h8}, year = {2011}, } @article{469, abstract = {Spontaneous release of glutamate is important for maintaining synaptic strength and controlling spike timing in the brain. Mechanisms regulating spontaneous exocytosis remain poorly understood. Extracellular calcium concentration ([Ca2+]o) regulates Ca2+ entry through voltage-activated calcium channels (VACCs) and consequently is a pivotal determinant of action potential-evoked vesicle fusion. Extracellular Ca 2+ also enhances spontaneous release, but via unknown mechanisms. Here we report that external Ca2+ triggers spontaneous glutamate release more weakly than evoked release in mouse neocortical neurons. Blockade of VACCs has no effect on the spontaneous release rate or its dependence on [Ca2+]o. Intracellular [Ca2+] slowly increases in a minority of neurons following increases in [Ca2+]o. Furthermore, the enhancement of spontaneous release by extracellular calcium is insensitive to chelation of intracellular calcium by BAPTA. Activation of the calcium-sensing receptor (CaSR), a G-protein-coupled receptor present in nerve terminals, by several specific agonists increased spontaneous glutamate release. The frequency of spontaneous synaptic transmission was decreased in CaSR mutant neurons. The concentration-effect relationship for extracellular calcium regulation of spontaneous release was well described by a combination of CaSR-dependent and CaSR-independent mechanisms. Overall these results indicate that extracellular Ca2+ does not trigger spontaneous glutamate release by simply increasing calcium influx but stimulates CaSR and thereby promotes resting spontaneous glutamate release. }, author = {Vyleta, Nicholas and Smith, Stephen}, journal = {European Journal of Neuroscience}, number = {12}, pages = {4593 -- 4606}, publisher = {Wiley-Blackwell}, title = {{Spontaneous glutamate release is independent of calcium influx and tonically activated by the calcium-sensing receptor}}, doi = {10.1523/JNEUROSCI.6398-10.2011}, volume = {31}, year = {2011}, } @article{490, abstract = {BioSig is an open source software library for biomedical signal processing. The aim of the BioSig project is to foster research in biomedical signal processing by providing free and open source software tools for many different application areas. Some of the areas where BioSig can be employed are neuroinformatics, brain-computer interfaces, neurophysiology, psychology, cardiovascular systems, and sleep research. Moreover, the analysis of biosignals such as the electroencephalogram (EEG), electrocorticogram (ECoG), electrocardiogram (ECG), electrooculogram (EOG), electromyogram (EMG), or respiration signals is a very relevant element of the BioSig project. Specifically, BioSig provides solutions for data acquisition, artifact processing, quality control, feature extraction, classification, modeling, and data visualization, to name a few. In this paper, we highlight several methods to help students and researchers to work more efficiently with biomedical signals. }, author = {Schlögl, Alois and Vidaurre, Carmen and Sander, Tilmann}, journal = {Computational Intelligence and Neuroscience}, publisher = {Hindawi Publishing Corporation}, title = {{BioSig: The free and open source software library for biomedical signal processing}}, doi = {10.1155/2011/935364}, volume = {2011}, year = {2011}, } @article{491, abstract = {In their search for antigens, lymphocytes continuously shuttle among blood vessels, lymph vessels, and lymphatic tissues. Chemokines mediate entry of lymphocytes into lymphatic tissues, and sphingosine 1-phosphate (S1P) promotes localization of lymphocytes to the vasculature. Both signals are sensed through G protein-coupled receptors (GPCRs). Most GPCRs undergo ligand-dependent homologous receptor desensitization, a process that decreases their signaling output after previous exposure to high ligand concentration. Such desensitization can explain why lymphocytes do not take an intermediate position between two signals but rather oscillate between them. The desensitization of S1P receptor 1 (S1PR1) is mediated by GPCR kinase 2 (GRK2). Deletion of GRK2 in lymphocytes compromises desensitization by high vascular S1P concentrations, thereby reducing responsiveness to the chemokine signal and trapping the cells in the vascular compartment. The desensitization kinetics of S1PR1 allows lymphocytes to dynamically shuttle between vasculature and lymphatic tissue, although the positional information in both compartments is static.}, author = {Eichner, Alexander and Sixt, Michael K}, journal = {Science Signaling}, number = {198}, publisher = {American Association for the Advancement of Science}, title = {{Setting the clock for recirculating lymphocytes}}, doi = {10.1126/scisignal.2002617}, volume = {4}, year = {2011}, } @article{518, abstract = {Cancer stem cells or cancer initiating cells are believed to contribute to cancer recurrence after therapy. MicroRNAs (miRNAs) are short RNA molecules with fundamental roles in gene regulation. The role of miRNAs in cancer stem cells is only poorly understood. Here, we report miRNA expression profiles of glioblastoma stem cell-containing CD133 + cell populations. We find that miR-9, miR-9 * (referred to as miR-9/9 *), miR-17 and miR-106b are highly abundant in CD133 + cells. Furthermore, inhibition of miR-9/9 * or miR-17 leads to reduced neurosphere formation and stimulates cell differentiation. Calmodulin-binding transcription activator 1 (CAMTA1) is a putative transcription factor, which induces the expression of the anti-proliferative cardiac hormone natriuretic peptide A (NPPA). We identify CAMTA1 as an miR-9/9 * and miR-17 target. CAMTA1 expression leads to reduced neurosphere formation and tumour growth in nude mice, suggesting that CAMTA1 can function as tumour suppressor. Consistently, CAMTA1 and NPPA expression correlate with patient survival. Our findings could provide a basis for novel strategies of glioblastoma therapy.}, author = {Schraivogel, Daniel and Weinmann, Lasse and Beier, Dagmar and Tabatabai, Ghazaleh and Eichner, Alexander and Zhu, Jia and Anton, Martina and Sixt, Michael K and Weller, Michael and Beier, Christoph and Meister, Gunter}, journal = {EMBO Journal}, number = {20}, pages = {4309 -- 4322}, publisher = {Wiley-Blackwell}, title = {{CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma stem cells}}, doi = {10.1038/emboj.2011.301}, volume = {30}, year = {2011}, } @article{531, abstract = {Software transactional memories (STM) are described in the literature with assumptions of sequentially consistent program execution and atomicity of high level operations like read, write, and abort. However, in a realistic setting, processors use relaxed memory models to optimize hardware performance. Moreover, the atomicity of operations depends on the underlying hardware. This paper presents the first approach to verify STMs under relaxed memory models with atomicity of 32 bit loads and stores, and read-modify-write operations. We describe RML, a simple language for expressing concurrent programs. We develop a semantics of RML parametrized by a relaxed memory model. We then present our tool, FOIL, which takes as input the RML description of an STM algorithm restricted to two threads and two variables, and the description of a memory model, and automatically determines the locations of fences, which if inserted, ensure the correctness of the restricted STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and McRT STM under the memory models of sequential consistency, total store order, partial store order, and relaxed memory order for two threads and two variables. Finally, we extend the verification results for DSTM and TL2 to an arbitrary number of threads and variables by manually proving that the structural properties of STMs are satisfied at the hardware level of atomicity under the considered relaxed memory models.}, author = {Guerraoui, Rachid and Henzinger, Thomas A and Singh, Vasu}, journal = {Formal Methods in System Design}, number = {3}, pages = {297 -- 331}, publisher = {Springer}, title = {{Verification of STM on relaxed memory models}}, doi = {10.1007/s10703-011-0131-3}, volume = {39}, year = {2011}, } @misc{5379, abstract = {Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is ̃O(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the ̃O(n·m) boundary by presenting a new technique that reduces the running time to O(n2). This bound also leads to O(n2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m > n4/3 an earlier bound of O(min(m1.5, m·n2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n2), which is an improvement over earlier bounds for m > n4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.}, author = {Chatterjee, Krishnendu and Henzinger, Monika H}, issn = {2664-1690}, pages = {20}, publisher = {IST Austria}, title = {{An O(n2) time algorithm for alternating Büchi games}}, doi = {10.15479/AT:IST-2011-0009}, year = {2011}, } @misc{5380, abstract = {We consider 2-player games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. We study concurrent games with ω-regular winning conditions specified as parity objectives. We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). We study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies. In terms of precision, strategies can be deterministic, uniform, finite-precision or infinite-precision; and in terms of memory, strategies can be memoryless, finite-memory or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies. We show that the winning sets can be computed in O(n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms,that are obtained by characterization of the winning sets as μ-calculus formulas, are considerably more involved than those for turn-based games.}, author = {Chatterjee, Krishnendu}, issn = {2664-1690}, pages = {53}, publisher = {IST Austria}, title = {{Bounded rationality in concurrent parity games}}, doi = {10.15479/AT:IST-2011-0008}, year = {2011}, }