@article{2411,
abstract = {The kingdom of fungi provides model organisms for biotechnology, cell biology, genetics, and life sciences in general. Only when their phylogenetic relationships are stably resolved, can individual results from fungal research be integrated into a holistic picture of biology. However, and despite recent progress, many deep relationships within the fungi remain unclear. Here, we present the first phylogenomic study of an entire eukaryotic kingdom that uses a consistency criterion to strengthen phylogenetic conclusions. We reason that branches (splits) recovered with independent data and different tree reconstruction methods are likely to reflect true evolutionary relationships. Two complementary phylogenomic data sets based on 99 fungal genomes and 109 fungal expressed sequence tag (EST) sets analyzed with four different tree reconstruction methods shed light from different angles on the fungal tree of life. Eleven additional data sets address specifically the phylogenetic position of Blastocladiomycota, Ustilaginomycotina, and Dothideomycetes, respectively. The combined evidence from the resulting trees supports the deep-level stability of the fungal groups toward a comprehensive natural system of the fungi. In addition, our analysis reveals methodologically interesting aspects. Enrichment for EST encoded data-a common practice in phylogenomic analyses-introduces a strong bias toward slowly evolving and functionally correlated genes. Consequently, the generalization of phylogenomic data sets as collections of randomly selected genes cannot be taken for granted. A thorough characterization of the data to assess possible influences on the tree reconstruction should therefore become a standard in phylogenomic analyses.},
author = {Ebersberger, Ingo and De Matos Simoes, Ricardo and Kupczok, Anne and Gube, Matthias and Kothe, Erika and Voigt, Kerstin and Von Haeseler, Arndt},
journal = {Molecular Biology and Evolution},
number = {5},
pages = {1319 -- 1334},
publisher = {Oxford University Press},
title = {{A consistent phylogenetic backbone for the fungi}},
doi = {10.1093/molbev/msr285},
volume = {29},
year = {2012},
}
@article{2904,
abstract = {Generalized van der Corput sequences are onedimensional, infinite sequences in the unit interval. They are generated from permutations in integer base b and are the building blocks of the multi-dimensional Halton sequences. Motivated by recent progress of Atanassov on the uniform distribution behavior of Halton sequences, we study, among others, permutations of the form P(i) = ai (mod b) for coprime integers a and b. We show that multipliers a that either divide b - 1 or b + 1 generate van der Corput sequences with weak distribution properties. We give explicit lower bounds for the asymptotic distribution behavior of these sequences and relate them to sequences generated from the identity permutation in smaller bases, which are, due to Faure, the weakest distributed generalized van der Corput sequences.},
author = {Pausinger, Florian},
journal = {Journal de Theorie des Nombres des Bordeaux},
number = {3},
pages = {729 -- 749},
publisher = {Universite de Bordeaux III},
title = {{Weak multipliers for generalized van der Corput sequences}},
doi = {10.5802/jtnb.819},
volume = {24},
year = {2012},
}
@unpublished{2928,
abstract = { This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. },
author = {Kolmogorov, Vladimir and Schoenemann, Thomas},
booktitle = {arXiv},
publisher = {ArXiv},
title = {{Generalized sequential tree-reweighted message passing}},
year = {2012},
}
@inproceedings{2930,
abstract = {In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively.
In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.
},
author = {Huber, Anna and Kolmogorov, Vladimir},
location = {Athens, Greece},
pages = {451 -- 462},
publisher = {Springer},
title = {{Towards minimizing k-submodular functions}},
doi = {10.1007/978-3-642-32147-4_40},
volume = {7422},
year = {2012},
}
@article{2959,
abstract = {We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. An algebraic elimination criterion allows us to find exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator (MLE) exists with probability one. This is applied to bipartite graphs, grids and colored graphs. We also study the ML degree, and we present the first instance of a graph for which the MLE exists with probability one, even when the number of observations equals the treewidth.},
author = {Uhler, Caroline},
journal = {Annals of Statistics},
number = {1},
pages = {238 -- 261},
publisher = {Institute of Mathematical Statistics},
title = {{Geometry of maximum likelihood estimation in Gaussian graphical models}},
doi = {10.1214/11-AOS957},
volume = {40},
year = {2012},
}
@article{2954,
abstract = {Spontaneous postsynaptic currents (PSCs) provide key information about the mechanisms of synaptic transmission and the activity modes of neuronal networks. However, detecting spontaneous PSCs in vitro and in vivo has been challenging, because of the small amplitude, the variable kinetics, and the undefined time of generation of these events. Here, we describe a, to our knowledge, new method for detecting spontaneous synaptic events by deconvolution, using a template that approximates the average time course of spontaneous PSCs. A recorded PSC trace is deconvolved from the template, resulting in a series of delta-like functions. The maxima of these delta-like events are reliably detected, revealing the precise onset times of the spontaneous PSCs. Among all detection methods, the deconvolution-based method has a unique temporal resolution, allowing the detection of individual events in high-frequency bursts. Furthermore, the deconvolution-based method has a high amplitude resolution, because deconvolution can substantially increase the signal/noise ratio. When tested against previously published methods using experimental data, the deconvolution-based method was superior for spontaneous PSCs recorded in vivo. Using the high-resolution deconvolution-based detection algorithm, we show that the frequency of spontaneous excitatory postsynaptic currents in dentate gyrus granule cells is 4.5 times higher in vivo than in vitro.},
author = {Pernia-Andrade, Alejandro and Goswami, Sarit and Stickler, Yvonne and Fröbe, Ulrich and Schlögl, Alois and Jonas, Peter M},
journal = {Biophysical Journal},
number = {7},
pages = {1429 -- 1439},
publisher = {Biophysical},
title = {{A deconvolution based method with high sensitivity and temporal resolution for detection of spontaneous synaptic currents in vitro and in vivo}},
doi = {10.1016/j.bpj.2012.08.039},
volume = {103},
year = {2012},
}
@article{2966,
abstract = {Background: The outcome of male-male competition can be predicted from the relative fighting qualities of the opponents, which often depend on their age. In insects, freshly emerged and still sexually inactive males are morphologically indistinct from older, sexually active males. These young inactive males may thus be easy targets for older males if they cannot conceal themselves from their attacks. The ant Cardiocondyla obscurior is characterised by lethal fighting between wingless (" ergatoid" ) males. Here, we analyse for how long young males are defenceless after eclosion, and how early adult males can detect the presence of rival males.Results: We found that old ergatoid males consistently won fights against ergatoid males younger than two days. Old males did not differentiate between different types of unpigmented pupae several days before emergence, but had more frequent contact to ready-to-eclose pupae of female sexuals and winged males than of workers and ergatoid males. In rare cases, old ergatoid males displayed alleviated biting of pigmented ergatoid male pupae shortly before adult eclosion, as well as copulation attempts to dark pupae of female sexuals and winged males. Ergatoid male behaviour may be promoted by a closer similarity of the chemical profile of ready-to-eclose pupae to the profile of adults than that of young pupae several days prior to emergence.Conclusion: Young ergatoid males of C. obscurior would benefit greatly by hiding their identity from older, resident males, as they are highly vulnerable during the first two days of their adult lives. In contrast to the winged males of the same species, which are able to prevent ergatoid male attacks by chemical female mimicry, young ergatoids do not seem to be able to produce a protective chemical profile. Conflicts in male-male competition between ergatoid males of different age thus seem to be resolved in favour of the older males. This might represent selection at the colony level rather than the individual level. © 2012 Cremer et al.; licensee BioMed Central Ltd.},
author = {Cremer, Sylvia and Suefuji, Masaki and Schrempf, Alexandra and Heinze, Jürgen},
journal = {BMC Ecology},
publisher = {BioMed Central},
title = {{The dynamics of male-male competition in Cardiocondyla obscurior ants}},
doi = {10.1186/1472-6785-12-7},
volume = {12},
year = {2012},
}
@article{3159,
abstract = {The structure of hierarchical networks in biological and physical systems has long been characterized using the Horton-Strahler ordering scheme. The scheme assigns an integer order to each edge in the network based on the topology of branching such that the order increases from distal parts of the network (e.g., mountain streams or capillaries) to the "root" of the network (e.g., the river outlet or the aorta). However, Horton-Strahler ordering cannot be applied to networks with loops because they they create a contradiction in the edge ordering in terms of which edge precedes another in the hierarchy. Here, we present a generalization of the Horton-Strahler order to weighted planar reticular networks, where weights are assumed to correlate with the importance of network edges, e.g., weights estimated from edge widths may correlate to flow capacity. Our method assigns hierarchical levels not only to edges of the network, but also to its loops, and classifies the edges into reticular edges, which are responsible for loop formation, and tree edges. In addition, we perform a detailed and rigorous theoretical analysis of the sensitivity of the hierarchical levels to weight perturbations. In doing so, we show that the ordering of the reticular edges is more robust to noise in weight estimation than is the ordering of the tree edges. We discuss applications of this generalized Horton-Strahler ordering to the study of leaf venation and other biological networks.},
author = {Mileyko, Yuriy and Edelsbrunner, Herbert and Price, Charles and Weitz, Joshua},
journal = {PLoS One},
number = {6},
publisher = {Public Library of Science},
title = {{Hierarchical ordering of reticular networks}},
doi = {10.1371/journal.pone.0036715},
volume = {7},
year = {2012},
}
@article{3161,
abstract = {Some inflammatory stimuli trigger activation of the NLRP3 inflammasome by inducing efflux of cellular potassium. Loss of cellular potassium is known to potently suppress protein synthesis, leading us to test whether the inhibition of protein synthesis itself serves as an activating signal for the NLRP3 inflammasome. Murine bone marrow-derived macrophages, either primed by LPS or unprimed, were exposed to a panel of inhibitors of ribosomal function: ricin, cycloheximide, puromycin, pactamycin, and anisomycin. Macrophages were also exposed to nigericin, ATP, monosodium urate (MSU), and poly I:C. Synthesis of pro-IL-ß and release of IL-1ß from cells in response to these agents was detected by immunoblotting and ELISA. Release of intracellular potassium was measured by mass spectrometry. Inhibition of translation by each of the tested translation inhibitors led to processing of IL-1ß, which was released from cells. Processing and release of IL-1ß was reduced or absent from cells deficient in NLRP3, ASC, or caspase-1, demonstrating the role of the NLRP3 inflammasome. Despite the inability of these inhibitors to trigger efflux of intracellular potassium, the addition of high extracellular potassium suppressed activation of the NLRP3 inflammasome. MSU and double-stranded RNA, which are known to activate the NLRP3 inflammasome, also substantially inhibited protein translation, supporting a close association between inhibition of translation and inflammasome activation. These data demonstrate that translational inhibition itself constitutes a heretofore-unrecognized mechanism underlying IL-1ß dependent inflammatory signaling and that other physical, chemical, or pathogen-associated agents that impair translation may lead to IL-1ß-dependent inflammation through activation of the NLRP3 inflammasome. For agents that inhibit translation through decreased cellular potassium, the application of high extracellular potassium restores protein translation and suppresses activation of the NLRP inflammasome. For agents that inhibit translation through mechanisms that do not involve loss of potassium, high extracellular potassium suppresses IL-1ß processing through a mechanism that remains undefined.},
author = {Vyleta, Meghan and Wong, John and Magun, Bruce},
journal = {PLoS One},
number = {5},
publisher = {Public Library of Science},
title = {{Suppression of ribosomal function triggers innate immune signaling through activation of the NLRP3 inflammasome}},
doi = {10.1371/journal.pone.0036044},
volume = {7},
year = {2012},
}
@inproceedings{3123,
abstract = {We introduce the idea of using an explicit triangle mesh to track the air/fluid interface in a smoothed particle hydrodynamics (SPH) simulator. Once an initial surface mesh is created, this mesh is carried forward in time using nearby particle velocities to advect the mesh vertices. The mesh connectivity remains mostly unchanged across time-steps; it is only modified locally for topology change events or for the improvement of triangle quality. In order to ensure that the surface mesh does not diverge from the underlying particle simulation, we periodically project the mesh surface onto an implicit surface defined by the physics simulation. The mesh surface gives us several advantages over previous SPH surface tracking techniques. We demonstrate a new method for surface tension calculations that clearly outperforms the state of the art in SPH surface tension for computer graphics. We also demonstrate a method for tracking detailed surface information (like colors) that is less susceptible to numerical diffusion than competing techniques. Finally, our temporally-coherent surface mesh allows us to simulate high-resolution surface wave dynamics without being limited by the particle resolution of the SPH simulation.},
author = {Yu, Jihun and Wojtan, Christopher J and Turk, Greg and Yap, Chee},
booktitle = {Computer Graphics Forum},
location = {Cagliari, Sardinia, Italy},
number = {2},
pages = {815 -- 824},
publisher = {Blackwell Publishing},
title = {{Explicit mesh surfaces for particle based fluids}},
doi = {10.1111/j.1467-8659.2012.03062.x},
volume = {31},
year = {2012},
}
@article{3130,
abstract = {Essential genes code for fundamental cellular functions required for the viability of an organism. For this reason, essential genes are often highly conserved across organisms. However, this is not always the case: orthologues of genes that are essential in one organism are sometimes not essential in other organisms or are absent from their genomes. This suggests that, in the course of evolution, essential genes can be rendered nonessential. How can a gene become non-essential? Here we used genetic manipulation to deplete the products of 26 different essential genes in Escherichia coli. This depletion results in a lethal phenotype, which could often be rescued by the overexpression of a non-homologous, non-essential gene, most likely through replacement of the essential function. We also show that, in a smaller number of cases, the essential genes can be fully deleted from the genome, suggesting that complete functional replacement is possible. Finally, we show that essential genes whose function can be replaced in the laboratory are more likely to be non-essential or not present in other taxa. These results are consistent with the notion that patterns of evolutionary conservation of essential genes are influenced by their compensability-that is, by how easily they can be functionally replaced, for example through increased expression of other genes.},
author = {Bergmiller, Tobias and Ackermann, Martin and Silander, Olin},
journal = {PLoS Genetics},
number = {6},
publisher = {Public Library of Science},
title = {{Patterns of evolutionary conservation of essential genes correlate with their compensability}},
doi = {10.1371/journal.pgen.1002803},
volume = {8},
year = {2012},
}
@article{3166,
abstract = {There is evidence that the genetic code was established prior to the existence of proteins, when metabolism was powered by ribozymes. Also, early proto-organisms had to rely on simple anaerobic bioenergetic processes. In this work I propose that amino acid fermentation powered metabolism in the RNA world, and that this was facilitated by proto-adapters, the precursors of the tRNAs. Amino acids were used as carbon sources rather than as catalytic or structural elements. In modern bacteria, amino acid fermentation is known as the Stickland reaction. This pathway involves two amino acids: the first undergoes oxidative deamination, and the second acts as an electron acceptor through reductive deamination. This redox reaction results in two keto acids that are employed to synthesise ATP via substrate-level phosphorylation. The Stickland reaction is the basic bioenergetic pathway of some bacteria of the genus Clostridium. Two other facts support Stickland fermentation in the RNA world. First, several Stickland amino acid pairs are synthesised in abiotic amino acid synthesis. This suggests that amino acids that could be used as an energy substrate were freely available. Second, anticodons that have complementary sequences often correspond to amino acids that form Stickland pairs. The main hypothesis of this paper is that pairs of complementary proto-adapters were assigned to Stickland amino acids pairs. There are signatures of this hypothesis in the genetic code. Furthermore, it is argued that the proto-adapters formed double strands that brought amino acid pairs into proximity to facilitate their mutual redox reaction, structurally constraining the anticodon pairs that are assigned to these amino acid pairs. Significance tests which randomise the code are performed to study the extent of the variability of the energetic (ATP) yield. Random assignments can lead to a substantial yield of ATP and maintain enough variability, thus selection can act and refine the assignments into a proto-code that optimises the energetic yield. Monte Carlo simulations are performed to evaluate the establishment of these simple proto-codes, based on amino acid substitutions and codon swapping. In all cases, donor amino acids are assigned to anticodons composed of U+G, and have low redundancy (1-2 codons), whereas acceptor amino acids are assigned to the the remaining codons. These bioenergetic and structural constraints allow for a metabolic role for amino acids before their co-option as catalyst cofactors. Reviewers: this article was reviewed by Prof. William Martin, Prof. Eors Szathmary (nominated by Dr. Gaspar Jekely) and Dr. Adam Kun (nominated by Dr. Sandor Pongor)},
author = {Vladar, Harold},
journal = {Biology Direct},
publisher = {BioMed Central},
title = {{Amino acid fermentation at the origin of the genetic code}},
doi = {10.1186/1745-6150-7-6},
volume = {7},
year = {2012},
}
@article{3262,
abstract = {Living cells must control the reading out or "expression" 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 statistical nonlinear and soft matter physics },
number = {4},
publisher = {American Institute of Physics},
title = {{Optimizing information flow in small genetic networks. III. A self-interacting gene}},
doi = {10.1103/PhysRevE.85.041903},
volume = {85},
year = {2012},
}
@article{3274,
abstract = {A boundary element model of a tunnel running through horizontally layered soil with anisotropic material properties is presented. Since there is no analytical fundamental solution for wave propagation inside a layered orthotropic medium in 3D, the fundamental displacements and stresses have to be calculated numerically. In our model this is done in the Fourier domain with respect to space and time. The assumption of a straight tunnel with infinite extension in the x direction makes it possible to decouple the system for every wave number kx, leading to a 2.5D-problem, which is suited for parallel computation. The special form of the fundamental solution, resulting from our Fourier ansatz, and the fact, that the calculation of the boundary integral equation is performed in the Fourier domain, enhances the stability and efficiency of the numerical calculations.},
author = {Rieckh, Georg and Kreuzer, Wolfgang and Waubke, Holger and Balazs, Peter},
journal = { Engineering Analysis with Boundary Elements},
number = {6},
pages = {960 -- 967},
publisher = {Elsevier},
title = {{A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered anisotropic soil}},
doi = {10.1016/j.enganabound.2011.12.014},
volume = {36},
year = {2012},
}
@inproceedings{3279,
abstract = {We show a hardness-preserving construction of a PRF from any length doubling PRG which improves upon known constructions whenever we can put a non-trivial upper bound q on the number of queries to the PRF. Our construction requires only O(logq) invocations to the underlying PRG with each query. In comparison, the number of invocations by the best previous hardness-preserving construction (GGM using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially secure if queried at most q = exp(√n)times and where each invocation of the PRF requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n) required by known constructions.
},
author = {Jain, Abhishek and Pietrzak, Krzysztof Z and Tentes, Aris},
location = {Taormina, Sicily, Italy},
pages = {369 -- 382},
publisher = {Springer},
title = {{Hardness preserving constructions of pseudorandom functions}},
doi = {10.1007/978-3-642-28914-9_21},
volume = {7194},
year = {2012},
}
@inproceedings{3281,
abstract = {We consider the problem of amplifying the "lossiness" of functions. We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f has image size at most 2 m-L. The question is whether such C* exists for L/m ≫ ℓ/n. This problem arises naturally in the context of cryptographic "lossy functions," where the relative lossiness is the key parameter. We show that for every circuit C* that makes at most t queries to f, the relative lossiness of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making a polynomial t = poly(n) number of queries can amplify relative lossiness by more than an O(logn)/n additive term. We show that this is tight by giving a simple construction (cascading with some randomization) that achieves such amplification.},
author = {Pietrzak, Krzysztof Z and Rosen, Alon and Segev, Gil},
location = {Taormina, Sicily, Italy},
pages = {458 -- 475},
publisher = {Springer},
title = {{Lossy functions do not amplify well}},
doi = {10.1007/978-3-642-28914-9_26},
volume = {7194},
year = {2012},
}
@inproceedings{3250,
abstract = {The Learning Parity with Noise (LPN) problem has recently found many applications in cryptography as the hardness assumption underlying the constructions of "provably secure" cryptographic schemes like encryption or authentication protocols. Being provably secure means that the scheme comes with a proof showing that the existence of an efficient adversary against the scheme implies that the underlying hardness assumption is wrong. LPN based schemes are appealing for theoretical and practical reasons. On the theoretical side, LPN based schemes offer a very strong security guarantee. The LPN problem is equivalent to the problem of decoding random linear codes, a problem that has been extensively studied in the last half century. The fastest known algorithms run in exponential time and unlike most number-theoretic problems used in cryptography, the LPN problem does not succumb to known quantum algorithms. On the practical side, LPN based schemes are often extremely simple and efficient in terms of code-size as well as time and space requirements. This makes them prime candidates for light-weight devices like RFID tags, which are too weak to implement standard cryptographic primitives like the AES block-cipher. This talk will be a gentle introduction to provable security using simple LPN based schemes as examples. Starting from pseudorandom generators and symmetric key encryption, over secret-key authentication protocols, and, if time admits, touching on recent constructions of public-key identification, commitments and zero-knowledge proofs.},
author = {Pietrzak, Krzysztof Z},
location = {Špindlerův Mlýn, Czech Republic},
pages = {99 -- 114},
publisher = {Springer},
title = {{Cryptography from learning parity with noise}},
doi = {10.1007/978-3-642-27660-6_9},
volume = {7147},
year = {2012},
}
@article{3248,
abstract = {We describe RTblob, a high speed vision system that detects objects in cluttered scenes based on their color and shape at a speed of over 800 frames/s. Because the system is available as open-source software and relies only on off-the-shelf PC hardware components, it can provide the basis for multiple application scenarios. As an illustrative example, we show how RTblob can be used in a robotic table tennis scenario to estimate ball trajectories through 3D space simultaneously from four cameras images at a speed of 200 Hz.},
author = {Lampert, Christoph and Peters, Jan},
journal = {Journal of Real-Time Image Processing},
number = {1},
pages = {31 -- 41},
publisher = {Springer},
title = {{Real-time detection of colored objects in multiple camera streams with off-the-shelf hardware components}},
doi = {10.1007/s11554-010-0168-3},
volume = {7},
year = {2012},
}
@article{3243,
author = {Danowski, Patrick},
journal = {Büchereiperspektiven},
pages = {11},
publisher = {Buchereiverband Österreichs},
title = {{Zwischen Technologie und Information}},
volume = {1/2012},
year = {2012},
}
@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{2916,
abstract = {The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a quantitative measure for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intu- itively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, and that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.},
author = {Cerny, Pavol and Chmelik, Martin and Henzinger, Thomas A and Radhakrishna, Arjun},
booktitle = {Electronic Proceedings in Theoretical Computer Science},
location = {Napoli, Italy},
pages = {29 -- 42},
publisher = {EPTCS},
title = {{Interface Simulation Distances}},
doi = {10.4204/EPTCS.96.3},
volume = {96},
year = {2012},
}
@inproceedings{2942,
abstract = {Interface theories provide a formal framework for component-based development of software and hardware which supports the incremental design of systems and the independent implementability of components. These capabilities are ensured through mathematical properties of the parallel composition operator and the refinement relation for components. More recently, a conjunction operation was added to interface theories in order to provide support for handling multiple viewpoints, requirements engineering, and component reuse. Unfortunately, the conjunction operator does not allow independent implementability in general. In this paper, we study conditions that need to be imposed on interface models in order to enforce independent implementability with respect to conjunction. We focus on multiple viewpoint specifications and propose a new compatibility criterion between two interfaces, which we call orthogonality. We show that orthogonal interfaces can be refined separately, while preserving both orthogonality and composability with other interfaces. We illustrate the independent implementability of different viewpoints with a FIFO buffer example.},
author = {Henzinger, Thomas A and Nickovic, Dejan},
booktitle = { Conference proceedings Monterey Workshop 2012},
location = {Oxford, UK},
pages = {380 -- 395},
publisher = {Springer},
title = {{Independent implementability of viewpoints}},
doi = {10.1007/978-3-642-34059-8_20},
volume = {7539},
year = {2012},
}
@inproceedings{2947,
abstract = {We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems.},
author = {Chatterjee, Krishnendu and Chmelik, Martin and Majumdar, Ritankar},
location = {Thiruvananthapuram, India},
pages = {385 -- 399},
publisher = {Springer},
title = {{Equivalence of games with probabilistic uncertainty and partial observation games}},
doi = {10.1007/978-3-642-33386-6_30},
volume = {7561},
year = {2012},
}
@article{3128,
abstract = {We consider two-player zero-sum stochastic games on graphs with ω-regular winning conditions specified as parity objectives. These games have applications in the design and control of reactive systems. We survey the complexity results for the problem of deciding the winner in such games, and in classes of interest obtained as special cases, based on the information and the power of randomization available to the players, on the class of objectives and on the winning mode. On the basis of information, these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have complete view of the game). The one-sided partial-observation games have two important subclasses: the one-player games, known as partial-observation Markov decision processes (POMDPs), and the blind one-player games, known as probabilistic automata. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Finally, various classes of games are obtained by restricting the parity objective to a reachability, safety, Büchi, or coBüchi condition. We also consider several winning modes, such as sure-winning (i.e., all outcomes of a strategy have to satisfy the winning condition), almost-sure winning (i.e., winning with probability 1), limit-sure winning (i.e., winning with probability arbitrarily close to 1), and value-threshold winning (i.e., winning with probability at least ν, where ν is a given rational). },
author = {Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A},
journal = {Formal Methods in System Design},
number = {2},
pages = {268 -- 284},
publisher = {Springer},
title = {{A survey of partial-observation stochastic parity games}},
doi = {10.1007/s10703-012-0164-2},
volume = {43},
year = {2012},
}
@inproceedings{3135,
abstract = {We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates. },
author = {Brázdil, Brázdil and Chatterjee, Krishnendu and Kučera, Antonín and Novotny, Petr},
location = {Berkeley, CA, USA},
pages = {23 -- 38},
publisher = {Springer},
title = {{Efficient controller synthesis for consumption games with multiple resource types}},
doi = {10.1007/978-3-642-31424-7_8},
volume = {7358},
year = {2012},
}
@inproceedings{3255,
abstract = {In this paper we survey results of two-player games on graphs and Markov decision processes with parity, mean-payoff and energy objectives, and the combination of mean-payoff and energy objectives with parity objectives. These problems have applications in verification and synthesis of reactive systems in resource-constrained environments.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
location = {Lednice, Czech Republic},
pages = {37 -- 46},
publisher = {Springer},
title = {{Games and Markov decision processes with mean payoff parity and energy parity objectives}},
doi = {10.1007/978-3-642-25929-6_3},
volume = {7119},
year = {2012},
}
@inproceedings{495,
abstract = {An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.},
author = {Kruckman, Alex and Rubin, Sasha and Sheridan, John and Zax, Ben},
booktitle = {Proceedings GandALF 2012},
location = {Napoli, Italy},
pages = {238 -- 246},
publisher = {Open Publishing Association},
title = {{A Myhill Nerode theorem for automata with advice}},
doi = {10.4204/EPTCS.96.18},
volume = {96},
year = {2012},
}
@article{6588,
abstract = {First we note that the best polynomial approximation to vertical bar x vertical bar on the set, which consists of an interval on the positive half-axis and a point on the negative half-axis, can be given by means of the classical Chebyshev polynomials. Then we explore the cases when a solution of the related problem on two intervals can be given in elementary functions.},
author = {Pausinger, Florian},
issn = {1812-9471},
journal = {Journal of Mathematical Physics, Analysis, Geometry},
number = {1},
pages = {63--78},
publisher = {B. Verkin Institute for Low Temperature Physics and Engineering},
title = {{Elementary solutions of the Bernstein problem on two intervals}},
volume = {8},
year = {2012},
}
@inproceedings{3270,
abstract = {The persistence diagram of a filtered simplicial com- plex is usually computed by reducing the boundary matrix of the complex. We introduce a simple op- timization technique: by processing the simplices of the complex in decreasing dimension, we can “kill” columns (i.e., set them to zero) without reducing them. This technique completely avoids reduction on roughly half of the columns. We demonstrate that this idea significantly improves the running time of the reduction algorithm in practice. We also give an output-sensitive complexity analysis for the new al- gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.},
author = {Chen, Chao and Kerber, Michael},
location = {Morschach, Switzerland},
pages = {197 -- 200},
publisher = {TU Dortmund},
title = {{Persistent homology computation with a twist}},
year = {2011},
}
@phdthesis{3275,
abstract = {Chemokines organize immune cell trafficking by inducing either directed (tactic) or random (kinetic) migration and by activating integrins in order to support surface adhesion (haptic). Beyond that the same chemokines can establish clearly defined functional areas in secondary lymphoid organs. Until now it is unclear how chemokines can fulfill such diverse functions. One decisive prerequisite to explain these capacities is to know how chemokines are presented in tissue. In theory chemokines could occur either soluble or immobilized, and could be distributed either homogenously or as a concentration gradient. To dissect if and how the presenting mode of chemokines influences immune cells, I tested the response of dendritic cells (DCs) to differentially displayed chemokines. DCs are antigen presenting cells that reside in the periphery and migrate into draining lymph nodes (LNs) once exposed to inflammatory stimuli to activate naïve T cells. DCs are guided to and within the LN by the chemokine receptor CCR7, which has two ligands, the chemokines CCL19 and CCL21. Both CCR7 ligands are expressed by fibroblastic reticular cells in the LN, but differ in their ability to bind to heparan sulfate residues. CCL21 has a highly charged C-terminal extension, which mediates binding to anionic surfaces, whereas CCL19 is lacking such residues and likely distributes as a soluble molecule. This study shows that surface-bound CCL21 causes random, haptokinetic DC motility, which is confined to the chemokine coated area by insideout activation of β2 integrins that mediate cell binding to the surface. CCL19 on the other hand forms concentration gradients which trigger directional, chemotactic movement, but no surface adhesion. In addition DCs can actively manipulate this system by recruiting and activating serine proteases on their surfaces, which create - by proteolytically removing the adhesive C-terminus - a solubilized variant of CCL21 that functionally resembles CCL19. By generating a CCL21 concentration gradient DCs establish a positive feedback loop to recruit further DCs from the periphery to the CCL21 coated region. In addition DCs can sense chemotactic gradients as well as immobilized haptokinetic fields at the same time and integrate these signals. The result is chemotactically biased haptokinesis - directional migration confined to a chemokine coated track or area - which could explain the dynamic but spatially tightly controlled swarming leukocyte locomotion patterns that have been observed in lymphatic organs by intravital microscopists. The finding that DCs can approach soluble cues in a non-adhesive manner while they attach to surfaces coated with immobilized cues raises the question how these cells transmit intracellular forces to the environment, especially in the non-adherent migration mode. In order to migrate, cells have to generate and transmit force to the extracellular substrate. Force transmission is the prerequisite to procure an expansion of the leading edge and a forward motion of the whole cell body. In the current conceptions actin polymerization at the leading edge is coupled to extracellular ligands via the integrin family of transmembrane receptors, which allows the transmission of intracellular force. Against the paradigm of force transmission during migration, leukocytes, like DCs, are able to migrate in threedimensional environments without using integrin transmembrane receptors (Lämmermann et al., 2008). This reflects the biological function of leukocytes, as they can invade almost all tissues, whereby their migration has to be independent from the extracellular environment. How the cells can achieve this is unclear. For this study I examined DC migration in a defined threedimensional environment and highlighted actin-dynamics with the probe Lifeact-GFP. The result was that chemotactic DCs can switch between integrin-dependent and integrin- independent locomotion and can thereby adapt to the adhesive properties of their environment. If the cells are able to couple their actin cytoskeleton to the substrate, actin polymerization is entirely converted into protrusion. Without coupling the actin cortex undergoes slippage and retrograde actin flow can be observed. But retrograde actin flow can be completely compensated by higher actin polymerization rate keeping the migration velocity and the shape of the cells unaltered. Mesenchymal cells like fibroblast cannot balance the loss of adhesive interaction, cannot protrude into open space and, therefore, strictly depend on integrinmediated force coupling. This leukocyte specific phenomenon of “adaptive force transmission” endows these cells with the unique ability to transit and invade almost every type of tissue. },
author = {Schumann, Kathrin},
pages = {141},
publisher = {IST Austria},
title = {{The role of chemotactic gradients in dendritic cell migration}},
year = {2011},
}
@article{3287,
abstract = {Diffusing membrane constituents are constantly exposed to a variety of forces that influence their stochastic path. Single molecule experiments allow for resolving trajectories at extremely high spatial and temporal accuracy, thereby offering insights into en route interactions of the tracer. In this review we discuss approaches to derive information about the underlying processes, based on single molecule tracking experiments. In particular, we focus on a new versatile way to analyze single molecule diffusion in the absence of a full analytical treatment. The method is based on comprehensive comparison of an experimental data set against the hypothetical outcome of multiple experiments performed on the computer. Since Monte Carlo simulations can be easily and rapidly performed even on state-of-the-art PCs, our method provides a simple way for testing various - even complicated - diffusion models. We describe the new method in detail, and show the applicability on two specific examples: firstly, kinetic rate constants can be derived for the transient interaction of mobile membrane proteins; secondly, residence time and corral size can be extracted for confined diffusion.},
author = {Ruprecht, Verena and Axmann, Markus and Wieser, Stefan and Schuetz, Gerhard},
journal = {Current Protein & Peptide Science},
number = {8},
pages = {714 -- 724},
publisher = {Bentham Science Publishers},
title = {{What can we learn from single molecule trajectories?}},
doi = {10.2174/138920311798841753},
volume = {12},
year = {2011},
}
@inproceedings{3299,
abstract = {We introduce propagation models, a formalism designed to support general and efficient data structures for the transient analysis of biochemical reaction networks. We give two use cases for propagation abstract data types: the uniformization method and numerical integration. We also sketch an implementation of a propagation abstract data type, which uses abstraction to approximate states.},
author = {Henzinger, Thomas A and Mateescu, Maria},
location = {Paris, France},
pages = {1 -- 3},
publisher = {Springer},
title = {{Propagation models for computing biochemical reaction networks}},
doi = {10.1145/2037509.2037510},
year = {2011},
}
@inproceedings{3302,
abstract = {Cloud computing aims to give users virtually unlimited pay-per-use computing resources without the burden of managing the underlying infrastructure. We present a new job execution environment Flextic that exploits scal- able static scheduling techniques to provide the user with a flexible pricing model, such as a tradeoff between dif- ferent degrees of execution speed and execution price, and at the same time, reduce scheduling overhead for the cloud provider. We have evaluated a prototype of Flextic on Amazon EC2 and compared it against Hadoop. For various data parallel jobs from machine learning, im- age processing, and gene sequencing that we considered, Flextic has low scheduling overhead and reduces job du- ration by up to 15% compared to Hadoop, a dynamic cloud scheduler.},
author = {Henzinger, Thomas A and Singh, Anmol and Singh, Vasu and Wies, Thomas and Zufferey, Damien},
pages = {1 -- 6},
publisher = {USENIX},
title = {{Static scheduling in clouds}},
year = {2011},
}
@article{3352,
abstract = {Exploring the connection of biology with reactive systems to better understand living systems.},
author = {Fisher, Jasmin and Harel, David and Henzinger, Thomas A},
journal = {Communications of the ACM},
number = {10},
pages = {72 -- 82},
publisher = {ACM},
title = {{Biology as reactivity}},
doi = {10.1145/2001269.2001289},
volume = {54},
year = {2011},
}
@inproceedings{3319,
abstract = {We address the problem of metric learning for multi-view data, namely the construction of embedding projections from data in different representations into a shared feature space, such that the Euclidean distance in this space provides a meaningful within-view as well as between-view similarity. Our motivation stems from the problem of cross-media retrieval tasks, where the availability of a joint Euclidean distance function is a pre-requisite to allow fast, in particular hashing-based, nearest neighbor queries. We formulate an objective function that expresses the intuitive concept that matching samples are mapped closely together in the output space, whereas non-matching samples are pushed apart, no matter in which view they are available. The resulting optimization problem is not convex, but it can be decomposed explicitly into a convex and a concave part, thereby allowing efficient optimization using the convex-concave procedure. Experiments on an image retrieval task show that nearest-neighbor based cross-view retrieval is indeed possible, and the proposed technique improves the retrieval accuracy over baseline techniques.},
author = {Quadrianto, Novi and Lampert, Christoph},
location = {Bellevue, USA},
pages = {425 -- 432},
publisher = {Omnipress},
title = {{Learning multi-view neighborhood preserving projections}},
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},
editor = {Bultan, Tevfik and Hsiung, Pao-Ann},
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{3357,
abstract = {We consider two-player graph games whose objectives are request-response condition, i.e conjunctions of conditions of the form "if a state with property Rq is visited, then later a state with property Rp is visited". The winner of such games can be decided in EXPTIME and the problem is known to be NP-hard. In this paper, we close this gap by showing that this problem is, in fact, EXPTIME-complete. We show that the problem becomes PSPACE-complete if we only consider games played on DAGs, and NP-complete or PTIME-complete if there is only one player (depending on whether he wants to enforce or spoil the request-response condition). We also present near-optimal bounds on the memory needed to design winning strategies for each player, in each case.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Horn, Florian},
editor = {Dediu, Adrian-Horia and Inenaga, Shunsuke and Martín-Vide, Carlos},
location = {Tarragona, Spain},
pages = {227 -- 237},
publisher = {Springer},
title = {{The complexity of request-response games}},
doi = {10.1007/978-3-642-21254-3_17},
volume = {6638},
year = {2011},
}
@article{3383,
author = {Heisenberg, Carl-Philipp J},
journal = {FEBS Journal},
number = {S1},
pages = {24 -- 24},
publisher = {Wiley-Blackwell},
title = {{Invited Lectures ‐ Symposia Area}},
doi = {10.1111/j.1742-4658.2011.08136.x},
volume = {278},
year = {2011},
}
@article{3388,
abstract = {Background: Fragmentation of terrestrial ecosystems has had detrimental effects on metapopulations of habitat specialists. Maculinea butterflies have been particularly affected because of their specialized lifecycles, requiring both specific food-plants and host-ants. However, the interaction between dispersal, effective population size, and long-term genetic erosion of these endangered butterflies remains unknown. Using non-destructive sampling, we investigated the genetic diversity of the last extant population of M. arion in Denmark, which experienced critically low numbers in the 1980s. Results: Using nine microsatellite markers, we show that the population is genetically impoverished compared to nearby populations in Sweden, but less so than monitoring programs suggested. Ten additional short repeat microsatellites were used to reconstruct changes in genetic diversity and population structure over the last 77 years from museum specimens. We also tested amplification efficiency in such historical samples as a function of repeat length and sample age. Low population numbers in the 1980s did not affect genetic diversity, but considerable turnover of alleles has characterized this population throughout the time-span of our analysis. Conclusions: Our results suggest that M. arion is less sensitive to genetic erosion via population bottlenecks than previously thought, and that managing clusters of high quality habitat may be key for long-term conservation.},
author = {Ugelvig, Line V and Nielsen, Per and Boomsma, Jacobus and Nash, David},
journal = {BMC Evolutionary Biology},
number = {201},
publisher = {BioMed Central},
title = {{Reconstructing eight decades of genetic variation in an isolated Danish population of the large blue butterfly Maculinea arion}},
doi = {10.1186/1471-2148-11-201},
volume = {11},
year = {2011},
}
@article{3390,
abstract = {What determines the genetic contribution that an individual makes to future generations? With biparental reproduction, each individual leaves a 'pedigree' of descendants, determined by the biparental relationships in the population. The pedigree of an individual constrains the lines of descent of each of its genes. An individual's reproductive value is the expected number of copies of each of its genes that is passed on to distant generations conditional on its pedigree. For the simplest model of biparental reproduction analogous to the Wright-Fisher model, an individual's reproductive value is determined within ~10 generations, independent of population size. Partial selfing and subdivision do not greatly slow this convergence. Our central result is that the probability that a gene will survive is proportional to the reproductive value of the individual that carries it, and that conditional on survival, after a few tens of generations, the distribution of the number of surviving copies is the same for all individuals, whatever their reproductive value. These results can be generalized to the joint distribution of surviving blocks of ancestral genome. Selection on unlinked loci in the genetic background may greatly increase the variance in reproductive value, but the above results nevertheless still hold. The almost linear relationship between survival probability and reproductive value also holds for weakly favored alleles. Thus, the influence of the complex pedigree of descendants on an individual's genetic contribution to the population can be summarized through a single number: its reproductive value.},
author = {Barton, Nicholas H and Etheridge, Alison},
journal = {Genetics},
number = {4},
pages = {953 -- 973},
publisher = {Genetics Society of America},
title = {{The relation between reproductive value and genetic contribution}},
doi = {10.1534/genetics.111.127555},
volume = {188},
year = {2011},
}
@article{3395,
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 aiming to evaluate the genetic health of the exploited populations. The present study is based on a set of ten nuclear markers amplified in 331 individuals from ten 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 instead showed a large and stable historical effective size. This result could be accounted for by specific life-history traits (reproduction and longevity) and the limitations of molecular markers in covering recent timescales for nontemporal samples. The findings of the present study emphasize the need to integrate 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},
journal = {Biological Journal of the Linnean Society},
number = {2},
pages = {407 -- 418},
publisher = {Wiley-Blackwell},
title = {{Effect of oceanographic barriers and overfishing on the population genetic structure of the European spiny lobster Palinurus elephas }},
doi = {10.1111/j.1095-8312.2011.01728.x},
volume = {104},
year = {2011},
}
@article{3376,
abstract = {Regulatory conflicts occur when two signals that individually trigger opposite cellular responses are present simultaneously. Here, we investigate regulatory conflicts in the bacterial response to antibiotic combinations. We use an Escherichia coli promoter-GFP library to study the transcriptional response of many promoters to either additive or antagonistic drug pairs at fine two-dimensional (2D) resolution of drug concentration. Surprisingly, we find that this data set can be characterized as a linear sum of only two principal components. Component one, accounting for over 70% of the response, represents the response to growth inhibition by the drugs. Component two describes how regulatory conflicts are resolved. For the additive drug pair, conflicts are resolved by linearly interpolating the single drug responses, while for the antagonistic drug pair, the growth-limiting drug dominates the response. Importantly, for a given drug pair, the same conflict resolution strategy applies to almost all genes. These results provide a recipe for predicting gene expression responses to antibiotic combinations.},
author = {Bollenbach, Mark Tobias and Kishony, Roy},
journal = {Molecular Cell},
number = {4},
pages = {413 -- 425},
publisher = {Cell Press},
title = {{Resolution of gene regulatory conflicts caused by combinations of antibiotics}},
doi = {10.1016/j.molcel.2011.04.016},
volume = {42},
year = {2011},
}
@article{3369,
abstract = {Rab3 interacting molecules (RIMs) are highly enriched in the active zones of presynaptic terminals. It is generally thought that they operate as effectors of the small G protein Rab3. Three recent papers, by Han et al. (this issue of Neuron), Deng et al. (this issue of Neuron), and Kaeser et al. (a recent issue of Cell), shed new light on the functional role of RIM in presynaptic terminals. First, RIM tethers Ca2+ channels to active zones. Second, RIM contributes to priming of synaptic vesicles by interacting with another presynaptic protein, Munc13.},
author = {Pernia-Andrade, Alejandro and Jonas, Peter M},
journal = {Neuron},
number = {2},
pages = {185 -- 187},
publisher = {Elsevier},
title = {{The multiple faces of RIM}},
doi = {10.1016/j.neuron.2011.01.010},
volume = {69},
year = {2011},
}
@article{3371,
abstract = {The Minisymposium “Cell Migration and Motility” was attended by approximately 500 visitors and covered a broad range of questions in the field using diverse model systems. Topics comprised actin dynamics, cell polarity, force transduction, signal transduction, bar- rier transmigration, and chemotactic guidance.},
author = {Sixt, Michael K and Parent, Carole},
journal = {Molecular Biology and Evolution},
number = {6},
pages = {724},
publisher = {Oxford University Press},
title = {{Cells on the move in Philadelphia}},
doi = {10.1091/mbc.E10-12-0958},
volume = {22},
year = {2011},
}
@article{3965,
abstract = {The elevation function on a smoothly embedded 2-manifold in R-3 reflects the multiscale topography of cavities and protrusions as local maxima. The function has been useful in identifying coarse docking configurations for protein pairs. Transporting the concept from the smooth to the piecewise linear category, this paper describes an algorithm for finding all local maxima. While its worst-case running time is the same as of the algorithm used in prior work, its performance in practice is orders of magnitudes superior. We cast light on this improvement by relating the running time to the total absolute Gaussian curvature of the 2-manifold.},
author = {Wang, Bei and Edelsbrunner, Herbert and Morozov, Dmitriy},
journal = {Journal of Experimental Algorithmics},
number = {2.2},
pages = {1 -- 13},
publisher = {ACM},
title = {{Computing elevation maxima by searching the Gauss sphere}},
doi = {10.1145/1963190.1970375},
volume = {16},
year = {2011},
}
@article{3364,
abstract = {Molecular noise, which arises from the randomness of the discrete events in the cell, significantly influences fundamental biological processes. Discrete-state continuous-time stochastic models (CTMC) can be used to describe such effects, but the calculation of the probabilities of certain events is computationally expensive. We present a comparison of two analysis approaches for CTMC. On one hand, we estimate the probabilities of interest using repeated Gillespie simulation and determine the statistical accuracy that we obtain. On the other hand, we apply a numerical reachability analysis that approximates the probability distributions of the system at several time instances. We use examples of cellular processes to demonstrate the superiority of the reachability analysis if accurate results are required.},
author = {Didier, Frédéric and Henzinger, Thomas A and Mateescu, Maria and Wolf, Verena},
journal = {Theoretical Computer Science},
number = {21},
pages = {2128 -- 2141},
publisher = {Elsevier},
title = {{Approximation of event probabilities in noisy cellular processes}},
doi = {10.1016/j.tcs.2010.10.022},
volume = {412},
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{504,
abstract = {Populations living in a spatially and temporally changing environment can adapt to the changing optimum and/or migrate toward favorable habitats. Here we extend previous analyses with a static optimum to allow the environment to vary in time as well as in space. The model follows both population dynamics and the trait mean under stabilizing selection, and the outcomes can be understood by comparing the loads due to genetic variance, dispersal, and temporal change. With fixed genetic variance, we obtain two regimes: (1) adaptation that is uniform along the environmental gradient and that responds to the moving optimum as expected for panmictic populations and when the spatial gradient is sufficiently steep, and (2) a population with limited range that adapts more slowly than the environmental optimum changes in both time and space; the population therefore becomes locally extinct and migrates toward suitable habitat. We also use a population‐genetic model with many loci to allow genetic variance to evolve, and we show that the only solution now has uniform adaptation.},
author = {Polechova, Jitka and Barton, Nicholas H and Marion, Glenn},
journal = {American Naturalist},
number = {4},
pages = {546 -- 547},
publisher = {University of Chicago Press},
title = {{Erratum: Species' range: Adaptation in space and time (American Naturalist 174 (E186 E204)) }},
doi = {10.1086/659642},
volume = {177},
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},
}
@misc{5384,
abstract = {We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether for every ε > 0 there is a word that is accepted with probability at least 1 − ε. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions.},
author = {Chatterjee, Krishnendu and Tracol, Mathieu},
issn = {2664-1690},
pages = {30},
publisher = {IST Austria},
title = {{Decidable problems for probabilistic automata on infinite words}},
doi = {10.15479/AT:IST-2011-0004},
year = {2011},
}
@inproceedings{3345,
abstract = {We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition re- quires that the resource level never drops below 0, and the mean-payoff condi- tion requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP ∩ coNP, while for mean- payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
location = {Warsaw, Poland},
pages = {206 -- 218},
publisher = {Springer},
title = {{Energy and mean-payoff parity Markov Decision Processes}},
doi = {10.1007/978-3-642-22993-0_21},
volume = {6907},
year = {2011},
}
@article{3269,
abstract = {The unintentional scattering of light between neighboring surfaces in complex projection environments increases the brightness and decreases the contrast, disrupting the appearance of the desired imagery. To achieve satisfactory projection results, the inverse problem of global illumination must be solved to cancel this secondary scattering. In this paper, we propose a global illumination cancellation method that minimizes the perceptual difference between the desired imagery and the actual total illumination in the resulting physical environment. Using Gauss-Newton and active set methods, we design a fast solver for the bound constrained nonlinear least squares problem raised by the perceptual error metrics. Our solver is further accelerated with a CUDA implementation and multi-resolution method to achieve 1–2 fps for problems with approximately 3000 variables. We demonstrate the global illumination cancellation algorithm with our multi-projector system. Results show that our method preserves the color fidelity of the desired imagery significantly better than previous methods.},
author = {Sheng, Yu and Cutler, Barbara and Chen, Chao and Nasman, Joshua},
journal = {Computer Graphics Forum},
number = {4},
pages = {1261 -- 1268},
publisher = {Wiley-Blackwell},
title = {{Perceptual global illumination cancellation in complex projection environments}},
doi = {10.1111/j.1467-8659.2011.01985.x},
volume = {30},
year = {2011},
}
@inbook{3271,
abstract = {In this paper we present an efficient framework for computation of persis- tent homology of cubical data in arbitrary dimensions. An existing algorithm using simplicial complexes is adapted to the setting of cubical complexes. The proposed approach enables efficient application of persistent homology in domains where the data is naturally given in a cubical form. By avoiding triangulation of the data, we significantly reduce the size of the complex. We also present a data-structure de- signed to compactly store and quickly manipulate cubical complexes. By means of numerical experiments, we show high speed and memory efficiency of our ap- proach. We compare our framework to other available implementations, showing its superiority. Finally, we report performance on selected 3D and 4D data-sets.},
author = {Wagner, Hubert and Chen, Chao and Vuçini, Erald},
booktitle = {Topological Methods in Data Analysis and Visualization II},
editor = {Peikert, Ronald and Hauser, Helwig and Carr, Hamish and Fuchs, Raphael},
pages = {91 -- 106},
publisher = {Springer},
title = {{Efficient computation of persistent homology for cubical data}},
doi = {10.1007/978-3-642-23175-9_7},
year = {2011},
}
@article{3288,
abstract = {The zonula adherens (ZA) of epithelial cells is a site of cell-cell adhesion where cellular forces are exerted and resisted. Increasing evidence indicates that E-cadherin adhesion molecules at the ZA serve to sense force applied on the junctions and coordinate cytoskeletal responses to those forces. Efforts to understand the role that cadherins play in mechanotransduction have been limited by the lack of assays to measure the impact of forces on the ZA. In this study we used 4D imaging of GFP-tagged E-cadherin to analyse the movement of the ZA. Junctions in confluent epithelial monolayers displayed prominent movements oriented orthogonal (perpendicular) to the ZA itself. Two components were identified in these movements: a relatively slow unidirectional (translational) component that could be readily fitted by least-squares regression analysis, upon which were superimposed more rapid oscillatory movements. Myosin IIB was a dominant factor responsible for driving the unilateral translational movements. In contrast, frequency spectrum analysis revealed that depletion of Myosin IIA increased the power of the oscillatory movements. This implies that Myosin IIA may serve to dampen oscillatory movements of the ZA. This extends our recent analysis of Myosin II at the ZA to demonstrate that Myosin IIA and Myosin IIB make distinct contributions to junctional movement at the ZA.},
author = {Smutny, Michael and Wu, Selwin and Gomez, Guillermo and Mangold, Sabine and Yap, Alpha and Hamilton, Nicholas},
journal = {PLoS One},
number = {7},
publisher = {Public Library of Science},
title = {{Multicomponent analysis of junctional movements regulated by Myosin II isoforms at the epithelial zonula adherens}},
doi = {10.1371/journal.pone.0022458},
volume = {6},
year = {2011},
}
@article{3290,
abstract = {Analysis of genomic data requires an efficient way to calculate likelihoods across very large numbers of loci. We describe a general method for finding the distribution of genealogies: we allow migration between demes, splitting of demes [as in the isolation-with-migration (IM) model], and recombination between linked loci. These processes are described by a set of linear recursions for the generating function of branch lengths. Under the infinite-sites model, the probability of any configuration of mutations can be found by differentiating this generating function. Such calculations are feasible for small numbers of sampled genomes: as an example, we show how the generating function can be derived explicitly for three genes under the two-deme IM model. This derivation is done automatically, using Mathematica. Given data from a large number of unlinked and nonrecombining blocks of sequence, these results can be used to find maximum-likelihood estimates of model parameters by tabulating the probabilities of all relevant mutational configurations and then multiplying across loci. The feasibility of the method is demonstrated by applying it to simulated data and to a data set previously analyzed by Wang and Hey (2010) consisting of 26,141 loci sampled from Drosophila simulans and D. melanogaster. Our results suggest that such likelihood calculations are scalable to genomic data as long as the numbers of sampled individuals and mutations per sequence block are small.},
author = {Lohse, Konrad and Harrison, Richard and Barton, Nicholas H},
journal = {Genetics},
number = {3},
pages = {977 -- 987},
publisher = {Genetics Society of America},
title = {{A general method for calculating likelihoods under the coalescent process}},
doi = {10.1534/genetics.111.129569},
volume = {189},
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{3163,
abstract = {We study multi-label prediction for structured output sets, a problem that occurs, for example, in object detection in images, secondary structure prediction in computational biology, and graph matching with symmetries. Conventional multilabel classification techniques are typically not applicable in this situation, because they require explicit enumeration of the label set, which is infeasible in case of structured outputs. Relying on techniques originally designed for single-label structured prediction, in particular structured support vector machines, results in reduced prediction accuracy, or leads to infeasible optimization problems. In this work we derive a maximum-margin training formulation for multi-label structured prediction that remains computationally tractable while achieving high prediction accuracy. It also shares most beneficial properties with single-label maximum-margin approaches, in particular formulation as a convex optimization problem, efficient working set training, and PAC-Bayesian generalization bounds.},
author = {Lampert, Christoph},
location = {Granada, Spain},
publisher = {Neural Information Processing Systems},
title = {{Maximum margin multi-label structured prediction}},
year = {2011},
}
@misc{3322,
abstract = {We study multi-label prediction for structured output spaces, a problem that occurs, for example, in object detection in images, secondary structure prediction in computational biology, and graph matching with symmetries. Conventional multi-label classification techniques are typically not applicable in this situation, because they require explicit enumeration of the label space, which is infeasible in case of structured outputs. Relying on techniques originally designed for single- label structured prediction, in particular structured support vector machines, results in reduced prediction accuracy, or leads to infeasible optimization problems. In this work we derive a maximum-margin training formulation for multi-label structured prediction that remains computationally tractable while achieving high prediction accuracy. It also shares most beneficial properties with single-label maximum-margin approaches, in particular a formulation as a convex optimization problem, efficient working set training, and PAC-Bayesian generalization bounds.},
author = {Lampert, Christoph},
booktitle = {NIPS: Neural Information Processing Systems},
publisher = {Neural Information Processing Systems},
title = {{Maximum margin multi label structured prediction}},
year = {2011},
}
@article{3334,
author = {Edelsbrunner, Herbert and Pach, János and Ziegler, Günter},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {1 -- 2},
publisher = {Springer},
title = {{Letter from the new editors-in-chief}},
doi = {10.1007/s00454-010-9313-9},
volume = {45},
year = {2011},
}
@inproceedings{3358,
abstract = {The static scheduling problem often arises as a fundamental problem in real-time systems and grid computing. We consider the problem of statically scheduling a large job expressed as a task graph on a large number of computing nodes, such as a data center. This paper solves the large-scale static scheduling problem using abstraction refinement, a technique commonly used in formal verification to efficiently solve computationally hard problems. A scheduler based on abstraction refinement first attempts to solve the scheduling problem with abstract representations of the job and the computing resources. As abstract representations are generally small, the scheduling can be done reasonably fast. If the obtained schedule does not meet specified quality conditions (like data center utilization or schedule makespan) then the scheduler refines the job and data center abstractions and, again solves the scheduling problem. We develop different schedulers based on abstraction refinement. We implemented these schedulers and used them to schedule task graphs from various computing domains on simulated data centers with realistic topologies. We compared the speed of scheduling and the quality of the produced schedules with our abstraction refinement schedulers against a baseline scheduler that does not use any abstraction. We conclude that abstraction refinement techniques give a significant speed-up compared to traditional static scheduling heuristics, at a reasonable cost in the quality of the produced schedules. We further used our static schedulers in an actual system that we deployed on Amazon EC2 and compared it against the Hadoop dynamic scheduler for large MapReduce jobs. Our experiments indicate that there is great potential for static scheduling techniques.},
author = {Henzinger, Thomas A and Singh, Vasu and Wies, Thomas and Zufferey, Damien},
location = {Salzburg, Austria},
pages = {329 -- 342},
publisher = {ACM},
title = {{Scheduling large jobs by abstraction refinement}},
doi = {10.1145/1966445.1966476},
year = {2011},
}
@article{3372,
abstract = {Nowak et al.1 argue that inclusive fitness theory has been of little value in explaining the natural world, and that it has led to negligible progress in explaining the evolution of eusociality. However, we believe that their arguments are based upon a misunderstanding of evolutionary theory and a misrepresentation of the empirical literature. We will focus our comments on three general issues.},
author = {Abbot, Patrick and Abe, Jun and Alcock, John and Alizon, Samuel and Alpedrinha, Joao and Andersson, Malte and Andre, Jean and Van Baalen, Minus and Balloux, Francois and Balshine, Sigal and Barton, Nicholas H and Beukeboom, Leo and Biernaskie, Jay and Bilde, Trine and Borgia, Gerald and Breed, Michael and Brown, Sam and Bshary, Redouan and Buckling, Angus and Burley, Nancy and Burton Chellew, Max and Cant, Michael and Chapuisat, Michel and Charnov, Eric and Clutton Brock, Tim and Cockburn, Andrew and Cole, Blaine and Colegrave, Nick and Cosmides, Leda and Couzin, Iain and Coyne, Jerry and Creel, Scott and Crespi, Bernard and Curry, Robert and Dall, Sasha and Day, Troy and Dickinson, Janis and Dugatkin, Lee and El Mouden, Claire and Emlen, Stephen and Evans, Jay and Ferriere, Regis and Field, Jeremy and Foitzik, Susanne and Foster, Kevin and Foster, William and Fox, Charles and Gadau, Juergen and Gandon, Sylvain and Gardner, Andy and Gardner, Michael and Getty, Thomas and Goodisman, Michael and Grafen, Alan and Grosberg, Rick and Grozinger, Christina and Gouyon, Pierre and Gwynne, Darryl and Harvey, Paul and Hatchwell, Ben and Heinze, Jürgen and Helantera, Heikki and Helms, Ken and Hill, Kim and Jiricny, Natalie and Johnstone, Rufus and Kacelnik, Alex and Kiers, E Toby and Kokko, Hanna and Komdeur, Jan and Korb, Judith and Kronauer, Daniel and Kümmerli, Rolf and Lehmann, Laurent and Linksvayer, Timothy and Lion, Sébastien and Lyon, Bruce and Marshall, James and Mcelreath, Richard and Michalakis, Yannis and Michod, Richard and Mock, Douglas and Monnin, Thibaud and Montgomerie, Robert and Moore, Allen and Mueller, Ulrich and Noë, Ronald and Okasha, Samir and Pamilo, Pekka and Parker, Geoff and Pedersen, Jes and Pen, Ido and Pfennig, David and Queller, David and Rankin, Daniel and Reece, Sarah and Reeve, Hudson and Reuter, Max and Roberts, Gilbert and Robson, Simon and Roze, Denis and Rousset, Francois and Rueppell, Olav and Sachs, Joel and Santorelli, Lorenzo and Schmid Hempel, Paul and Schwarz, Michael and Scott Phillips, Tom and Shellmann Sherman, Janet and Sherman, Paul and Shuker, David and Smith, Jeff and Spagna, Joseph and Strassmann, Beverly and Suarez, Andrew and Sundström, Liselotte and Taborsky, Michael and Taylor, Peter and Thompson, Graham and Tooby, John and Tsutsui, Neil and Tsuji, Kazuki and Turillazzi, Stefano and Úbeda, Francisco and Vargo, Edward and Voelkl, Bernard and Wenseleers, Tom and West, Stuart and West Eberhard, Mary and Westneat, David and Wiernasz, Diane and Wild, Geoff and Wrangham, Richard and Young, Andrew and Zeh, David and Zeh, Jeanne and Zink, Andrew},
journal = {Nature},
number = {7339},
pages = {E1 -- E4},
publisher = {Nature Publishing Group},
title = {{Inclusive fitness theory and eusociality}},
doi = {10.1038/nature09831},
volume = {471},
year = {2011},
}
@inproceedings{3365,
abstract = {We present the tool Quasy, a quantitative synthesis tool. Quasy takes qualitative and quantitative specifications and automatically constructs a system that satisfies the qualitative specification and optimizes the quantitative specification, if such a system exists. The user can choose between a system that satisfies and optimizes the specifications (a) under all possible environment behaviors or (b) under the most-likely environment behaviors given as a probability distribution on the possible input sequences. Quasy solves these two quantitative synthesis problems by reduction to instances of 2-player games and Markov Decision Processes (MDPs) with quantitative winning objectives. Quasy can also be seen as a game solver for quantitative games. Most notable, it can solve lexicographic mean-payoff games with 2 players, MDPs with mean-payoff objectives, and ergodic MDPs with mean-payoff parity objectives.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Jobstmann, Barbara and Singh, Rohit},
location = {Saarbrucken, Germany},
pages = {267 -- 271},
publisher = {Springer},
title = {{QUASY: quantitative synthesis tool}},
doi = {10.1007/978-3-642-19835-9_24},
volume = {6605},
year = {2011},
}
@article{3377,
abstract = {By definition, transverse intersections are stable under in- finitesimal perturbations. Using persistent homology, we ex- tend this notion to sizeable perturbations. Specifically, we assign to each homology class of the intersection its robust- ness, the magnitude of a perturbation necessary to kill it, and prove that robustness is stable. Among the applications of this result is a stable notion of robustness for fixed points of continuous mappings and a statement of stability for con- tours of smooth mappings.},
author = {Edelsbrunner, Herbert and Morozov, Dmitriy and Patel, Amit},
journal = {Foundations of Computational Mathematics},
number = {3},
pages = {345 -- 361},
publisher = {Springer},
title = {{Quantifying transversality by measuring the robustness of intersections}},
doi = {10.1007/s10208-011-9090-8},
volume = {11},
year = {2011},
}
@article{3771,
abstract = {The small-sized frugivorous bat Carollia perspicillata is an understory specialist and occurs in a wide range of lowland habitats, tending to be more common in tropical dry or moist forests of South and Central America. Its sister species, Carollia brevicauda, occurs almost exclusively in the Amazon rainforest. A recent phylogeographic study proposed a hypothesis of origin and subsequent diversification for C. perspicillata along the Atlantic coastal forest of Brazil. Additionally, it also found two allopatric clades for C. brevicauda separated by the Amazon Basin. We used cytochrome b gene sequences and a more extensive sampling to test hypotheses related to the origin and diversification of C. perspicillata plus C. brevicauda clade in South America. The results obtained indicate that there are two sympatric evolutionary lineages within each species. In C. perspicillata, one lineage is limited to the Southern Atlantic Forest, whereas the other is widely distributed. Coalescent analysis points to a simultaneous origin for C. perspicillata and C. brevicauda, although no place for the diversification of each species can be firmly suggested. The phylogeographic pattern shown by C. perspicillata is also congruent with the Pleistocene refugia hypothesis as a likely vicariant phenomenon shaping the present distribution of its intraspecific lineages.},
author = {Pavan, Ana and Martins, Felipe and Santos, Fabrício and Ditchfield, Albert and Fernandes Redondo, Rodrigo A},
journal = {Biological Journal of the Linnean Society},
number = {3},
pages = {527 -- 539},
publisher = {Wiley-Blackwell},
title = {{Patterns of diversification in two species of short-tailed bats (Carollia Gray, 1838): the effects of historical fragmentation of Brazilian rainforests.}},
doi = {10.1111/j.1095-8312.2010.01601.x},
volume = {102},
year = {2011},
}
@article{3384,
abstract = {Here we introduce a database of calibrated natural images publicly available through an easy-to-use web interface. Using a Nikon D70 digital SLR camera, we acquired about six-megapixel images of Okavango Delta of Botswana, a tropical savanna habitat similar to where the human eye is thought to have evolved. Some sequences of images were captured unsystematically while following a baboon troop, while others were designed to vary a single parameter such as aperture, object distance, time of day or position on the horizon. Images are available in the raw RGB format and in grayscale. Images are also available in units relevant to the physiology of human cone photoreceptors, where pixel values represent the expected number of photoisomerizations per second for cones sensitive to long (L), medium (M) and short (S) wavelengths. This database is distributed under a Creative Commons Attribution-Noncommercial Unported license to facilitate research in computer vision, psychophysics of perception, and visual neuroscience.},
author = {Tkacik, Gasper and Garrigan, Patrick and Ratliff, Charles and Milcinski, Grega and Klein, Jennifer and Seyfarth, Lucia and Sterling, Peter and Brainard, David and Balasubramanian, Vijay},
journal = {PLoS One},
number = {6},
publisher = {Public Library of Science},
title = {{Natural images from the birthplace of the human eye}},
doi = {10.1371/journal.pone.0020409},
volume = {6},
year = {2011},
}
@article{3389,
abstract = {Kernel canonical correlation analysis (KCCA) is a general technique for subspace learning that incorporates principal components analysis (PCA) and Fisher linear discriminant analysis (LDA) as special cases. By finding directions that maximize correlation, KCCA learns representations that are more closely tied to the underlying process that generates the data and can ignore high-variance noise directions. However, for data where acquisition in one or more modalities is expensive or otherwise limited, KCCA may suffer from small sample effects. We propose to use semi-supervised Laplacian regularization to utilize data that are present in only one modality. This approach is able to find highly correlated directions that also lie along the data manifold, resulting in a more robust estimate of correlated subspaces. Functional magnetic resonance imaging (fMRI) acquired data are naturally amenable to subspace techniques as data are well aligned. fMRI data of the human brain are a particularly interesting candidate. In this study we implemented various supervised and semi-supervised versions of KCCA on human fMRI data, with regression to single and multi-variate labels (corresponding to video content subjects viewed during the image acquisition). In each variate condition, the semi-supervised variants of KCCA performed better than the supervised variants, including a supervised variant with Laplacian regularization. We additionally analyze the weights learned by the regression in order to infer brain regions that are important to different types of visual processing.},
author = {Blaschko, Matthew and Shelton, Jacquelyn and Bartels, Andreas and Lampert, Christoph and Gretton, Arthur},
journal = {Pattern Recognition Letters},
number = {11},
pages = {1572 -- 1583},
publisher = {Elsevier},
title = {{Semi supervised kernel canonical correlation analysis with application to human fMRI}},
doi = {10.1016/j.patrec.2011.02.011},
volume = {32},
year = {2011},
}
@article{3391,
abstract = {Evolutionary biology shares many concepts with statistical physics: both deal with populations, whether of molecules or organisms, and both seek to simplify evolution in very many dimensions. Often, methodologies have undergone parallel and independent development, as with stochastic methods in population genetics. Here, we discuss aspects of population genetics that have embraced methods from physics: non-equilibrium statistical mechanics, travelling waves and Monte-Carlo methods, among others, have been used to study polygenic evolution, rates of adaptation and range expansions. These applications indicate that evolutionary biology can further benefit from interactions with other areas of statistical physics; for example, by following the distribution of paths taken by a population through time},
author = {de Vladar, Harold and Barton, Nicholas H},
journal = {Trends in Ecology and Evolution},
number = {8},
pages = {424 -- 432},
publisher = {Cell Press},
title = {{The contribution of statistical physics to evolutionary biology}},
doi = {10.1016/j.tree.2011.04.002},
volume = {26},
year = {2011},
}
@article{3396,
abstract = {Facial branchiomotor neurons (FBMNs) in zebrafish and mouse embryonic hindbrain undergo a characteristic tangential migration from rhombomere (r) 4, where they are born, to r6/7. Cohesion among neuroepithelial cells (NCs) has been suggested to function in FBMN migration by inhibiting FBMNs positioned in the basal neuroepithelium such that they move apically between NCs towards the midline of the neuroepithelium instead of tangentially along the basal side of the neuroepithelium towards r6/7. However, direct experimental evaluation of this hypothesis is still lacking. Here, we have used a combination of biophysical cell adhesion measurements and high-resolution time-lapse microscopy to determine the role of NC cohesion in FBMN migration. We show that reducing NC cohesion by interfering with Cadherin 2 (Cdh2) activity results in FBMNs positioned at the basal side of the neuroepithelium moving apically towards the neural tube midline instead of tangentially towards r6/7. In embryos with strongly reduced NC cohesion, ectopic apical FBMN movement frequently results in fusion of the bilateral FBMN clusters over the apical midline of the neural tube. By contrast, reducing cohesion among FBMNs by interfering with Contactin 2 (Cntn2) expression in these cells has little effect on apical FBMN movement, but reduces the fusion of the bilateral FBMN clusters in embryos with strongly diminished NC cohesion. These data provide direct experimental evidence that NC cohesion functions in tangential FBMN migration by restricting their apical movement.},
author = {Stockinger, Petra and Heisenberg, Carl-Philipp J and Maître, Jean-Léon},
journal = {Development},
number = {21},
pages = {4673 -- 4683},
publisher = {Company of Biologists},
title = {{Defective neuroepithelial cell cohesion affects tangential branchiomotor neuron migration in the zebrafish neural tube}},
doi = {10.1242/dev.071233},
volume = {138},
year = {2011},
}
@article{3505,
abstract = {Cell migration on two-dimensional (2D) substrates follows entirely different rules than cell migration in three-dimensional (3D) environments. This is especially relevant for leukocytes that are able to migrate in the absence of adhesion receptors within the confined geometry of artificial 3D extracellular matrix scaffolds and within the interstitial space in vivo. Here, we describe in detail a simple and economical protocol to visualize dendritic cell migration in 3D collagen scaffolds along chemotactic gradients. This method can be adapted to other cell types and may serve as a physiologically relevant paradigm for the directed locomotion of most amoeboid cells.},
author = {Sixt, Michael K and Lämmermann, Tim},
journal = {Cell Migration},
pages = {149 -- 165},
publisher = {Springer},
title = {{In vitro analysis of chemotactic leukocyte migration in 3D environments}},
doi = {10.1007/978-1-61779-207-6_11},
volume = {769},
year = {2011},
}
@article{3315,
abstract = {We consider two-player games played in real time on game structures with clocks where the objectives of players are described using parity conditions. The games are concurrent in that at each turn, both players independently propose a time delay and an action, and the action with the shorter delay is chosen. To prevent a player from winning by blocking time, we restrict each player to play strategies that ensure that the player cannot be responsible for causing a zeno run. First, we present an efficient reduction of these games to turn-based (i.e., not concurrent) finite-state (i.e., untimed) parity games. Our reduction improves the best known complexity for solving timed parity games. Moreover, the rich class of algorithms for classical parity games can now be applied to timed parity games. The states of the resulting game are based on clock regions of the original game, and the state space of the finite game is linear in the size of the region graph. Second, we consider two restricted classes of strategies for the player that represents the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust winning strategies. Using a limit-robust winning strategy, the controller cannot choose an exact real-valued time delay but must allow for some nonzero jitter in each of its actions. If there is a given lower bound on the jitter, then the strategy is bounded-robust winning. We show that exact strategies are more powerful than limit-robust strategies, which are more powerful than bounded-robust winning strategies for any bound. For both kinds of robust strategies, we present efficient reductions to standard timed automaton games. These reductions provide algorithms for the synthesis of robust real-time controllers.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Prabhu, Vinayak},
journal = {Logical Methods in Computer Science},
number = {4},
publisher = {International Federation of Computational Logic},
title = {{Timed parity games: Complexity and robustness}},
doi = {10.2168/LMCS-7(4:8)2011},
volume = {7},
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{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},
}
@article{6496,
abstract = {We report the switching behavior of the full bacterial flagellum system that includes the filament and the motor in wild-type Escherichia coli cells. In sorting the motor behavior by the clockwise bias, we find that the distributions of the clockwise (CW) and counterclockwise (CCW) intervals are either exponential or nonexponential with long tails. At low bias, CW intervals are exponentially distributed and CCW intervals exhibit long tails. At intermediate CW bias (0.5) both CW and CCW intervals are mainly exponentially distributed. A simple model suggests that these two distinct switching behaviors are governed by the presence of signaling noise within the chemotaxis network. Low noise yields exponentially distributed intervals, whereas large noise yields nonexponential behavior with long tails. These drastically different motor statistics may play a role in optimizing bacterial behavior for a wide range of environmental conditions.},
author = {Park, Heungwon and Oikonomou, Panos and Guet, Calin C and Cluzel, Philippe},
issn = {0006-3495},
journal = {Biophysical Journal},
number = {10},
pages = {2336--2340},
publisher = {Elsevier BV},
title = {{Noise underlies switching behavior of the bacterial flagellum}},
doi = {10.1016/j.bpj.2011.09.040},
volume = {101},
year = {2011},
}
@inproceedings{3346,
abstract = {We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with k reward functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the single-objective case, both randomization and memory are necessary for strategies, and that finite-memory randomized strategies are sufficient. Under the satisfaction objective, in contrast to the single-objective case, infinite memory is necessary for strategies, and that randomized memoryless strategies are sufficient for epsilon-approximation, for all epsilon>;0. We further prove that the decision problems for both expectation and satisfaction objectives can be solved in polynomial time and the trade-off curve (Pareto curve) can be epsilon-approximated in time polynomial in the size of the MDP and 1/epsilon, and exponential in the number of reward functions, for all epsilon>;0. Our results also reveal flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, correct the flaws and obtain improved results.},
author = {Brázdil, Tomáš and Brožek, Václav and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín},
location = {Toronto, Canada},
publisher = {IEEE},
title = {{Two views on multiple mean payoff objectives in Markov Decision Processes}},
doi = {10.1109/LICS.2011.10},
year = {2011},
}
@article{3353,
abstract = {Compositional theories are crucial when designing large and complex systems from smaller components. In this work we propose such a theory for synchronous concurrent systems. Our approach follows so-called interface theories, which use game-theoretic interpretations of composition and refinement. These are appropriate for systems with distinct inputs and outputs, and explicit conditions on inputs that must be enforced during composition. Our interfaces model systems that execute in an infinite sequence of synchronous rounds. At each round, a contract must be satisfied. The contract is simply a relation specifying the set of valid input/output pairs. Interfaces can be composed by parallel, serial or feedback composition. A refinement relation between interfaces is defined, and shown to have two main properties: (1) it is preserved by composition, and (2) it is equivalent to substitutability, namely, the ability to replace an interface by another one in any context. Shared refinement and abstraction operators, corresponding to greatest lower and least upper bounds with respect to refinement, are also defined. Input-complete interfaces, that impose no restrictions on inputs, and deterministic interfaces, that produce a unique output for any legal input, are discussed as special cases, and an interesting duality between the two classes is exposed. A number of illustrative examples are provided, as well as algorithms to compute compositions, check refinement, and so on, for finite-state interfaces.},
author = {Tripakis, Stavros and Lickly, Ben and Henzinger, Thomas A and Lee, Edward},
journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)},
number = {4},
publisher = {ACM},
title = {{A theory of synchronous relational interfaces}},
doi = {10.1145/1985342.1985345},
volume = {33},
year = {2011},
}
@inproceedings{3264,
abstract = {Verification of programs with procedures, multi-threaded programs, and higher-order functional programs can be effectively au- tomated using abstraction and refinement schemes that rely on spurious counterexamples for abstraction discovery. The analysis of counterexam- ples can be automated by a series of interpolation queries, or, alterna- tively, as a constraint solving query expressed by a set of recursion free Horn clauses. (A set of interpolation queries can be formulated as a single constraint over Horn clauses with linear dependency structure between the unknown relations.) In this paper we present an algorithm for solving recursion free Horn clauses over a combined theory of linear real/rational arithmetic and uninterpreted functions. Our algorithm performs resolu- tion to deal with the clausal structure and relies on partial solutions to deal with (non-local) instances of functionality axioms.},
author = {Gupta, Ashutosh and Popeea, Corneliu and Rybalchenko, Andrey},
editor = {Yang, Hongseok},
location = {Kenting, Taiwan},
pages = {188 -- 203},
publisher = {Springer},
title = {{Solving recursion-free Horn clauses over LI+UIF}},
doi = {10.1007/978-3-642-25318-8_16},
volume = {7078},
year = {2011},
}
@inproceedings{3360,
abstract = {A discounted-sum automaton (NDA) is a nondeterministic finite automaton with edge weights, which values a run by the discounted sum of visited edge weights. More precisely, the weight in the i-th position of the run is divided by lambda^i, where the discount factor lambda is a fixed rational number greater than 1. Discounted summation is a common and useful measuring scheme, especially for infinite sequences, which reflects the assumption that earlier weights are more important than later weights. Determinizing automata is often essential, for example, in formal verification, where there are polynomial algorithms for comparing two deterministic NDAs, while the equivalence problem for NDAs is not known to be decidable. Unfortunately, however, discounted-sum automata are, in general, not determinizable: it is currently known that for every rational discount factor 1 < lambda < 2, there is an NDA with lambda (denoted lambda-NDA) that cannot be determinized. We provide positive news, showing that every NDA with an integral factor is determinizable. We also complete the picture by proving that the integers characterize exactly the discount factors that guarantee determinizability: we show that for every non-integral rational factor lambda, there is a nondeterminizable lambda-NDA. Finally, we prove that the class of NDAs with integral discount factors enjoys closure under the algebraic operations min, max, addition, and subtraction, which is not the case for general NDAs nor for deterministic NDAs. This shows that for integral discount factors, the class of NDAs forms an attractive specification formalism in quantitative formal verification. All our results hold equally for automata over finite words and for automata over infinite words. },
author = {Boker, Udi and Henzinger, Thomas A},
location = {Bergen, Norway},
pages = {82 -- 96},
publisher = {Springer},
title = {{Determinizing discounted-sum automata}},
doi = {10.4230/LIPIcs.CSL.2011.82},
volume = {12},
year = {2011},
}
@misc{5385,
abstract = {There is recently a significant effort to add quantitative objectives to formal verification and synthesis. We introduce and investigate the extension of temporal logics with quantitative atomic assertions, aiming for a general and flexible framework for quantitative-oriented specifications. In the heart of quantitative objectives lies the accumulation of values along a computation. It is either the accumulated summation, as with the energy objectives, or the accumulated average, as with the mean-payoff objectives. We investigate the extension of temporal logics with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is a numeric variable of the system, c is a constant rational number, and Sum(v) and Avg(v) denote the accumulated sum and average of the values of v from the beginning of the computation up to the current point of time. We also allow the path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring to the average value along an entire computation. We study the border of decidability for extensions of various temporal logics. In particular, we show that extending the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities by prefix-accumulation assertions and extending LTL with path-accumulation assertions, result in temporal logics whose model-checking problem is decidable. The extended logics allow to significantly extend the currently known energy and mean-payoff objectives. Moreover, the prefix-accumulation assertions may be refined with “controlled-accumulation”, allowing, for example, to specify constraints on the average waiting time between a request and a grant. On the negative side, we show that the fragment we point to is, in a sense, the maximal logic whose extension with prefix-accumulation assertions permits a decidable model-checking procedure. Extending a temporal logic that has the EG or EU modalities, and in particular CTL and LTL, makes the problem undecidable.},
author = {Boker, Udi and Chatterjee, Krishnendu and Henzinger, Thomas A and Kupferman, Orna},
issn = {2664-1690},
pages = {14},
publisher = {IST Austria},
title = {{Temporal specifications with accumulative values}},
doi = {10.15479/AT:IST-2011-0003},
year = {2011},
}
@inbook{3311,
abstract = {Alpha shapes have been conceived in 1981 as an attempt to define the shape of a finite set of point in the plane. Since then, connections to diverse areas in the sciences and engineering have developed, including to pattern recognition, digital shape sampling and processing, and structural molecular biology. This survey begins with a historical account and discusses geometric, algorithmic, topological, and combinatorial aspects of alpha shapes in this sequence.},
author = {Herbert Edelsbrunner},
booktitle = {Tessellations in the Sciences},
publisher = {Springer},
title = {{Alpha shapes - a survey}},
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},
}
@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},
}
@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},
}
@article{3784,
abstract = {Advanced stages of Scyllarus phyllosoma larvae were collected by demersal trawling during fishery research surveys in the western Mediterranean Sea in 2003–2005. Nucleotide sequence analysis of the mitochondrial 16S rDNA gene allowed the final-stage phyllosoma of Scyllarus arctus to be identified among these larvae. Its morphology is described and illustrated. This constitutes the second complete description of a Scyllaridae phyllosoma with its specific identity being validated by molecular techniques (the first was S. pygmaeus). These results also solved a long lasting taxonomic anomaly of several species assigned to the ancient genus Phyllosoma Leach, 1814. Detailed examination indicated that the final-stage phyllosoma of S. arctus shows closer affinities with the American scyllarid Scyllarus depressus or with the Australian Scyllarus sp. b (sensu Phillips et al., 1981) than to its sympatric species S. pygmaeus.},
author = {Palero, Ferran and Guerao, Guillermo and Clark, Paul and Abello, Pere},
journal = {Journal of the Marine Biological Association of the United Kingdom},
number = {2},
pages = {485 -- 492},
publisher = {Cambridge University Press},
title = {{Scyllarus arctus (Crustacea: Decapoda: Scyllaridae) final stage phyllosoma identified by DNA analysis, with morphological description}},
doi = {10.1017/S0025315410000287},
volume = {91},
year = {2011},
}
@inbook{3791,
abstract = {During the development of multicellular organisms, cell fate specification is followed by the sorting of different cell types into distinct domains from where the different tissues and organs are formed. Cell sorting involves both the segregation of a mixed population of cells with different fates and properties into distinct domains, and the active maintenance of their segregated state. Because of its biological importance and apparent resemblance to fluid segregation in physics, cell sorting was extensively studied by both biologists and physicists over the last decades. Different theories were developed that try to explain cell sorting on the basis of the physical properties of the constituent cells. However, only recently the molecular and cellular mechanisms that control the physical properties driving cell sorting, have begun to be unraveled. In this review, we will provide an overview of different cell-sorting processes in development and discuss how these processes can be explained by the different sorting theories, and how these theories in turn can be connected to the molecular and cellular mechanisms driving these processes.},
author = {Krens, Gabriel and Heisenberg, Carl-Philipp J},
booktitle = {Current Topics in Developmental Biology},
editor = {Labouesse, Michel},
pages = {189 -- 213},
publisher = {Elsevier},
title = {{Cell sorting in development}},
doi = {10.1016/B978-0-12-385065-2.00006-2},
volume = {95},
year = {2011},
}
@inbook{3796,
abstract = {We address the problem of covering ℝ n with congruent balls, while minimizing the number of balls that contain an average point. Considering the 1-parameter family of lattices defined by stretching or compressing the integer grid in diagonal direction, we give a closed formula for the covering density that depends on the distortion parameter. We observe that our family contains the thinnest lattice coverings in dimensions 2 to 5. We also consider the problem of packing congruent balls in ℝ n , for which we give a closed formula for the packing density as well. Again we observe that our family contains optimal configurations, this time densest packings in dimensions 2 and 3.},
author = {Edelsbrunner, Herbert and Kerber, Michael},
booktitle = {Rainbow of Computer Science},
editor = {Calude, Cristian and Rozenberg, Grzegorz and Salomaa, Arto},
pages = {20 -- 35},
publisher = {Springer},
title = {{Covering and packing with spheres by diagonal distortion in R^n}},
doi = {10.1007/978-3-642-19391-0_2},
volume = {6570},
year = {2011},
}
@article{3385,
author = {Sixt, Michael K},
journal = {Immunology Letters},
number = {1},
pages = {32 -- 34},
publisher = {Elsevier},
title = {{Interstitial locomotion of leukocytes}},
doi = {10.1016/j.imlet.2011.02.013},
volume = {138},
year = {2011},
}
@article{3392,
abstract = {Migrating lymphocytes acquire a polarized phenotype with a leading and a trailing edge, or uropod. Although in vitro experiments in cell lines or activated primary cell cultures have established that Rho-p160 coiled-coil kinase (ROCK)-myosin II-mediated uropod contractility is required for integrin de-adhesion on two-dimensional surfaces and nuclear propulsion through narrow pores in three-dimensional matrices, less is known about the role of these two events during the recirculation of primary, nonactivated lymphocytes. Using pharmacological antagonists of ROCK and myosin II, we report that inhibition of uropod contractility blocked integrin-independent mouse T cell migration through narrow, but not large, pores in vitro. T cell crawling on chemokine-coated endothelial cells under shear was severely impaired by ROCK inhibition, whereas transendothelial migration was only reduced through endothelial cells with high, but not low, barrier properties. Using three-dimensional thick-tissue imaging and dynamic two-photon microscopy of T cell motility in lymphoid tissue, we demonstrated a significant role for uropod contractility in intraluminal crawling and transendothelial migration through lymph node, but not bone marrow, endothelial cells. Finally, we demonstrated that ICAM-1, but not anatomical constraints or integrin-independent interactions, reduced parenchymal motility of inhibitor-treated T cells within the dense lymphoid microenvironment, thus assigning context-dependent roles for uropod contraction during lymphocyte recirculation.},
author = {Soriano, Silvia and Hons, Miroslav and Schumann, Kathrin and Kumar, Varsha and Dennier, Timo and Lyck, Ruth and Sixt, Michael K and Stein, Jens},
journal = {Journal of Immunology},
number = {5},
pages = {2356 -- 2364},
publisher = {American Association of Immunologists},
title = {{In vivo analysis of uropod function during physiological T cell trafficking}},
doi = {10.4049/jimmunol.1100935},
volume = {187},
year = {2011},
}
@article{3397,
abstract = {Recent advances in microscopy techniques and biophysical measurements have provided novel insight into the molecular, cellular and biophysical basis of cell adhesion. However, comparably little is known about a core element of cell–cell adhesion—the energy of adhesion at the cell–cell contact. In this review, we discuss approaches to understand the nature and regulation of adhesion energy, and propose strategies to determine adhesion energy between cells in vitro and in vivo.},
author = {Maître, Jean-Léon and Heisenberg, Carl-Philipp J},
journal = {Current Opinion in Cell Biology},
number = {5},
pages = {508 -- 514},
publisher = {Elsevier},
title = {{The role of adhesion energy in controlling cell-cell contacts}},
doi = {10.1016/j.ceb.2011.07.004},
volume = {23},
year = {2011},
}
@article{3405,
abstract = {Glutamate is the major excitatory neurotransmitter in the mammalian central nervous system and gates non-selective cation channels. The origins of glutamate receptors are not well understood as they differ structurally and functionally from simple bacterial ligand-gated ion channels. Here we report the discovery of an ionotropic glutamate receptor that combines the typical eukaryotic domain architecture with the 'TXVGYG' signature sequence of the selectivity filter found in K+ channels. This receptor exhibits functional properties intermediate between bacterial and eukaryotic glutamate-gated ion channels, suggesting a link in the evolution of ionotropic glutamate receptors.},
author = {Janovjak, Harald L and Sandoz, Guillaume and Isacoff, Ehud},
journal = {Nature Communications},
number = {232},
pages = {1 -- 6},
publisher = {Nature Publishing Group},
title = {{Modern ionotropic glutamate receptor with a K+ selectivity signature sequence}},
doi = {10.1038/ncomms1231},
volume = {2},
year = {2011},
}
@article{3429,
abstract = {Transcription factors are central to sustaining pluripotency, yet little is known about transcription factor dynamics in defining pluripotency in the early mammalian embryo. Here, we establish a fluorescence decay after photoactivation (FDAP) assay to quantitatively study the kinetic behaviour of Oct4, a key transcription factor controlling pre-implantation development in the mouse embryo. FDAP measurements reveal that each cell in a developing embryo shows one of two distinct Oct4 kinetics, before there are any morphologically distinguishable differences or outward signs of lineage patterning. The differences revealed by FDAP are due to differences in the accessibility of Oct4 to its DNA binding sites in the nucleus. Lineage tracing of the cells in the two distinct sub-populations demonstrates that the Oct4 kinetics predict lineages of the early embryo. Cells with slower Oct4 kinetics are more likely to give rise to the pluripotent cell lineage that contributes to the inner cell mass. Those with faster Oct4 kinetics contribute mostly to the extra-embryonic lineage. Our findings identify Oct4 kinetics, rather than differences in total transcription factor expression levels, as a predictive measure of developmental cell lineage patterning in the early mouse embryo.},
author = {Plachta, Nicolas and Bollenbach, Mark Tobias and Pease, Shirley and Fraser, Scott and Pantazis, Periklis},
journal = {Nature Cell Biology},
number = {2},
pages = {117 -- 123},
publisher = {Nature Publishing Group},
title = {{Oct4 kinetics predict cell lineage patterning in the early mammalian embryo}},
doi = {10.1038/ncb2154},
volume = {13},
year = {2011},
}
@article{3373,
abstract = {The use of optical traps to measure or apply forces on the molecular level requires a precise knowledge of the trapping force field. Close to the trap center, this field is typically approximated as linear in the displacement of the trapped microsphere. However, applications demanding high forces at low laser intensities can probe the light-microsphere interaction beyond the linear regime. Here, we measured the full nonlinear force and displacement response of an optical trap in two dimensions using a dual-beam optical trap setup with back-focal-plane photodetection. We observed a substantial stiffening of the trap beyond the linear regime that depends on microsphere size, in agreement with Mie theory calculations. Surprisingly, we found that the linear detection range for forces exceeds the one for displacement by far. Our approach allows for a complete calibration of an optical trap.},
author = {Jahnel, Marcus and Behrndt, Martin and Jannasch, Anita and Schaeffer, Erik and Grill, Stephan},
journal = {Optics Letters},
number = {7},
pages = {1260 -- 1262},
publisher = {OSA},
title = {{Measuring the complete force field of an optical trap}},
doi = {10.1364/OL.36.001260},
volume = {36},
year = {2011},
}
@article{3378,
abstract = {The theory of intersection homology was developed to study the singularities of a topologically stratified space. This paper in- corporates this theory into the already developed framework of persistent homology. We demonstrate that persistent intersec- tion homology gives useful information about the relationship between an embedded stratified space and its singularities. We give, and prove the correctness of, an algorithm for the computa- tion of the persistent intersection homology groups of a filtered simplicial complex equipped with a stratification by subcom- plexes. We also derive, from Poincare ́ Duality, some structural results about persistent intersection homology.},
author = {Bendich, Paul and Harer, John},
journal = {Foundations of Computational Mathematics},
number = {3},
pages = {305 -- 336},
publisher = {Springer},
title = {{Persistent intersection homology}},
doi = {10.1007/s10208-010-9081-1},
volume = {11},
year = {2011},
}
@article{3380,
abstract = {Linkage between markers and genes that affect a phenotype of interest may be determined by examining differences in marker allele frequency in the extreme progeny of a cross between two inbred lines. This strategy is usually employed when pooling is used to reduce genotyping costs. When the cross progeny are asexual, the extreme progeny may be selected by multiple generations of asexual reproduction and selection. We analyse this method of measuring phenotype in asexual progeny and examine the changes in marker allele frequency due to selection over many generations. Stochasticity in marker frequency in the selected population arises due to the finite initial population size. We derive the distribution of marker frequency as a result of selection at a single major locus, and show that in order to avoid spurious changes in marker allele frequency in the selected population, the initial population size should be in the low to mid hundreds.},
author = {Logeswaran, Sayanthan and Barton, Nicholas H},
journal = {Genetical Research},
number = {3},
pages = {221 -- 232},
publisher = {Cambridge University Press},
title = {{Mapping Mendelian traits in asexual progeny using changes in marker allele frequency}},
doi = {10.1017/S0016672311000115},
volume = {93},
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},
}
@misc{5386,
abstract = {We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks.},
author = {Chen, Chao and Freedman, Daniel and Lampert, Christoph},
issn = {2664-1690},
pages = {69},
publisher = {IST Austria},
title = {{Enforcing topological constraints in random field image segmentation}},
doi = {10.15479/AT:IST-2011-0002},
year = {2011},
}
@inproceedings{3323,
abstract = {We present a new decidable logic called TREX for expressing constraints about imperative tree data structures. In particular, TREX supports a transitive closure operator that can express reachability constraints, which often appear in data structure invariants. We show that our logic is closed under weakest precondition computation, which enables its use for automated software verification. We further show that satisfiability of formulas in TREX is decidable in NP. The low complexity makes it an attractive alternative to more expensive logics such as monadic second-order logic (MSOL) over trees, which have been traditionally used for reasoning about tree data structures.},
author = {Wies, Thomas and Muñiz, Marco and Kuncak, Viktor},
location = {Wrocław, Poland},
pages = {476 -- 491},
publisher = {Springer},
title = {{An efficient decision procedure for imperative tree data structures}},
doi = {10.1007/978-3-642-22438-6_36},
volume = {6803},
year = {2011},
}
@misc{5381,
abstract = {In two-player finite-state stochastic games of partial obser- vation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distri- bution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or pos- itively (i.e., with positive probability), no matter the strategy of the second player.
We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two- sided with (c) both players having partial observation. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization.
Our main results for pure strategies are as follows: (1) For one-sided games with player 2 perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strate- gies are not sufficient, and present an exponential upper bound on mem- ory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algo- rithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 perfect observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and posi- tive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least non-elementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence re- sult exhibit serious flaws in previous results in the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
issn = {2664-1690},
pages = {43},
publisher = {IST Austria},
title = {{Partial-observation stochastic games: How to win when belief fails}},
doi = {10.15479/AT:IST-2011-0007},
year = {2011},
}
@inproceedings{3316,
abstract = {In addition to being correct, a system should be robust, that is, it should behave reasonably even after receiving unexpected inputs. In this paper, we summarize two formal notions of robustness that we have introduced previously for reactive systems. One of the notions is based on assigning costs for failures on a user-provided notion of incorrect transitions in a specification. Here, we define a system to be robust if a finite number of incorrect inputs does not lead to an infinite number of incorrect outputs. We also give a more refined notion of robustness that aims to minimize the ratio of output failures to input failures. The second notion is aimed at liveness. In contrast to the previous notion, it has no concept of recovery from an error. Instead, it compares the ratio of the number of liveness constraints that the system violates to the number of liveness constraints that the environment violates.},
author = {Bloem, Roderick and Chatterjee, Krishnendu and Greimel, Karin and Henzinger, Thomas A and Jobstmann, Barbara},
booktitle = {6th IEEE International Symposium on Industrial and Embedded Systems},
location = {Vasteras, Sweden},
pages = {176 -- 185},
publisher = {IEEE},
title = {{Specification-centered robustness}},
doi = {10.1109/SIES.2011.5953660},
year = {2011},
}
@inproceedings{3366,
abstract = {We present an algorithmic method for the quantitative, performance-aware synthesis of concurrent programs. The input consists of a nondeterministic partial program and of a parametric performance model. The nondeterminism allows the programmer to omit which (if any) synchronization construct is used at a particular program location. The performance model, specified as a weighted automaton, can capture system architectures by assigning different costs to actions such as locking, context switching, and memory and cache accesses. The quantitative synthesis problem is to automatically resolve the nondeterminism of the partial program so that both correctness is guaranteed and performance is optimal. As is standard for shared memory concurrency, correctness is formalized "specification free", in particular as race freedom or deadlock freedom. For worst-case (average-case) performance, we show that the problem can be reduced to 2-player graph games (with probabilistic transitions) with quantitative objectives. While we show, using game-theoretic methods, that the synthesis problem is Nexp-complete, we present an algorithmic method and an implementation that works efficiently for concurrent programs and performance models of practical interest. We have implemented a prototype tool and used it to synthesize finite-state concurrent programs that exhibit different programming patterns, for several performance models representing different architectures. },
author = {Cerny, Pavol and Chatterjee, Krishnendu and Henzinger, Thomas A and Radhakrishna, Arjun and Singh, Rohit},
editor = {Gopalakrishnan, Ganesh and Qadeer, Shaz},
location = {Snowbird, USA},
pages = {243 -- 259},
publisher = {Springer},
title = {{Quantitative synthesis for concurrent programs}},
doi = {10.1007/978-3-642-22110-1_20 },
volume = {6806},
year = {2011},
}
@inproceedings{3359,
abstract = {Motivated by improvements in constraint-solving technology and by the increase of routinely available computational power, partial-program synthesis is emerging as an effective approach for increasing programmer productivity. The goal of the approach is to allow the programmer to specify a part of her intent imperatively (that is, give a partial program) and a part of her intent declaratively, by specifying which conditions need to be achieved or maintained. The task of the synthesizer is to construct a program that satisfies the specification. As an example, consider a partial program where threads access shared data without using any synchronization mechanism, and a declarative specification that excludes data races and deadlocks. The task of the synthesizer is then to place locks into the program code in order for the program to meet the specification.
In this paper, we argue that quantitative objectives are needed in partial-program synthesis in order to produce higher-quality programs, while enabling simpler specifications. Returning to the example, the synthesizer could construct a naive solution that uses one global lock for shared data. This can be prevented either by constraining the solution space further (which is error-prone and partly defeats the point of synthesis), or by optimizing a quantitative objective that models performance. Other quantitative notions useful in synthesis include fault tolerance, robustness, resource (memory, power) consumption, and information flow.},
author = {Cerny, Pavol and Henzinger, Thomas A},
location = {Taipei; Taiwan},
pages = {149 -- 154},
publisher = {ACM},
title = {{From boolean to quantitative synthesis}},
doi = {10.1145/2038642.2038666},
year = {2011},
}