@article{1054,
  abstract     = {We investigate local three-body correlations for bosonic particles in three dimensions and one dimension as a function of the interaction strength. The three-body correlation function g(3) is determined by measuring the three-body recombination rate in an ultracold gas of Cs atoms. In three dimensions, we measure the dependence of g(3) on the gas parameter in a BEC, finding good agreement with the theoretical prediction accounting for beyond-mean-field effects. In one dimension, we observe a reduction of g( 3) by several orders of magnitude upon increasing interactions from the weakly interacting BEC to the strongly interacting Tonks-Girardeau regime, in good agreement with predictions from the Lieb-Liniger model for all strengths of interaction.},
  author       = {Haller, Elmar and Rabie, Mahmoud and Mark, Manfred and Danzl, Johann G and Hart, Russell and Lauber, Katharina and Pupillo, Guido and Nägerl, Hanns},
  journal      = {Physical Review Letters},
  number       = {23},
  publisher    = {American Physical Society},
  title        = {{Three-body correlation functions and recombination rates for bosons in three dimensions and one dimension}},
  doi          = {10.1103/PhysRevLett.107.230404},
  volume       = {107},
  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},
}

@inproceedings{9648,
  abstract     = {In this paper, we establish a correspondence between the incremental algorithm for computing AT-models [8,9] and the one for computing persistent homology [6,14,15]. We also present a decremental algorithm for computing AT-models that allows to extend the persistence computation to a wider setting. Finally, we show how to combine incremental and decremental techniques for persistent homology computation.},
  author       = {Gonzalez-Diaz, Rocio and Ion, Adrian and Jimenez, Maria Jose and Poyatos, Regina},
  booktitle    = {Computer Analysis of Images and Patterns},
  isbn         = {9783642236716},
  issn         = {16113349},
  location     = {Seville, Spain},
  pages        = {286--293},
  publisher    = {Springer Nature},
  title        = {{Incremental-decremental algorithm for computing AT-models and persistent homology}},
  doi          = {10.1007/978-3-642-23672-3_35},
  volume       = {6854},
  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{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},
}

@inproceedings{9943,
  abstract     = {Segmentation is the process of partitioning digital images into meaningful regions. The analysis of biological high content images often requires segmentation as a first step. We propose ilastik as an easy-to-use tool which allows the user without expertise in image processing to perform segmentation and classification in a unified way. ilastik learns from labels provided by the user through a convenient mouse interface. Based on these labels, ilastik infers a problem specific segmentation. A random forest classifier is used in the learning step, in which each pixel's neighborhood is characterized by a set of generic (nonlinear) features. ilastik supports up to three spatial plus one spectral dimension and makes use of all dimensions in the feature calculation. ilastik provides realtime feedback that enables the user to interactively refine the segmentation result and hence further fine-tune the classifier. An uncertainty measure guides the user to ambiguous regions in the images. Real time performance is achieved by multi-threading which fully exploits the capabilities of modern multi-core machines. Once a classifier has been trained on a set of representative images, it can be exported and used to automatically process a very large number of images (e.g. using the CellProfiler pipeline). ilastik is an open source project and released under the BSD license at www.ilastik.org.},
  author       = {Sommer, Christoph M and Straehle, Christoph and Köthe, Ullrich and Hamprecht, Fred A.},
  booktitle    = {2011 IEEE International Symposium on Biomedical Imaging: from Nano to Micro},
  isbn         = {978-1-4244-4127-3},
  issn         = {1945-8452},
  keywords     = {image segmentation, biomedical imaging, three dimensional displays, neurons, retina, observers, image color analysis},
  location     = {Chicago, Illinois, USA},
  publisher    = {Institute of Electrical and Electronics Engineers},
  title        = {{Ilastik: Interactive learning and segmentation toolkit}},
  doi          = {10.1109/isbi.2011.5872394},
  year         = {2011},
}

@article{3318,
  abstract     = {Parvalbumin is thought to act in a manner similar to EGTA, but how a slow Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear. Direct measurements of parvalbumin concentration and paired recordings in rodent hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics only when expressed at high levels. Modeling suggests that, in high concentrations, parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition with local saturation of endogenous fixed buffers.},
  author       = {Eggermann, Emmanuel and Jonas, Peter M},
  journal      = {Nature Neuroscience},
  pages        = {20 -- 22},
  publisher    = {Nature Publishing Group},
  title        = {{How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses}},
  doi          = {10.1038/nn.3002},
  volume       = {15},
  year         = {2011},
}

@article{3320,
  abstract     = {Powerful statistical models that can be learned efficiently from large amounts of data are currently revolutionizing computer vision. These models possess a rich internal structure reflecting task-specific relations and constraints. This monograph introduces the reader to the most popular classes of structured models in computer vision. Our focus is discrete undirected graphical models which we cover in detail together with a description of algorithms for both probabilistic inference and maximum a posteriori inference. We discuss separately recently successful techniques for prediction in general structured models. In the second part of this monograph we describe methods for parameter learning where we distinguish the classic maximum likelihood based methods from the more recent prediction-based parameter learning methods. We highlight developments to enhance current models and discuss kernelized models and latent variable models. To make the monograph more practical and to provide links to further study we provide examples of successful application of many methods in the computer vision literature.},
  author       = {Nowozin, Sebastian and Lampert, Christoph},
  journal      = {Foundations and Trends in Computer Graphics and Vision},
  number       = {3-4},
  pages        = {185 -- 365},
  publisher    = {Now Publishers},
  title        = {{Structured learning and prediction in computer vision}},
  doi          = {10.1561/0600000033},
  volume       = {6},
  year         = {2011},
}

@inproceedings{3324,
  abstract     = {Automated termination provers often use the following schema to prove that a program terminates: construct a relational abstraction of the program's transition relation and then show that the relational abstraction is well-founded. The focus of current tools has been on developing sophisticated techniques for constructing the abstractions while relying on known decidable logics (such as linear arithmetic) to express them. We believe we can significantly increase the class of programs that are amenable to automated termination proofs by identifying more expressive decidable logics for reasoning about well-founded relations. We therefore present a new decision procedure for reasoning about multiset orderings, which are among the most powerful orderings used to prove termination. We show that, using our decision procedure, one can automatically prove termination of natural abstractions of programs.},
  author       = {Piskac, Ruzica and Wies, Thomas},
  editor       = {Jhala, Ranjit and Schmidt, David},
  location     = {Texas, USA},
  pages        = {371 -- 386},
  publisher    = {Springer},
  title        = {{Decision procedures for automating termination proofs}},
  doi          = {10.1007/978-3-642-18275-4_26},
  volume       = {6538},
  year         = {2011},
}

@inproceedings{3326,
  abstract     = {Weighted automata map input words to numerical values. Ap- plications of weighted automata include formal verification of quantitative properties, as well as text, speech, and image processing. A weighted au- tomaton is defined with respect to a semiring. For the tropical semiring, the weight of a run is the sum of the weights of the transitions taken along the run, and the value of a word is the minimal weight of an accepting run on it. In the 90’s, Krob studied the decidability of problems on rational series defined with respect to the tropical semiring. Rational series are strongly related to weighted automata, and Krob’s results apply to them. In par- ticular, it follows from Krob’s results that the universality problem (that is, deciding whether the values of all words are below some threshold) is decidable for weighted automata defined with respect to the tropical semir- ing with domain ∪ {∞}, and that the equality problem is undecidable when the domain is ∪ {∞}. In this paper we continue the study of the borders of decidability in weighted automata, describe alternative and direct proofs of the above results, and tighten them further. Unlike the proofs of Krob, which are algebraic in their nature, our proofs stay in the terrain of state machines, and the reduction is from the halting problem of a two-counter machine. This enables us to significantly simplify Krob’s reasoning, make the un- decidability result accessible to the automata-theoretic community, and strengthen it to apply already to a very simple class of automata: all the states are accepting, there are no initial nor final weights, and all the weights on the transitions are from the set {−1, 0, 1}. The fact we work directly with the automata enables us to tighten also the decidability re- sults and to show that the universality problem for weighted automata defined with respect to the tropical semiring with domain ∪ {∞}, and in fact even with domain ≥0 ∪ {∞}, is PSPACE-complete. Our results thus draw a sharper picture about the decidability of decision problems for weighted automata, in both the front of containment vs. universality and the front of the ∪ {∞} vs. the ∪ {∞} domains.},
  author       = {Almagor, Shaull and Boker, Udi and Kupferman, Orna},
  location     = {Taipei, Taiwan},
  pages        = {482 -- 491},
  publisher    = {Springer},
  title        = {{What’s decidable about weighted automata }},
  doi          = {10.1007/978-3-642-24372-1_37},
  volume       = {6996},
  year         = {2011},
}

@inproceedings{3328,
  abstract     = {We report on a generic uni- and bivariate algebraic kernel that is publicly available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art implementations on polynomials, roots of polynomial systems, and the support to analyze algebraic curves defined by bivariate polynomials. The kernel design is generic, that is, various number types and substeps can be exchanged. It is accompanied with a ready-to-use interface to enable arrangements induced by algebraic curves, that have already been used as basis for various geometric applications, as arrangements on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel applications: arrangements of rotated algebraic curves and Boolean set operations on polygons bounded by segments of algebraic curves. We also provide experiments showing that our general implementation is competitive and even often clearly outperforms existing implementations that are explicitly tailored for specific types of non-linear curves that are available in CGAL.},
  author       = {Berberich, Eric and Hemmer, Michael and Kerber, Michael},
  location     = {Paris, France},
  pages        = {179 -- 186},
  publisher    = {ACM},
  title        = {{A generic algebraic kernel for non linear geometric applications}},
  doi          = {10.1145/1998196.1998224},
  year         = {2011},
}

@inproceedings{3329,
  abstract     = {We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm.},
  author       = {Berberich, Eric and Halperin, Dan and Kerber, Michael and Pogalnikova, Roza},
  booktitle    = {Proceedings of the twenty-seventh annual symposium on Computational geometry},
  location     = {Paris, France},
  pages        = {187 -- 196},
  publisher    = {ACM},
  title        = {{Deconstructing approximate offsets}},
  doi          = {10.1145/1998196.1998225},
  year         = {2011},
}

@inproceedings{3330,
  abstract     = {We consider the problem of approximating all real roots of a square-free polynomial f. Given isolating intervals, our algorithm refines each of them to a width at most 2-L, that is, each of the roots is approximated to L bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating f, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms.},
  author       = {Kerber, Michael and Sagraloff, Michael},
  location     = {California, USA},
  pages        = {209 -- 216},
  publisher    = {Springer},
  title        = {{Root refinement for real polynomials}},
  doi          = {10.1145/1993886.1993920},
  year         = {2011},
}

@article{3332,
  abstract     = {Given an algebraic hypersurface O in ℝd, how many simplices are necessary for a simplicial complex isotopic to O? We address this problem and the variant where all vertices of the complex must lie on O. We give asymptotically tight worst-case bounds for algebraic plane curves. Our results gradually improve known bounds in higher dimensions; however, the question for tight bounds remains unsolved for d ≥ 3.},
  author       = {Kerber, Michael and Sagraloff, Michael},
  journal      = {Graphs and Combinatorics},
  number       = {3},
  pages        = {419 -- 430},
  publisher    = {Springer},
  title        = {{A note on the complexity of real algebraic hypersurfaces}},
  doi          = {10.1007/s00373-011-1020-7},
  volume       = {27},
  year         = {2011},
}

@inbook{3335,
  abstract     = {We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent Betti numbers, which formalize the topological information content of the cosmic mass distribution. While the Betti numbers do not fully quantify topology, they extend the information beyond conventional cosmological studies of topology in terms of genus and Euler characteristic. The richer information content of Betti numbers goes along the availability of fast algorithms to compute them. For continuous density fields, we determine the scale-dependence of Betti numbers by invoking the cosmologically familiar filtration of sublevel or superlevel sets defined by density thresholds. For the discrete galaxy distribution, however, the analysis is based on the alpha shapes of the particles. These simplicial complexes constitute an ordered sequence of nested subsets of the Delaunay tessellation, a filtration defined by the scale parameter, α. As they are homotopy equivalent to the sublevel sets of the distance field, they are an excellent tool for assessing the topological structure of a discrete point distribution. In order to develop an intuitive understanding for the behavior of Betti numbers as a function of α, and their relation to the morphological patterns in the Cosmic Web, we first study them within the context of simple heuristic Voronoi clustering models. These can be tuned to consist of specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or sheets. To elucidate the relative prominence of the various Betti numbers in different stages of morphological evolution, we introduce the concept of alpha tracks. Subsequently, we address the topology of structures emerging in the standard LCDM scenario and in cosmological scenarios with alternative dark energy content. The evolution of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic Web. We also demonstrate that the scale-dependence of the Betti numbers yields a promising measure of cosmological parameters, with a potential to help in determining the nature of dark energy and to probe primordial non-Gaussianities. We also discuss the expected Betti numbers as a function of the density threshold for superlevel sets of a Gaussian random field. Finally, we introduce the concept of persistent homology. It measures scale levels of the mass distribution and allows us to separate small from large scale features. Within the context of the hierarchical cosmic structure formation, persistence provides a natural formalism for a multiscale topology study of the Cosmic Web.},
  author       = {Van De Weygaert, Rien and Vegter, Gert and Edelsbrunner, Herbert and Jones, Bernard and Pranav, Pratyush and Park, Changbom and Hellwing, Wojciech and Eldering, Bob and Kruithof, Nico and Bos, Patrick and Hidding, Johan and Feldbrugge, Job and Ten Have, Eline and Van Engelen, Matti and Caroli, Manuel and Teillaud, Monique},
  booktitle    = {Transactions on Computational Science XIV},
  editor       = {Gavrilova, Marina and Tan, Kenneth and Mostafavi, Mir},
  pages        = {60 -- 101},
  publisher    = {Springer},
  title        = {{Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web}},
  doi          = {10.1007/978-3-642-25249-5_3},
  volume       = {6970},
  year         = {2011},
}

@unpublished{3338,
  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 inde- pendently 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, respec- tively. 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 power- ful 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},
  booktitle    = {arXiv},
  pages        = {1 -- 51},
  publisher    = {ArXiv},
  title        = {{Bounded rationality in concurrent parity games}},
  year         = {2011},
}

@unpublished{3339,
  abstract     = {Turn-based stochastic games and its important subclass Markov decision processes (MDPs) provide models for systems with both probabilistic and nondeterministic behaviors. We consider turn-based stochastic games with two classical quantitative objectives: discounted-sum and long-run average objectives. The game models and the quantitative objectives are widely used in probabilistic verification, planning, optimal inventory control, network protocol and performance analysis. Games and MDPs that model realistic systems often have very large state spaces, and probabilistic abstraction techniques are necessary to handle the state-space explosion. The commonly used full-abstraction techniques do not yield space-savings for systems that have many states with similar value, but does not necessarily have similar transition structure. A semi-abstraction technique, namely Magnifying-lens abstractions (MLA), that clusters states based on value only, disregarding differences in their transition relation was proposed for qualitative objectives (reachability and safety objectives). In this paper we extend the MLA technique to solve stochastic games with discounted-sum and long-run average objectives. We present the MLA technique based abstraction-refinement algorithm for stochastic games and MDPs with discounted-sum objectives. For long-run average objectives, our solution works for all MDPs and a sub-class of stochastic games where every state has the same value. },
  author       = {Chatterjee, Krishnendu and De Alfaro, Luca and Pritam, Roy},
  booktitle    = {arXiv},
  pages        = {17},
  publisher    = {ArXiv},
  title        = {{Magnifying lens abstraction for stochastic games with discounted and long-run average objectives}},
  year         = {2011},
}

@inproceedings{3342,
  abstract     = {We consider Markov decision processes (MDPs) with ω-regular specifications given as parity objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. The algorithms for the computation of the almost-sure winning set for parity objectives iteratively use the solutions for the almost-sure winning set for Büchi objectives (a special case of parity objectives). Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes O(nm)  symbolic steps as compared to the previous known algorithm that takes O(n 2) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs often have constant out-degree, and then our symbolic algorithm takes O(nn)  symbolic steps, as compared to the previous known O(n 2) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires O(nK)  symbolic steps, where K is the maximal number of edges of strongly connected components (scc’s) of the MDP. The win-lose algorithm requires symbolic computation of scc’s. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5·n symbolic steps, whereas our new algorithm takes 4 ·n symbolic steps.},
  author       = {Chatterjee, Krishnendu and Henzinger, Monika H and Joglekar, Manas and Nisarg, Shah},
  editor       = {Gopalakrishnan, Ganesh and Qadeer, Shaz},
  location     = {Snowbird, USA},
  pages        = {260 -- 276},
  publisher    = {Springer},
  title        = {{Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives}},
  doi          = {10.1007/978-3-642-22110-1_21},
  volume       = {6806},
  year         = {2011},
}