@inproceedings{2891,
  abstract     = {Quantitative automata are nondeterministic finite automata with edge weights. They value a
run by some function from the sequence of visited weights to the reals, and value a word by its
minimal/maximal run. They generalize boolean automata, and have gained much attention in
recent years. Unfortunately, important automaton classes, such as sum, discounted-sum, and
limit-average automata, cannot be determinized. Yet, the quantitative setting provides the potential
of approximate determinization. We define approximate determinization with respect to
a distance function, and investigate this potential.
We show that sum automata cannot be determinized approximately with respect to any
distance function. However, restricting to nonnegative weights allows for approximate determinization
with respect to some distance functions.
Discounted-sum automata allow for approximate determinization, as the influence of a word’s
suffix is decaying. However, the naive approach, of unfolding the automaton computations up
to a sufficient level, is shown to be doubly exponential in the discount factor. We provide an
alternative construction that is singly exponential in the discount factor, in the precision, and
in the number of states. We prove matching lower bounds, showing exponential dependency on
each of these three parameters.
Average and limit-average automata are shown to prohibit approximate determinization with
respect to any distance function, and this is the case even for two weights, 0 and 1.},
  author       = {Boker, Udi and Henzinger, Thomas A},
  booktitle    = {Leibniz International Proceedings in Informatics},
  location     = {Hyderabad, India},
  pages        = {362 -- 373},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Approximate determinization of quantitative automata}},
  doi          = {10.4230/LIPIcs.FSTTCS.2012.362},
  volume       = {18},
  year         = {2012},
}

@inproceedings{10906,
  abstract     = {HSF(C) is a tool that automates verification of safety and liveness properties for C programs. This paper describes the verification approach taken by HSF(C) and provides instructions on how to install and use the tool.},
  author       = {Grebenshchikov, Sergey and Gupta, Ashutosh and Lopes, Nuno P. and Popeea, Corneliu and Rybalchenko, Andrey},
  booktitle    = {Tools and Algorithms for the Construction and Analysis of Systems},
  editor       = {Flanagan, Cormac and König, Barbara},
  isbn         = {9783642287558},
  issn         = {1611-3349},
  location     = {Tallinn, Estonia},
  pages        = {549--551},
  publisher    = {Springer},
  title        = {{HSF(C): A software verifier based on Horn clauses}},
  doi          = {10.1007/978-3-642-28756-5_46},
  volume       = {7214},
  year         = {2012},
}

@article{506,
  author       = {Sixt, Michael K},
  journal      = {Journal of Cell Biology},
  number       = {3},
  pages        = {347 -- 349},
  publisher    = {Rockefeller University Press},
  title        = {{Cell migration: Fibroblasts find a new way to get ahead}},
  doi          = {10.1083/jcb.201204039},
  volume       = {197},
  year         = {2012},
}

@inproceedings{10904,
  abstract     = {Multi-dimensional mean-payoff and energy games provide the mathematical foundation for the quantitative study of reactive systems, and play a central role in the emerging quantitative theory of verification and synthesis. In this work, we study the strategy synthesis problem for games with such multi-dimensional objectives along with a parity condition, a canonical way to express ω-regular conditions. While in general, the winning strategies in such games may require infinite memory, for synthesis the most relevant problem is the construction of a finite-memory winning strategy (if one exists). Our main contributions are as follows. First, we show a tight exponential bound (matching upper and lower bounds) on the memory required for finite-memory winning strategies in both multi-dimensional mean-payoff and energy games along with parity objectives. This significantly improves the triple exponential upper bound for multi energy games (without parity) that could be derived from results in literature for games on VASS (vector addition systems with states). Second, we present an optimal symbolic and incremental algorithm to compute a finite-memory winning strategy (if one exists) in such games. Finally, we give a complete characterization of when finite memory of strategies can be traded off for randomness. In particular, we show that for one-dimension mean-payoff parity games, randomized memoryless strategies are as powerful as their pure finite-memory counterparts.},
  author       = {Chatterjee, Krishnendu and Randour, Mickael and Raskin, Jean-François},
  booktitle    = {CONCUR 2012 - Concurrency Theory},
  editor       = {Koutny, Maciej and Ulidowski, Irek},
  isbn         = {9783642329395},
  issn         = {1611-3349},
  location     = {Newcastle upon Tyne, United Kingdom},
  pages        = {115--131},
  publisher    = {Springer},
  title        = {{Strategy synthesis for multi-dimensional quantitative objectives}},
  doi          = {10.1007/978-3-642-32940-1_10},
  volume       = {7454},
  year         = {2012},
}

@article{3243,
  abstract     = {Wie wandelt sich das Berufsbild in Wissenschaftlichen Bibliotheken? Patrick Danowski gibt seine Einschätzung ab. },
  author       = {Danowski, Patrick},
  issn         = {1607-7172},
  journal      = {Büchereiperspektiven},
  number       = {1},
  pages        = {11},
  publisher    = {Büchereiverband Österreichs},
  title        = {{Zwischen Technologie und Kommunikation}},
  volume       = {2012},
  year         = {2012},
}

@article{2950,
  abstract     = {Contractile actomyosin rings drive various fundamental morphogenetic processes ranging from cytokinesis to wound healing. Actomyosin rings are generally thought to function by circumferential contraction. Here, we show that the spreading of the enveloping cell layer (EVL) over the yolk cell during zebrafish gastrulation is driven by a contractile actomyosin ring. In contrast to previous suggestions, we find that this ring functions not only by circumferential contraction but also by a flow-friction mechanism. This generates a pulling force through resistance against retrograde actomyosin flow. EVL spreading proceeds normally in situations where circumferential contraction is unproductive, indicating that the flow-friction mechanism is sufficient. Thus, actomyosin rings can function in epithelial morphogenesis through a combination of cable-constriction and flow-friction mechanisms.},
  author       = {Behrndt, Martin and Salbreux, Guillaume and Campinho, Pedro and Hauschild, Robert and Oswald, Felix and Roensch, Julia and Grill, Stephan and Heisenberg, Carl-Philipp J},
  journal      = {Science},
  number       = {6104},
  pages        = {257 -- 260},
  publisher    = {American Association for the Advancement of Science},
  title        = {{Forces driving epithelial spreading in zebrafish gastrulation}},
  doi          = {10.1126/science.1224143},
  volume       = {338},
  year         = {2012},
}

@article{3157,
  abstract     = {Colorectal tumours that are wild type for KRAS are often sensitive to EGFR blockade, but almost always develop resistance within several months of initiating therapy. The mechanisms underlying this acquired resistance to anti-EGFR antibodies are largely unknown. This situation is in marked contrast to that of small-molecule targeted agents, such as inhibitors of ABL, EGFR, BRAF and MEK, in which mutations in the genes encoding the protein targets render the tumours resistant to the effects of the drugs. The simplest hypothesis to account for the development of resistance to EGFR blockade is that rare cells with KRAS mutations pre-exist at low levels in tumours with ostensibly wild-type KRAS genes. Although this hypothesis would seem readily testable, there is no evidence in pre-clinical models to support it, nor is there data from patients. To test this hypothesis, we determined whether mutant KRAS DNA could be detected in the circulation of 28 patients receiving monotherapy with panitumumab, a therapeutic anti-EGFR antibody. We found that 9 out of 24 (38%) patients whose tumours were initially KRAS wild type developed detectable mutations in KRAS in their sera, three of which developed multiple different KRAS mutations. The appearance of these mutations was very consistent, generally occurring between 5 and 6months following treatment. Mathematical modelling indicated that the mutations were present in expanded subclones before the initiation of panitumumab treatment. These results suggest that the emergence of KRAS mutations is a mediator of acquired resistance to EGFR blockade and that these mutations can be detected in a non-invasive manner. They explain why solid tumours develop resistance to targeted therapies in a highly reproducible fashion.},
  author       = {Diaz Jr, Luis and Williams, Richard and Wu, Jian and Kinde, Isaac and Hecht, Joel and Berlin, Jordan and Allen, Benjamin and Božić, Ivana and Reiter, Johannes and Nowak, Martin and Kinzler, Kenneth and Oliner, Kelly and Vogelstein, Bert},
  journal      = {Nature},
  number       = {7404},
  pages        = {537 -- 540},
  publisher    = {Nature Publishing Group},
  title        = {{The molecular evolution of acquired resistance to targeted EGFR blockade in colorectal cancers}},
  doi          = {10.1038/nature11219},
  volume       = {486},
  year         = {2012},
}

@article{3260,
  abstract     = {Many scenarios in the living world, where individual organisms compete for winning positions (or resources), have properties of auctions. Here we study the evolution of bids in biological auctions. For each auction, n individuals are drawn at random from a population of size N. Each individual makes a bid which entails a cost. The winner obtains a benefit of a certain value. Costs and benefits are translated into reproductive success (fitness). Therefore, successful bidding strategies spread in the population. We compare two types of auctions. In “biological all-pay auctions”, the costs are the bid for every participating individual. In “biological second price all-pay auctions”, the cost for everyone other than the winner is the bid, but the cost for the winner is the second highest bid. Second price all-pay auctions are generalizations of the “war of attrition” introduced by Maynard Smith. We study evolutionary dynamics in both types of auctions. We calculate pairwise invasion plots and evolutionarily stable distributions over the continuous strategy space. We find that the average bid in second price all-pay auctions is higher than in all-pay auctions, but the average cost for the winner is similar in both auctions. In both cases, the average bid is a declining function of the number of participants, n. The more individuals participate in an auction the smaller is the chance of winning, and thus expensive bids must be avoided.
},
  author       = {Chatterjee, Krishnendu and Reiter, Johannes and Nowak, Martin},
  journal      = {Theoretical Population Biology},
  number       = {1},
  pages        = {69 -- 80},
  publisher    = {Academic Press},
  title        = {{Evolutionary dynamics of biological auctions}},
  doi          = {10.1016/j.tpb.2011.11.003},
  volume       = {81},
  year         = {2012},
}

@article{2263,
  abstract     = {Nestin-cre transgenic mice have been widely used to direct recombination to neural stem cells (NSCs) and intermediate neural progenitor cells (NPCs). Here we report that a readily utilized, and the only commercially available, Nestin-cre line is insufficient for directing recombination in early embryonic NSCs and NPCs. Analysis of recombination efficiency in multiple cre-dependent reporters and a genetic mosaic line revealed consistent temporal and spatial patterns of recombination in NSCs and NPCs. For comparison we utilized a knock-in Emx1cre line and found robust recombination in NSCs and NPCs in ventricular and subventricular zones of the cerebral cortices as early as embryonic day 12.5. In addition we found that the rate of Nestin-cre driven recombination only reaches sufficiently high levels in NSCs and NPCs during late embryonic and early postnatal periods. These findings are important when commercially available cre lines are considered for directing recombination to embryonic NSCs and NPCs.},
  author       = {Liang, Huixuan and Hippenmeyer, Simon and Ghashghaei, H.},
  journal      = {Biology Open},
  number       = {12},
  pages        = {1200 -- 1203},
  publisher    = {Company of Biologists},
  title        = {{A Nestin-cre transgenic mouse is insufficient for recombination in early embryonic neural progenitors}},
  doi          = {10.1242/bio.20122287},
  volume       = {1},
  year         = {2012},
}

@article{2965,
  abstract     = {Dieser Artikel soll die sechs verschiedenen Creative Commons Lizenzen erläutern und ihre Bedeutung im Rahmen des wissenschaftlichen Publizierens und des Open Access erklären (CC-BY, CC-BY-SA, CC-BY-NC, CC-BY-ND, CC-BYNC-SA, CC-BY-NC-ND).},
  author       = {Danowski, Patrick},
  journal      = {Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare},
  number       = {2},
  pages        = {200 -- 212},
  publisher    = {Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare},
  title        = {{Kontext Open Access: Creative Commons}},
  volume       = {65},
  year         = {2012},
}

@article{3262,
  abstract     = {Living cells must control the reading out or &quot;expression&quot; of information encoded in their genomes, and this regulation often is mediated by transcription factors--proteins that bind to DNA and either enhance or repress the expression of nearby genes. But the expression of transcription factor proteins is itself regulated, and many transcription factors regulate their own expression in addition to responding to other input signals. Here we analyze the simplest of such self-regulatory circuits, asking how parameters can be chosen to optimize information transmission from inputs to outputs in the steady state. Some nonzero level of self-regulation is almost always optimal, with self-activation dominant when transcription factor concentrations are low and self-repression dominant when concentrations are high. In steady state the optimal self-activation is never strong enough to induce bistability, although there is a limit in which the optimal parameters are very close to the critical point.},
  author       = {Tkacik, Gasper and Walczak, Aleksandra and Bialek, William},
  journal      = {Physical Review E},
  number       = {4},
  publisher    = {American Physical Society},
  title        = {{Optimizing information flow in small genetic networks. III. A self-interacting gene}},
  doi          = {10.1103/PhysRevE.85.041903},
  volume       = {85},
  year         = {2012},
}

@inproceedings{2936,
  abstract     = {The notion of delays arises naturally in many computational models, such as, in the design of circuits, control systems, and dataflow languages. In this work, we introduce automata with delay blocks (ADBs), extending finite state automata with variable time delay blocks, for deferring individual transition output symbols, in a discrete-time setting. We show that the ADB languages strictly subsume the regular languages, and are incomparable in expressive power to the context-free languages. We show that ADBs are closed under union, concatenation and Kleene star, and under intersection with regular languages, but not closed under complementation and intersection with other ADB languages. We show that the emptiness and the membership problems are decidable in polynomial time for ADBs, whereas the universality problem is undecidable. Finally we consider the linear-time model checking problem, i.e., whether the language of an ADB is contained in a regular language, and show that the model checking problem is PSPACE-complete. Copyright 2012 ACM.},
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Prabhu, Vinayak},
  booktitle    = {Proceedings of the 10th ACM international conference on Embedded software},
  location     = {Tampere, Finland},
  pages        = {43 -- 52},
  publisher    = {ACM},
  title        = {{Finite automata with time delay blocks}},
  doi          = {10.1145/2380356.2380370},
  year         = {2012},
}

@inproceedings{10907,
  abstract     = {This paper presents a method to create a model of an articulated object using the planar motion in an initialization video. The model consists of rigid parts connected by points of articulation. The rigid parts are described by the positions of salient feature-points tracked throughout the video. Following a filtering step that identifies points that belong to different objects, rigid parts are found by a grouping process in a graph pyramid. Valid articulation points are selected by verifying multiple hypotheses for each pair of parts.},
  author       = {Artner, Nicole M. and Ion, Adrian and Kropatsch, Walter G.},
  booktitle    = {Graph-Based Representations in Pattern Recognition},
  editor       = {Jiang, Xiaoyi and Ferrer, Miquel and Torsello, Andrea},
  isbn         = {9783642208430},
  issn         = {1611-3349},
  location     = {Münster, Germany},
  pages        = {215--224},
  publisher    = {Springer},
  title        = {{Spatio-temporal extraction of articulated models in a graph pyramid}},
  doi          = {10.1007/978-3-642-20844-7_22},
  volume       = {6658},
  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},
}

