@misc{5405,
abstract = {The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running
in time O(d · n^{2d}·MeanGame) to compute the set of almost-sure winning states from which the objective
can be ensured with probability 1, where n is the number of states of the game, d the number of priorities
of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states
in 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems
with both functional requirement (given as a qualitative objective) and performance requirement (given
as a quantitative objective).},
author = {Chatterjee, Krishnendu and Doyen, Laurent and Gimbert, Hugo and Oualhadj, Youssouf},
issn = {2664-1690},
pages = {22},
publisher = {IST Austria},
title = {{Perfect-information stochastic mean-payoff parity games}},
doi = {10.15479/AT:IST-2013-128-v1-1},
year = {2013},
}
@misc{5406,
abstract = {We consider the distributed synthesis problem fortemporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTLand our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3)Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan and Pavlogiannis, Andreas},
issn = {2664-1690},
pages = {11},
publisher = {IST Austria},
title = {{Distributed synthesis for LTL Fragments}},
doi = {10.15479/AT:IST-2013-130-v1-1},
year = {2013},
}
@techreport{5407,
abstract = {This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the mandatory features, which need to be fulfilled to provide an institutional repository as a platform and also a service to the scientists at the institute. It also includes optional features, which would be of strong benefit for the scientists and would increase the usage of the repository, and hence the visibility of research at IST Austria.},
author = {Porsche, Jana},
publisher = {IST Austria},
title = {{Technical requirements and features}},
year = {2013},
}
@misc{5408,
abstract = {We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are
EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. },
author = {Chatterjee, Krishnendu and Doyen, Laurent and Nain, Sumit and Vardi, Moshe},
issn = {2664-1690},
pages = {17},
publisher = {IST Austria},
title = {{The complexity of partial-observation stochastic parity games with finite-memory strategies}},
doi = {10.15479/AT:IST-2013-141-v1-1},
year = {2013},
}
@misc{5409,
abstract = {The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition.
In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in timestamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than delta away from the parameter, for delta>0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and we show analogous decidability results for rectangular automata.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Majumdar, Rupak},
issn = {2664-1690},
pages = {12},
publisher = {IST Austria},
title = {{Edit distance for timed automata}},
doi = {10.15479/AT:IST-2013-144-v1-1},
year = {2013},
}
@misc{5410,
abstract = {Board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in development of mathematical and logical skills, but also in emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants.
Our approach generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. Also, the presence of such states for standard game variants like Tic-Tac-Toe on board size 4x4 opens up new games to be played that have not been played for ages since the default start state is heavily biased. },
author = {Ahmed, Umair and Chatterjee, Krishnendu and Gulwani, Sumit},
issn = {2664-1690},
pages = {13},
publisher = {IST Austria},
title = {{Automatic generation of alternative starting positions for traditional board games}},
doi = {10.15479/AT:IST-2013-146-v1-1},
year = {2013},
}
@inbook{5747,
author = {Dragoi, Cezara and Gupta, Ashutosh and Henzinger, Thomas A},
booktitle = {Computer Aided Verification},
isbn = {9783642397981},
issn = {0302-9743},
location = {Saint Petersburg, Russia},
pages = {174--190},
publisher = {Springer Berlin Heidelberg},
title = {{Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates}},
doi = {10.1007/978-3-642-39799-8_11},
volume = {8044},
year = {2013},
}
@misc{6440,
abstract = {In order to guarantee that each method of a data structure updates the logical state exactly once, al-most all non-blocking implementations employ Compare-And-Swap (CAS) based synchronization. For FIFO queue implementations this translates into concurrent enqueue or dequeue methods competing among themselves to update the same variable, the tail or the head, respectively, leading to high contention and poor scalability. Recent non-blocking queue implementations try to alleviate high contentionby increasing the number of contention points, all the while using CAS-based synchronization. Furthermore, obtaining a wait-free implementation with competition is achieved by additional synchronization which leads to further degradation of performance.In this paper we formalize the notion of competitiveness of a synchronizing statement which can beused as a measure for the scalability of concurrent implementations. We present a new queue implementation, the Speculative Pairing (SP) queue, which, as we show, decreases competitiveness by using Fetch-And-Increment (FAI) instead of CAS. We prove that the SP queue is linearizable and lock-free.We also show that replacing CAS with FAI leads to wait-freedom for dequeue methods without an adverse effect on performance. In fact, our experiments suggest that the SP queue can perform and scale better than the state-of-the-art queue implementations.},
author = {Henzinger, Thomas A and Payer, Hannes and Sezgin, Ali},
issn = {2664-1690},
pages = {23},
publisher = {IST Austria},
title = {{Replacing competition with cooperation to achieve scalable lock-free FIFO queues }},
doi = {10.15479/AT:IST-2013-124-v1-1},
year = {2013},
}
@inproceedings{1374,
abstract = {We study two-player zero-sum games over infinite-state graphs equipped with ωB and finitary conditions. Our first contribution is about the strategy complexity, i.e the memory required for winning strategies: we prove that over general infinite-state graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory suffices for finitary parity games. We then study pushdown games with boundedness conditions, with two contributions. First we prove a collapse result for pushdown games with ωB-conditions, implying the decidability of solving these games. Second we consider pushdown games with finitary parity along with stack boundedness conditions, and show that solving these games is EXPTIME-complete.},
author = {Chatterjee, Krishnendu and Fijalkow, Nathanaël},
booktitle = {22nd EACSL Annual Conference on Computer Science Logic},
location = {Torino, Italy},
pages = {181 -- 196},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Infinite-state games with finitary conditions}},
doi = {10.4230/LIPIcs.CSL.2013.181},
volume = {23},
year = {2013},
}
@inproceedings{1376,
abstract = {We consider the distributed synthesis problem for temporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTL and our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3) Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan and Pavlogiannis, Andreas},
booktitle = {13th International Conference on Formal Methods in Computer-Aided Design},
location = {Portland, OR, United States},
pages = {18 -- 25},
publisher = {IEEE},
title = {{Distributed synthesis for LTL fragments}},
doi = {10.1109/FMCAD.2013.6679386},
year = {2013},
}
@inproceedings{1385,
abstract = {It is often difficult to correctly implement a Boolean controller for a complex system, especially when concurrency is involved. Yet, it may be easy to formally specify a controller. For instance, for a pipelined processor it suffices to state that the visible behavior of the pipelined system should be identical to a non-pipelined reference system (Burch-Dill paradigm). We present a novel procedure to efficiently synthesize multiple Boolean control signals from a specification given as a quantified first-order formula (with a specific quantifier structure). Our approach uses uninterpreted functions to abstract details of the design. We construct an unsatisfiable SMT formula from the given specification. Then, from just one proof of unsatisfiability, we use a variant of Craig interpolation to compute multiple coordinated interpolants that implement the Boolean control signals. Our method avoids iterative learning and back-substitution of the control functions. We applied our approach to synthesize a controller for a simple two-stage pipelined processor, and present first experimental results.},
author = {Hofferek, Georg and Gupta, Ashutosh and Könighofer, Bettina and Jiang, Jie and Bloem, Roderick},
booktitle = {2013 Formal Methods in Computer-Aided Design},
location = {Portland, OR, United States},
pages = {77 -- 84},
publisher = {IEEE},
title = {{Synthesizing multiple boolean functions using interpolation on a single proof}},
doi = {10.1109/FMCAD.2013.6679394},
year = {2013},
}
@inproceedings{1387,
abstract = {Choices made by nondeterministic word automata depend on both the past (the prefix of the word read so far) and the future (the suffix yet to be read). In several applications, most notably synthesis, the future is diverse or unknown, leading to algorithms that are based on deterministic automata. Hoping to retain some of the advantages of nondeterministic automata, researchers have studied restricted classes of nondeterministic automata. Three such classes are nondeterministic automata that are good for trees (GFT; i.e., ones that can be expanded to tree automata accepting the derived tree languages, thus whose choices should satisfy diverse futures), good for games (GFG; i.e., ones whose choices depend only on the past), and determinizable by pruning (DBP; i.e., ones that embody equivalent deterministic automata). The theoretical properties and relative merits of the different classes are still open, having vagueness on whether they really differ from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also open is the possible succinctness of GFG and GFT automata compared to deterministic automata. We study these problems for ω-regular automata with all common acceptance conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction for GFG automata.},
author = {Boker, Udi and Kuperberg, Denis and Kupferman, Orna and Skrzypczak, Michał},
location = {Riga, Latvia},
number = {PART 2},
pages = {89 -- 100},
publisher = {Springer},
title = {{Nondeterminism in the presence of a diverse or unknown future}},
doi = {10.1007/978-3-642-39212-2_11},
volume = {7966},
year = {2013},
}
@phdthesis{1406,
abstract = {Epithelial spreading is a critical part of various developmental and wound repair processes. Here we use zebrafish epiboly as a model system to study the cellular and molecular mechanisms underlying the spreading of epithelial sheets. During zebrafish epiboly the enveloping cell layer (EVL), a simple squamous epithelium, spreads over the embryo to eventually cover the entire yolk cell by the end of gastrulation. The EVL leading edge is anchored through tight junctions to the yolk syncytial layer (YSL), where directly adjacent to the EVL margin a contractile actomyosin ring is formed that is thought to drive EVL epiboly. The prevalent view in the field was that the contractile ring exerts a pulling force on the EVL margin, which pulls the EVL towards the vegetal pole. However, how this force is generated and how it affects EVL morphology still remains elusive. Moreover, the cellular mechanisms mediating the increase in EVL surface area, while maintaining tissue integrity and function are still unclear. Here we show that the YSL actomyosin ring pulls on the EVL margin by two distinct force-generating mechanisms. One mechanism is based on contraction of the ring around its circumference, as previously proposed. The second mechanism is based on actomyosin retrogade flows, generating force through resistance against the substrate. The latter can function at any epiboly stage even in situations where the contraction-based mechanism is unproductive. Additionally, we demonstrate that during epiboly the EVL is subjected to anisotropic tension, which guides the orientation of EVL cell division along the main axis (animal-vegetal) of tension. The influence of tension in cell division orientation involves cell elongation and requires myosin-2 activity for proper spindle alignment. Strikingly, we reveal that tension-oriented cell divisions release anisotropic tension within the EVL and that in the absence of such divisions, EVL cells undergo ectopic fusions. We conclude that forces applied to the EVL by the action of the YSL actomyosin ring generate a tension anisotropy in the EVL that orients cell divisions, which in turn limit tissue tension increase thereby facilitating tissue spreading.},
author = {Campinho, Pedro},
pages = {123},
publisher = {IST Austria},
title = {{Mechanics of zebrafish epiboly: Tension-oriented cell divisions limit anisotropic tissue tension in epithelial spreading}},
year = {2013},
}
@article{9055,
abstract = {Spontaneous formation of colonies of bacteria or flocks of birds are examples of self-organization in active living matter. Here, we demonstrate a form of self-organization from nonequilibrium driving forces in a suspension of synthetic photoactivated colloidal particles. They lead to two-dimensional "living crystals," which form, break, explode, and re-form elsewhere. The dynamic assembly results from a competition between self-propulsion of particles and an attractive interaction induced respectively by osmotic and phoretic effects and activated by light. We measured a transition from normal to giant-number fluctuations. Our experiments are quantitatively described by simple numerical simulations. We show that the existence of the living crystals is intrinsically related to the out-of-equilibrium collisions of the self-propelled particles.},
author = {Palacci, Jérémie A and Sacanna, S. and Steinberg, A. P. and Pine, D. J. and Chaikin, P. M.},
issn = {1095-9203},
journal = {Science},
keywords = {Multidisciplinary},
number = {6122},
pages = {936--940},
publisher = {American Association for the Advancement of Science },
title = {{Living crystals of light-activated colloidal surfers}},
doi = {10.1126/science.1230020},
volume = {339},
year = {2013},
}
@article{450,
abstract = {Understanding the relative importance of heterosis and outbreeding depression over multiple generations is a key question in evolutionary biology and is essential for identifying appropriate genetic sources for population and ecosystem restoration. Here we use 2455 experimental crosses between 12 population pairs of the rare perennial plant Rutidosis leptorrhynchoides (Asteraceae) to investigate the multi-generational (F1, F2, F3) fitness outcomes of inter-population hybridization. We detected no evidence of outbreeding depression, with inter-population hybrids and backcrosses showing either similar fitness or significant heterosis for fitness components across the three generations. Variation in heterosis among population pairs was best explained by characteristics of the foreign source or home population, and was greatest when the source population was large, with high genetic diversity and low inbreeding, and the home population was small and inbred. Our results indicate that the primary consideration for maximizing progeny fitness following population augmentation or restoration is the use of seed from large, genetically diverse populations.},
author = {Pickup, Melinda and Field, David and Rowell, David and Young, Andrew},
journal = {Proceedings of the Royal Society of London Series B Biological Sciences},
number = {1750},
publisher = {Royal Society, The},
title = {{Source population characteristics affect heterosis following genetic rescue of fragmented plant populations}},
doi = {10.1098/rspb.2012.2058},
volume = {280},
year = {2013},
}
@article{3116,
abstract = {Multithreaded programs coordinate their interaction through synchronization primitives like mutexes and semaphores, which are managed by an OS-provided resource manager. We propose algorithms for the automatic construction of code-aware resource managers for multithreaded embedded applications. Such managers use knowledge about the structure and resource usage (mutex and semaphore usage) of the threads to guarantee deadlock freedom and progress while managing resources in an efficient way. Our algorithms compute managers as winning strategies in certain infinite games, and produce a compact code description of these strategies. We have implemented the algorithms in the tool Cynthesis. Given a multithreaded program in C, the tool produces C code implementing a code-aware resource manager. We show in experiments that Cynthesis produces compact resource managers within a few minutes on a set of embedded benchmarks with up to 6 threads. © 2012 Springer Science+Business Media, LLC.},
author = {Chatterjee, Krishnendu and De Alfaro, Luca and Faella, Marco and Majumdar, Ritankar and Raman, Vishwanath},
journal = {Formal Methods in System Design},
number = {2},
pages = {142 -- 174},
publisher = {Springer},
title = {{Code aware resource management}},
doi = {10.1007/s10703-012-0170-4},
volume = {42},
year = {2013},
}
@article{3261,
abstract = {Cells in a developing embryo have no direct way of "measuring" their physical position. Through a variety of processes, however, the expression levels of multiple genes come to be correlated with position, and these expression levels thus form a code for "positional information." We show how to measure this information, in bits, using the gap genes in the Drosophila embryo as an example. Individual genes carry nearly two bits of information, twice as much as expected if the expression patterns consisted only of on/off domains separated by sharp boundaries. Taken together, four gap genes carry enough information to define a cell's location with an error bar of ~1% along the anterior-posterior axis of the embryo. This precision is nearly enough for each cell to have a unique identity, which is the maximum information the system can use, and is nearly constant along the length of the embryo. We argue that this constancy is a signature of optimality in the transmission of information from primary morphogen inputs to the output of the gap gene network.},
author = {Dubuis, Julien and Tkacik, Gasper and Wieschaus, Eric and Gregor, Thomas and Bialek, William},
journal = {PNAS},
number = {41},
pages = {16301 -- 16308},
publisher = {National Academy of Sciences},
title = {{Positional information, in bits}},
doi = {10.1073/pnas.1315642110},
volume = {110},
year = {2013},
}
@misc{3321,
author = {Quadrianto, Novi and Lampert, Christoph},
booktitle = {Encyclopedia of Systems Biology},
editor = {Dubitzky, Werner and Wolkenhauer, Olaf and Cho, Kwang and Yokota, Hiroki},
pages = {1069 -- 1069},
publisher = {Springer},
title = {{Kernel based learning}},
doi = {10.1007/978-1-4419-9863-7_604},
volume = {3},
year = {2013},
}
@phdthesis{1405,
abstract = {Motivated by the analysis of highly dynamic message-passing systems, i.e. unbounded thread creation, mobility, etc. we present a framework for the analysis of depth-bounded systems. Depth-bounded systems are one of the most expressive known fragment of the π-calculus for which interesting verification problems are still decidable. Even though they are infinite state systems depth-bounded systems are well-structured, thus can be analyzed algorithmically. We give an interpretation of depth-bounded systems as graph-rewriting systems. This gives more flexibility and ease of use to apply depth-bounded systems to other type of systems like shared memory concurrency.
First, we develop an adequate domain of limits for depth-bounded systems, a prerequisite for the effective representation of downward-closed sets. Downward-closed sets are needed by forward saturation-based algorithms to represent potentially infinite sets of states. Then, we present an abstract interpretation framework to compute the covering set of well-structured transition systems. Because, in general, the covering set is not computable, our abstraction over-approximates the actual covering set. Our abstraction captures the essence of acceleration based-algorithms while giving up enough precision to ensure convergence. We have implemented the analysis in the PICASSO tool and show that it is accurate in practice. Finally, we build some further analyses like termination using the covering set as starting point.},
author = {Zufferey, Damien},
pages = {134},
publisher = {IST Austria},
title = {{Analysis of dynamic message passing programs}},
year = {2013},
}
@inproceedings{2847,
abstract = {Depth-Bounded Systems form an expressive class of well-structured transition systems. They can model a wide range of concurrent infinite-state systems including those with dynamic thread creation, dynamically changing communication topology, and complex shared heap structures. We present the first method to automatically prove fair termination of depth-bounded systems. Our method uses a numerical abstraction of the system, which we obtain by systematically augmenting an over-approximation of the system’s reachable states with a finite set of counters. This numerical abstraction can be analyzed with existing termination provers. What makes our approach unique is the way in which it exploits the well-structuredness of the analyzed system. We have implemented our work in a prototype tool and used it to automatically prove liveness properties of complex concurrent systems, including nonblocking algorithms such as Treiber’s stack and several distributed processes. Many of these examples are beyond the scope of termination analyses that are based on traditional counter abstractions.},
author = {Bansal, Kshitij and Koskinen, Eric and Wies, Thomas and Zufferey, Damien},
editor = {Piterman, Nir and Smolka, Scott},
location = {Rome, Italy},
pages = {62 -- 77},
publisher = {Springer},
title = {{Structural Counter Abstraction}},
doi = {10.1007/978-3-642-36742-7_5},
volume = {7795},
year = {2013},
}
@inproceedings{2445,
abstract = {We develop program synthesis techniques that can help programmers fix concurrency-related bugs. We make two new contributions to synthesis for concurrency, the first improving the efficiency of the synthesized code, and the second improving the efficiency of the synthesis procedure itself. The first contribution is to have the synthesis procedure explore a variety of (sequential) semantics-preserving program transformations. Classically, only one such transformation has been considered, namely, the insertion of synchronization primitives (such as locks). Based on common manual bug-fixing techniques used by Linux device-driver developers, we explore additional, more efficient transformations, such as the reordering of independent instructions. The second contribution is to speed up the counterexample-guided removal of concurrency bugs within the synthesis procedure by considering partial-order traces (instead of linear traces) as counterexamples. A partial-order error trace represents a set of linear (interleaved) traces of a concurrent program all of which lead to the same error. By eliminating a partial-order error trace, we eliminate in a single iteration of the synthesis procedure all linearizations of the partial-order trace. We evaluated our techniques on several simplified examples of real concurrency bugs that occurred in Linux device drivers.},
author = {Cerny, Pavol and Henzinger, Thomas A and Radhakrishna, Arjun and Ryzhyk, Leonid and Tarrach, Thorsten},
location = {St. Petersburg, Russia},
pages = {951 -- 967},
publisher = {Springer},
title = {{Efficient synthesis for concurrency by semantics-preserving transformations}},
doi = {10.1007/978-3-642-39799-8_68},
volume = {8044},
year = {2013},
}
@article{2247,
abstract = {Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise.},
author = {Zagorsky, Benjamin and Reiter, Johannes and Chatterjee, Krishnendu and Nowak, Martin},
journal = {PLoS One},
number = {12},
publisher = {Public Library of Science},
title = {{Forgiver triumphs in alternating prisoner's dilemma }},
doi = {10.1371/journal.pone.0080814},
volume = {8},
year = {2013},
}
@misc{9749,
abstract = {Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise.},
author = {Zagorsky, Benjamin and Reiter, Johannes and Chatterjee, Krishnendu and Nowak, Martin},
publisher = {Public Library of Science},
title = {{Forgiver triumphs in alternating prisoner's dilemma }},
doi = {10.1371/journal.pone.0080814.s001},
year = {2013},
}
@article{2284,
abstract = {Background: The brood of ants and other social insects is highly susceptible to pathogens, particularly those that penetrate the soft larval and pupal cuticle. We here test whether the presence of a pupal cocoon, which occurs in some ant species but not in others, affects the sanitary brood care and fungal infection patterns after exposure to the entomopathogenic fungus Metarhizium brunneum. We use a) a comparative approach analysing four species with either naked or cocooned pupae and b) a within-species analysis of a single ant species, in which both pupal types co-exist in the same colony. Results: We found that the presence of a cocoon did not compromise fungal pathogen detection by the ants and that species with cocooned pupae increased brood grooming after pathogen exposure. All tested ant species further removed brood from their nests, which was predominantly expressed towards larvae and naked pupae treated with the live fungal pathogen. In contrast, cocooned pupae exposed to live fungus were not removed at higher rates than cocooned pupae exposed to dead fungus or a sham control. Consistent with this, exposure to the live fungus caused high numbers of infections and fungal outgrowth in larvae and naked pupae, but not in cocooned pupae. Moreover, the ants consistently removed the brood prior to fungal outgrowth, ensuring a clean brood chamber. Conclusion: Our study suggests that the pupal cocoon has a protective effect against fungal infection, causing an adaptive change in sanitary behaviours by the ants. It further demonstrates that brood removal-originally described for honeybees as "hygienic behaviour"-is a widespread sanitary behaviour in ants, which likely has important implications on disease dynamics in social insect colonies.},
author = {Tragust, Simon and Ugelvig, Line V and Chapuisat, Michel and Heinze, Jürgen and Cremer, Sylvia},
journal = {BMC Evolutionary Biology},
number = {1},
publisher = {BioMed Central},
title = {{Pupal cocoons affect sanitary brood care and limit fungal infections in ant colonies}},
doi = {10.1186/1471-2148-13-225},
volume = {13},
year = {2013},
}
@article{2277,
abstract = {Redundancies and correlations in the responses of sensory neurons may seem to waste neural resources, but they can also carry cues about structured stimuli and may help the brain to correct for response errors. To investigate the effect of stimulus structure on redundancy in retina, we measured simultaneous responses from populations of retinal ganglion cells presented with natural and artificial stimuli that varied greatly in correlation structure; these stimuli and recordings are publicly available online. Responding to spatio-temporally structured stimuli such as natural movies, pairs of ganglion cells were modestly more correlated than in response to white noise checkerboards, but they were much less correlated than predicted by a non-adapting functional model of retinal response. Meanwhile, responding to stimuli with purely spatial correlations, pairs of ganglion cells showed increased correlations consistent with a static, non-adapting receptive field and nonlinearity. We found that in response to spatio-temporally correlated stimuli, ganglion cells had faster temporal kernels and tended to have stronger surrounds. These properties of individual cells, along with gain changes that opposed changes in effective contrast at the ganglion cell input, largely explained the pattern of pairwise correlations across stimuli where receptive field measurements were possible.},
author = {Simmons, Kristina and Prentice, Jason and Tkacik, Gasper and Homann, Jan and Yee, Heather and Palmer, Stephanie and Nelson, Philip and Balasubramanian, Vijay},
journal = {PLoS Computational Biology},
number = {12},
publisher = {Public Library of Science},
title = {{Transformation of stimulus correlations by the retina}},
doi = {10.1371/journal.pcbi.1003344},
volume = {9},
year = {2013},
}
@article{2853,
abstract = {High relatedness among interacting individuals has generally been considered a precondition for the evolution of altruism. However, kin-selection theory also predicts the evolution of altruism when relatedness is low, as long as the cost of the altruistic act is minor compared with its benefit. Here, we demonstrate evidence for a low-cost altruistic act in bacteria. We investigated Escherichia coli responding to the attack of an obligately lytic phage by committing suicide in order to prevent parasite transmission to nearby relatives. We found that bacterial suicide provides large benefits to survivors at marginal costs to committers. The cost of suicide was low, because infected cells are moribund, rapidly dying upon phage infection, such that no more opportunity for reproduction remains. As a consequence of its marginal cost, host suicide was selectively favoured even when relatedness between committers and survivors approached zero. Altogether, our findings demonstrate that low-cost suicide can evolve with ease, represents an effective host-defence strategy, and seems to be widespread among microbes. Moreover, low-cost suicide might also occur in higher organisms as exemplified by infected social insect workers leaving the colony to die in isolation.},
author = {Refardt, Dominik and Bergmiller, Tobias and Kümmerli, Rolf},
journal = {Proceedings of the Royal Society of London Series B Biological Sciences},
number = {1759},
publisher = {Royal Society, The},
title = {{Altruism can evolve when relatedness is low: Evidence from bacteria committing suicide upon phage infection}},
doi = {10.1098/rspb.2012.3035},
volume = {280},
year = {2013},
}
@misc{9751,
abstract = {High relatedness among interacting individuals has generally been considered a precondition for the evolution of altruism. However, kin-selection theory also predicts the evolution of altruism when relatedness is low, as long as the cost of the altruistic act is minor compared to its benefit. Here, we demonstrate evidence for a low-cost altruistic act in bacteria. We investigated Escherichia coli responding to the attack of an obligately lytic phage by committing suicide in order to prevent parasite transmission to nearby relatives. We found that bacterial suicide provides large benefits to survivors at marginal costs to committers. The cost of suicide was low because infected cells are moribund, rapidly dying upon phage infection, such that no more opportunity for reproduction remains. As a consequence of its marginal cost, host suicide was selectively favoured even when relatedness between committers and survivors approached zero. Altogether, our findings demonstrate that low-cost suicide can evolve with ease, represents an effective host-defence strategy, and seems to be widespread among microbes. Moreover, low-cost suicide might also occur in higher organisms as exemplified by infected social insect workers leaving the colony to die in isolation.},
author = {Refardt, Dominik and Bergmiller, Tobias and Kümmerli, Rolf},
publisher = {Dryad},
title = {{Data from: Altruism can evolve when relatedness is low: evidence from bacteria committing suicide upon phage infection}},
doi = {10.5061/dryad.b1q2n},
year = {2013},
}
@misc{9754,
abstract = {Short-read sequencing technologies have in principle made it feasible to draw detailed inferences about the recent history of any organism. In practice, however, this remains challenging due to the difficulty of genome assembly in most organisms and the lack of statistical methods powerful enough to discriminate among recent, non-equilibrium histories. We address both the assembly and inference challenges. We develop a bioinformatic pipeline for generating outgroup-rooted alignments of orthologous sequence blocks from de novo low-coverage short-read data for a small number of genomes, and show how such sequence blocks can be used to fit explicit models of population divergence and admixture in a likelihood framework. To illustrate our approach, we reconstruct the Pleistocene history of an oak-feeding insect (the oak gallwasp Biorhiza pallida) which, in common with many other taxa, was restricted during Pleistocene ice ages to a longitudinal series of southern refugia spanning theWestern Palaearctic. Our analysis of sequence blocks sampled from a single genome from each of three major glacial refugia reveals support for an unexpected history dominated by recent admixture. Despite the fact that 80% of the genome is affected by admixture during the last glacial cycle, we are able to infer the deeper divergence history of these populations. These inferences are robust to variation in block length, mutation model, and the sampling location of individual genomes within refugia. This combination of de novo assembly and numerical likelihood calculation provides a powerful framework for estimating recent population history that can be applied to any organism without the need for prior genetic resources.},
author = {Hearn, Jack and Stone, Graham and Barton, Nicholas H and Lohse, Konrad and Bunnefeld, Lynsey},
publisher = {Dryad},
title = {{Data from: Likelihood-based inference of population history from low coverage de novo genome assemblies}},
doi = {10.5061/dryad.r3r60},
year = {2013},
}
@article{2926,
abstract = {To fight infectious diseases, host immune defenses are employed at multiple levels. Sanitary behavior, such as pathogen avoidance and removal, acts as a first line of defense to prevent infection [1] before activation of the physiological immune system. Insect societies have evolved a wide range of collective hygiene measures and intensive health care toward pathogen-exposed group members [2]. One of the most common behaviors is allogrooming, in which nestmates remove infectious particles from the body surfaces of exposed individuals [3]. Here we show that, in invasive garden ants, grooming of fungus-exposed brood is effective beyond the sheer mechanical removal of fungal conidiospores; it also includes chemical disinfection through the application of poison produced by the ants themselves. Formic acid is the main active component of the poison. It inhibits fungal growth of conidiospores remaining on the brood surface after grooming and also those collected in the mouth of the grooming ant. This dual function is achieved by uptake of the poison droplet into the mouth through acidopore self-grooming and subsequent application onto the infectious brood via brood grooming. This extraordinary behavior extends the current understanding of grooming and the establishment of social immunity in insect societies.},
author = {Tragust, Simon and Mitteregger, Barbara and Barone, Vanessa and Konrad, Matthias and Ugelvig, Line V and Cremer, Sylvia},
journal = {Current Biology},
number = {1},
pages = {76 -- 82},
publisher = {Cell Press},
title = {{Ants disinfect fungus-exposed brood by oral uptake and spread of their poison}},
doi = {10.1016/j.cub.2012.11.034},
volume = {23},
year = {2013},
}
@article{2944,
abstract = {We propose a two-step procedure for estimating multiple migration rates in an approximate Bayesian computation (ABC) framework, accounting for global nuisance parameters. The approach is not limited to migration, but generally of interest for inference problems with multiple parameters and a modular structure (e.g. independent sets of demes or loci). We condition on a known, but complex demographic model of a spatially subdivided population, motivated by the reintroduction of Alpine ibex (Capra ibex) into Switzerland. In the first step, the global parameters ancestral mutation rate and male mating skew have been estimated for the whole population in Aeschbacher et al. (Genetics 2012; 192: 1027). In the second step, we estimate in this study the migration rates independently for clusters of demes putatively connected by migration. For large clusters (many migration rates), ABC faces the problem of too many summary statistics. We therefore assess by simulation if estimation per pair of demes is a valid alternative. We find that the trade-off between reduced dimensionality for the pairwise estimation on the one hand and lower accuracy due to the assumption of pairwise independence on the other depends on the number of migration rates to be inferred: the accuracy of the pairwise approach increases with the number of parameters, relative to the joint estimation approach. To distinguish between low and zero migration, we perform ABC-type model comparison between a model with migration and one without. Applying the approach to microsatellite data from Alpine ibex, we find no evidence for substantial gene flow via migration, except for one pair of demes in one direction.},
author = {Aeschbacher, Simon and Futschik, Andreas and Beaumont, Mark},
journal = {Molecular Ecology},
number = {4},
pages = {987 -- 1002},
publisher = {Wiley-Blackwell},
title = {{Approximate Bayesian computation for modular inference problems with many parameters: the example of migration rates. }},
doi = {10.1111/mec.12165},
volume = {22},
year = {2013},
}
@article{2263,
abstract = {Nestin-cre transgenic mice have been widely used to direct recombination to neural stem cells (NSCs) and intermediate neural progenitor cells (NPCs). Here we report that a readily utilized, and the only commercially available, Nestin-cre line is insufficient for directing recombination in early embryonic NSCs and NPCs. Analysis of recombination efficiency in multiple cre-dependent reporters and a genetic mosaic line revealed consistent temporal and spatial patterns of recombination in NSCs and NPCs. For comparison we utilized a knock-in Emx1cre line and found robust recombination in NSCs and NPCs in ventricular and subventricular zones of the cerebral cortices as early as embryonic day 12.5. In addition we found that the rate of Nestin-cre driven recombination only reaches sufficiently high levels in NSCs and NPCs during late embryonic and early postnatal periods. These findings are important when commercially available cre lines are considered for directing recombination to embryonic NSCs and NPCs.},
author = {Liang, Huixuan and Hippenmeyer, Simon and Ghashghaei, H.},
journal = {Biology open},
number = {12},
pages = {1200 -- 1203},
publisher = {The Company of Biologists},
title = {{A Nestin-cre transgenic mouse is insufficient for recombination in early embryonic neural progenitors}},
doi = {10.1242/bio.20122287},
volume = {1},
year = {2012},
}
@article{2302,
abstract = {We introduce propagation models (PMs), a formalism able to express several kinds of equations that describe the behavior of biochemical reaction networks. Furthermore, we introduce the propagation abstract data type (PADT), which separates concerns regarding different numerical algorithms for the transient analysis of biochemical reaction networks from concerns regarding their implementation, thus allowing for portable and efficient solutions. The state of a propagation abstract data type is given by a vector that assigns mass values to a set of nodes, and its (next) operator propagates mass values through this set of nodes. We propose an approximate implementation of the (next) operator, based on threshold abstraction, which propagates only "significant" mass values and thus achieves a compromise between efficiency and accuracy. Finally, we give three use cases for propagation models: the chemical master equation (CME), the reaction rate equation (RRE), and a hybrid method that combines these two equations. These three applications use propagation models in order to propagate probabilities and/or expected values and variances of the model's variables.},
author = {Henzinger, Thomas A and Mateescu, Maria},
journal = {IEEE ACM Transactions on Computational Biology and Bioinformatics},
number = {2},
pages = {310 -- 322},
publisher = {IEEE},
title = {{The propagation approach for computing biochemical reaction networks}},
doi = {10.1109/TCBB.2012.91},
volume = {10},
year = {2012},
}
@article{2318,
abstract = {We show that bosons interacting via pair potentials with negative scattering length form bound states for a suitable number of particles. In other words, the absence of many-particle bound states of any kind implies the non-negativity of the scattering length of the interaction potential. },
author = {Seiringer, Robert},
journal = {Journal of Spectral Theory},
number = {3},
pages = {321--328},
publisher = {European Mathematical Society},
title = {{Absence of bound states implies non-negativity of the scattering length}},
doi = {10.4171/JST/31},
volume = {2},
year = {2012},
}
@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},
}
@inproceedings{2715,
abstract = {We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning vertices from where the objective can be ensured with probability 1. We study for the first time the average case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average case running time is linear (as compared to the worst case linear number of iterations and quadratic time complexity). Second, for the average case analysis over all MDPs we show that the expected number of iterations is constant and the average case running time is linear (again as compared to the worst case linear number of iterations and quadratic time complexity). Finally we also show that given that all MDPs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small.},
author = {Chatterjee, Krishnendu and Joglekar, Manas and Shah, Nisarg},
location = {Hyderabad, India},
pages = {461 -- 473},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives}},
doi = {10.4230/LIPIcs.FSTTCS.2012.461},
volume = {18},
year = {2012},
}
@inproceedings{2825,
abstract = {We study the problem of maximum marginal prediction (MMP) in probabilistic graphical models, a task that occurs, for example, as the Bayes optimal decision rule under a Hamming loss. MMP is typically performed as a two-stage procedure: one estimates each variable's marginal probability and then forms a prediction from the states of maximal probability. In this work we propose a simple yet effective technique for accelerating MMP when inference is sampling-based: instead of the above two-stage procedure we directly estimate the posterior probability of each decision variable. This allows us to identify the point of time when we are sufficiently certain about any individual decision. Whenever this is the case, we dynamically prune the variables we are confident about from the underlying factor graph. Consequently, at any time only samples of variables whose decision is still uncertain need to be created. Experiments in two prototypical scenarios, multi-label classification and image inpainting, show that adaptive sampling can drastically accelerate MMP without sacrificing prediction accuracy.},
author = {Lampert, Christoph},
location = {Lake Tahoe, NV, United States},
pages = {82 -- 90},
publisher = {Neural Information Processing Systems},
title = {{Dynamic pruning of factor graphs for maximum marginal prediction}},
volume = {1},
year = {2012},
}
@article{2848,
abstract = {We study evolutionary game theory in a setting where individuals learn from each other. We extend the traditional approach by assuming that a population contains individuals with different learning abilities. In particular, we explore the situation where individuals have different search spaces, when attempting to learn the strategies of others. The search space of an individual specifies the set of strategies learnable by that individual. The search space is genetically given and does not change under social evolutionary dynamics. We introduce a general framework and study a specific example in the context of direct reciprocity. For this example, we obtain the counter intuitive result that cooperation can only evolve for intermediate benefit-to-cost ratios, while small and large benefit-to-cost ratios favor defection. Our paper is a step toward making a connection between computational learning theory and evolutionary game dynamics.},
author = {Chatterjee, Krishnendu and Zufferey, Damien and Nowak, Martin},
journal = {Journal of Theoretical Biology},
pages = {161 -- 173},
publisher = {Elsevier},
title = {{Evolutionary game dynamics in populations with different learners}},
doi = {10.1016/j.jtbi.2012.02.021},
volume = {301},
year = {2012},
}
@article{2849,
author = {Edelsbrunner, Herbert and Strelkova, Nataliya},
journal = {Russian Mathematical Surveys},
number = {6},
pages = {1167 -- 1168},
publisher = {IOP Publishing Ltd.},
title = {{On the configuration space of Steiner minimal trees}},
doi = {10.1070/RM2012v067n06ABEH004820},
volume = {67},
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},
}
@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},
}
@article{2902,
abstract = {We present an algorithm for simplifying linear cartographic objects and results obtained with a computer program implementing this algorithm. },
author = {Edelsbrunner, Herbert and Musin, Oleg and Ukhalov, Alexey and Yakimova, Olga and Alexeev, Vladislav and Bogaevskaya, Victoriya and Gorohov, Andrey and Preobrazhenskaya, Margarita},
journal = {Modeling and Analysis of Information Systems},
number = {6},
pages = {152 -- 160},
publisher = {Technische Universität Darmstadt},
title = {{Fractal and computational geometry for generalizing cartographic objects}},
volume = {19},
year = {2012},
}
@inproceedings{2903,
abstract = {In order to enjoy a digital version of the Jordan Curve Theorem, it is common to use the closed topology for the foreground and the open topology for the background of a 2-dimensional binary image. In this paper, we introduce a single topology that enjoys this theorem for all thresholds decomposing a real-valued image into foreground and background. This topology is easy to construct and it generalizes to n-dimensional images.},
author = {Edelsbrunner, Herbert and Symonova, Olga},
location = {New Brunswick, NJ, USA },
pages = {41 -- 48},
publisher = {IEEE},
title = {{The adaptive topology of a digital image}},
doi = {10.1109/ISVD.2012.11},
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},
issn = {2118-8572},
journal = {Journal de Theorie des Nombres des Bordeaux},
number = {3},
pages = {729 -- 749},
publisher = {Universite de Bordeaux},
title = {{Weak multipliers for generalized van der Corput sequences}},
doi = {10.5802/jtnb.819},
volume = {24},
year = {2012},
}
@article{2912,
author = {Edelsbrunner, Herbert and Strelkova, Nataliya},
journal = { Uspekhi Mat. Nauk},
number = {6},
pages = {203 -- 204},
publisher = {Moscow Mathematical Society },
title = {{Configuration space for shortest networks }},
doi = {10.4213/rm9503},
volume = {67},
year = {2012},
}
@inproceedings{2915,
author = {Kroemer, Oliver and Lampert, Christoph and Peters, Jan},
publisher = {Deutsches Zentrum für Luft und Raumfahrt},
title = {{Multi-modal learning for dynamic tactile sensing}},
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},
}
@article{2917,
abstract = {The search for extra-terrestrial intelligence (SETI) has been performed principally as a one-way survey, listening of radio frequencies across the Milky Way and other galaxies. However, scientists have engaged in an active messaging only rarely. This suggests the simple rationale that if other civilizations exist and take a similar approach to ours, namely listening but not broadcasting, the result is a silent universe. A simple game theoretical model, the prisoner's dilemma, explains this situation: each player (civilization) can passively search (defect), or actively search and broadcast (cooperate). In order to maximize the payoff (or, equivalently, minimize the risks) the best strategy is not to broadcast. In fact, the active search has been opposed on the basis that it might be dangerous to expose ourselves. However, most of these ideas have not been based on objective arguments, and ignore accounting of the possible gains and losses. Thus, the question stands: should we perform an active search? I develop a game-theoretical framework where civilizations can be of different types, and explicitly apply it to a situation where societies are either interested in establishing a two-way communication or belligerent and in urge to exploit ours. The framework gives a quantitative solution (a mixed-strategy), which is how frequent we should perform the active SETI. This frequency is roughly proportional to the inverse of the risk, and can be extremely small. However, given the immense amount of stars being scanned, it supports active SETI. The model is compared with simulations, and the possible actions are evaluated through the San Marino scale, measuring the risks of messaging.},
author = {Vladar, Harold},
journal = {International Journal of Astrobiology},
number = {1},
pages = {53 -- 62},
publisher = {Cambridge University Press},
title = {{The game of active search for extra terrestrial intelligence Breaking the Great Silence }},
doi = {10.1017/S1473550412000407},
volume = {12},
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},
pages = {16},
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},
}