TY - CONF
AB - The Feistel-network is a popular structure underlying many block-ciphers where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key.
Luby and Rackoff showed that the three-round Feistel-network – each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (CPA) – is a CPA secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers.
But the round functions used in actual block-ciphers are – for efficiency reasons – far from being pseudorandom. We investigate the security of the Feistel-network against CPA distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (nCPA). We show that in the information-theoretic setting, four rounds with nCPA secure round functions are sufficient (and necessary) to get a CPA secure permutation. Unfortunately, this result does not translate into the more interesting pseudorandom setting. In fact, under the so-called Inverse Decisional Diffie-Hellman assumption the Feistel-network with four rounds, each instantiated with a nCPA secure pseudorandom function, is in general not a CPA secure pseudorandom permutation.
AU - Maurer, Ueli M
AU - Oswald, Yvonne A
AU - Krzysztof Pietrzak
AU - Sjödin, Johan
ID - 3214
TI - Luby Rackoff ciphers from weak round functions
VL - 4004
ER -
TY - CONF
AB - Most cryptographic primitives such as encryption, authentication or secret sharing require randomness. Usually one assumes that perfect randomness is available, but those primitives might also be realized under weaker assumptions. In this work we continue the study of building secure cryptographic primitives from imperfect random sources initiated by Dodis and Spencer (FOCS’02). Their main result shows that there exists a (high-entropy) source of randomness allowing for perfect encryption of a bit, and yet from which one cannot extract even a single weakly random bit, separating encryption from extraction. Our main result separates encryption from 2-out-2 secret sharing (both in the information-theoretic and in the computational settings): any source which can be used to achieve one-bit encryption also can be used for 2-out-2 secret sharing of one bit, but the converse is false, even for high-entropy sources. Therefore, possibility of extraction strictly implies encryption, which in turn strictly implies 2-out-2 secret sharing.
AU - Dodis, Yevgeniy
AU - Krzysztof Pietrzak
AU - Przydatek, Bartosz
ID - 3215
TI - Separating sources for encryption and secret sharing
VL - 3876
ER -
TY - CONF
AB - We prove a new upper bound on the advantage of any adversary for distinguishing the encrypted CBC-MAC (EMAC) based on random permutations from a random function. Our proof uses techniques recently introduced in [BPR05], which again were inspired by [DGH + 04].
The bound we prove is tight — in the sense that it matches the advantage of known attacks up to a constant factor — for a wide range of the parameters: let n denote the block-size, q the number of queries the adversary is allowed to make and ℓ an upper bound on the length (i.e. number of blocks) of the messages, then for ℓ ≤ 2 n/8 and q≥ł2 the advantage is in the order of q 2/2 n (and in particular independent of ℓ). This improves on the previous bound of q 2ℓΘ(1/ln ln ℓ)/2 n from [BPR05] and matches the trivial attack (which thus is basically optimal) where one simply asks random queries until a collision is found.
AU - Krzysztof Pietrzak
ID - 3216
TI - A tight bound for EMAC
VL - 4052
ER -
TY - CONF
AB - To prove that a secure key-agreement protocol exists one must at least show P ≠NP. Moreover any proof that the sequential composition of two non-adaptively secure pseudorandom functions is secure against at least two adaptive queries must falsify the decisional Diffie-Hellman assumption, a standard assumption from public-key cryptography. Hence proving any of this two seemingly unrelated statements would require a significant breakthrough. We show that at least one of the two statements is true.
To our knowledge this gives the first positive cryptographic result (namely that composition implies some weak adaptive security) which holds in Minicrypt, but not in Cryptomania, i.e. under the assumption that one-way functions exist, but public-key cryptography does not.
AU - Krzysztof Pietrzak
ID - 3217
TI - Composition implies adaptive security in minicrypt
VL - 4004
ER -
TY - CHAP
AU - Harald Janovjak
AU - Sawhney, Ravi K
AU - Stark, Martin
AU - Mueller, Daniel J
ID - 3404
T2 - Techniques in Microscopy for Biomedical Applications
TI - Atomic force microscopy
VL - 2
ER -
TY - JOUR
AB - Despite their crucial importance for cellular function, little is known about the folding mechanisms of membrane proteins. Recently details of the folding energy landscape were elucidated by atomic force microscope (AFM)-based single molecule force spectroscopy. Upon unfolding and extraction of individual membrane proteins energy barriers in structural elements such as loops and helices were mapped and quantified with the precision of a few amino acids.
Here we report on the next logical step: controlled refolding of single proteins into the membrane. First individual bacteriorhodopsin monomers were partially unfolded and extracted from the purple membrane by pulling at the C-terminal end with an AFM tip. Then by gradually lowering the tip, the protein was allowed to refold into the membrane while the folding force was recorded.
We discovered that upon refolding certain helices are pulled into the membraneagainst a sizable externalforce of several tens of picoNewton. From the mechanical work, which the helix performs on the AFM cantilever, we derive an upper limit for the Gibbs free folding energy. Subsequent unfolding allowed us to analyze the pattern of unfolding barriers and corroborate that the protein had refolded into the native state.
AU - Kessler, Max
AU - Gottschalk, Kay E
AU - Harald Janovjak
AU - Mueller, Daniel J
AU - Gaub, Hermann
ID - 3413
IS - 2
JF - Journal of Molecular Biology
TI - Bacteriorhodopsin folds into the membrane against an external force
VL - 357
ER -
TY - JOUR
AB - Mechanisms of folding and misfolding of membrane proteins are of interest in cell biology. Recently, we have established single-molecule force spectroscopy to observe directly the stepwise folding of the Na+/H+antiporter NhaA from Escherichia coli in vitro. Here, we improved this approach significantly to track the folding intermediates of asingle NhaA polypeptide forming structural segments such as the Na+-binding site, transmembrane α-helices, and helical pairs. The folding rates of structural segments ranged from 0.31 s−1 to 47 s−1, providing detailed insight into a distinct folding hierarchy of an unfolded polypeptide into the native membrane protein structure. In some cases, however, the folding chain formed stable and kinetically trapped non-native structures, which could be assigned to misfolding events of the antiporter.
AU - Kedrov, Alexej
AU - Harald Janovjak
AU - Ziegler, Christine
AU - Kühlbrandt, Werner
AU - Mueller, Daniel J
ID - 3414
IS - 1
JF - Journal of Molecular Biology
TI - Observing folding pathways and kinetics of a single sodium-proton antiporter from Escherichia coli
VL - 355
ER -
TY - GEN
AU - Harald Janovjak
AU - Kedrov, Alexej
AU - Cisneros, David
AU - Sapra, Tanuj K
AU - Struckmeier, Jens
AU - Mueller, Daniel J
ID - 3415
T2 - Neurobiology of Aging
TI - Imaging and detecting molecular interactions of single membrane proteins
VL - 27
ER -
TY - GEN
AB - Ising models with pairwise interactions are the least structured, or maximum-entropy, probability distributions that exactly reproduce measured pairwise correlations between spins. Here we use this equivalence to construct Ising models that describe the correlated spiking activity of populations of 40 neurons in the retina, and show that pairwise interactions account for observed higher-order correlations. By first finding a representative ensemble for observed networks we can create synthetic networks of 120 neurons, and find that with increasing size the networks operate closer to a critical point and start exhibiting collective behaviors reminiscent of spin glasses.
AU - Gasper Tkacik
AU - Schneidman, E.
AU - Berry, M. J.
AU - Bialek, William S
ID - 3431
T2 - ArXiv
TI - Ising models for networks of real neurons
ER -
TY - JOUR
AB - The mutational landscape model is a theoretical model describing sequence evolution in natural populations. However, recent experimental work has begun to test its predictions in laboratory populations of microbes. Several of these studies have focused on testing the prediction that the effects of beneficial mutations should be roughly exponentially distributed. The prediction appears to be borne out by most of these studies, at least qualitatively. Another study showed that a modified version of the model was able to predict, with reasonable accuracy, which of a ranked set of beneficial alleles will be fixed next. Although it remains to be seen whether the mutational landscape model adequately describes adaptation in organisms other than microbes, together these studies suggest that adaptive evolution has surprisingly general properties that can be successfully captured by theoretical models.
AU - Betancourt, Andrea J
AU - Jonathan Bollback
ID - 3437
IS - 6
JF - Current Opinion in Genetics & Development
TI - Fitness effects of beneficial mutations: the mutational landscape model in experimental evolution
VL - 16
ER -
TY - CONF
AB - We argue that games are expressive enough to encompass (history-based) access control, (resource) usage control (e.g., dynamic adaptive access control of reputation systems), accountability based controls (e.g., insurance), controls derived from rationality assumptions on participants (e.g., network mechanisms), and their composition. Building on the extensive research into games, we demonstrate that this expressive power coexists with a formal analysis framework comparable to that available for access control.
AU - Krishnendu Chatterjee
AU - Jagadeesan, Rhada
AU - Pitcher, Corin
ID - 3449
TI - Games for controls
ER -
TY - GEN
AB - It is widely accepted that the hippocampus plays a major role in learning and memory. The mossy fiber synapse between granule cells in the dentate gyrus and pyramidal neurons in the CA3 region is a key component of the hippocampal trisynaptic circuit. Recent work, partially based on direct presynaptic patch-clamp recordings from hippocampal mossy fiber boutons, sheds light on the mechanisms of synaptic transmission and plasticity at mossy fiber synapses. A high Na(+) channel density in mossy fiber boutons leads to a large amplitude of the presynaptic action potential. Together with the fast gating of presynaptic Ca(2+) channels, this generates a large and brief presynaptic Ca(2+) influx, which can trigger transmitter release with high efficiency and temporal precision. The large number of release sites, the large size of the releasable pool of vesicles, and the huge extent of presynaptic plasticity confer unique strength to this synapse, suggesting a large impact onto the CA3 pyramidal cell network under specific behavioral conditions. The characteristic properties of the hippocampal mossy fiber synapse may be important for pattern separation and information storage in the dentate gyrus-CA3 cell network.
AU - Bischofberger, Joseph
AU - Engel, Dominique
AU - Frotscher, Michael
AU - Peter Jonas
ID - 3463
IS - 3
T2 - Pflugers Archiv : European Journal of Physiology
TI - Timing and efficacy of transmitter release at mossy fiber synapses in the hippocampal network. (Review)
VL - 453
ER -
TY - CONF
AB - We study infinite stochastic games played by n-players on a finite graph with goals specified by sets of infinite traces. The games are concurrent (each player simultaneously and independently chooses an action at each round), stochastic (the next state is determined by a probability distribution depending on the current state and the chosen actions), infinite (the game continues for an infinite number of rounds), nonzero-sum (the players’ goals are not necessarily conflicting), and undiscounted. We show that if each player has an upward-closed objective, then there exists an ε-Nash equilibrium in memoryless strategies, for every ε>0; and exact Nash equilibria need not exist. Upward-closure of an objective means that if a set Z of infinitely repeating states is winning, then all supersets of Z of infinitely repeating states are also winning. Memoryless strategies are strategies that are independent of history of plays and depend only on the current state. We also study the complexity of finding values (payoff profile) of an ε-Nash equilibrium. We show that the values of an ε-Nash equilibrium in nonzero-sum concurrent games with upward-closed objectives for all players can be computed by computing ε-Nash equilibrium values of nonzero-sum concurrent games with reachability objectives for all players and a polynomial procedure. As a consequence we establish that values of an ε-Nash equilibrium can be computed in TFNP (total functional NP), and hence in EXPTIME.
AU - Krishnendu Chatterjee
ID - 3499
TI - Nash equilibrium for upward-closed objectives
VL - 4207
ER -
TY - CONF
AB - The classical algorithm for solving Bu ̈chi games requires time O(n · m) for game graphs with n states and m edges. For game graphs with constant outdegree, the best known algorithm has running time O(n2/logn). We present two new algorithms for Bu ̈chi games. First, we give an algorithm that performs at most O(m) more work than the classical algorithm, but runs in time O(n) on infinitely many graphs of constant outdegree on which the classical algorithm requires time O(n2). Second, we give an algorithm with running time O(n · m · log δ(n)/ log n), where 1 ≤ δ(n) ≤ n is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if δ(n) = O(log n).
AU - Krishnendu Chatterjee
AU - Thomas Henzinger
AU - Piterman, Nir
ID - 3500
TI - Algorithms for Büchi Games
ER -
TY - GEN
AB - Embodiments automatically generate an accurate network of watertight NURBS patches from polygonal models of objects while automatically detecting and preserving character lines thereon. These embodiments generate from an initial triangulation of the surface, a hierarchy of progressively coarser triangulations of the surface by performing a sequence of edge contractions using a greedy algorithm that selects edge contractions by their numerical properties. Operations are also performed to connect the triangulations in the hierarchy using homeomorphisms that preserve the topology of the initial triangulation in the coarsest triangulation. A desired quadrangulation of the surface can then be generated by homeomorphically mapping edges of a coarsest triangulation in the hierarchy back to the initial triangulation. This quadrangulation is topologically consistent with the initial triangulation and is defined by a plurality of quadrangular patches. These quadrangular patches are linked together by a (U, V) mesh that is guaranteed to be continuous at patch boundaries. A grid is then preferably fit to each of the quadrangles in the resulting quadrangulation by decomposing each of the quadrangles into k.sup.2 smaller quadrangles. A watertight NURBS model may be generated from the resulting quadrangulation.
AU - Herbert Edelsbrunner
AU - Fu, Ping
AU - Nekhayev, Dmitry V
AU - Facello, Michael
AU - Williams, Steven P
ID - 3510
TI - Method, apparatus and computer program products for automatically generating NURBS models of triangulated surfaces using homeomorphism
ER -
TY - GEN
AB - Methods, apparatus and computer program products provide efficient techniques for designing and printing shells of hearing-aid devices with a high degree of quality assurance and reliability and with a reduced number of manual and time consuming production steps and operations. These techniques also preferably provide hearing-aid shells having internal volumes that can approach a maximum allowable ratio of internal volume relative to external volume. These high internal volumes facilitate the inclusion of hearing-aid electrical components having higher degrees of functionality and/or the use of smaller and less conspicuous hearing-aid shells. A preferred method includes operations to generate a watertight digital model of a hearing-aid shell by thickening a three-dimensional digital model of a shell surface in a manner that eliminates self-intersections and results in a thickened model having an internal volume that is a high percentage of an external volume of the model.
AU - Fu, Ping
AU - Nekhayev, Dmitry V
AU - Herbert Edelsbrunner
ID - 3511
TI - Manufacturing methods and systems for rapid production of hearing-aid shells
ER -
TY - GEN
AB - Methods, apparatus and computer program products provide efficient techniques for reconstructing surfaces from data point sets. These techniques include reconstructing surfaces from sets of scanned data points that have preferably undergone preprocessing operations to improve their quality by, for example, reducing noise and removing outliers. These techniques include reconstructing a dense and locally two-dimensionally distributed 3D point set (e.g., point cloud) by merging stars in two-dimensional weighted Delaunay triangulations within estimated tangent planes. The techniques include determining a plurality of stars from a plurality of points p.sub.i in a 3D point set S that at least partially describes the 3D surface, by projecting the plurality of points p.sub.i onto planes T.sub.i that are each estimated to be tangent about a respective one of the plurality of points p.sub.i. The plurality of stars are then merged into a digital model of the 3D surface.
AU - Fletcher, Yates G
AU - Gloth, Tobias
AU - Herbert Edelsbrunner
AU - Fu, Ping
ID - 3512
TI - Method, apparatus and computer products that reconstruct surfaces from data points
ER -
TY - JOUR
AB - We observed sharp wave/ripples (SWR) during exploration within brief (< 2.4 s) interruptions of or during theta oscillations. CA1 network responses of SWRs occurring during exploration (eSWR) and SWRs detected in waking immobility or sleep were similar. However, neuronal activity during eSWR was location dependent, and eSWR-related firing was stronger inside the place field than outside. The eSPW-related firing increase was stronger than the baseline increase inside compared to outside, suggesting a “supralinear” summation of eSWR and place-selective inputs. Pairs of cells with similar place fields and/or correlated firing during exploration showed stronger coactivation during eSWRs and subsequent sleep-SWRs. Sequential activation of place cells was not required for the reactivation of waking co-firing patterns; cell pairs with symmetrical cross-correlations still showed reactivated waking co-firing patterns during sleep-SWRs. We suggest that place-selective firing during eSWRs facilitates initial associations between cells with similar place fields that enable place-related ensemble patterns to recur during subsequent sleep-SWRs.
AU - Joseph O'Neill
AU - Senior,Timothy
AU - Jozsef Csicsvari
ID - 3522
IS - 1
JF - Neuron
TI - Place-selective firing of CA1 pyramidal cells during sharp wave/ripple network patterns in exploratory behavior
VL - 49
ER -
TY - JOUR
AB - The functional organization of the basal ganglia ( BG) is often defined according to one of two opposing schemes. The first proposes multiple, essentially independent channels of information processing. The second posits convergence and lateral integration of striatal channels at the level of the globus pallidus ( GP). We tested the hypothesis that these proposed aspects of functional connectivity within the striatopallidal axis are dynamic and related to brain state. Local field potentials ( LFPs) were simultaneously recorded from multiple sites in striatum and GP in anesthetized rats during slow-wave activity( SWA) and during global activation evoked by sensory stimulation. Functional connectivity was inferred from comparative analyses of the internuclear and intranuclear coherence between bipolar derivations of LFPs. During prominent SWA, as shown in the electrocorticogram and local field potentials in the basal ganglia, intranuclear coherence, and, thus, lateral functional connectivity within striatum or globus pallidus was relatively weak. Furthermore, the temporal coupling of LFPs recorded across these two nuclei involved functional convergence at the level of GP. Global activation, indicated by a loss of SWA, was accompanied by a rapid functional reorganization of the striatopallidal axis. Prominent lateral functional connectivity developed within GP and, to a significantly more constrained spatial extent, striatum. Additionally, functional convergence on GP was no longer apparent, despite increased internuclear coherence. These data demonstrate that functional connectivity within the BG is highly dynamic and suggest that the relative expression of organizational principles, such as parallel, independent processing channels, striatopallidal convergence, and lateral integration within BG nuclei, is dependent on brain state.
AU - Magill,Peter J
AU - Pogosyan,Alek
AU - Sharott,Andrew
AU - Jozsef Csicsvari
AU - Bolam, John Paul
AU - Brown,Peter
ID - 3545
IS - 23
JF - Journal of Neuroscience
TI - Changes in functional connectivity within the rat striatopallidal axis during global brain activation in vivo
VL - 26
ER -
TY - CONF
AB - Persistent homology is the mathematical core of recent work on shape, including reconstruction, recognition, and matching. Its per- tinent information is encapsulated by a pairing of the critical values of a function, visualized by points forming a diagram in the plane. The original algorithm in [10] computes the pairs from an ordering of the simplices in a triangulation and takes worst-case time cubic in the number of simplices. The main result of this paper is an algorithm that maintains the pairing in worst-case linear time per transposition in the ordering. A side-effect of the algorithm’s anal- ysis is an elementary proof of the stability of persistence diagrams [7] in the special case of piecewise-linear functions. We use the algorithm to compute 1-parameter families of diagrams which we apply to the study of protein folding trajectories.
AU - Cohen-Steiner, David
AU - Herbert Edelsbrunner
AU - Morozov, Dmitriy
ID - 3559
TI - Vines and vineyards by updating persistence in linear time
ER -
TY - CONF
AB - We continue the study of topological persistence [5] by investigat- ing the problem of simplifying a function f in a way that removes topological noise as determined by its persistence diagram [2]. To state our results, we call a function g an ε-simplification of another function f if ∥f − g∥∞ ≤ ε, and the persistence diagrams of g are the same as those of f except all points within L1-distance at most ε from the diagonal have been removed. We prove that for func- tions f on a 2-manifold such ε-simplification exists, and we give an algorithm to construct them in the piecewise linear case.
AU - Herbert Edelsbrunner
AU - Morozov, Dmitriy
AU - Pascucci, Valerio
ID - 3560
TI - Persistence-sensitive simplification of functions on 2-manifolds
ER -
TY - GEN
AU - Pemberton, Josephine M
AU - Swanson, Graeme M
AU - Nicholas Barton
AU - Livingstone, Suzanne R
AU - Senn, Helen V
ID - 3594
IS - 9
T2 - Deer
TI - Hybridisation between red and sika deer in Scotland
VL - 13
ER -
TY - JOUR
AB - We apply new analytical methods to understand the consequences of population bottlenecks for expected additive genetic variance. We analyze essentially all models for multilocus epistasis that have been numerically simulated to demonstrate increased additive variance. We conclude that for biologically plausible models, large increases in expected additive variance–attributable to epistasis rather than dominance–are unlikely. Naciri-Graven and Goudet (2003) found that as the number of epistatically interacting loci increases, additive variance tends to be inflated more after a bottleneck. We argue that this result reflects biologically unrealistic aspects of their models. Specifically, as the number of loci increases, higher-order epistatic interactions become increasingly important in these models, with an increasing fraction of the genetic variance becoming nonadditive, contrary to empirical observations. As shown by Barton and Turelli (2004), without dominance, conversion of nonadditive to additive variance depends only on the variance components and not on the number of loci per se. Numerical results indicating that more inbreeding is needed to produce maximal release of additive variance with more loci follow directly from our analytical results, which show that high levels of inbreeding (F > 0.5) are needed for significant conversion of higher-order components. We discuss alternative approaches to modeling multilocus epistasis and understanding its consequences.
AU - Turelli, Michael
AU - Nicholas Barton
ID - 3607
IS - 9
JF - Evolution; International Journal of Organic Evolution
TI - Will population bottlenecks and multilocus epistasis increase additive genetic variance?
VL - 60
ER -
TY - JOUR
AB - We study the evolution of inversions that capture locally adapted alleles when two populations are exchanging migrants or hybridizing. By suppressing recombination between the loci, a new inversion can spread. Neither drift nor coadaptation between the alleles (epistasis) is needed, so this local adaptation mechanism may apply to a broader range of genetic and demographic situations than alternative hypotheses that have been widely discussed. The mechanism can explain many features observed in inversion systems. It will drive an inversion to high frequency if there is no countervailing force, which could explain fixed differences observed between populations and species. An inversion can be stabilized at an intermediate frequency if it also happens to capture one or more deleterious recessive mutations, which could explain polymorphisms that are common in some species. This polymorphism can cycle in frequency with the changing selective advantage of the locally favored alleles. The mechanism can establish underdominant inversions that decrease heterokaryotype fitness by several percent if the cause of fitness loss is structural, while if the cause is genic there is no limit to the strength of underdominance that can result. The mechanism is expected to cause loci responsible for adaptive species-specific differences to map to inversions, as seen in recent QTL studies. We discuss data that support the hypothesis, review other mechanisms for inversion evolution, and suggest possible tests.
AU - Kirkpatrick, Mark
AU - Nicholas Barton
ID - 3608
IS - 1
JF - Genetics
TI - Chromosome inversions, local adaptation, and speciation
VL - 173
ER -
TY - JOUR
AB - Bombina bombina and B. variegata are two anciently diverged toad taxa that have adapted to different breeding habitats yet hybridize freely in zones of overlap where their parapatric distributions meet. Here, we report on a joint genetic and ecological analysis of a hybrid zone in the vicinity of Stryi in western Ukraine. We used five unlinked allozyme loci, two nuclear single nucleotide polymorphisms and a mitochondrial DNA haplotype as genetic markers. Parallel allele frequency clines with a sharp central step occur across a sharp ecotone, where transitions in aquatic habitat, elevation, and terrestrial vegetation coincide. The width of the hybrid zone, estimated as the inverse of the maximum gradient in allele frequency, is 2.3 km. This is the smallest of four estimates derived from different clinal transects across Europe. We argue that the narrow cline near Stryi is mainly due to a combination of habitat distribution and habitat preference. Adult toads show a preference for either ponds (B. bombina) or puddles (B. variegata), which is known to affect the distribution of genotypes within the hybrid zones. At Stryi, it should cause a reduction of the dispersal rate across the ecotone and thus narrow the cline. A detailed comparison of all five intensively studied Bombina transects lends support to the hypothesis that habitat distribution plus habitat preference can jointly affect the structure of hybrid zones and, ultimately, the resulting barriers to gene flow between differentiated gene pools. This study also represents a resampling of an area that was last studied more than 70 years ago. Our allele-frequency clines largely coincide with those that were described then on the basis of morphological variation. However, we found asymmetrical introgression of B. variegata genes into B. bombina territory along the bank of a river.
AU - Yanchukov, Alexey
AU - Hofman, Sebastian
AU - Szymura, Jacek M
AU - Mezhzherin, Sergey V
AU - Morozov-Leonov, Sviatoslav
AU - Nicholas Barton
AU - Nürnberger, Beate
ID - 3609
IS - 3
JF - Evolution; International Journal of Organic Evolution
TI - Hybridization of Bombina bombina and B. variegata (Anura, Discoglossidae) at a sharp ecotone in western Ukraine: comparisons across transects and over time
VL - 60
ER -
TY - JOUR
AB - For a model of diallelic loci with arbitrary epistasis, Barton and Turelli [2004. Effects of genetic drift on variance components under a general model of epistasis. Evolution 58, 2111–2132] gave results for variances among and within replicate lines obtained by inbreeding without selection. Here, we discuss the relation between their population genetic methods and classical quantitative genetic arguments. In particular, we consider the case of no dominance using classical identity by descent arguments, which generalizes their results from two alleles to multiple alleles. To clarify the connections between the alternative methods, we obtain the same results using an intermediate method, which explicitly identifies the statistical effects of sets of loci. We also discuss the effects of population bottlenecks on covariances among relatives.
AU - Hill, William G
AU - Nicholas Barton
AU - Turelli, Michael
ID - 3610
IS - 1
JF - Theoretical Population Biology
TI - Prediction of effects of genetic drift on variance components under a general model of epistasis
VL - 70
ER -
TY - CONF
AB - We propose a video retrieval framework based on a novel combination of spatiograms and the Jensen-Shannon divergence, and validate its performance in two quantitative experiments on TRECVID BBC Rushes data. In the first experiment, color-based methods are tested by grouping redundant shots in an unsupervised clustering. Results of the second experiment show that motion-based spatiograms make a promising fast, compressed-domain descriptor for the detection of interview scenes.
AU - Ulges, Adrian
AU - Christoph Lampert
AU - Keysers,Daniel
ID - 3677
TI - Spatiogram-based shot distances for video retrieval
ER -
TY - CONF
AB - This paper describes a new system for "Finding Satellite Tracks” in astronomical images based on the modern geometric approach. There is an increasing need of using methods with solid mathematical and statistical foundation in astronomical image processing. Where the computational methods are serving in all disciplines of science, they are becoming popular in the field of astronomy as well. Currently different computational systems are required to be numerically optimized before to get applied on astronomical images. So at present there is no single system which solves the problems of astronomers using computational methods based on modern approaches. The system "Finding Satellite Tracks” is based on geometric matching method "Recognition by Adaptive Subdivision of Transformation Space (RAST)".
AU - Ali,Haider
AU - Christoph Lampert
AU - Breuel,Thomas M
ID - 3679
TI - Satellite tracks removal in astronomical images
VL - 4225
ER -
TY - CONF
AB - The detection of counterfeit in printed documents is currently based mainly on built-in security features or on human expertise. We propose a classification system that supports non-expert users to distinguish original documents from PC-made forgeries by analyzing the printing technique used. Each letter in a document is classified using a support vector machine that has been trained to distinguish laser from inkjet printouts. A color-coded visualization helps the user to interpret the per-letter classification results
AU - Christoph Lampert
AU - Mei,Lin
AU - Breuel,Thomas M
ID - 3680
TI - Printing technique classification for document counterfeit detection
VL - 1
ER -
TY - CONF
AB - Many algorithms to remove distortion from document images have be proposed in recent years, but so far there is no reliable method for comparing their performance. In this paper we propose a collection of methods to measure the quality of such restoration algorithms for document image which show a non-linear distortion due to perspective or page curl. For the result from these measurement to be meaningful, a common data set of ground truth is required. We therefore started with the buildup of a document image database that is meant to serve as a common data basis for all kinds of restoration from images of 3D-shaped document. The long term goal would be to establish this database and following extensions in the area of document image dewarping as an as fruitful and indispensable tool as e.g. the NIST database is for OCR, or the Caltech database is for object and face recognition.
AU - Christoph Lampert
AU - Breuel,Thomas M
ID - 3683
TI - Objective quality measurement for geometric document image restoration
ER -
TY - CONF
AB - Video compression currently is dominated by engineering and fine-tuned heuristic methods. In this paper, we propose to instead apply the well-developed machinery of machine learning in order to support the optimization of existing video encoders and the creation of new ones. Exemplarily, we show how by machine learning we can improve one encoding step that is crucial for the performance of all current video standards: macroblock mode decision. By formulating the problem in a Bayesian setup, we show that macroblock mode decision can be reduced to a classification problem with a cost function for misclassification that is sample dependent. We demonstrate how to apply different machine learning techniques to obtain suitable classifiers and we show in detailed experiments that all of these perform better than the state-of-the-art heuristic method
AU - Christoph Lampert
ID - 3685
TI - Machine learning for video compression: Macroblock mode decision
ER -
TY - CONF
AU - Keysers,Daniel
AU - Christoph Lampert
AU - Breuel,Thomas M
ID - 3692
TI - Color image dequantization by constrained diffusion
VL - 6058
ER -
TY - CONF
AB - Gaussian filtering in one, two or three dimensions is among the most commonly needed tasks in signal and image processing. Finite impulse response filters in the time domain with Gaussian masks are easy to implement in either floating or fixed point arithmetic, because Gaussian kernels are strictly positive and bounded. But these implementations are slow for large images or kernels. With the recursive IIR-filters and FFT-based methods, there are at least two alternative methods to perform Gaussian filtering in a faster way, but so far they are only applicable when floating-point hardware is available. In this paper, a fixed-point implementation of recursive Gaussian filtering is discussed and applied to isotropic and anisotropic image filtering by making use of a non-orthogonal separation scheme of the Gaussian filter.
AU - Christoph Lampert
AU - Wirjadi,Oliver
ID - 3693
TI - Anisotropic Gaussian filtering using fixed point arithmetic
ER -
TY - JOUR
AB - We give an analytical and geometrical treatment of what it means to separate a Gaussian kernel along arbitrary axes in Ropfn, and we present a separation scheme that allows us to efficiently implement anisotropic Gaussian convolution filters for data of arbitrary dimensionality. Based on our previous analysis we show that this scheme is optimal with regard to the number of memory accesses and interpolation operations needed. The proposed method relies on nonorthogonal convolution axes and works completely in image space. Thus, it avoids the need for a fast Fourier transform (FFT)-subroutine. Depending on the accuracy and speed requirements, different interpolation schemes and methods to implement the one-dimensional Gaussian (finite impulse response and infinite impulse response) can be integrated. Special emphasis is put on analyzing the performance and accuracy of the new method. In particular, we show that without any special optimization of the source code, it can perform anisotropic Gaussian filtering faster than methods relying on the FFT.
AU - Christoph Lampert
AU - Wirjadi,Oliver
ID - 3695
IS - 11
JF - IEEE Transactions on Image Processing (TIP)
TI - An optimal non-orthogonal separation of the anisotropic Gaussian convolution filter
VL - 15
ER -
TY - CHAP
AU - Harald Janovjak
AU - Mueller, Daniel J
ID - 3722
T2 - Bioanalytik
TI - Rastersondenmikroskopie
ER -
TY - JOUR
AB - Mechanical unfolding of single bacteriorhodopsins from a membrane bilayer is studied using molecular dynamics simulations. The initial conformation of the lipid membrane is determined through all-atom simulations and then its coarse-grained representation is used in the studies of stretching. A Go-like model with a realistic contact map and with Lennard–Jones contact interactions is applied to model the protein–membrane system. The model qualitatively reproduces the experimentally observed differences between force-extension patterns obtained on bacteriorhodopsin at different temperatures and predicts a lack of symmetry in the choice of the terminus to pull by. It also illustrates the decisive role of the interactions of the protein with the membrane in determining the force pattern and thus the stability of transmembrane proteins.
AU - Cieplak, Marek
AU - Filipek, Sławomir
AU - Harald Janovjak
AU - Krzysko, Krystiana A
ID - 3728
IS - 4
JF - Biochimica et Biophysica Acta (BBA) - Biomembranes
TI - Pulling single bacteriorhodopsin out of a membrane: Comparison of simulation and experiment
VL - 1758
ER -
TY - JOUR
AB - Measuring the visco-elastic properties of biological macromolecules constitutes an important step towards the understanding of dynamic biological processes, such as cell adhesion, muscle function, or plant cell wall stability. Force spectroscopy techniques based on the atomic force microscope (AFM) are increasingly used to study the complex visco-elastic response of (bio-)molecules on a single-molecule level. These experiments either require that the AFM cantilever is actively oscillated or that the molecule is clamped at constant force to monitor thermal cantilever motion. Here we demonstrate that the visco-elasticity of single bio-molecules can readily be extracted from the Brownian cantilever motion during conventional force-extension measurements. It is shown that the characteristics of the cantilever determine the signal-to-noise (S/N) ratio and time resolution. Using a small cantilever, the visco-elastic properties of single dextran molecules were resolved with a time resolution of 8.3 ms. The presented approach can be directly applied to probe the dynamic response of complex bio-molecular systems or proteins in force-extension experiments.
AU - Bippes, Christian A
AU - Humphris, Andrew D
AU - Stark, Martin
AU - Mueller, Daniel J
AU - Harald Janovjak
ID - 3729
IS - 3
JF - European Biophysics Journal
TI - Direct measurement of single-molecule visco-elasticity in atomic force microscope force-extension experiments
VL - 35
ER -
TY - JOUR
AB - We applied a single-cell assay to characterize how transcription dynamics affects protein expression levels of a tetracycline-inducible gene expression system. Transcriptional activity of the tetracycline promoter in response to a steady level of inducer is steady in ΔacrAB efflux mutant but pulsating in wildtype Escherichia coli cells. We found that the expression level of the green fluorescent protein is several folds higher in ΔacrAB efflux mutant than in wildtype cells.
AU - Le,Thuc T.
AU - Calin Guet
AU - Cluzel,Philippe
ID - 3750
IS - 1
JF - Protein Expression and Purification
TI - Protein expression enhancement in efflux-deleted mutant bacteria
VL - 48
ER -
TY - JOUR
AB - A primitive example of adaptation in gene expression is the balance between the rate of synthesis and degradation of cellular RNA, which allows rapid responses to environmental signals. Here, we investigate how multidrug efflux pump systems mediate the dynamics of a simple drug-inducible system in response to a steady level of inducer. Using fluorescence correlation spectroscopy, we measured in real time within a single bacterium the transcription activity at the RNA level of the acrAB-TolC multidrug efflux pump system. When cells are exposed to constant level of anhydrotetracycline inducer and are adsorbed onto a poly-L-lysine-coated surface, we found that the acrAB-TolC promoter is steadily active. We also monitored the activity of the tet promoter to characterize the effect of this efflux system on the dynamics of drug-inducible transcription. We found that the transcriptional response of the tet promoter to a steady level of aTc rises and then falls back to its preinduction level. The rate of RNA degradation was constant throughout the transcriptional pulse, indicating that the modulation of intracellular inducer concentration alone can produce this pulsating response. Single-cell experiments together with numerical simulations suggest that such pulsating response in drug-inducible genetic systems is a property emerging from the dependence of drug-inducible transcription on multidrug efflux systems.
AU - Le,Thuc T.
AU - Emonet,Thierry
AU - Harlepp, Sébastien
AU - Calin Guet
AU - Cluzel,Philippe
ID - 3755
IS - 9
JF - Biophysical Journal
TI - Dynamical determinants of drug-inducible gene expression in a single bacterium
VL - 90
ER -
TY - CONF
AB - Control of physical simulation has become a popular topic in the field of computer graphics. Keyframe control has been applied to simulations of rigid bodies, smoke, liquid, flocks, and finite element-based elastic bodies. In this paper, we create a framework for controlling systems of interacting particles -- paying special attention to simulations of cloth and flocking behavior. We introduce a novel integrator-swapping approximation in order to apply the adjoint method to linearized implicit schemes appropriate for cloth simulation. This allows the control of cloth while avoiding computationally infeasible derivative calculations. Meanwhile, flocking control using the adjoint method is significantly more efficient than currently-used methods for constraining group behaviors, allowing the controlled simulation of greater numbers of agents in fewer optimization iterations.
AU - Wojtan, Chris
AU - Mucha, Peter J
AU - Turk, Greg
ID - 3758
TI - Keyframe control of complex particle systems using the adjoint method
ER -
TY - JOUR
AB - Models of RNA secondary structure folding are widely used to study evolution in theory and simulation. However, systematic studies of the parameters involved are rare. In this paper, we study by simulation how RNA evolution is influenced by three different factors, namely the mutation rate, scaling of the fitness function, and distance measure. We found that for low mutation rates the qualitative evolutionary behavior is robust with respect to the scaling of the fitness function. For efficient mutation rates, which are close to the error threshold, scaling and distance measure have a strong influence on the evolutionary behavior. A global distance measure that takes sequence information additively into account lowers the error threshold. When using a local sequence-structure alignment for the distance, we observed a smoother evolution of the fitness over time. Finally, in addition to the well known error threshold, we identify another threshold of the mutation rate, called divergence threshold, where the qualitative transient behavior changes from a localized to an exploratory search.
AU - Anne Kupczok
AU - Dittrich,Peter
ID - 3767
IS - 3
JF - Journal of Theoretical Biology
TI - Determinants of simulated RNA evolution.
VL - 238
ER -
TY - JOUR
AB - Networks of GABAergic neurons are key elements in the generation of gamma oscillations in the brain. Computational studies suggested that the emergence of coherent oscillations requires hyperpolarizing inhibition. Here, we show that GABA(A) receptor-mediated inhibition in mature interneurons of the hippocampal dentate gyrus is shunting rather than hyperpolarizing. Unexpectedly, when shunting inhibition is incorporated into a structured interneuron network model with fast and strong synapses, coherent oscillations emerge. In comparison to hyperpolarizing inhibition, networks with shunting inhibition show several advantages. First, oscillations are generated with smaller tonic excitatory drive. Second, network frequencies are tuned to the gamma band. Finally, robustness against heterogeneity in the excitatory drive is markedly improved. In single interneurons, shunting inhibition shortens the interspike interval for low levels of drive but prolongs it for high levels, leading to homogenization of neuronal firing rates. Thus, shunting inhibition may confer increased robustness to gamma oscillations in the brain.
AU - Vida, Imre
AU - Bartos, Marlene
AU - Peter Jonas
ID - 3811
IS - 1
JF - Neuron
TI - Shunting inhibition improves robustness of gamma oscillations in hippocampal interneuron networks by homogenizing firing rates
VL - 49
ER -
TY - JOUR
AB - Hyperpolarization-activated channels (Ih or HCN channels) are widely expressed in principal neurons in the central nervous system. However, Ih in inhibitory GABAergic interneurons is less well characterized. We examined the functional properties of Ih in fast-spiking basket cells (BCs) of the dentate gyrus, using hippocampal slices from 17- to 21-day-old rats. Bath application of the Ih channel blocker ZD 7288 at a concentration of 30 microm induced a hyperpolarization of 5.7 +/- 1.5 mV, an increase in input resistance and a correlated increase in apparent membrane time constant. ZD 7288 blocked a hyperpolarization-activated current in a concentration-dependent manner (IC50, 1.4 microm). The effects of ZD 7288 were mimicked by external Cs+. The reversal potential of Ih was -27.4 mV, corresponding to a Na+ to K+ permeability ratio (PNa/PK) of 0.36. The midpoint potential of the activation curve of Ih was -83.9 mV, and the activation time constant at -120 mV was 190 ms. Single-cell expression analysis using reverse transcription followed by quantitative polymerase chain reaction revealed that BCs coexpress HCN1 and HCN2 subunit mRNA, suggesting the formation of heteromeric HCN1/2 channels. ZD 7288 increased the current threshold for evoking antidromic action potentials by extracellular stimulation, consistent with the expression of Ih in BC axons. Finally, ZD 7288 decreased the frequency of miniature inhibitory postsynaptic currents (mIPSCs) in hippocampal granule cells, the main target cells of BCs, to 70 +/- 4% of the control value. In contrast, the amplitude of mIPSCs was unchanged, consistent with the presence of Ih in inhibitory terminals. In conclusion, our results suggest that Ih channels are expressed in the somatodendritic region, axon and presynaptic elements of fast-spiking BCs in the hippocampus.
AU - Aponte, Yexica
AU - Lien, Cheng-Chang
AU - Reisinger, Ellen
AU - Peter Jonas
ID - 3813
IS - Pt 1
JF - Journal of Physiology
TI - Hyperpolarization-activated cation channels in fast-spiking interneurons of rat hippocampus
VL - 574
ER -
TY - GEN
AB - The axon terminals (mossy fibers) of hippocampal dentate granule cells form characteristic synaptic connections with large spines or excrescences of both hilar mossy cells and CA3 pyramidal neurons. Interneurons of the hilar region and area CA3 are also prominent targets of mossy fibers. The tracing of biocytin-filled mossy fibers and immunolabeling of target cells with interneuron markers has revealed that the majority of mossy fiber synapses project to gamma aminobutyric acid (GABA)-ergic inhibitory interneurons rather than to excitatory principal cells, although the functional implications of these quantitative differences are unclear. Following a brief description of the "classical" mossy fiber synapse on excrescences of CA3 pyramidal cells, the present review focuses on the contacts formed between granule cells and GABAergic interneurons, both normally and after synaptic reorganization. In response to deafferentation of mossy cell target cells, which include both granule cells and interneurons, mossy fibers "sprout" new axon collaterals that form a band of supragranular mossy fibers in the inner molecular layer of the dentate gyrus. Although most newly formed recurrent mossy fibers establish synapses with granule cells, there is an apparently convergent input of new mossy fibers onto GABA-immunoreactive interneuron dendrites that traverse the inner molecular layer. These mossy fiber-interneuron synapses in the dentate gyrus are observed in chronically epileptic rats and may be the structural correlate of the granule cell hyperinhibition observed in these animals in vivo. Together, the findings reviewed here establish mossy fiber synapses as an important component of inhibitory circuits in the hippocampus.
AU - Frotscher, Michael
AU - Peter Jonas
AU - Sloviter, Robert S
ID - 3814
IS - 2
T2 - Cell and Tissue Research
TI - Synapses formed by normal and abnormal hippocampal mossy fibers (Review)
VL - 326
ER -
TY - JOUR
AB - It is widely accepted that the hippocampus plays a major role in learning and memory. The mossy fiber synapse between granule cells in the dentate gyrus and pyramidal neurons in the CA3 region is a key component of the hippocampal trisynaptic circuit. Recent work, partially based on direct presynaptic patch-clamp recordings from hippocampal mossy fiber boutons, sheds light on the mechanisms of synaptic transmission and plasticity at mossy fiber synapses. A high Na(+) channel density in mossy fiber boutons leads to a large amplitude of the presynaptic action potential. Together with the fast gating of presynaptic Ca(2+) channels, this generates a large and brief presynaptic Ca(2+) influx, which can trigger transmitter release with high efficiency and temporal precision. The large number of release sites, the large size of the releasable pool of vesicles, and the huge extent of presynaptic plasticity confer unique strength to this synapse, suggesting a large impact onto the CA3 pyramidal cell network under specific behavioral conditions. The characteristic properties of the hippocampal mossy fiber synapse may be important for pattern separation and information storage in the dentate gyrus-CA3 cell network.
AU - Bischofberger, Josef
AU - Engel, Dominique
AU - Frotscher, Michael
AU - Peter Jonas
ID - 3815
IS - 3
JF - Pflugers Archiv : European Journal of Physiology
TI - Timing and efficacy of transmitter release at mossy fiber synapses in the hippocampal network
VL - 453
ER -
TY - JOUR
AU - Frotscher, Michael
AU - Gundelfinger, Eckart
AU - Peter Jonas
AU - Neher, Erwin
AU - Seeburg, Peter
ID - 3817
IS - 2
JF - Cell and Tissue Research
TI - The most important recent advances in synapse research from my point of view--and what remains to be done
VL - 326
ER -
TY - JOUR
AB - Rigorous analysis of synaptic transmission in the central nervous system requires access to presynaptic terminals. However, cortical terminals have been largely inaccessible to presynaptic patch-clamp recording, due to their small size. Using improved patch-clamp techniques in brain slices, we recorded from mossy fiber terminals in the CA3 region of the hippocampus, which have a diameter of 2-5 microm. The major steps of improvement were the enhanced visibility provided by high-numerical aperture objectives and infrared illumination, the development of vibratomes with minimal vertical blade vibrations and the use of sucrose-based solutions for storage and cutting. Based on these improvements, we describe a protocol that allows us to routinely record from hippocampal mossy fiber boutons. Presynaptic recordings can be obtained in slices from both rats and mice. Presynaptic recordings can be also obtained in slices from transgenic mice in which terminals are labeled with enhanced green fluorescent protein.
AU - Bischofberger, Josef
AU - Engel, Dominique
AU - Li, Liyi
AU - Geiger, Jörg R
AU - Peter Jonas
ID - 3818
IS - 4
JF - Nature Protocols
TI - Patch-clamp recording from mossy fiber terminals in hippocampal slices
VL - 1
ER -
TY - CONF
AB - A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with omega-regular winning conditions specified as Rabin or Streett objectives. These games are NP-complete and coNP-complete, respectively. The value of the game for a player at a state s given an objective Phi is the maximal probability with which the player can guarantee the satisfaction of Phi from s. We present a strategy-improvement algorithm to compute values in stochastic Rabin games, where an improvement step involves solving Markov decision processes (MDPs) and nonstochastic Rabin games. The algorithm also computes values for stochastic Streett games but does not directly yield an optimal strategy for Streett objectives. We then show how to obtain an optimal strategy for Streett objectives by solving certain nonstochastic Streett games.
AU - Krishnendu Chatterjee
AU - Thomas Henzinger
ID - 3888
TI - Strategy improvement for stochastic Rabin and Streett games
VL - 4137
ER -
TY - CONF
AB - We study observation-based strategies for two-player turn-based games on graphs with omega-regular objectives. An observation-based strategy relies on imperfect information about the history of a play, namely, on the past sequence of observations. Such games occur in the synthesis of a controller that does not see the private state of the plant. Our main results are twofold. First, we give a fixed-point algorithm for computing the set of states from which a player can win with a deterministic observation-based strategy for any omega-regular objective. The fixed point is computed in the lattice of antichains of state sets. This algorithm has the advantages of being directed by the objective and of avoiding an explicit subset construction on the game graph. Second, we give an algorithm for computing the set of states from which a player can win with probability 1 with a randomized observation-based strategy for a Buchi objective. This set is of interest because in the absence of perfect information, randomized strategies are more powerful than deterministic ones. We show that our algorithms are optimal by proving matching lower bounds.
AU - Krishnendu Chatterjee
AU - Doyen, Laurent
AU - Thomas Henzinger
AU - Raskin, Jean-François
ID - 3889
TI - Algorithms for omega-regular games with imperfect information
VL - 4207
ER -
TY - CONF
AB - We consider two-player infinite games played on graphs. The games are concurrent, in that at each state the players choose their moves simultaneously and independently, and stochastic, in that the moves determine a probability distribution for the successor state. The value of a game is the maximal probability with which a player can guarantee the satisfaction of her objective. We show that the values of concurrent games with w-regular objectives expressed as parity conditions can be decided in NP boolean AND coNP. This result substantially improves the best known previous bound of 3EXPTIME. It also shows that the full class of concurrent parity games is no harder than the special case of turn-based stochastic reachability games, for which NP boolean AND coNP is the best known bound. While the previous, more restricted NP boolean AND coNP results for graph games relied on the existence of particularly simple (pure memoryless) optimal strategies, in concurrent games with parity objectives optimal strategies may not exist, and epsilon-optimal strategies (which achieve the value of the game within a parameter epsilon > 0) require in general both randomization and infinite memory. Hence our proof must rely on a more detailed analysis of strategies and, in addition to the main result, yields two results that are interesting on their own. First, we show that there exist epsilon-optimal strategies that in the limit coincide with memoryless strategies; this parallels the celebrated result of Mertens-Neyman for concurrent games with limit-average objectives. Second, we complete the characterization of the memory requirements for epsilon-optimal strategies for concurrent games with parity conditions, by showing that memoryless strategies suffice for epsilon-optimality for coBachi conditions.
AU - Krishnendu Chatterjee
AU - de Alfaro, Luca
AU - Thomas Henzinger
ID - 3890
TI - The complexity of quantitative concurrent parity games
ER -
TY - CONF
AB - We study infinite stochastic games played by two-players over a finite state space, with objectives specified by sets of infinite traces. The games are concurrent (players make moves simultaneously and independently), stochastic (the next state is determined by a probability distribution that depends on the current state and chosen moves of the players) and infinite (proceeds for infinite number of rounds). The analysis of concurrent stochastic games can be classified into: quantitative analysis, analyzing the optimum value of the game; and qualitative analysis, analyzing the set of states with optimum value 1. We consider concurrent games with tail objectives, i.e., objectives that are independent of the finite-prefix of traces, and show that the class of tail objectives are strictly richer than the omega-regular objectives. We develop new proof techniques to extend several properties of concurrent games with omega-regular objectives to concurrent games with tail objectives. We prove the positive limit-one property for tail objectives, that states for all concurrent games if the optimum value for a player is positive for a tail objective Phi at some state, then there is a state where the optimum value is 1 for Phi, for the player. We also show that the optimum values of zero-sum (strictly conflicting objectives) games with tail objectives can be related to equilibrium values of nonzero-sum (not strictly conflicting objectives) games with simpler reachability objectives. A consequence of our analysis presents a polynomial time reduction of the quantitative analysis of tail objectives to the qualitative analysis for the sub-class of one-player stochastic games (Markov decision processes).
AU - Krishnendu Chatterjee
ID - 3891
TI - Concurrent games with tail objectives
VL - 4207
ER -