@article{2234,
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 κ limit-average 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 case of one limit-average function, both randomization and memory are necessary for strategies even for ε-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e. randomized finite-memory strategies are not sufficient), whereas memoryless randomized strategies are sufficient for ε-approximation, for all ε > 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 ε-approximated in time polynomial in the size of the MDP and 1/ε, and exponential in the number of limit-average functions, for all ε > 0. Our analysis also reveals flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, corrects the flaws, and allows us to obtain improved results.},
author = {Brázdil, Tomáš and Brožek, Václav and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín},
issn = {18605974},
journal = {Logical Methods in Computer Science},
number = {1},
publisher = {International Federation of Computational Logic},
title = {{Markov decision processes with multiple long-run average objectives}},
doi = {10.2168/LMCS-10(1:13)2014},
volume = {10},
year = {2014},
}
@article{2235,
abstract = {Emerging infectious diseases (EIDs) pose a risk to human welfare, both directly and indirectly, by affecting managed livestock and wildlife that provide valuable resources and ecosystem services, such as the pollination of crops. Honeybees (Apis mellifera), the prevailing managed insect crop pollinator, suffer from a range of emerging and exotic high-impact pathogens, and population maintenance requires active management by beekeepers to control them. Wild pollinators such as bumblebees (Bombus spp.) are in global decline, one cause of which may be pathogen spillover from managed pollinators like honeybees or commercial colonies of bumblebees. Here we use a combination of infection experiments and landscape-scale field data to show that honeybee EIDs are indeed widespread infectious agents within the pollinator assemblage. The prevalence of deformed wing virus (DWV) and the exotic parasite Nosema ceranae in honeybees and bumblebees is linked; as honeybees have higher DWV prevalence, and sympatric bumblebees and honeybees are infected by the same DWV strains, Apis is the likely source of at least one major EID in wild pollinators. Lessons learned from vertebrates highlight the need for increased pathogen control in managed bee species to maintain wild pollinators, as declines in native pollinators may be caused by interspecies pathogen transmission originating from managed pollinators.},
author = {Fürst, Matthias and Mcmahon, Dino and Osborne, Juliet and Paxton, Robert and Brown, Mark},
issn = {00280836},
journal = {Nature},
number = {7488},
pages = {364 -- 366},
publisher = {Nature Publishing Group},
title = {{Disease associations between honeybees and bumblebees as a threat to wild pollinators}},
doi = {10.1038/nature12977},
volume = {506},
year = {2014},
}
@inproceedings{2236,
abstract = {Consider a joint distribution (X,A) on a set. We show that for any family of distinguishers, there exists a simulator such that 1 no function in can distinguish (X,A) from (X,h(X)) with advantage ε, 2 h is only O(2 3ℓ ε -2) times less efficient than the functions in. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ε > 0 is negligible and consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of our theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt'09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem.},
author = {Jetchev, Dimitar and Pietrzak, Krzysztof Z},
editor = {Lindell, Yehuda},
isbn = {978-364254241-1},
location = {San Diego, USA},
pages = {566 -- 590},
publisher = {Springer},
title = {{How to fake auxiliary input}},
doi = {10.1007/978-3-642-54242-8_24},
volume = {8349},
year = {2014},
}
@article{2246,
abstract = {Muller games are played by two players moving a token along a graph; the winner is determined by the set of vertices that occur infinitely often. The central algorithmic problem is to compute the winning regions for the players. Different classes and representations of Muller games lead to problems of varying computational complexity. One such class are parity games; these are of particular significance in computational complexity, as they remain one of the few combinatorial problems known to be in NP ∩ co-NP but not known to be in P. We show that winning regions for a Muller game can be determined from the alternating structure of its traps. To every Muller game we then associate a natural number that we call its trap depth; this parameter measures how complicated the trap structure is. We present algorithms for parity games that run in polynomial time for graphs of bounded trap depth, and in general run in time exponential in the trap depth. },
author = {Grinshpun, Andrey and Phalitnonkiat, Pakawat and Rubin, Sasha and Tarfulea, Andrei},
issn = {03043975},
journal = {Theoretical Computer Science},
pages = {73 -- 91},
publisher = {Elsevier},
title = {{Alternating traps in Muller and parity games}},
doi = {10.1016/j.tcs.2013.11.032},
volume = {521},
year = {2014},
}
@article{2249,
abstract = {The unfolded protein response (UPR) is a signaling network triggered by overload of protein-folding demand in the endoplasmic reticulum (ER), a condition termed ER stress. The UPR is critical for growth and development; nonetheless, connections between the UPR and other cellular regulatory processes remain largely unknown. Here, we identify a link between the UPR and the phytohormone auxin, a master regulator of plant physiology. We show that ER stress triggers down-regulation of auxin receptors and transporters in Arabidopsis thaliana. We also demonstrate that an Arabidopsis mutant of a conserved ER stress sensor IRE1 exhibits defects in the auxin response and levels. These data not only support that the plant IRE1 is required for auxin homeostasis, they also reveal a species-specific feature of IRE1 in multicellular eukaryotes. Furthermore, by establishing that UPR activation is reduced in mutants of ER-localized auxin transporters, including PIN5, we define a long-neglected biological significance of ER-based auxin regulation. We further examine the functional relationship of IRE1 and PIN5 by showing that an ire1 pin5 triple mutant enhances defects of UPR activation and auxin homeostasis in ire1 or pin5. Our results imply that the plant UPR has evolved a hormone-dependent strategy for coordinating ER function with physiological processes.},
author = {Chen, Yani and Aung, Kyaw and Rolčík, Jakub and Walicki, Kathryn and Friml, Jirí and Brandizzí, Federica},
issn = {09607412},
journal = {Plant Journal},
number = {1},
pages = {97 -- 107},
publisher = {Wiley-Blackwell},
title = {{Inter-regulation of the unfolded protein response and auxin signaling}},
doi = {10.1111/tpj.12373},
volume = {77},
year = {2014},
}
@article{2250,
abstract = {The genome sequences of new viruses often contain many "orphan" or "taxon-specific" proteins apparently lacking homologs. However, because viral proteins evolve very fast, commonly used sequence similarity detection methods such as BLAST may overlook homologs. We analyzed a data set of proteins from RNA viruses characterized as "genus specific" by BLAST. More powerful methods developed recently, such as HHblits or HHpred (available through web-based, user-friendly interfaces), could detect distant homologs of a quarter of these proteins, suggesting that these methods should be used to annotate viral genomes. In-depth manual analyses of a subset of the remaining sequences, guided by contextual information such as taxonomy, gene order, or domain cooccurrence, identified distant homologs of another third. Thus, a combination of powerful automated methods and manual analyses can uncover distant homologs of many proteins thought to be orphans. We expect these methodological results to be also applicable to cellular organisms, since they generally evolve much more slowly than RNA viruses. As an application, we reanalyzed the genome of a bee pathogen, Chronic bee paralysis virus (CBPV). We could identify homologs of most of its proteins thought to be orphans; in each case, identifying homologs provided functional clues. We discovered that CBPV encodes a domain homologous to the Alphavirus methyltransferase-guanylyltransferase; a putative membrane protein, SP24, with homologs in unrelated insect viruses and insect-transmitted plant viruses having different morphologies (cileviruses, higreviruses, blunerviruses, negeviruses); and a putative virion glycoprotein, ORF2, also found in negeviruses. SP24 and ORF2 are probably major structural components of the virionsd.},
author = {Kuchibhatla, Durga and Sherman, Westley and Chung, Betty and Cook, Shelley and Schneider, Georg and Eisenhaber, Birgit and Karlin, David},
issn = {0022538X},
journal = {Journal of Virology},
number = {1},
pages = {10 -- 20},
publisher = {ASM},
title = {{Powerful sequence similarity search methods and in-depth manual analyses can identify remote homologs in many apparently "orphan" viral proteins}},
doi = {10.1128/JVI.02595-13},
volume = {88},
year = {2014},
}
@article{2251,
abstract = {Sharp wave/ripple (SWR, 150–250 Hz) hippocampal events have long been postulated to be involved in memory consolidation. However, more recent work has investigated SWRs that occur during active waking behaviour: findings that suggest that SWRs may also play a role in cell assembly strengthening or spatial working memory. Do such theories of SWR function apply to animal learning? This review discusses how general theories linking SWRs to memory-related function may explain circuit mechanisms related to rodent spatial learning and to the associated stabilization of new cognitive maps.},
author = {Csicsvari, Jozsef L and Dupret, David},
issn = {09628436},
journal = {Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences},
number = {1635},
publisher = {Royal Society, The},
title = {{Sharp wave/ripple network oscillations and learning-associated hippocampal maps}},
doi = {10.1098/rstb.2012.0528},
volume = {369},
year = {2014},
}
@article{2253,
abstract = {Plant growth is achieved predominantly by cellular elongation, which is thought to be controlled on several levels by apoplastic auxin. Auxin export into the apoplast is achieved by plasma membrane efflux catalysts of the PIN-FORMED (PIN) and ATP-binding cassette protein subfamily B/phosphor- glycoprotein (ABCB/PGP) classes; the latter were shown to depend on interaction with the FKBP42, TWISTED DWARF1 (TWD1). Here by using a transgenic approach in combination with phenotypical, biochemical and cell biological analyses we demonstrate the importance of a putative C-terminal in-plane membrane anchor of TWD1 in the regulation of ABCB-mediated auxin transport. In contrast with dwarfed twd1 loss-of-function alleles, TWD1 gain-of-function lines that lack a putative in-plane membrane anchor (HA-TWD1-Ct) show hypermorphic plant architecture, characterized by enhanced stem length and leaf surface but reduced shoot branching. Greater hypocotyl length is the result of enhanced cell elongation that correlates with reduced polar auxin transport capacity for HA-TWD1-Ct. As a consequence, HA-TWD1-Ct displays higher hypocotyl auxin accumulation, which is shown to result in elevated auxin-induced cell elongation rates. Our data highlight the importance of C-terminal membrane anchoring for TWD1 action, which is required for specific regulation of ABCB-mediated auxin transport. These data support a model in which TWD1 controls lateral ABCB1-mediated export into the apoplast, which is required for auxin-mediated cell elongation.},
author = {Bailly, Aurélien and Wang, Bangjun and Zwiewka, Marta and Pollmann, Stephan and Schenck, Daniel and Lüthen, Hartwig and Schulz, Alexander and Friml, Jirí and Geisler, Markus},
issn = {09607412},
journal = {Plant Journal},
number = {1},
pages = {108 -- 118},
publisher = {Wiley-Blackwell},
title = {{Expression of TWISTED DWARF1 lacking its in-plane membrane anchor leads to increased cell elongation and hypermorphic growth}},
doi = {10.1111/tpj.12369},
volume = {77},
year = {2014},
}
@article{2254,
abstract = {Theta-gamma network oscillations are thought to represent key reference signals for information processing in neuronal ensembles, but the underlying synaptic mechanisms remain unclear. To address this question, we performed whole-cell (WC) patch-clamp recordings from mature hippocampal granule cells (GCs) in vivo in the dentate gyrus of anesthetized and awake rats. GCs in vivo fired action potentials at low frequency, consistent with sparse coding in the dentate gyrus. GCs were exposed to barrages of fast AMPAR-mediated excitatory postsynaptic currents (EPSCs), primarily relayed from the entorhinal cortex, and inhibitory postsynaptic currents (IPSCs), presumably generated by local interneurons. EPSCs exhibited coherence with the field potential predominantly in the theta frequency band, whereas IPSCs showed coherence primarily in the gamma range. Action potentials in GCs were phase locked to network oscillations. Thus, theta-gamma-modulated synaptic currents may provide a framework for sparse temporal coding of information in the dentate gyrus.},
author = {Pernia-Andrade, Alejandro and Jonas, Peter M},
issn = {08966273},
journal = {Neuron},
number = {1},
pages = {140 -- 152},
publisher = {Elsevier},
title = {{Theta-gamma-modulated synaptic currents in hippocampal granule cells in vivo define a mechanism for network oscillations}},
doi = {10.1016/j.neuron.2013.09.046},
volume = {81},
year = {2014},
}
@article{2255,
abstract = {Motivated by applications in biology, we present an algorithm for estimating the length of tube-like shapes in 3-dimensional Euclidean space. In a first step, we combine the tube formula of Weyl with integral geometric methods to obtain an integral representation of the length, which we approximate using a variant of the Koksma-Hlawka Theorem. In a second step, we use tools from computational topology to decrease the dependence on small perturbations of the shape. We present computational experiments that shed light on the stability and the convergence rate of our algorithm.},
author = {Edelsbrunner, Herbert and Pausinger, Florian},
issn = {09249907},
journal = {Journal of Mathematical Imaging and Vision},
number = {1},
pages = {164 -- 177},
publisher = {Springer},
title = {{Stable length estimates of tube-like shapes}},
doi = {10.1007/s10851-013-0468-x},
volume = {50},
year = {2014},
}
@article{2257,
abstract = {Maximum entropy models are the least structured probability distributions that exactly reproduce a chosen set of statistics measured in an interacting network. Here we use this principle to construct probabilistic models which describe the correlated spiking activity of populations of up to 120 neurons in the salamander retina as it responds to natural movies. Already in groups as small as 10 neurons, interactions between spikes can no longer be regarded as small perturbations in an otherwise independent system; for 40 or more neurons pairwise interactions need to be supplemented by a global interaction that controls the distribution of synchrony in the population. Here we show that such “K-pairwise” models—being systematic extensions of the previously used pairwise Ising models—provide an excellent account of the data. We explore the properties of the neural vocabulary by: 1) estimating its entropy, which constrains the population's capacity to represent visual information; 2) classifying activity patterns into a small set of metastable collective modes; 3) showing that the neural codeword ensembles are extremely inhomogenous; 4) demonstrating that the state of individual neurons is highly predictable from the rest of the population, allowing the capacity for error correction.},
author = {Tkacik, Gasper and Marre, Olivier and Amodei, Dario and Schneidman, Elad and Bialek, William and Berry, Michael},
issn = {1553734X},
journal = {PLoS Computational Biology},
number = {1},
publisher = {Public Library of Science},
title = {{Searching for collective behavior in a large network of sensory neurons}},
doi = {10.1371/journal.pcbi.1003408},
volume = {10},
year = {2014},
}
@article{7598,
author = {Tan, Shutang and Xue, Hong-Wei},
issn = {2211-1247},
journal = {Cell Reports},
number = {5},
pages = {1692--1702},
publisher = {Elsevier},
title = {{Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting the turnover of ACS5}},
doi = {10.1016/j.celrep.2014.10.047},
volume = {9},
year = {2014},
}
@inproceedings{772,
abstract = {Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.},
author = {Alistarh, Dan-Adrian and Censor Hillel, Keren and Shavit, Nir},
pages = {714 -- 723},
publisher = {ACM},
title = {{Are lock-free concurrent algorithms practically wait-free?}},
doi = {10.1145/2591796.2591836},
year = {2014},
}
@inproceedings{775,
abstract = {The long-lived renaming problem appears in shared-memory systems where a set of threads need to register and deregister frequently from the computation, while concurrent operations scan the set of currently registered threads. Instances of this problem show up in concurrent implementations of transactional memory, flat combining, thread barriers, and memory reclamation schemes for lock-free data structures. In this paper, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the Level Array, has previously been used for hashing and one-shot (single-use) renaming. Our main contribution is to prove that, in long-lived executions, where processes may register and deregister polynomially many times, the technique guarantees constant steps on average and O (log log n) steps with high probability for registering, unit cost for deregistering, and O (n) steps for collect queries, where n is an upper bound on the number of processes that may be active at any point in time. We also show that the algorithm has the surprising property that it is self-healing: under reasonable assumptions on the schedule, operations running while the data structure is in a degraded state implicitly help the data structure re-balance itself. This subtle mechanism obviates the need for expensive periodic rebuilding procedures. Our benchmarks validate this approach, showing that, for typical use parameters, the average number of steps a process takes to register is less than two and the worst-case number of steps is bounded by six, even in executions with billions of operations. We contrast this with other randomized implementations, whose worst-case behavior we show to be unreliable, and with deterministic implementations, whose cost is linear in n.},
author = {Alistarh, Dan-Adrian and Kopinsky, Justin and Matveev, Alexander and Shavit, Nir},
pages = {348 -- 357},
publisher = {IEEE},
title = {{The levelarray: A fast, practical long-lived renaming algorithm}},
doi = {10.1109/ICDCS.2014.43},
year = {2014},
}
@article{7771,
abstract = {In their Letter, Schreck, Bertrand, O'Hern and Shattuck [Phys. Rev. Lett. 107, 078301 (2011)] study nonlinearities in jammed particulate systems that arise when contacts are altered. They conclude that there is "no harmonic regime in the large system limit for all compressions" and "at jamming onset for any system size." Their argument rests on the claim that for finite-range repulsive potentials, of the form used in studies of jamming, the breaking or forming of a single contact is sufficient to destroy the linear regime. We dispute these conclusions and argue that linear response is both justified and essential for understanding the nature of the jammed solid. },
author = {Goodrich, Carl Peter and Liu, Andrea J. and Nagel, Sidney R.},
issn = {0031-9007},
journal = {Physical Review Letters},
number = {4},
publisher = {American Physical Society},
title = {{Comment on “Repulsive contact interactions make jammed particulate systems inherently nonharmonic”}},
doi = {10.1103/physrevlett.112.049801},
volume = {112},
year = {2014},
}
@article{468,
abstract = {Invasive alien parasites and pathogens are a growing threat to biodiversity worldwide, which can contribute to the extinction of endemic species. On the Galápagos Islands, the invasive parasitic fly Philornis downsi poses a major threat to the endemic avifauna. Here, we investigated the influence of this parasite on the breeding success of two Darwin's finch species, the warbler finch (Certhidea olivacea) and the sympatric small tree finch (Camarhynchus parvulus), on Santa Cruz Island in 2010 and 2012. While the population of the small tree finch appeared to be stable, the warbler finch has experienced a dramatic decline in population size on Santa Cruz Island since 1997. We aimed to identify whether warbler finches are particularly vulnerable during different stages of the breeding cycle. Contrary to our prediction, breeding success was lower in the small tree finch than in the warbler finch. In both species P. downsi had a strong negative impact on breeding success and our data suggest that heavy rain events also lowered the fledging success. On the one hand parents might be less efficient in compensating their chicks' energy loss due to parasitism as they might be less efficient in foraging on days of heavy rain. On the other hand, intense rainfalls might lead to increased humidity and more rapid cooling of the nests. In the case of the warbler finch we found that the control of invasive plant species with herbicides had a significant additive negative impact on the breeding success. It is very likely that the availability of insects (i.e. food abundance) is lower in such controlled areas, as herbicide usage led to the removal of the entire understory. Predation seems to be a minor factor in brood loss.},
author = {Cimadom, Arno and Ulloa, Angel and Meidl, Patrick and Zöttl, Markus and Zöttl, Elisabet and Fessl, Birgit and Nemeth, Erwin and Dvorak, Michael and Cunninghame, Francesca and Tebbich, Sabine},
journal = {PLoS One},
number = {9},
publisher = {Public Library of Science},
title = {{Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin's finches}},
doi = {10.1371/journal.pone.0107518},
volume = {9},
year = {2014},
}
@inproceedings{475,
abstract = {First cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity and mean-payoff games. We study the memory requirements for winning strategies of FCGs and certain associated infinite duration games. We exhibit a simple FCG that is not memoryless determined (this corrects a mistake in Memoryless determinacy of parity and mean payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims that FCGs for which Y is closed under cyclic permutations are memoryless determined). We show that θ (n)! memory (where n is the number of nodes in the graph), which is always sufficient, may be necessary to win some FCGs. On the other hand, we identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations, and both Y and its complement are closed under concatenation) that are sufficient to ensure that the corresponding FCGs and their associated infinite duration games are memoryless determined. We demonstrate that many games considered in the literature, such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE, solving some families of FCGs is PSPACE-hard. },
author = {Aminof, Benjamin and Rubin, Sasha},
booktitle = {Electronic Proceedings in Theoretical Computer Science, EPTCS},
location = {Grenoble, France},
pages = {83 -- 90},
publisher = {Open Publishing Association},
title = {{First cycle games}},
doi = {10.4204/EPTCS.146.11},
volume = {146},
year = {2014},
}
@article{535,
abstract = {Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.},
author = {Chatterjee, Krishnendu and Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon},
journal = {Algorithmica},
number = {3},
pages = {457 -- 492},
publisher = {Springer},
title = {{Polynomial time algorithms for energy games with special weight structures}},
doi = {10.1007/s00453-013-9843-7},
volume = {70},
year = {2014},
}
@article{537,
abstract = {Transgenerational effects are broader than only parental relationships. Despite mounting evidence that multigenerational effects alter phenotypic and life-history traits, our understanding of how they combine to determine fitness is not well developed because of the added complexity necessary to study them. Here, we derive a quantitative genetic model of adaptation to an extraordinary new environment by an additive genetic component, phenotypic plasticity, maternal and grandmaternal effects. We show how, at equilibrium, negative maternal and negative grandmaternal effects maximize expected population mean fitness. We define negative transgenerational effects as those that have a negative effect on trait expression in the subsequent generation, that is, they slow, or potentially reverse, the expected evolutionary dynamic. When maternal effects are positive, negative grandmaternal effects are preferred. As expected under Mendelian inheritance, the grandmaternal effects have a lower impact on fitness than the maternal effects, but this dual inheritance model predicts a more complex relationship between maternal and grandmaternal effects to constrain phenotypic variance and so maximize expected population mean fitness in the offspring.},
author = {Prizak, Roshan and Ezard, Thomas and Hoyle, Rebecca},
journal = {Ecology and Evolution},
number = {15},
pages = {3139 -- 3145},
publisher = {Wiley-Blackwell},
title = {{Fitness consequences of maternal and grandmaternal effects}},
doi = {10.1002/ece3.1150},
volume = {4},
year = {2014},
}
@misc{5411,
abstract = {Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to their complexity, testing presents a considerable portion of the effort and cost in the design process. Exploiting the compositional structure of system specifications can considerably reduce the effort in model-based testing. Moreover, inferring properties about the system from testing its individual components allows the designer to reduce the amount of integration testing.
In this paper, we study compositional properties of the IOCO-testing theory. We propose a new approach to composition and hiding operations, inspired by contract-based design and interface theories. These operations preserve behaviors that are compatible under composition and hiding, and prune away incompatible ones. The resulting specification characterizes the input sequences for which the unit testing of components is sufficient to infer the correctness of component integration without the need for further tests. We provide a methodology that uses these results to minimize integration testing effort, but also to detect potential weaknesses in specifications. While we focus on asynchronous models and the IOCO conformance relation, the resulting methodology can be applied to a broader class of systems.},
author = {Daca, Przemyslaw and Henzinger, Thomas A and Krenn, Willibald and Nickovic, Dejan},
issn = {2664-1690},
pages = {20},
publisher = {IST Austria},
title = {{Compositional specifications for IOCO testing}},
doi = {10.15479/AT:IST-2014-148-v2-1},
year = {2014},
}