@article{1831, abstract = {This paper introduces a theme issue presenting the latest developments in research on the impacts of sociality on health and fitness. The articles that follow cover research on societies ranging from insects to humans. Variation in measures of fitness (i.e. survival and reproduction) has been linked to various aspects of sociality in humans and animals alike, and variability in individual health and condition has been recognized as a key mediator of these relationships. Viewed from a broad evolutionary perspective, the evolutionary transitions from a solitary lifestyle to group living have resulted in several new health-related costs and benefits of sociality. Social transmission of parasites within groups represents a major cost of group living, but some behavioural mechanisms, such as grooming, have evolved repeatedly to reduce this cost. Group living also has created novel costs in terms of altered susceptibility to infectious and non-infectious disease as a result of the unavoidable physiological consequences of social competition and integration, which are partly alleviated by social buffering in some vertebrates. Here, we define the relevant aspects of sociality, summarize their health-related costs and benefits, and discuss possible fitness measures in different study systems. Given the pervasive effects of social factors on health and fitness, we propose a synthesis of existing conceptual approaches in disease ecology, ecological immunology and behavioural neurosciences by adding sociality as a key factor, with the goal to generate a broader framework for organismal integration of health-related research.}, author = {Kappeler, Peter and Cremer, Sylvia and Nunn, Charles}, journal = {Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences}, number = {1669}, publisher = {Royal Society}, title = {{Sociality and health: Impacts of sociality on disease susceptibility and transmission in animal and human societies}}, doi = {10.1098/rstb.2014.0116}, volume = {370}, year = {2015}, } @article{1832, abstract = {Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on the identification of the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof. }, author = {Chakraborty, Soham and Henzinger, Thomas A and Sezgin, Ali and Vafeiadis, Viktor}, journal = {Logical Methods in Computer Science}, number = {1}, publisher = {International Federation of Computational Logic}, title = {{Aspect-oriented linearizability proofs}}, doi = {10.2168/LMCS-11(1:20)2015}, volume = {11}, year = {2015}, } @article{1834, abstract = {Huge body of evidences demonstrated that volatile anesthetics affect the hippocampal neurogenesis and neurocognitive functions, and most of them showed impairment at anesthetic dose. Here, we investigated the effect of low dose (1.8%) sevoflurane on hippocampal neurogenesis and dentate gyrus-dependent learning. Neonatal rats at postnatal day 4 to 6 (P4-6) were treated with 1.8% sevoflurane for 6 hours. Neurogenesis was quantified by bromodeoxyuridine labeling and electrophysiology recording. Four and seven weeks after treatment, the Morris water maze and contextual-fear discrimination learning tests were performed to determine the influence on spatial learning and pattern separation. A 6-hour treatment with 1.8% sevoflurane promoted hippocampal neurogenesis and increased the survival of newborn cells and the proportion of immature granular cells in the dentate gyrus of neonatal rats. Sevoflurane-treated rats performed better during the training days of the Morris water maze test and in contextual-fear discrimination learning test. These results suggest that a subanesthetic dose of sevoflurane promotes hippocampal neurogenesis in neonatal rats and facilitates their performance in dentate gyrus-dependent learning tasks.}, author = {Chen, Chong and Wang, Chao and Zhao, Xuan and Zhou, Tao and Xu, Dao and Wang, Zhi and Wang, Ying}, journal = {ASN Neuro}, number = {2}, publisher = {SAGE Publications}, title = {{Low-dose sevoflurane promoteshippocampal neurogenesis and facilitates the development of dentate gyrus-dependent learning in neonatal rats}}, doi = {10.1177/1759091415575845}, volume = {7}, year = {2015}, } @inproceedings{1835, abstract = {The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs –an important problem of interest in evolutionary biology– more efficiently than the classical simulation method. We specify the property in linear temporal logics. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.}, author = {Giacobbe, Mirco and Guet, Calin C and Gupta, Ashutosh and Henzinger, Thomas A and Paixao, Tiago and Petrov, Tatjana}, location = {London, United Kingdom}, pages = {469 -- 483}, publisher = {Springer}, title = {{Model checking gene regulatory networks}}, doi = {10.1007/978-3-662-46681-0_47}, volume = {9035}, year = {2015}, } @inproceedings{1836, abstract = {In the standard framework for worst-case execution time (WCET) analysis of programs, the main data structure is a single instance of integer linear programming (ILP) that represents the whole program. The instance of this NP-hard problem must be solved to find an estimate forWCET, and it must be refined if the estimate is not tight.We propose a new framework for WCET analysis, based on abstract segment trees (ASTs) as the main data structure. The ASTs have two advantages. First, they allow computing WCET by solving a number of independent small ILP instances. Second, ASTs store more expressive constraints, thus enabling a more efficient and precise refinement procedure. In order to realize our framework algorithmically, we develop an algorithm for WCET estimation on ASTs, and we develop an interpolation-based counterexample-guided refinement scheme for ASTs. Furthermore, we extend our framework to obtain parametric estimates of WCET. We experimentally evaluate our approach on a set of examples from WCET benchmark suites and linear-algebra packages. We show that our analysis, with comparable effort, provides WCET estimates that in many cases significantly improve those computed by existing tools.}, author = {Cerny, Pavol and Henzinger, Thomas A and Kovács, Laura and Radhakrishna, Arjun and Zwirchmayr, Jakob}, location = {London, United Kingdom}, pages = {105 -- 131}, publisher = {Springer}, title = {{Segment abstraction for worst-case execution time analysis}}, doi = {10.1007/978-3-662-46669-8_5}, volume = {9032}, year = {2015}, } @article{1837, abstract = {Transition to turbulence in straight pipes occurs in spite of the linear stability of the laminar Hagen-Poiseuille flow if both the amplitude of flow perturbations and the Reynolds number Re exceed a minimum threshold (subcritical transition). As the pipe curvature increases, centrifugal effects become important, modifying the basic flow as well as the most unstable linear modes. If the curvature (tube-to-coiling diameter d/D) is sufficiently large, a Hopf bifurcation (supercritical instability) is encountered before turbulence can be excited (subcritical instability). We trace the instability thresholds in the Re - d/D parameter space in the range 0.01 ≤ d/D\ ≤ 0.1 by means of laser-Doppler velocimetry and determine the point where the subcritical and supercritical instabilities meet. Two different experimental set-ups are used: a closed system where the pipe forms an axisymmetric torus and an open system employing a helical pipe. Implications for the measurement of friction factors in curved pipes are discussed.}, author = {Kühnen, Jakob and Braunshier, P and Schwegel, M and Kuhlmann, Hendrik and Hof, Björn}, journal = {Journal of Fluid Mechanics}, number = {5}, publisher = {Cambridge University Press}, title = {{Subcritical versus supercritical transition to turbulence in curved pipes}}, doi = {10.1017/jfm.2015.184}, volume = {770}, year = {2015}, } @inproceedings{1838, abstract = {Synthesis of program parts is particularly useful for concurrent systems. However, most approaches do not support common design tasks, like modifying a single process without having to re-synthesize or verify the whole system. Assume-guarantee synthesis (AGS) provides robustness against modifications of system parts, but thus far has been limited to the perfect information setting. This means that local variables cannot be hidden from other processes, which renders synthesis results cumbersome or even impossible to realize.We resolve this shortcoming by defining AGS under partial information. We analyze the complexity and decidability in different settings, showing that the problem has a high worstcase complexity and is undecidable in many interesting cases. Based on these observations, we present a pragmatic algorithm based on bounded synthesis, and demonstrate its practical applicability on several examples.}, author = {Bloem, Roderick and Chatterjee, Krishnendu and Jacobs, Swen and Könighofer, Robert}, location = {London, United Kingdom}, pages = {517 -- 532}, publisher = {Springer}, title = {{Assume-guarantee synthesis for concurrent reactive programs with partial information}}, doi = {10.1007/978-3-662-46681-0_50}, volume = {9035}, year = {2015}, } @inproceedings{1839, abstract = {We present MultiGain, a tool to synthesize strategies for Markov decision processes (MDPs) with multiple mean-payoff objectives. Our models are described in PRISM, and our tool uses the existing interface and simulator of PRISM. Our tool extends PRISM by adding novel algorithms for multiple mean-payoff objectives, and also provides features such as (i) generating strategies and exploring them for simulation, and checking them with respect to other properties; and (ii) generating an approximate Pareto curve for two mean-payoff objectives. In addition, we present a new practical algorithm for the analysis of MDPs with multiple mean-payoff objectives under memoryless strategies.}, author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín}, location = {London, United Kingdom}, pages = {181 -- 187}, publisher = {Springer}, title = {{Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives}}, doi = {10.1007/978-3-662-46681-0_12}, volume = {9035}, year = {2015}, } @article{1840, abstract = {In this paper, we present a method for reducing a regular, discrete-time Markov chain (DTMC) to another DTMC with a given, typically much smaller number of states. The cost of reduction is defined as the Kullback-Leibler divergence rate between a projection of the original process through a partition function and a DTMC on the correspondingly partitioned state space. Finding the reduced model with minimal cost is computationally expensive, as it requires an exhaustive search among all state space partitions, and an exact evaluation of the reduction cost for each candidate partition. Our approach deals with the latter problem by minimizing an upper bound on the reduction cost instead of minimizing the exact cost. The proposed upper bound is easy to compute and it is tight if the original chain is lumpable with respect to the partition. Then, we express the problem in the form of information bottleneck optimization, and propose using the agglomerative information bottleneck algorithm for searching a suboptimal partition greedily, rather than exhaustively. The theory is illustrated with examples and one application scenario in the context of modeling bio-molecular interactions.}, author = {Geiger, Bernhard and Petrov, Tatjana and Kubin, Gernot and Koeppl, Heinz}, issn = {0018-9286}, journal = {IEEE Transactions on Automatic Control}, number = {4}, pages = {1010 -- 1022}, publisher = {IEEE}, title = {{Optimal Kullback-Leibler aggregation via information bottleneck}}, doi = {10.1109/TAC.2014.2364971}, volume = {60}, year = {2015}, } @article{1841, abstract = {We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diffusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. The new family of algorithms can be viewed as a generalization of TRW-S from pairwise to higher-order graphical models. We test SRMP on several real-world problems with promising results.}, author = {Kolmogorov, Vladimir}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {5}, pages = {919 -- 930}, publisher = {IEEE}, title = {{A new look at reweighted message passing}}, doi = {10.1109/TPAMI.2014.2363465}, volume = {37}, year = {2015}, } @article{1845, abstract = {Based on extrapolation from excitatory synapses, it is often assumed that depletion of the releasable pool of synaptic vesicles is the main factor underlying depression at inhibitory synapses. In this issue of Neuron, using subcellular patch-clamp recording from inhibitory presynaptic terminals, Kawaguchi and Sakaba (2015) show that at Purkinje cell-deep cerebellar nuclei neuron synapses, changes in presynaptic action potential waveform substantially contribute to synaptic depression. Based on extrapolation from excitatory synapses, it is often assumed that depletion of the releasable pool of synaptic vesicles is the main factor underlying depression at inhibitory synapses. In this issue of Neuron, using subcellular patch-clamp recording from inhibitory presynaptic terminals, Kawaguchi and Sakaba (2015) show that at Purkinje cell-deep cerebellar nuclei neuron synapses, changes in presynaptic action potential waveform substantially contribute to synaptic depression.}, author = {Vandael, David H and Espinoza Martinez, Claudia and Jonas, Peter M}, journal = {Neuron}, number = {6}, pages = {1149 -- 1151}, publisher = {Elsevier}, title = {{Excitement about inhibitory presynaptic terminals}}, doi = {10.1016/j.neuron.2015.03.006}, volume = {85}, year = {2015}, } @article{1846, abstract = {Modal transition systems (MTS) is a well-studied specification formalism of reactive systems supporting a step-wise refinement methodology. Despite its many advantages, the formalism as well as its currently known extensions are incapable of expressing some practically needed aspects in the refinement process like exclusive, conditional and persistent choices. We introduce a new model called parametric modal transition systems (PMTS) together with a general modal refinement notion that overcomes many of the limitations. We investigate the computational complexity of modal and thorough refinement checking on PMTS and its subclasses and provide a direct encoding of the modal refinement problem into quantified Boolean formulae, allowing us to employ state-of-the-art QBF solvers for modal refinement checking. The experiments we report on show that the feasibility of refinement checking is more influenced by the degree of nondeterminism rather than by the syntactic restrictions on the types of formulae allowed in the description of the PMTS.}, author = {Beneš, Nikola and Kretinsky, Jan and Larsen, Kim and Möller, Mikael and Sickert, Salomon and Srba, Jiří}, journal = {Acta Informatica}, number = {2-3}, pages = {269 -- 297}, publisher = {Springer}, title = {{Refinement checking on parametric modal transition systems}}, doi = {10.1007/s00236-015-0215-4}, volume = {52}, year = {2015}, } @article{1847, author = {Grones, Peter and Friml, Jiřĺ}, journal = {Molecular Plant}, number = {3}, pages = {356 -- 358}, publisher = {Elsevier}, title = {{ABP1: Finally docking}}, doi = {10.1016/j.molp.2014.12.013}, volume = {8}, year = {2015}, } @article{1849, abstract = {Cell polarity is a fundamental property of pro- and eukaryotic cells. It is necessary for coordination of cell division, cell morphogenesis and signaling processes. How polarity is generated and maintained is a complex issue governed by interconnected feed-back regulations between small GTPase signaling and membrane tension-based signaling that controls membrane trafficking, and cytoskeleton organization and dynamics. Here, we will review the potential role for calcium as a crucial signal that connects and coordinates the respective processes during polarization processes in plants. This article is part of a Special Issue entitled: 13th European Symposium on Calcium.}, author = {Himschoot, Ellie and Beeckman, Tom and Friml, Jiřĺ and Vanneste, Steffen}, journal = {Biochimica et Biophysica Acta - Molecular Cell Research}, number = {9}, pages = {2168 -- 2172}, publisher = {Elsevier}, title = {{Calcium is an organizer of cell polarity in plants}}, doi = {10.1016/j.bbamcr.2015.02.017}, volume = {1853}, year = {2015}, } @article{1850, abstract = {Entomopathogenic fungi are potent biocontrol agents that are widely used against insect pests, many of which are social insects. Nevertheless, theoretical investigations of their particular life history are scarce. We develop a model that takes into account the main distinguishing features between traditionally studied diseases and obligate killing pathogens, like the (biocontrol-relevant) insect-pathogenic fungi Metarhizium and Beauveria. First, obligate killing entomopathogenic fungi produce new infectious particles (conidiospores) only after host death and not yet on the living host. Second, the killing rates of entomopathogenic fungi depend strongly on the initial exposure dosage, thus we explicitly consider the pathogen load of individual hosts. Further, we make the model applicable not only to solitary host species, but also to group living species by incorporating social interactions between hosts, like the collective disease defences of insect societies. Our results identify the optimal killing rate for the pathogen that minimises its invasion threshold. Furthermore, we find that the rate of contact between hosts has an ambivalent effect: dense interaction networks between individuals are considered to facilitate disease outbreaks because of increased pathogen transmission. In social insects, this is compensated by their collective disease defences, i.e., social immunity. For the type of pathogens considered here, we show that even without social immunity, high contact rates between live individuals dilute the pathogen in the host colony and hence can reduce individual pathogen loads below disease-causing levels.}, author = {Novak, Sebastian and Cremer, Sylvia}, journal = {Journal of Theoretical Biology}, number = {5}, pages = {54 -- 64}, publisher = {Elsevier}, title = {{Fungal disease dynamics in insect societies: Optimal killing rates and the ambivalent effect of high social interaction rates}}, doi = {10.1016/j.jtbi.2015.02.018}, volume = {372}, year = {2015}, } @article{1851, abstract = {We consider mating strategies for females who search for males sequentially during a season of limited length. We show that the best strategy rejects a given male type if encountered before a time-threshold but accepts him after. For frequency-independent benefits, we obtain the optimal time-thresholds explicitly for both discrete and continuous distributions of males, and allow for mistakes being made in assessing the correct male type. When the benefits are indirect (genes for the offspring) and the population is under frequency-dependent ecological selection, the benefits depend on the mating strategy of other females as well. This case is particularly relevant to speciation models that seek to explore the stability of reproductive isolation by assortative mating under frequency-dependent ecological selection. We show that the indirect benefits are to be quantified by the reproductive values of couples, and describe how the evolutionarily stable time-thresholds can be found. We conclude with an example based on the Levene model, in which we analyze the evolutionarily stable assortative mating strategies and the strength of reproductive isolation provided by them.}, author = {Priklopil, Tadeas and Kisdi, Eva and Gyllenberg, Mats}, issn = {1558-5646}, journal = {Evolution}, number = {4}, pages = {1015 -- 1026}, publisher = {Wiley}, title = {{Evolutionarily stable mating decisions for sequentially searching females and the stability of reproductive isolation by assortative mating}}, doi = {10.1111/evo.12618}, volume = {69}, year = {2015}, } @article{1855, abstract = {Summary: Declining populations of bee pollinators are a cause of concern, with major repercussions for biodiversity loss and food security. RNA viruses associated with honeybees represent a potential threat to other insect pollinators, but the extent of this threat is poorly understood. This study aims to attain a detailed understanding of the current and ongoing risk of emerging infectious disease (EID) transmission between managed and wild pollinator species across a wide range of RNA viruses. Within a structured large-scale national survey across 26 independent sites, we quantify the prevalence and pathogen loads of multiple RNA viruses in co-occurring managed honeybee (Apis mellifera) and wild bumblebee (Bombus spp.) populations. We then construct models that compare virus prevalence between wild and managed pollinators. Multiple RNA viruses associated with honeybees are widespread in sympatric wild bumblebee populations. Virus prevalence in honeybees is a significant predictor of virus prevalence in bumblebees, but we remain cautious in speculating over the principle direction of pathogen transmission. We demonstrate species-specific differences in prevalence, indicating significant variation in disease susceptibility or tolerance. Pathogen loads within individual bumblebees may be high and in the case of at least one RNA virus, prevalence is higher in wild bumblebees than in managed honeybee populations. Our findings indicate widespread transmission of RNA viruses between managed and wild bee pollinators, pointing to an interconnected network of potential disease pressures within and among pollinator species. In the context of the biodiversity crisis, our study emphasizes the importance of targeting a wide range of pathogens and defining host associations when considering potential drivers of population decline.}, author = {Mcmahon, Dino and Fürst, Matthias and Caspar, Jesicca and Theodorou, Panagiotis and Brown, Mark and Paxton, Robert}, journal = {Journal of Animal Ecology}, number = {3}, pages = {615 -- 624}, publisher = {Wiley}, title = {{A sting in the spit: Widespread cross-infection of multiple RNA viruses across wild and managed bees}}, doi = {10.1111/1365-2656.12345}, volume = {84}, year = {2015}, } @article{1856, abstract = {The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given specification. Under a probabilistic assumption about the possible inputs, such a preference order is naturally expressed by a weighted automaton, which assigns to each word a value, such that a system is preferred if it generates a higher expected value. We solve the following optimal synthesis problem: given an omega-regular specification, a Markov chain that describes the distribution of inputs, and a weighted automaton that measures how well a system satisfies the given specification under the input assumption, synthesize a system that optimizes the measured value. For safety specifications and quantitative measures that are defined by mean-payoff automata, the optimal synthesis problem reduces to finding a strategy in a Markov decision process (MDP) that is optimal for a long-run average reward objective, which can be achieved in polynomial time. For general omega-regular specifications along with mean-payoff automata, the solution rests on a new, polynomial-time algorithm for computing optimal strategies in MDPs with mean-payoff parity objectives. Our algorithm constructs optimal strategies that consist of two memoryless strategies and a counter. The counter is in general not bounded. To obtain a finite-state system, we show how to construct an ε-optimal strategy with a bounded counter, for all ε > 0. Furthermore, we show how to decide in polynomial time if it is possible to construct an optimal finite-state system (i.e., a system without a counter) for a given specification. We have implemented our approach and the underlying algorithms in a tool that 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. We present some experimental results showing optimal systems that were automatically generated in this way.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Jobstmann, Barbara and Singh, Rohit}, journal = {Journal of the ACM}, number = {1}, publisher = {ACM}, title = {{Measuring and synthesizing systems in probabilistic environments}}, doi = {10.1145/2699430}, volume = {62}, year = {2015}, } @inproceedings{1857, abstract = {Sharing information between multiple tasks enables algorithms to achieve good generalization performance even from small amounts of training data. However, in a realistic scenario of multi-task learning not all tasks are equally related to each other, hence it could be advantageous to transfer information only between the most related tasks. In this work we propose an approach that processes multiple tasks in a sequence with sharing between subsequent tasks instead of solving all tasks jointly. Subsequently, we address the question of curriculum learning of tasks, i.e. finding the best order of tasks to be learned. Our approach is based on a generalization bound criterion for choosing the task order that optimizes the average expected classification performance over all tasks. Our experimental results show that learning multiple related tasks sequentially can be more effective than learning them jointly, the order in which tasks are being solved affects the overall performance, and that our model is able to automatically discover the favourable order of tasks. }, author = {Pentina, Anastasia and Sharmanska, Viktoriia and Lampert, Christoph}, location = {Boston, MA, United States}, pages = {5492 -- 5500}, publisher = {IEEE}, title = {{Curriculum learning of multiple tasks}}, doi = {10.1109/CVPR.2015.7299188}, year = {2015}, } @inproceedings{1858, abstract = {We study the problem of predicting the future, though only in the probabilistic sense of estimating a future state of a time-varying probability distribution. This is not only an interesting academic problem, but solving this extrapolation problem also has many practical application, e.g. for training classifiers that have to operate under time-varying conditions. Our main contribution is a method for predicting the next step of the time-varying distribution from a given sequence of sample sets from earlier time steps. For this we rely on two recent machine learning techniques: embedding probability distributions into a reproducing kernel Hilbert space, and learning operators by vector-valued regression. We illustrate the working principles and the practical usefulness of our method by experiments on synthetic and real data. We also highlight an exemplary application: training a classifier in a domain adaptation setting without having access to examples from the test time distribution at training time.}, author = {Lampert, Christoph}, location = {Boston, MA, United States}, pages = {942 -- 950}, publisher = {IEEE}, title = {{Predicting the future behavior of a time-varying probability distribution}}, doi = {10.1109/CVPR.2015.7298696}, year = {2015}, }