@article{6832,
  abstract     = {Steady-state turnover is a hallmark of epithelial tissues throughout adult life. Intestinal epithelial turnover is marked by continuous cell migration, which is assumed to be driven by mitotic pressure from the crypts. However, the balance of forces in renewal remains ill-defined. Combining biophysical modeling and quantitative three-dimensional tissue imaging with genetic and physical manipulations, we revealed the existence of an actin-related protein 2/3 complex–dependent active migratory force, which explains quantitatively the profiles of cell speed, density, and tissue tension along the villi. Cells migrate collectively with minimal rearrangements while displaying dual—apicobasal and front-back—polarity characterized by actin-rich basal protrusions oriented in the direction of migration. We propose that active migration is a critical component of gut epithelial turnover.},
  author       = {Krndija, Denis and Marjou, Fatima El and Guirao, Boris and Richon, Sophie and Leroy, Olivier and Bellaiche, Yohanns and Hannezo, Edouard B and Vignjevic, Danijela Matic},
  journal      = {Science},
  number       = {6454},
  pages        = {705--710},
  publisher    = {American Association for the Advancement of Science},
  title        = {{Active cell migration is critical for steady-state epithelial turnover in the gut}},
  doi          = {10.1126/science.aau3429},
  volume       = {365},
  year         = {2019},
}

@article{6835,
  abstract     = {We derive the Hasse principle and weak approximation for fibrations of certain varieties in the spirit of work by Colliot-Thélène–Sansuc and Harpaz–Skorobogatov–Wittenberg. Our varieties are defined through polynomials in many variables and part of our work is devoted to establishing Schinzel's hypothesis for polynomials of this kind. This last part is achieved by using arguments behind Birch's well-known result regarding the Hasse principle for complete intersections with the notable difference that we prove our result in 50% fewer variables than in the classical Birch setting. We also study the problem of square-free values of an integer polynomial with 66.6% fewer variables than in the Birch setting.},
  author       = {Destagnol, Kevin N and Sofos, Efthymios},
  issn         = {0007-4497},
  journal      = {Bulletin des Sciences Mathematiques},
  number       = {11},
  publisher    = {Elsevier},
  title        = {{Rational points and prime values of polynomials in moderately many variables}},
  doi          = {10.1016/j.bulsci.2019.102794},
  volume       = {156},
  year         = {2019},
}

@article{6836,
  abstract     = {Direct reciprocity is a powerful mechanism for the evolution of cooperation on the basis of repeated interactions1,2,3,4. It requires that interacting individuals are sufficiently equal, such that everyone faces similar consequences when they cooperate or defect. Yet inequality is ubiquitous among humans5,6 and is generally considered to undermine cooperation and welfare7,8,9,10. Most previous models of reciprocity do not include inequality11,12,13,14,15. These models assume that individuals are the same in all relevant aspects. Here we introduce a general framework to study direct reciprocity among unequal individuals. Our model allows for multiple sources of inequality. Subjects can differ in their endowments, their productivities and in how much they benefit from public goods. We find that extreme inequality prevents cooperation. But if subjects differ in productivity, some endowment inequality can be necessary for cooperation to prevail. Our mathematical predictions are supported by a behavioural experiment in which we vary the endowments and productivities of the subjects. We observe that overall welfare is maximized when the two sources of heterogeneity are aligned, such that more productive individuals receive higher endowments. By contrast, when endowments and productivities are misaligned, cooperation quickly breaks down. Our findings have implications for policy-makers concerned with equity, efficiency and the provisioning of public goods.},
  author       = {Hauser, Oliver P. and Hilbe, Christian and Chatterjee, Krishnendu and Nowak, Martin A.},
  issn         = {14764687},
  journal      = {Nature},
  number       = {7770},
  pages        = {524--527},
  publisher    = {Springer Nature},
  title        = {{Social dilemmas among unequals}},
  doi          = {10.1038/s41586-019-1488-5},
  volume       = {572},
  year         = {2019},
}

@article{6837,
  abstract     = {Migrasomes are a recently discovered type of extracellular vesicles that are characteristically generated along retraction fibers in migrating cells. Two studies now show how migrasomes are formed and how they function in the physiologically relevant context of the developing zebrafish embryo.},
  author       = {Tavano, Ste and Heisenberg, Carl-Philipp J},
  issn         = {1476-4679},
  journal      = {Nature Cell Biology},
  number       = {8},
  pages        = {918--920},
  publisher    = {Springer Nature},
  title        = {{Migrasomes take center stage}},
  doi          = {10.1038/s41556-019-0369-3},
  volume       = {21},
  year         = {2019},
}

@article{6840,
  abstract     = {We discuss thermodynamic properties of harmonically trapped
imperfect quantum gases. The spatial inhomogeneity of these systems imposes
a redefinition of the mean-field interparticle potential energy as compared
to the homogeneous case. In our approach, it takes the form a
2N2 ωd, where
N is the number of particles, ω—the harmonic trap frequency, d—system’s
dimensionality, and a is a parameter characterizing the interparticle interaction.
We provide arguments that this model corresponds to the limiting case of
a long-ranged interparticle potential of vanishingly small amplitude. This
conclusion is drawn from a computation similar to the well-known Kac scaling
procedure, which is presented here in a form adapted to the case of an isotropic
harmonic trap. We show that within the model, the imperfect gas of trapped
repulsive bosons undergoes the Bose–Einstein condensation provided d > 1.
The main result of our analysis is that in d = 1 the gas of attractive imperfect
fermions with a = −aF < 0 is thermodynamically equivalent to the gas of
repulsive bosons with a = aB > 0 provided the parameters aF and aB fulfill
the relation aB + aF = . This result supplements similar recent conclusion
about thermodynamic equivalence of two-dimensional (2D) uniform imperfect
repulsive Bose and attractive Fermi gases.},
  author       = {Mysliwy, Krzysztof and Napiórkowski, Marek},
  issn         = {1742-5468},
  journal      = {Journal of Statistical Mechanics: Theory and Experiment},
  number       = {6},
  publisher    = {IOP Publishing},
  title        = {{Thermodynamics of inhomogeneous imperfect quantum gases in harmonic traps}},
  doi          = {10.1088/1742-5468/ab190d},
  volume       = {2019},
  year         = {2019},
}

@article{6843,
  abstract     = {The aim of this short paper is to offer a complete characterization of all (not necessarily surjective) isometric embeddings of the Wasserstein space Wp(X), where S is a countable discrete metric space and 0<p<∞ is any parameter value. Roughly speaking, we will prove that any isometric embedding can be described by a special kind of X×(0,1]-indexed family of nonnegative finite measures. Our result implies that a typical non-surjective isometric embedding of Wp(X) splits mass and does not preserve the shape of measures. In order to stress that the lack of surjectivity is what makes things challenging, we will prove alternatively that Wp(X) is isometrically rigid for all 0<p<∞.},
  author       = {Gehér, György Pál and Titkos, Tamás and Virosztek, Daniel},
  issn         = {10960813},
  journal      = {Journal of Mathematical Analysis and Applications},
  number       = {2},
  publisher    = {Elsevier},
  title        = {{On isometric embeddings of Wasserstein spaces – the discrete case}},
  doi          = {10.1016/j.jmaa.2019.123435},
  volume       = {480},
  year         = {2019},
}

@article{6844,
  abstract     = {Studying the progression of the proliferative and differentiative patterns of neural stem cells at the individual cell level is crucial to the understanding of cortex development and how the disruption of such patterns can lead to malformations and neurodevelopmental diseases. However, our understanding of the precise lineage progression programme at single-cell resolution is still incomplete due to the technical variations in lineage- tracing approaches. One of the key challenges involves developing a robust theoretical framework in which we can integrate experimental observations and introduce correction factors to obtain a reliable and representative description of the temporal modulation of proliferation and differentiation. In order to obtain more conclusive insights, we carry out virtual clonal analysis using mathematical modelling and compare our results against experimental data. Using a dataset obtained with Mosaic Analysis with Double Markers, we illustrate how the theoretical description can be exploited to interpret and reconcile the disparity between virtual and experimental results.},
  author       = {Picco, Noemi and Hippenmeyer, Simon and Rodarte, Julio and Streicher, Carmen and Molnár, Zoltán and Maini, Philip K. and Woolley, Thomas E.},
  issn         = {1469-7580},
  journal      = {Journal of Anatomy},
  number       = {3},
  pages        = {686--696},
  publisher    = {Wiley},
  title        = {{A mathematical insight into cell labelling experiments for clonal analysis}},
  doi          = {10.1111/joa.13001},
  volume       = {235},
  year         = {2019},
}

@article{6848,
  abstract     = {Proton-translocating transhydrogenase (also known as nicotinamide nucleotide transhydrogenase (NNT)) is found in the plasma membranes of bacteria and the inner mitochondrial membranes of eukaryotes. NNT catalyses the transfer of a hydride between NADH and NADP+, coupled to the translocation of one proton across the membrane. Its main physiological function is the generation of NADPH, which is a substrate in anabolic reactions and a regulator of oxidative status; however, NNT may also fine-tune the Krebs cycle1,2. NNT deficiency causes familial glucocorticoid deficiency in humans and metabolic abnormalities in mice, similar to those observed in type II diabetes3,4. The catalytic mechanism of NNT has been proposed to involve a rotation of around 180° of the entire NADP(H)-binding domain that alternately participates in hydride transfer and proton-channel gating. However, owing to the lack of high-resolution structures of intact NNT, the details of this process remain unclear5,6. Here we present the cryo-electron microscopy structure of intact mammalian NNT in different conformational states. We show how the NADP(H)-binding domain opens the proton channel to the opposite sides of the membrane, and we provide structures of these two states. We also describe the catalytically important interfaces and linkers between the membrane and the soluble domains and their roles in nucleotide exchange. These structures enable us to propose a revised mechanism for a coupling process in NNT that is consistent with a large body of previous biochemical work. Our results are relevant to the development of currently unavailable NNT inhibitors, which may have therapeutic potential in ischaemia reperfusion injury, metabolic syndrome and some cancers7,8,9.},
  author       = {Kampjut, Domen and Sazanov, Leonid A},
  issn         = {1476-4687},
  journal      = {Nature},
  number       = {7773},
  pages        = {291–295},
  publisher    = {Springer Nature},
  title        = {{Structure and mechanism of mitochondrial proton-translocating transhydrogenase}},
  doi          = {10.1038/s41586-019-1519-2},
  volume       = {573},
  year         = {2019},
}

@phdthesis{6849,
  abstract     = {Brain function is mediated by complex dynamical interactions between excitatory and inhibitory cell types. The Cholecystokinin-expressing inhibitory cells (CCK-interneurons) are one of the least studied types, despite being suspected to play important roles in cognitive processes. We studied the network effects of optogenetic silencing of CCK-interneurons in the CA1 hippocampal area during exploration and sleep states. The cell firing pattern in response to light pulses allowed us to classify the recorded neurons in 5 classes, including disinhibited and non-responsive pyramidal cell and interneurons, and the inhibited interneurons corresponding to the CCK group. The light application, which inhibited the activity of CCK interneurons triggered wider changes in the firing dynamics of cells. We observed rate changes (i.e. remapping) of pyramidal cells during the exploration session in which the light was applied relative to the previous control session that was not restricted neither in time nor space to the light delivery. Also, the disinhibited pyramidal cells had higher increase in bursting than in single spike firing rate as a result of CCK silencing. In addition, the firing activity patterns during exploratory periods were more weakly reactivated in sleep for those periods in which CCK-interneuron were silenced than in the unaffected periods. Furthermore, light pulses during sleep disrupted the reactivation of recent waking patterns. Hence, silencing CCK neurons during exploration suppressed the reactivation of waking firing patterns in sleep and CCK interneuron activity was also required during sleep for the normal reactivation of waking patterns. These findings demonstrate the involvement of CCK cells in reactivation-related memory consolidation. An important part of our analysis was to test the relationship of the identified CCKinterneurons to brain oscillations. Our findings showed that these cells exhibited different oscillatory behaviour during anaesthesia and natural waking and sleep conditions. We showed that: 1) Contrary to the past studies performed under anaesthesia, the identified CCKinterneurons fired on the descending portion of the theta phase in waking exploration. 2) CCKinterneuron preferred phases around the trough of gamma oscillations. 3) Contrary to anaesthesia conditions, the average firing rate of the CCK-interneurons increased around the peak activity of the sharp-wave ripple (SWR) events in natural sleep, which is congruent with new reports about their functional connectivity. We also found that light driven CCK-interneuron silencing altered the dynamics on the CA1 network oscillatory activity: 1) Pyramidal cells negatively shifted their preferred theta phases when the light was applied, while interneurons responses were less consistent. 2) As a population, pyramidal cells negatively shifted their preferred activity during gamma oscillations, albeit we did not find gamma modulation differences related to the light application when pyramidal cells were subdivided into the disinhibited and unaffected groups. 3) During the peak of SWR events, all but the CCK-interneurons had a reduction in their relative firing rate change during the light application as compared to the change observed at SWR initiation. Finally, regarding to the place field activity of the recorded pyramidal neurons, we showed that the disinhibited pyramidal cells had reduced place field similarity, coherence and spatial information, but only during the light application. The mechanisms behind such observed behaviours might involve eCB signalling and plastic changes in CCK-interneuron synapses. In conclusion, the observed changes related to the light-mediated silencing of CCKinterneurons have unravelled characteristics of this interneuron subpopulation that might change the understanding not only of their particular network interactions, but also of the current theories about the emergence of certain cognitive processes such as place coding needed for navigation or hippocampus-dependent memory consolidation. },
  author       = {Rangel Guerrero, Dámaris K},
  isbn         = {9783990780039},
  issn         = {2663-337X},
  pages        = {97},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{The role of CCK-interneurons in regulating hippocampal network dynamics}},
  doi          = {10.15479/AT:ISTA:6849},
  year         = {2019},
}

@article{6855,
  abstract     = {Many traits of interest are highly heritable and genetically complex, meaning that much of the variation they exhibit arises from differences at numerous loci in the genome. Complex traits and their evolution have been studied for more than a century, but only in the last decade have genome-wide association studies (GWASs) in humans begun to reveal their genetic basis. Here, we bring these threads of research together to ask how findings from GWASs can further our understanding of the processes that give rise to heritable variation in complex traits and of the genetic basis of complex trait evolution in response to changing selection pressures (i.e., of polygenic adaptation). Conversely, we ask how evolutionary thinking helps us to interpret findings from GWASs and informs related efforts of practical importance.},
  author       = {Sella, Guy and Barton, Nicholas H},
  issn         = {1545-293X},
  journal      = {Annual Review of Genomics and Human Genetics},
  pages        = {461--493},
  publisher    = {Annual Reviews},
  title        = {{Thinking about the evolution of complex traits in the era of genome-wide association studies}},
  doi          = {10.1146/annurev-genom-083115-022316},
  volume       = {20},
  year         = {2019},
}

@article{6856,
  abstract     = {Plant mating systems play a key role in structuring genetic variation both within and between species. In hybrid zones, the outcomes and dynamics of hybridization are usually interpreted as the balance between gene flow and selection against hybrids. Yet, mating systems can introduce selective forces that alter these expectations; with diverse outcomes for the level and direction of gene flow depending on variation in outcrossing and whether the mating systems of the species pair are the same or divergent. We present a survey of hybridization in 133 species pairs from 41 plant families and examine how patterns of hybridization vary with mating system. We examine if hybrid zone mode, level of gene flow, asymmetries in gene flow and the frequency of reproductive isolating barriers vary in relation to mating system/s of the species pair. We combine these results with a simulation model and examples from the literature to address two general themes: (i) the two‐way interaction between introgression and the evolution of reproductive systems, and (ii) how mating system can facilitate or restrict interspecific gene flow. We conclude that examining mating system with hybridization provides unique opportunities to understand divergence and the processes underlying reproductive isolation.},
  author       = {Pickup, Melinda and Barton, Nicholas H and Brandvain, Yaniv and Fraisse, Christelle and Yakimowski, Sarah and Dixit, Tanmay and Lexer, Christian and Cereghetti, Eva and Field, David},
  issn         = {1469-8137},
  journal      = {New Phytologist},
  number       = {3},
  pages        = {1035--1047},
  publisher    = {Wiley},
  title        = {{Mating system variation in hybrid zones: Facilitation, barriers and asymmetries to gene flow}},
  doi          = {10.1111/nph.16180},
  volume       = {224},
  year         = {2019},
}

@article{6857,
  abstract     = {Gene Drives are regarded as future tools with a high potential for population control. Due to their inherent ability to overcome the rules of Mendelian inheritance, gene drives (GD) may spread genes rapidly through populations of sexually reproducing organisms. A release of organisms carrying a GD would constitute a paradigm shift in the handling of genetically modified organisms because gene drive organisms (GDO) are designed to drive their transgenes into wild populations and thereby increase the number of GDOs. The rapid development in this field and its focus on wild populations demand a prospective risk assessment with a focus on exposure related aspects. Presently, it is unclear how adequate risk management could be guaranteed to limit the spread of GDs in time and space, in order to avoid potential adverse effects in socio‐ecological systems.

The recent workshop on the “Evaluation of Spatial and Temporal Control of Gene Drives” hosted by the Institute of Safety/Security and Risk Sciences (ISR) in Vienna aimed at gaining some insight into the potential population dynamic behavior of GDs and appropriate measures of control. Scientists from France, Germany, England, and the USA discussed both topics in this meeting on April 4–5, 2019. This article summarizes results of the workshop.},
  author       = {Giese, B and Friess, J L and Schetelig, M F  and Barton, Nicholas H and Messer, Philip and Debarre, Florence and Meimberg, H and Windbichler, N and Boete, C},
  issn         = {1521-1878},
  journal      = {BioEssays},
  number       = {11},
  publisher    = {Wiley},
  title        = {{Gene Drives: Dynamics and regulatory matters – A report from the workshop “Evaluation of spatial and temporal control of Gene Drives”, 4 – 5 April 2019, Vienna}},
  doi          = {10.1002/bies.201900151},
  volume       = {41},
  year         = {2019},
}

@article{6858,
  author       = {Barton, Nicholas H},
  issn         = {2053-714X},
  journal      = {National Science Review},
  number       = {2},
  pages        = {291--292},
  publisher    = {Oxford University Press},
  title        = {{Is speciation driven by cycles of mixing and isolation?}},
  doi          = {10.1093/nsr/nwy113},
  volume       = {6},
  year         = {2019},
}

@article{6859,
  abstract     = {V (vacuolar)/A (archaeal)-type adenosine triphosphatases (ATPases), found in archaeaand eubacteria, couple ATP hydrolysis or synthesis to proton translocation across theplasma membrane using the rotary-catalysis mechanism. They belong to the V-typeATPase family, which differs from the mitochondrial/chloroplast F-type ATP synthasesin overall architecture. We solved cryo–electron microscopy structures of the intactThermus thermophilusV/A-ATPase, reconstituted into lipid nanodiscs, in three rotationalstates and two substates. These structures indicate substantial flexibility betweenV1and Voin a working enzyme, which results from mechanical competition between centralshaft rotation and resistance from the peripheral stalks. We also describedetails of adenosine diphosphate inhibition release, V1-Votorque transmission, andproton translocation, which are relevant for the entire V-type ATPase family.},
  author       = {Zhou, Long and Sazanov, Leonid A},
  issn         = {1095-9203},
  journal      = {Science},
  number       = {6455},
  publisher    = {AAAS},
  title        = {{Structure and conformational plasticity of the intact Thermus thermophilus V/A-type ATPase}},
  doi          = {10.1126/science.aaw9144},
  volume       = {365},
  year         = {2019},
}

@article{6867,
  abstract     = {A novel magnetic scratch method achieves repeatability, reproducibility and geometric control greater than pipette scratch assays and closely approximating the precision of cell exclusion assays while inducing the cell injury inherently necessary for wound healing assays. The magnetic scratch is affordable, easily implemented and standardisable and thus may contribute toward better comparability of data generated in different studies and laboratories.},
  author       = {Fenu, M. and Bettermann, T. and Vogl, C. and Darwish-Miranda, Nasser and Schramel, J. and Jenner, F. and Ribitsch, I.},
  issn         = {20452322},
  journal      = {Scientific Reports},
  number       = {1},
  publisher    = {Springer Nature},
  title        = {{A novel magnet-based scratch method for standardisation of wound-healing assays}},
  doi          = {10.1038/s41598-019-48930-7},
  volume       = {9},
  year         = {2019},
}

@article{6868,
  abstract     = {Hyperpolarization-activated cyclic-nucleotide-gated (HCN) channels control electrical rhythmicity and excitability in the heart and brain, but the function of HCN channels at the subcellular level in axons remains poorly understood. Here, we show that the action potential conduction velocity in both myelinated and unmyelinated central axons can be bidirectionally modulated by a HCN channel blocker, cyclic adenosine monophosphate (cAMP), and neuromodulators. Recordings from mouse cerebellar mossy fiber boutons show that HCN channels ensure reliable high-frequency firing and are strongly modulated by cAMP (EC50 40 mM; estimated endogenous cAMP concentration 13 mM). In addition, immunogold-electron microscopy revealed HCN2 as the dominating subunit in cerebellar mossy fibers. Computational modeling indicated that HCN2 channels control conduction velocity primarily by altering the resting membrane potential
and are associated with significant metabolic costs. These results suggest that the cAMP-HCN pathway provides neuromodulators with an opportunity to finely tune energy consumption and temporal delays across axons in the brain.},
  author       = {Byczkowicz, Niklas and Eshra, Abdelmoneim and Montanaro-Punzengruber, Jacqueline-Claire and Trevisiol, Andrea and Hirrlinger, Johannes and Kole, Maarten Hp and Shigemoto, Ryuichi and Hallermann, Stefan},
  issn         = {2050084X},
  journal      = {eLife},
  publisher    = {eLife Sciences Publications},
  title        = {{HCN channel-mediated neuromodulation can control action potential velocity and fidelity in central axons}},
  doi          = {10.7554/eLife.42766},
  volume       = {8},
  year         = {2019},
}

@article{6877,
  author       = {Kopf, Aglaja and Sixt, Michael K},
  issn         = {1097-4172},
  journal      = {Cell},
  number       = {1},
  pages        = {51--53},
  publisher    = {Elsevier},
  title        = {{The neural crest pitches in to remove apoptotic debris}},
  doi          = {10.1016/j.cell.2019.08.047},
  volume       = {179},
  year         = {2019},
}

@inproceedings{6884,
  abstract     = {In two-player games on graphs, the players move a token through a graph to produce a finite or infinite path, which determines the qualitative winner or quantitative payoff of the game. We study bidding games in which the players bid for the right to move the token. Several bidding rules were studied previously. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the "bank" rather than the other player. Taxman bidding spans the spectrum between Richman and poorman bidding. They are parameterized by a constant tau in [0,1]: portion tau of the winning bid is paid to the other player, and portion 1-tau to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games. It was previously shown that both Richman and poorman infinite-duration games with qualitative objectives reduce to reachability games, and we show a similar result here. Our most interesting results concern quantitative taxman games, namely mean-payoff games, where poorman and Richman bidding differ significantly. A central quantity in these games is the ratio between the two players' initial budgets. While in poorman mean-payoff games, the optimal payoff of a player depends on the initial ratio, in Richman bidding, the payoff depends only on the structure of the game. In both games the optimal payoffs can be found using (different) probabilistic connections with random-turn games in which in each turn, instead of bidding, a coin is tossed to determine which player moves. While the value with Richman bidding equals the value of a random-turn game with an un-biased coin, with poorman bidding, the bias in the coin is the initial ratio of the budgets. We give a complete classification of mean-payoff taxman games that is based on a probabilistic connection: the value of a taxman bidding game with parameter tau and initial ratio r, equals the value of a random-turn game that uses a coin with bias F(tau, r) = (r+tau * (1-r))/(1+tau). Thus, we show that Richman bidding is the exception; namely, for every tau <1, the value of the game depends on the initial ratio. Our proof technique simplifies and unifies the previous proof techniques for both Richman and poorman bidding. },
  author       = {Avni, Guy and Henzinger, Thomas A and Zikelic, Dorde},
  location     = {Aachen, Germany},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Bidding mechanisms in graph games}},
  doi          = {10.4230/LIPICS.MFCS.2019.11},
  volume       = {138},
  year         = {2019},
}

@inproceedings{6885,
  abstract     = {A vector addition system with states (VASS) consists of a finite set of states and counters. A configuration is a state and a value for each counter; a transition changes the state and each counter is incremented, decremented, or left unchanged. While qualitative properties such as state and configuration reachability have been studied for VASS, we consider the long-run average cost of infinite computations of VASS. The cost of a configuration is for each state, a linear combination of the counter values. In the special case of uniform cost functions, the linear combination is the same for all states. The (regular) long-run emptiness problem is, given a VASS, a cost function, and a threshold value, if there is a (lasso-shaped) computation such that the long-run average value of the cost function does not exceed the threshold. For uniform cost functions, we show that the regular long-run emptiness problem is (a) decidable in polynomial time for integer-valued VASS, and (b) decidable but nonelementarily hard for natural-valued VASS (i.e., nonnegative counters). For general cost functions, we show that the problem is (c) NP-complete for integer-valued VASS, and (d) undecidable for natural-valued VASS. Our most interesting result is for (c) integer-valued VASS with general cost functions, where we establish a connection between the regular long-run emptiness problem and quadratic Diophantine inequalities. The general (nonregular) long-run emptiness problem is equally hard as the regular problem in all cases except (c), where it remains open. },
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan},
  location     = {Amsterdam, Netherlands},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Long-run average behavior of vector addition systems with states}},
  doi          = {10.4230/LIPICS.CONCUR.2019.27},
  volume       = {140},
  year         = {2019},
}

@inproceedings{6886,
  abstract     = {In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players bid for the right to move the token: in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Bidding games are known to have a clean and elegant mathematical structure that relies on the ability of the players to submit arbitrarily small bids. Many applications, however, require a fixed granularity for the bids, which can represent, for example, the monetary value expressed in cents. We study, for the first time, the combination of discrete-bidding and infinite-duration games. Our most important result proves that these games form a large determined subclass of concurrent games, where determinacy is the strong property that there always exists exactly one player who can guarantee winning the game. In particular, we show that, in contrast to non-discrete bidding games, the mechanism with which tied bids are resolved plays an important role in discrete-bidding games. We study several natural tie-breaking mechanisms and show that, while some do not admit determinacy, most natural mechanisms imply determinacy for every pair of initial budgets. },
  author       = {Aghajohari, Milad and Avni, Guy and Henzinger, Thomas A},
  location     = {Amsterdam, Netherlands},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Determinacy in discrete-bidding infinite-duration games}},
  doi          = {10.4230/LIPICS.CONCUR.2019.20},
  volume       = {140},
  year         = {2019},
}