@inproceedings{1320,
  abstract     = {In recent years, several biomolecular systems have been shown to be scale-invariant (SI), i.e. to show the same output dynamics when exposed to geometrically scaled input signals (u → pu, p > 0) after pre-adaptation to accordingly scaled constant inputs. In this article, we show that SI systems-as well as systems invariant with respect to other input transformations-can realize nonlinear differential operators: when excited by inputs obeying functional forms characteristic for a given class of invariant systems, the systems' outputs converge to constant values directly quantifying the speed of the input.},
  author       = {Lang, Moritz and Sontag, Eduardo},
  location     = {Boston, MA, USA},
  publisher    = {IEEE},
  title        = {{Scale-invariant systems realize nonlinear differential operators}},
  doi          = {10.1109/ACC.2016.7526722},
  volume       = {2016-July},
  year         = {2016},
}

@article{1322,
  abstract     = {Direct reciprocity is a major mechanism for the evolution of cooperation. Several classical studies have suggested that humans should quickly learn to adopt reciprocal strategies to establish mutual cooperation in repeated interactions. On the other hand, the recently discovered theory of ZD strategies has found that subjects who use extortionate strategies are able to exploit and subdue cooperators. Although such extortioners have been predicted to succeed in any population of adaptive opponents, theoretical follow-up studies questioned whether extortion can evolve in reality. However, most of these studies presumed that individuals have similar strategic possibilities and comparable outside options, whereas asymmetries are ubiquitous in real world applications. Here we show with a model and an economic experiment that extortionate strategies readily emerge once subjects differ in their strategic power. Our experiment combines a repeated social dilemma with asymmetric partner choice. In our main treatment there is one randomly chosen group member who is unilaterally allowed to exchange one of the other group members after every ten rounds of the social dilemma. We find that this asymmetric replacement opportunity generally promotes cooperation, but often the resulting payoff distribution reflects the underlying power structure. Almost half of the subjects in a better strategic position turn into extortioners, who quickly proceed to exploit their peers. By adapting their cooperation probabilities consistent with ZD theory, extortioners force their co-players to cooperate without being similarly cooperative themselves. Comparison to non-extortionate players under the same conditions indicates a substantial net gain to extortion. Our results thus highlight how power asymmetries can endanger mutually beneficial interactions, and transform them into exploitative relationships. In particular, our results indicate that the extortionate strategies predicted from ZD theory could play a more prominent role in our daily interactions than previously thought.},
  author       = {Hilbe, Christian and Hagel, Kristin and Milinski, Manfred},
  journal      = {PLoS One},
  number       = {10},
  publisher    = {Public Library of Science},
  title        = {{Asymmetric power boosts extortion in an economic experiment}},
  doi          = {10.1371/journal.pone.0163867},
  volume       = {11},
  year         = {2016},
}

@article{1323,
  abstract     = {Mossy fiber synapses on CA3 pyramidal cells are 'conditional detonators' that reliably discharge postsynaptic targets. The 'conditional' nature implies that burst activity in dentate gyrus granule cells is required for detonation. Whether single unitary excitatory postsynaptic potentials (EPSPs) trigger spikes in CA3 neurons remains unknown. Mossy fiber synapses exhibit both pronounced short-term facilitation and uniquely large post-tetanic potentiation (PTP). We tested whether PTP could convert mossy fiber synapses from subdetonator into detonator mode, using a recently developed method to selectively and noninvasively stimulate individual presynaptic terminals in rat brain slices. Unitary EPSPs failed to initiate a spike in CA3 neurons under control conditions, but reliably discharged them after induction of presynaptic short-term plasticity. Remarkably, PTP switched mossy fiber synapses into full detonators for tens of seconds. Plasticity-dependent detonation may be critical for efficient coding, storage, and recall of information in the granule cell–CA3 cell network.},
  author       = {Vyleta, Nicholas and Borges Merjane, Carolina and Jonas, Peter M},
  journal      = {eLife},
  publisher    = {eLife Sciences Publications},
  title        = {{Plasticity-dependent, full detonation at hippocampal mossy fiber–CA3 pyramidal neuron synapses}},
  doi          = {10.7554/eLife.17977},
  volume       = {5},
  year         = {2016},
}

@inproceedings{1324,
  abstract     = {DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. Copyright },
  author       = {Chatterjee, Krishnendu and Chmelik, Martin},
  booktitle    = {Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling},
  location     = {London, United Kingdom},
  pages        = {88 -- 96},
  publisher    = {AAAI Press},
  title        = {{Indefinite-horizon reachability in Goal-DEC-POMDPs}},
  doi          = {10.1609/icaps.v26i1.13737},
  volume       = {2016},
  year         = {2016},
}

@inproceedings{1325,
  abstract     = {We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.},
  author       = {Brázdil, Tomáš and Forejt, Vojtěch and Kučera, Antonín and Novotny, Petr},
  location     = {Quebec City, Canada},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Stability in graphs and games}},
  doi          = {10.4230/LIPIcs.CONCUR.2016.10},
  volume       = {59},
  year         = {2016},
}

@inproceedings{1326,
  abstract     = {Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff. },
  author       = {Brázdil, Tomáš and Kučera, Antonín and Novotny, Petr},
  location     = {Chiba, Japan},
  pages        = {32 -- 49},
  publisher    = {Springer},
  title        = {{Optimizing the expected mean payoff in Energy Markov Decision Processes}},
  doi          = {10.1007/978-3-319-46520-3_3},
  volume       = {9938},
  year         = {2016},
}

@inproceedings{1327,
  abstract     = {We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels. },
  author       = {Brázdil, Tomáš and Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Anchit and Novotny, Petr},
  booktitle    = {Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems},
  location     = {Singapore},
  pages        = {1465 -- 1466},
  publisher    = {ACM},
  title        = {{Stochastic shortest path with energy constraints in POMDPs}},
  year         = {2016},
}

@article{1329,
  abstract     = {Daphnia species have become models for ecological genomics and exhibit interesting features, such as high phenotypic plasticity and a densely packed genome with many lineage-specific genes. They are also cyclic parthenogenetic, with alternating asexual and sexual cycles and environmental sex determination. Here, we present a de novo transcriptome assembly of over 32,000 D. galeata genes and use it to investigate gene expression in females and spontaneously produced males of two clonal lines derived from lakes in Germany and the Czech Republic. We find that only a low percentage (18%) of genes shows sex-biased expression and that there are many more female-biased gene (FBG) than male-biased gene (MBG). Furthermore, FBGs tend to be more conserved between species than MBGs in both sequence and expression. These patterns may be a consequence of cyclic parthenogenesis leading to a relaxation of purifying selection on MBGs. The two clonal lines show considerable differences in both number and identity of sex-biased genes, suggesting that they may have reproductive strategies differing in their investment in sexual reproduction. Orthologs of key genes in the sex determination and juvenile hormone pathways, which are thought to be important for the transition from asexual to sexual reproduction, are present in D. galeata and highly conserved among Daphnia species.},
  author       = {Huylmans, Ann K and López Ezquerra, Alberto and Parsch, John and Cordellier, Mathilde},
  journal      = {Genome Biology and Evolution},
  number       = {10},
  pages        = {3120 -- 3139},
  publisher    = {Oxford University Press},
  title        = {{De novo transcriptome assembly and sex-biased gene expression in the cyclical parthenogenetic Daphnia galeata}},
  doi          = {10.1093/gbe/evw221},
  volume       = {8},
  year         = {2016},
}

@article{1330,
  abstract     = {In this paper we investigate the existence of closed billiard trajectories in not necessarily smooth convex bodies. In particular, we show that if a body K ⊂ Rd has the property that the tangent cone of every non-smooth point q ∉ ∂K is acute (in a certain sense), then there is a closed billiard trajectory in K.},
  author       = {Akopyan, Arseniy and Balitskiy, Alexey},
  journal      = {Israel Journal of Mathematics},
  number       = {2},
  pages        = {833 -- 845},
  publisher    = {Springer},
  title        = {{Billiards in convex bodies with acute angles}},
  doi          = {10.1007/s11856-016-1429-z},
  volume       = {216},
  year         = {2016},
}

@article{1331,
  abstract     = {Cytokinin is a phytohormone that is well known for its roles in numerous plant growth and developmental processes, yet it has also been linked to abiotic stress response in a less defined manner. Arabidopsis (Arabidopsis thaliana) Cytokinin Response Factor 6 (CRF6) is a cytokinin-responsive AP2/ERF-family transcription factor that, through the cytokinin signaling pathway, plays a key role in the inhibition of dark-induced senescence. CRF6 expression is also induced by oxidative stress, and here we show a novel function for CRF6 in relation to oxidative stress and identify downstream transcriptional targets of CRF6 that are repressed in response to oxidative stress. Analysis of transcriptomic changes in wild-type and crf6 mutant plants treated with H2O2 identified CRF6-dependent differentially expressed transcripts, many of which were repressed rather than induced. Moreover, many repressed genes also show decreased expression in 35S:CRF6 overexpressing plants. Together, these findings suggest that CRF6 functions largely as a transcriptional repressor. Interestingly, among the H2O2 repressed CRF6-dependent transcripts was a set of five genes associated with cytokinin processes: (signaling) ARR6, ARR9, ARR11, (biosynthesis) LOG7, and (transport) ABCG14. We have examined mutants of these cytokinin-associated target genes to reveal novel connections to oxidative stress. Further examination of CRF6-DNA interactions indicated that CRF6 may regulate its targets both directly and indirectly. Together, this shows that CRF6 functions during oxidative stress as a negative regulator to control this cytokinin-associated module of CRF6- dependent genes and establishes a novel connection between cytokinin and oxidative stress response.},
  author       = {Zwack, Paul and De Clercq, Inge and Howton, Timothy and Hallmark, H Tucker and Hurny, Andrej and Keshishian, Erika and Parish, Alyssa and Benková, Eva and Mukhtar, M Shahid and Van Breusegem, Frank and Rashotte, Aaron},
  issn         = {1532-2548},
  journal      = {Plant Physiology},
  number       = {2},
  pages        = {1249 -- 1258},
  publisher    = {American Society of Plant Biologists},
  title        = {{Cytokinin response factor 6 represses cytokinin-associated genes during oxidative stress}},
  doi          = {10.1104/pp.16.00415},
  volume       = {172},
  year         = {2016},
}

@article{1332,
  abstract     = {Antibiotic-sensitive and -resistant bacteria coexist in natural environments with low, if detectable, antibiotic concentrations. Except possibly around localized antibiotic sources, where resistance can provide a strong advantage, bacterial fitness is dominated by stresses unaffected by resistance to the antibiotic. How do such mixed and heterogeneous conditions influence the selective advantage or disadvantage of antibiotic resistance? Here we find that sub-inhibitory levels of tetracyclines potentiate selection for or against tetracycline resistance around localized sources of almost any toxin or stress. Furthermore, certain stresses generate alternating rings of selection for and against resistance around a localized source of the antibiotic. In these conditions, localized antibiotic sources, even at high strengths, can actually produce a net selection against resistance to the antibiotic. Our results show that interactions between the effects of an antibiotic and other stresses in inhomogeneous environments can generate pervasive, complex patterns of selection both for and against antibiotic resistance.},
  author       = {Chait, Remy P and Palmer, Adam and Yelin, Idan and Kishony, Roy},
  journal      = {Nature Communications},
  publisher    = {Nature Publishing Group},
  title        = {{Pervasive selection for and against antibiotic resistance in inhomogeneous multistress environments}},
  doi          = {10.1038/ncomms10333},
  volume       = {7},
  year         = {2016},
}

@article{1333,
  abstract     = {Social dilemmas force players to balance between personal and collective gain. In many dilemmas, such as elected governments negotiating climate-change mitigation measures, the decisions are made not by individual players but by their representatives. However, the behaviour of representatives in social dilemmas has not been investigated experimentally. Here inspired by the negotiations for greenhouse-gas emissions reductions, we experimentally study a collective-risk social dilemma that involves representatives deciding on behalf of their fellow group members. Representatives can be re-elected or voted out after each consecutive collective-risk game. Selfish players are preferentially elected and are hence found most frequently in the "representatives" treatment. Across all treatments, we identify the selfish players as extortioners. As predicted by our mathematical model, their steadfast strategies enforce cooperation from fair players who finally compensate almost completely the deficit caused by the extortionate co-players. Everybody gains, but the extortionate representatives and their groups gain the most.},
  author       = {Milinski, Manfred and Hilbe, Christian and Semmann, Dirk and Sommerfeld, Ralf and Marotzke, Jochem},
  journal      = {Nature Communications},
  publisher    = {Nature Publishing Group},
  title        = {{Humans choose representatives who enforce cooperation in social dilemmas through extortion}},
  doi          = {10.1038/ncomms10915},
  volume       = {7},
  year         = {2016},
}

@article{1334,
  abstract     = {Hippocampal neurons encode a cognitive map of space. These maps are thought to be updated during learning and in response to changes in the environment through activity-dependent synaptic plasticity. Here we examine how changes in activity influence spatial coding in rats using halorhodopsin-mediated, spatially selective optogenetic silencing. Halorhoposin stimulation leads to light-induced suppression in many place cells and interneurons; some place cells increase their firing through disinhibition, whereas some show no effect. We find that place fields of the unaffected subpopulation remain stable. On the other hand, place fields of suppressed place cells were unstable, showing remapping across sessions before and after optogenetic inhibition. Disinhibited place cells had stable maps but sustained an elevated firing rate. These findings suggest that place representation in the hippocampus is constantly governed by activity-dependent processes, and that disinhibition may provide a mechanism for rate remapping.},
  author       = {Schönenberger, Philipp and O'Neill, Joseph and Csicsvari, Jozsef L},
  journal      = {Nature Communications},
  publisher    = {Nature Publishing Group},
  title        = {{Activity dependent plasticity of hippocampal place maps}},
  doi          = {10.1038/ncomms11824},
  volume       = {7},
  year         = {2016},
}

@inproceedings{1335,
  abstract     = {In this paper we review various automata-theoretic formalisms for expressing quantitative properties. We start with finite-state Boolean automata that express the traditional regular properties. We then consider weighted ω-automata that can measure the average density of events, which finite-state Boolean automata cannot. However, even weighted ω-automata cannot express basic performance properties like average response time. We finally consider two formalisms of weighted ω-automata with monitors, where the monitors are either (a) counters or (b) weighted automata themselves. We present a translation result to establish that these two formalisms are equivalent. Weighted ω-automata with monitors generalize weighted ω-automata, and can express average response time property. They present a natural, robust, and expressive framework for quantitative specifications, with important decidable properties.},
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan},
  location     = {Edinburgh, United Kingdom},
  pages        = {23 -- 38},
  publisher    = {Springer},
  title        = {{Quantitative monitor automata}},
  doi          = {10.1007/978-3-662-53413-7_2},
  volume       = {9837},
  year         = {2016},
}

@article{19814,
  abstract     = {Metallic transition-metal dichalcogenides (TMDCs) are benchmark systems for studying and controlling intertwined electronic orders in solids, with superconductivity developing from a charge-density wave state. The interplay between such phases is thought to play a critical role in the unconventional superconductivity of cuprates, Fe-based and heavy-fermion systems, yet even for the more moderately-correlated TMDCs, their nature and origins have proved controversial. Here, we study a prototypical example, 2H-NbSe2, by spin- and angle-resolved photoemission and first-principles theory. We find that the normal state, from which its hallmark collective phases emerge, is characterized by quasiparticles whose spin is locked to their valley pseudospin. This results from a combination of strong spin–orbit interactions and local inversion symmetry breaking, while interlayer coupling further drives a rich three-dimensional momentum dependence of the underlying Fermi-surface spin texture. These findings necessitate a re-investigation of the nature of charge order and superconducting pairing in NbSe2 and related TMDCs.},
  author       = {Bawden, L. and Cooil, S. P. and Mazzola, F. and Riley, J. M. and Collins-McIntyre, L. J. and Sunko, Veronika and Hunvik, K. W. B. and Leandersson, M. and Polley, C. M. and Balasubramanian, T. and Kim, T. K. and Hoesch, M. and Wells, J. W. and Balakrishnan, G. and Bahramy, M. S. and King, P. D. C.},
  issn         = {2041-1723},
  journal      = {Nature Communications},
  publisher    = {Springer Nature},
  title        = {{Spin-valley locking in the normal state of a transition-metal dichalcogenide superconductor}},
  doi          = {10.1038/ncomms11711},
  volume       = {7},
  year         = {2016},
}

@inbook{19991,
  abstract     = {When applying machine learning techniques to real-world problems, prior knowledge plays a crucial role in enriching the learning system. This prior knowledge is typically defined by domain experts and can be integrated into machine learning algorithms in a variety of ways: as a preference of certain prediction functions over others, as a Bayesian prior over parameters, or as additional information about the samples in the training set used for learning a prediction function. The latter setup is called learning using privileged information (LUPI) and was adopted by Vapnik and Vashist in (Neural Netw, 2009). Formally, LUPI refers to the setting when, in addition to the main data modality, the learning system has access to an extra source of information about the training examples. The additional source of information is only available during training and therefore is called privileged. The main goal of LUPI is to utilize privileged information and to learn a better model in the main data modality than one would learn without the privileged source. As an illustration, for protein classification based on amino-acid sequences, the protein tertiary structure can be considered additional information. Another example is recognizing objects in images; the textual information in the form of image tags contains additional object descriptions and can be used as privileged.},
  author       = {Sharmanska, Viktoriia and Quadrianto, Novi},
  booktitle    = {Encyclopedia of Machine Learning and Data Mining},
  pages        = {1--4},
  publisher    = {Springer Nature},
  title        = {{Learning Using Privileged Information}},
  doi          = {10.1007/978-1-4899-7502-7_892-1},
  year         = {2016},
}

@article{1881,
  abstract     = {We consider random matrices of the form H=W+λV, λ∈ℝ+, where W is a real symmetric or complex Hermitian Wigner matrix of size N and V is a real bounded diagonal random matrix of size N with i.i.d.\ entries that are independent of W. We assume subexponential decay for the matrix entries of W and we choose λ∼1, so that the eigenvalues of W and λV are typically of the same order. Further, we assume that the density of the entries of V is supported on a single interval and is convex near the edges of its support. In this paper we prove that there is λ+∈ℝ+ such that the largest eigenvalues of H are in the limit of large N determined by the order statistics of V for λ>λ+. In particular, the largest eigenvalue of H has a Weibull distribution in the limit N→∞ if λ>λ+. Moreover, for N sufficiently large, we show that the eigenvectors associated to the largest eigenvalues are partially localized for λ>λ+, while they are completely delocalized for λ<λ+. Similar results hold for the lowest eigenvalues. },
  author       = {Lee, Jioon and Schnelli, Kevin},
  journal      = {Probability Theory and Related Fields},
  number       = {1-2},
  pages        = {165 -- 241},
  publisher    = {Springer},
  title        = {{Extremal eigenvalues and eigenvectors of deformed Wigner matrices}},
  doi          = {10.1007/s00440-014-0610-8},
  volume       = {164},
  year         = {2016},
}

@article{1475,
  abstract     = {The actin cytoskeleton plays important roles in the formation and internalization of endocytic vesicles. In yeast, endocytic vesicles move towards early endosomes along actin cables, however, the molecular machinery regulating interaction between endocytic vesicles and actin cables is poorly understood. The Eps15-like protein Pan1p plays a key role in actin-mediated endocytosis and is negatively regulated by Ark1 and Prk1 kinases. Here we show that pan1 mutated to prevent phosphorylation at all 18 threonines, pan1-18TA, displayed almost the same endocytic defect as ark1Δ prk1Δ cells, and contained abnormal actin concentrations including several endocytic compartments. Early endosomes were highly localized in the actin concentrations and displayed movement along actin cables. The dephosphorylated form of Pan1p also caused stable associations between endocytic vesicles and actin cables, and between endocytic vesicles and endosomes. Thus Pan1 phosphorylation is part of a novel mechanism that regulates endocytic compartment interactions with each other and with actin cables.},
  author       = {Toshima, Junko and Furuya, Eri and Nagano, Makoto and Kanno, Chisa and Sakamoto, Yuta and Ebihara, Masashi and Siekhaus, Daria E and Toshima, Jiro},
  journal      = {eLife},
  number       = {February 2016},
  publisher    = {eLife Sciences Publications},
  title        = {{Yeast Eps15-like endocytic protein Pan1p regulates the interaction between endocytic vesicles, endosomes and the actin cytoskeleton}},
  doi          = {10.7554/eLife.10276},
  volume       = {5},
  year         = {2016},
}

@article{1476,
  abstract     = {The dynamic assembly and disassembly of actin filaments is essential for the formation and transport of vesicles during endocytosis. In yeast, two types of actin structures, namely cortical patches and cytoplasmic cables, play a direct role in endocytosis, but how their interaction is regulated remains unclear. Here, we show that Srv2/CAP, an evolutionarily conserved actin regulator, is required for efficient endocytosis owing to its role in the formation of the actin patches that aid initial vesicle invagination and of the actin cables that these move along. Deletion of the SRV2 gene resulted in the appearance of aberrant fragmented actin cables that frequently moved past actin patches, the sites of endocytosis. We find that the C-terminal CARP domain of Srv2p is vitally important for the proper assembly of actin patches and cables; we also demonstrate that the N-terminal helical folded domain of Srv2 is required for its localization to actin patches, specifically to the ADP-actin rich region through an interaction with cofilin. These results demonstrate the in vivo roles of Srv2p in the regulation of the actin cytoskeleton during clathrin-mediated endocytosis},
  author       = {Toshima, Junko and Horikomi, Chika and Okada, Asuka and Hatori, Makiko and Nagano, Makoto and Masuda, Atsushi and Yamamoto, Wataru and Siekhaus, Daria E and Toshima, Jiro},
  journal      = {Journal of Cell Science},
  number       = {2},
  pages        = {367 -- 379},
  publisher    = {Company of Biologists},
  title        = {{Srv2/CAP is required for polarized actin cable assembly and patch internalization during clathrin-mediated endocytosis}},
  doi          = {10.1242/jcs.176651},
  volume       = {129},
  year         = {2016},
}

@article{1477,
  abstract     = {We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages provides a robust specification language to express properties in verification, and parity objectives are canonical forms to express them. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are undecidable even for special cases of parity objectives, we establish decidability (with optimal complexity) for POMDPs with all parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. We also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of POMDP examples.},
  author       = {Chatterjee, Krishnendu and Chmelik, Martin and Tracol, Mathieu},
  journal      = {Journal of Computer and System Sciences},
  number       = {5},
  pages        = {878 -- 911},
  publisher    = {Elsevier},
  title        = {{What is decidable about partially observable Markov decision processes with ω-regular objectives}},
  doi          = {10.1016/j.jcss.2016.02.009},
  volume       = {82},
  year         = {2016},
}