TY - JOUR
AB - We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff, the ratio, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with bounded treewidthโa class that contains the control flow graphs of most programs. Let n denote the number of nodes of a graph, m the number of edges (for bounded treewidth ๐=๐(๐)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for the minimum initial credit problem we show that (1) for general graphs the problem can be solved in ๐(๐2โ
๐) time and the associated decision problem in ๐(๐โ
๐) time, improving the previous known ๐(๐3โ
๐โ
log(๐โ
๐)) and ๐(๐2โ
๐) bounds, respectively; and (2) for bounded treewidth graphs we present an algorithm that requires ๐(๐โ
log๐) time. Second, for bounded treewidth graphs we present an algorithm that approximates the mean-payoff value within a factor of 1+๐ in time ๐(๐โ
log(๐/๐)) as compared to the classical exact algorithms on general graphs that require quadratic time. Third, for the ratio property we present an algorithm that for bounded treewidth graphs works in time ๐(๐โ
log(|๐โ
๐|))=๐(๐โ
log(๐โ
๐)), when the output is ๐๐, as compared to the previously best known algorithm on general graphs with running time ๐(๐2โ
log(๐โ
๐)). We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 9393
JF - Formal Methods in System Design
SN - 09259856
TI - Faster algorithms for quantitative verification in bounded treewidth graphs
ER -
TY - JOUR
AB - Chromosomal inversions have long been recognized for their role in local adaptation. By suppressing recombination in heterozygous individuals, they can maintain coadapted gene complexes and protect them from homogenizing effects of gene flow. However, to fully understand their importance for local adaptation we need to know their influence on phenotypes under divergent selection. For this, the marine snail Littorina saxatilis provides an ideal study system. Divergent ecotypes adapted to wave action and crab predation occur in close proximity on intertidal shores with gene flow between them. Here, we used F2 individuals obtained from crosses between the ecotypes to test for associations between genomic regions and traits distinguishing the Crabโ/Waveโadapted ecotypes including size, shape, shell thickness, and behavior. We show that most of these traits are influenced by two previously detected inversion regions that are divergent between ecotypes. We thus gain a better understanding of one important underlying mechanism responsible for the rapid and repeated formation of ecotypes: divergent selection acting on inversions. We also found that some inversions contributed to more than one trait suggesting that they may contain several loci involved in adaptation, consistent with the hypothesis that suppression of recombination within inversions facilitates differentiation in the presence of gene flow.
AU - Koch, Eva L.
AU - Morales, Hernรกn E.
AU - Larsson, Jenny
AU - Westram, Anja M
AU - Faria, Rui
AU - Lemmon, Alan R.
AU - Lemmon, E. Moriarty
AU - Johannesson, Kerstin
AU - Butlin, Roger K.
ID - 9394
JF - Evolution Letters
TI - Genetic variation for adaptive traits is associated with polymorphic inversions in Littorina saxatilis
ER -
TY - DATA
AB - This .zip File contains the transport data for "Non-topological zero bias peaks in full-shell nanowires induced by flux tunable Andreev states" by M. Valentini, et. al.
The measurements were done using Labber Software and the data is stored in the hdf5 file format.
Instructions of how to read the data are in "Notebook_Valentini.pdf".
AU - Valentini, Marco
ID - 9389
TI - Research data for "Non-topological zero bias peaks in full-shell nanowires induced by flux tunable Andreev states"
ER -
TY - JOUR
AU - Stankowski, Sean
AU - Ravinet, Mark
ID - 9392
IS - 9
JF - Current Biology
SN - 09609822
TI - Quantifying the use of species concepts
VL - 31
ER -
TY - JOUR
AB - Direct and indirect reciprocity are key mechanisms for the evolution of cooperation. Direct reciprocity means that individuals use their own experience to decide whether to cooperate with another person. Indirect reciprocity means that they also consider the experiences of others. Although these two mechanisms are intertwined, they are typically studied in isolation. Here, we introduce a mathematical framework that allows us to explore both kinds of reciprocity simultaneously. We show that the well-known โgenerous tit-for-tatโ strategy of direct reciprocity has a natural analogue in indirect reciprocity, which we call โgenerous scoringโ. Using an equilibrium analysis, we characterize under which conditions either of the two strategies can maintain cooperation. With simulations, we additionally explore which kind of reciprocity evolves when members of a population engage in social learning to adapt to their environment. Our results draw unexpected connections between direct and indirect reciprocity while highlighting important differences regarding their evolvability.
AU - Schmid, Laura
AU - Chatterjee, Krishnendu
AU - Hilbe, Christian
AU - Nowak, Martin A.
ID - 9402
JF - Nature Human Behaviour
TI - A unified framework of direct and indirect reciprocity
ER -
TY - CHAP
AB - Optimal decision making requires individuals to know their available options and to anticipate correctly what consequences these options have. In many social interactions, however, we refrain from gathering all relevant information, even if this information would help us make better decisions and is costless to obtain. This chapter examines several examples of โdeliberate ignorance.โ Two simple models are proposed to illustrate how ignorance can evolve among self-interested and payoff - maximizing individuals, and open problems are highlighted that lie ahead for future research to explore.
AU - Schmid, Laura
AU - Hilbe, Christian
ED - Hertwig, Ralph
ED - Engel, Christoph
ID - 9403
SN - 978-0-262-04559-9
T2 - Deliberate Ignorance: Choosing Not To Know
TI - The evolution of strategic ignorance in strategic interaction
VL - 29
ER -
TY - JOUR
AB - We extend our recent result [22] on the central limit theorem for the linear eigenvalue statistics of non-Hermitian matrices X with independent, identically distributed complex entries to the real symmetry class. We find that the expectation and variance substantially differ from their complex counterparts, reflecting (i) the special spectral symmetry of real matrices onto the real axis; and (ii) the fact that real i.i.d. matrices have many real eigenvalues. Our result generalizes the previously known special cases where either the test function is analytic [49] or the first four moments of the matrix elements match the real Gaussian [59, 44]. The key element of the proof is the analysis of several weakly dependent Dyson Brownian motions (DBMs). The conceptual novelty of the real case compared with [22] is that the correlation structure of the stochastic differentials in each individual DBM is non-trivial, potentially even jeopardising its well-posedness.
AU - Cipolloni, Giorgio
AU - Erdรถs, Lรกszlรณ
AU - Schrรถder, Dominik J
ID - 9412
JF - Electronic Journal of Probability
TI - Fluctuation around the circular law for random matrices with real entries
VL - 26
ER -
TY - JOUR
AB - The dynamics of a triangular magnetocapillary swimmer is studied using the lattice Boltzmann method. We extend on our previous work, which deals with the self-assembly and a specific type of the swimmer motion characterized by the swimmerโs maximum velocity centred around the particleโs inverse viscous time. Here, we identify additional regimes of motion. First, modifying the ratio of surface tension and magnetic forces allows to study the swimmer propagation in the regime of significantly lower frequencies mainly defined by the strength of the magnetocapillary potential. Second, introducing a constant magnetic contribution in each of the particles in addition to their magnetic moment induced by external fields leads to another regime characterized by strong in-plane swimmer reorientations that resemble experimental observations.
AU - Sukhov, Alexander
AU - Hubert, Maxime
AU - Grosjean, Galien M
AU - Trosman, Oleg
AU - Ziegler, Sebastian
AU - Collard, Ylona
AU - Vandewalle, Nicolas
AU - Smith, Ana Sunฤana
AU - Harting, Jens
ID - 9411
IS - 4
JF - European Physical Journal E
SN - 12928941
TI - Regimes of motion of magnetocapillary swimmers
VL - 44
ER -
TY - JOUR
AB - Microtubule plus-end depolymerization rate is a potentially important target of physiological regulation, but it has been challenging to measure, so its role in spatial organization is poorly understood. Here we apply a method for tracking plus ends based on time difference imaging to measure depolymerization rates in large interphase asters growing in Xenopus egg extract. We observed strong spatial regulation of depolymerization rates, which were higher in the aster interior compared with the periphery, and much less regulation of polymerization or catastrophe rates. We interpret these data in terms of a limiting component model, where aster growth results in lower levels of soluble tubulin and microtubule-associated proteins (MAPs) in the interior cytosol compared with that at the periphery. The steady-state polymer fraction of tubulin was โผ30%, so tubulin is not strongly depleted in the aster interior. We propose that the limiting component for microtubule assembly is a MAP that inhibits depolymerization, and that egg asters are tuned to low microtubule density.
AU - Ishihara, Keisuke
AU - Decker, Franziska
AU - Dos Santos Caldas, Paulo R
AU - Pelletier, James F.
AU - Loose, Martin
AU - Bruguรฉs, Jan
AU - Mitchison, Timothy J.
ID - 9414
IS - 9
JF - Molecular Biology of the Cell
SN - 10591524
TI - Spatial variation of microtubule depolymerization in large asters
VL - 32
ER -
TY - CONF
AB - Formal design of embedded and cyber-physical systems relies on mathematical modeling. In this paper, we consider the model class of hybrid automata whose dynamics are defined by affine differential equations. Given a set of time-series data, we present an algorithmic approach to synthesize a hybrid automaton exhibiting behavior that is close to the data, up to a specified precision, and changes in synchrony with the data. A fundamental problem in our synthesis algorithm is to check membership of a time series in a hybrid automaton. Our solution integrates reachability and optimization techniques for affine dynamical systems to obtain both a sufficient and a necessary condition for membership, combined in a refinement framework. The algorithm processes one time series at a time and hence can be interrupted, provide an intermediate result, and be resumed. We report experimental results demonstrating the applicability of our synthesis approach.
AU - Garcia Soto, Miriam
AU - Henzinger, Thomas A
AU - Schilling, Christian
ID - 9200
KW - hybrid automaton
KW - membership
KW - system identification
SN - 9781450383394
T2 - HSCC '21: Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control
TI - Synthesis of hybrid automata with affine dynamics from time-series data
ER -