@article{2965,
abstract = {Dieser Artikel soll die sechs verschiedenen Creative Commons Lizenzen erläutern und ihre Bedeutung im Rahmen des wissenschaftlichen Publizierens und des Open Access erklären (CC-BY, CC-BY-SA, CC-BY-NC, CC-BY-ND, CC-BYNC-SA, CC-BY-NC-ND).},
author = {Danowski, Patrick},
journal = {Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen & Bibliothekare},
number = {2},
pages = {200 -- 212},
publisher = {VÖB},
title = {{Kontext Open Access: Creative Commons}},
volume = {65},
year = {2012},
}
@article{2953,
author = {Heisenberg, Carl-Philipp J and Fässler, Reinhard},
journal = {Current Opinion in Cell Biology},
number = {5},
pages = {559 -- 561},
publisher = {Elsevier},
title = {{Cell-cell adhesion and extracellular matrix diversity counts}},
doi = {10.1016/j.ceb.2012.09.002},
volume = {24},
year = {2012},
}
@article{3122,
abstract = {Since Darwin's pioneering research on plant reproductive biology (e.g. Darwin 1877), understanding the mechanisms maintaining the diverse sexual strategies of plants has remained an important challenge for evolutionary biologists. In some species, populations are sexually polymorphic and contain two or more mating morphs (sex phenotypes). Differences in morphology or phenology among the morphs influence patterns of non-random mating. In these populations, negative frequency-dependent selection arising from disassortative (intermorph) mating is usually required for the evolutionary maintenance of sexual polymorphism, but few studies have demonstrated the required patterns of non-random mating. In the current issue of Molecular Ecology, Shang (2012) make an important contribution to our understanding of how disassortative mating influences sex phenotype ratios in Acer pictum subsp. mono (painted maple), a heterodichogamous, deciduous tree of eastern China. They monitored sex expression in 97 adults and used paternity analysis of open-pollinated seed to examine disassortative mating among three sex phenotypes. Using a deterministic 'pollen transfer' model, Shang et al. present convincing evidence that differences in the degree of disassortative mating in progeny arrays of the sex phenotypes can explain their uneven frequencies in the adult population. This study provides a useful example of how the deployment of genetic markers, demographic monitoring and modelling can be integrated to investigate the maintenance of sexual diversity in plants. },
author = {Field, David and Barrett, Spencer},
journal = {Molecular Ecology},
number = {15},
pages = {3640 -- 3643},
publisher = {Wiley-Blackwell},
title = {{Disassortative mating and the maintenance of sexual polymorphism in painted maple}},
doi = {10.1111/j.1365-294X.2012.05643.x},
volume = {21},
year = {2012},
}
@inproceedings{3127,
abstract = {When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques.
We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data, we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations.},
author = {Quadrianto, Novi and Lampert, Christoph and Chen, Chao},
booktitle = {Proceedings of the 29th International Conference on Machine Learning},
location = {Edinburgh, United Kingdom},
pages = {211--218},
publisher = {Omnipress},
title = {{The most persistent soft-clique in a set of sampled graphs}},
year = {2012},
}
@inproceedings{3134,
abstract = {It has been an open question whether the sum of finitely many isotropic Gaussian kernels in n ≥ 2 dimensions can have more modes than kernels, until in 2003 Carreira-Perpiñán and Williams exhibited n +1 isotropic Gaussian kernels in ℝ n with n + 2 modes. We give a detailed analysis of this example, showing that it has exponentially many critical points and that the resilience of the extra mode grows like √n. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes. },
author = {Edelsbrunner, Herbert and Fasy, Brittany and Rote, Günter},
booktitle = {Proceedings of the twenty-eighth annual symposium on Computational geometry },
location = {Chapel Hill, NC, USA},
pages = {91 -- 100},
publisher = {ACM},
title = {{Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions}},
doi = {10.1145/2261250.2261265},
year = {2012},
}
@article{3242,
abstract = {Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated disease defences at the individual and colony level. An intriguing yet little understood phenomenon is that social contact to pathogen-exposed individuals reduces susceptibility of previously naive nestmates to this pathogen. We tested whether such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium anisopliae is based on active upregulation of the immune system of nestmates following contact to an infectious individual or passive protection via transfer of immune effectors among group members—that is, active versus passive immunisation. We found no evidence for involvement of passive immunisation via transfer of antimicrobials among colony members. Instead, intensive allogrooming behaviour between naive and pathogen-exposed ants before fungal conidia firmly attached to their cuticle suggested passage of the pathogen from the exposed individuals to their nestmates. By tracing fluorescence-labelled conidia we indeed detected frequent pathogen transfer to the nestmates, where they caused low-level infections as revealed by growth of small numbers of fungal colony forming units from their dissected body content. These infections rarely led to death, but instead promoted an enhanced ability to inhibit fungal growth and an active upregulation of immune genes involved in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there was no upregulation of the gene cathepsin L, which is associated with antibacterial and antiviral defences, and we found no increased antibacterial activity of nestmates of fungus-exposed ants. This indicates that social immunisation after fungal exposure is specific, similar to recent findings for individual-level immune priming in invertebrates. Epidemiological modeling further suggests that active social immunisation is adaptive, as it leads to faster elimination of the disease and lower death rates than passive immunisation. Interestingly, humans have also utilised the protective effect of low-level infections to fight smallpox by intentional transfer of low pathogen doses (“variolation” or “inoculation”).},
author = {Konrad, Matthias and Vyleta, Meghan and Theis, Fabian and Stock, Miriam and Tragust, Simon and Klatt, Martina and Drescher, Verena and Marr, Carsten and Ugelvig, Line V and Cremer, Sylvia},
journal = {PLoS Biology},
number = {4},
publisher = {Public Library of Science},
title = {{Social transfer of pathogenic fungus promotes active immunisation in ant colonies}},
doi = {10.1371/journal.pbio.1001300},
volume = {10},
year = {2012},
}
@article{3158,
abstract = {We describe here the development and characterization of a conditionally inducible mouse model expressing Lifeact-GFP, a peptide that reports the dynamics of filamentous actin. We have used this model to study platelets, megakaryocytes and melanoblasts and we provide evidence that Lifeact-GFP is a useful reporter in these cell types ex vivo. In the case of platelets and megakaryocytes, these cells are not transfectable by traditional methods, so conditional activation of Lifeact allows the study of actin dynamics in these cells live. We studied melanoblasts in native skin explants from embryos, allowing the visualization of live actin dynamics during cytokinesis and migration. Our study revealed that melanoblasts lacking the small GTPase Rac1 show a delay in the formation of new pseudopodia following cytokinesis that accounts for the previously reported cytokinesis delay in these cells. Thus, through use of this mouse model, we were able to gain insights into the actin dynamics of cells that could only previously be studied using fixed specimens or following isolation from their native tissue environment.},
author = {Schachtner, Hannah and Li, Ang and Stevenson, David and Calaminus, Simon and Thomas, Steven and Watson, Steve and Sixt, Michael K and Wedlich Söldner, Roland and Strathdee, Douglas and Machesky, Laura},
journal = {European Journal of Cell Biology},
number = {11-12},
pages = {923 -- 929},
publisher = {Elsevier},
title = {{Tissue inducible Lifeact expression allows visualization of actin dynamics in vivo and ex vivo}},
doi = {10.1016/j.ejcb.2012.04.002},
volume = {91},
year = {2012},
}
@article{3160,
abstract = {There is a long-running controversy about how early cell fate decisions are made in the developing mammalian embryo. 1,2 In particular, it is controversial when the first events that can predict the establishment of the pluripotent and extra-embryonic lineages in the blastocyst of the pre-implantation embryo occur. It has long been proposed that the position and polarity of cells at the 16- to 32-cell stage embryo influence their decision to either give rise to the pluripotent cell lineage that eventually contributes to the inner cell mass (ICM), comprising the primitive endoderm (PE) and the epiblast (EPI), or the extra-embryonic trophectoderm (TE) surrounding the blastocoel. The positioning of cells in the embryo at this developmental stage could largely be the result of random events, making this a stochastic model of cell lineage allocation. Contrary to such a stochastic model, some studies have detected putative differences in the lineage potential of individual blastomeres before compaction, indicating that the first cell fate decisions may occur as early as at the 4-cell stage. Using a non-invasive, quantitative in vivo imaging assay to study the kinetic behavior of Oct4 (also known as POU5F1), a key transcription factor (TF) controlling pre-implantation development in the mouse embryo, 3-5 a recent study identifies Oct4 kinetics as a predictive measure of cell lineage patterning in the early mouse embryo. 6 Here, we discuss the implications of such molecular heterogeneities in early development and offer potential avenues toward a mechanistic understanding of these observations, contributing to the resolution of the controversy of developmental cell lineage allocation.},
author = {Pantazis, Periklis and Bollenbach, Tobias},
journal = {Cell Cycle},
number = {11},
pages = {2055 -- 2058},
publisher = {Taylor and Francis},
title = {{Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo}},
doi = {10.4161/cc.20118},
volume = {11},
year = {2012},
}
@inproceedings{3280,
abstract = {The (decisional) learning with errors problem (LWE) asks to distinguish "noisy" inner products of a secret vector with random vectors from uniform. The learning parities with noise problem (LPN) is the special case where the elements of the vectors are bits. In recent years, the LWE and LPN problems have found many applications in cryptography. In this paper we introduce a (seemingly) much stronger adaptive assumption, called "subspace LWE" (SLWE), where the adversary can learn the inner product of the secret and random vectors after they were projected into an adaptively and adversarially chosen subspace. We prove that, surprisingly, the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE using secrets of length d (the other direction is trivial.) This result immediately implies that several existing cryptosystems whose security is based on the hardness of the LWE/LPN problems are provably secure in a much stronger sense than anticipated. As an illustrative example we show that the standard way of using LPN for symmetric CPA secure encryption is even secure against a very powerful class of related key attacks. },
author = {Pietrzak, Krzysztof Z},
location = {Taormina, Sicily, Italy},
pages = {548 -- 563},
publisher = {Springer},
title = {{Subspace LWE}},
doi = {10.1007/978-3-642-28914-9_31},
volume = {7194},
year = {2012},
}
@article{3317,
abstract = {The physical distance between presynaptic Ca2+ channels and the Ca2+ sensors that trigger exocytosis of neurotransmitter-containing vesicles is a key determinant of the signalling properties of synapses in the nervous system. Recent functional analysis indicates that in some fast central synapses, transmitter release is triggered by a small number of Ca2+ channels that are coupled to Ca2+ sensors at the nanometre scale. Molecular analysis suggests that this tight coupling is generated by protein–protein interactions involving Ca2+ channels, Ca2+ sensors and various other synaptic proteins. Nanodomain coupling has several functional advantages, as it increases the efficacy, speed and energy efficiency of synaptic transmission.},
author = {Eggermann, Emmanuel and Bucurenciu, Iancu and Goswami, Sarit and Jonas, Peter M},
journal = {Nature Reviews Neuroscience},
number = {1},
pages = {7 -- 21},
publisher = {Nature Publishing Group},
title = {{Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses}},
doi = {10.1038/nrn3125},
volume = {13},
year = {2012},
}
@article{3247,
abstract = {The Brazilian Merganser is a very rare and threatened species that nowadays inhabits only a few protected areas and their surroundings in the Brazilian territory. In order to estimate the remaining genetic diversity and population structure in this species, two mitochondrial genes were sequenced in 39 individuals belonging to two populations and in one individual collected in Argentina in 1950. We found a highly significant divergence between two major remaining populations of Mergus octosetaceus, which suggests a historical population structure in this species. Furthermore, two deeply divergent lineages were found in a single location, which could due to current or historical secondary contact. Based on the available genetic data, we point out future directions which would contribute to design strategies for conservation and management of this threatened species.},
author = {Vilaça, Sibelle and Fernandes Redondo, Rodrigo A and Lins, Lívia and Santos, Fabrício},
journal = {Conservation Genetics},
number = {1},
pages = {293 -- 298},
publisher = {Springer},
title = {{Remaining genetic diversity in Brazilian Merganser (Mergus octosetaceus)}},
doi = {10.1007/s10592-011-0262-5},
volume = {13},
year = {2012},
}
@article{3331,
abstract = {Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve.},
author = {Kerber, Michael and Sagraloff, Michael},
journal = { Journal of Symbolic Computation},
number = {3},
pages = {239 -- 258},
publisher = {Elsevier},
title = {{A worst case bound for topology computation of algebraic curves}},
doi = {10.1016/j.jsc.2011.11.001},
volume = {47},
year = {2012},
}
@article{3115,
abstract = {We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one.},
author = {Berberich, Eric and Halperin, Dan and Kerber, Michael and Pogalnikova, Roza},
journal = {Discrete & Computational Geometry},
number = {4},
pages = {964 -- 989},
publisher = {Springer},
title = {{Deconstructing approximate offsets}},
doi = {10.1007/s00454-012-9441-5},
volume = {48},
year = {2012},
}
@article{3836,
abstract = {Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine (or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram structure needs to be flattened; the flattening makes separatecompilation difficult, and may result in E machinecode of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchicalprogram structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order.},
author = {Ghosal, Arkadeb and Iercan, Daniel and Kirsch, Christoph and Henzinger, Thomas A and Sangiovanni Vincentelli, Alberto},
journal = {Science of Computer Programming},
number = {2},
pages = {96 -- 112},
publisher = {Elsevier},
title = {{Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code}},
doi = {10.1016/j.scico.2010.06.004},
volume = {77},
year = {2012},
}
@article{494,
abstract = {We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata.},
author = {Boker, Udi and Kupferman, Orna},
journal = {ACM Transactions on Computational Logic (TOCL)},
number = {4},
publisher = {ACM},
title = {{Translating to Co-Büchi made tight, unified, and useful}},
doi = {10.1145/2362355.2362357},
volume = {13},
year = {2012},
}
@inproceedings{2888,
abstract = {Formal verification aims to improve the quality of hardware and software by detecting errors before they do harm. At the basis of formal verification lies the logical notion of correctness, which purports to capture whether or not a circuit or program behaves as desired. We suggest that the boolean partition into correct and incorrect systems falls short of the practical need to assess the behavior of hardware and software in a more nuanced fashion against multiple criteria.},
author = {Henzinger, Thomas A},
booktitle = {Conference proceedings MODELS 2012},
location = {Innsbruck, Austria},
pages = {1 -- 2},
publisher = {Springer},
title = {{Quantitative reactive models}},
doi = {10.1007/978-3-642-33666-9_1},
volume = {7590},
year = {2012},
}
@inproceedings{2890,
abstract = {Systems are often specified using multiple requirements on their behavior. In practice, these requirements can be contradictory. The classical approach to specification, verification, and synthesis demands more detailed specifications that resolve any contradictions in the requirements. These detailed specifications are usually large, cumbersome, and hard to maintain or modify. In contrast, quantitative frameworks allow the formalization of the intuitive idea that what is desired is an implementation that comes "closest" to satisfying the mutually incompatible requirements, according to a measure of fit that can be defined by the requirements engineer. One flexible framework for quantifying how "well" an implementation satisfies a specification is offered by simulation distances that are parameterized by an error model. We introduce this framework, study its properties, and provide an algorithmic solution for the following quantitative synthesis question: given two (or more) behavioral requirements specified by possibly incompatible finite-state machines, and an error model, find the finite-state implementation that minimizes the maximal simulation distance to the given requirements. Furthermore, we generalize the framework to handle infinite alphabets (for example, realvalued domains). We also demonstrate how quantitative specifications based on simulation distances might lead to smaller and easier to modify specifications. Finally, we illustrate our approach using case studies on error correcting codes and scheduler synthesis.},
author = {Cerny, Pavol and Gopi, Sivakanth and Henzinger, Thomas A and Radhakrishna, Arjun and Totla, Nishant},
booktitle = {Proceedings of the tenth ACM international conference on Embedded software},
location = {Tampere, Finland},
pages = {53 -- 62},
publisher = {ACM},
title = {{Synthesis from incompatible specifications}},
doi = {10.1145/2380356.2380371},
year = {2012},
}
@article{2972,
abstract = {Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the game) must remain positive. Beside their own interest in the design and synthesis of resource-constrained omega-regular specifications, energy parity games provide one of the simplest model of games with combined qualitative and quantitative objectives. Our main results are as follows: (a) exponential memory is sufficient and may be necessary for winning strategies in energy parity games; (b) the problem of deciding the winner in energy parity games can be solved in NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to energy games. We also show that the problem of deciding the winner in energy parity games is logspace-equivalent to the problem of deciding the winner in mean-payoff parity games, which can thus be solved in NP ∩ coNP. As a consequence we also obtain a conceptually simple algorithm to solve mean-payoff parity games.},
author = {Chatterjee, Krishnendu and Doyen, Laurent},
journal = {Theoretical Computer Science},
pages = {49 -- 60},
publisher = {Elsevier},
title = {{Energy parity games}},
doi = {10.1016/j.tcs.2012.07.038},
volume = {458},
year = {2012},
}
@inproceedings{3165,
abstract = {Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n 2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n 3)), and (3) in Markov decision processes (improving for m > n 4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n 2), which is an improvement over earlier bounds for m > n 4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.},
author = {Chatterjee, Krishnendu and Henzinger, Monika},
booktitle = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms},
location = {Kyoto, Japan},
pages = {1386 -- 1399},
publisher = {SIAM},
title = {{An O(n2) time algorithm for alternating Büchi games}},
doi = {10.1137/1.9781611973099.109},
year = {2012},
}
@article{3254,
abstract = {The theory of graph games with ω-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the qualitative problem asks for the set of states from which a player can win with probability 1 (almost-sure winning); and the quantitative problem asks for the maximal probability of winning (optimal winning) from each state. We consider ω-regular winning conditions formalized as Müller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with Müller winning conditions. We also study the complexity of stochastic Müller games and show that both the qualitative and quantitative analysis problems are PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes.},
author = {Chatterjee, Krishnendu},
journal = {Information and Computation},
pages = {29 -- 48},
publisher = {Elsevier},
title = {{The complexity of stochastic Müller games}},
doi = {10.1016/j.ic.2011.11.004},
volume = {211},
year = {2012},
}