@phdthesis{1400, abstract = {Cancer results from an uncontrolled growth of abnormal cells. Sequentially accumulated genetic and epigenetic alterations decrease cell death and increase cell replication. We used mathematical models to quantify the effect of driver gene mutations. The recently developed targeted therapies can lead to dramatic regressions. However, in solid cancers, clinical responses are often short-lived because resistant cancer cells evolve. We estimated that approximately 50 different mutations can confer resistance to a typical targeted therapeutic agent. We find that resistant cells are likely to be present in expanded subclones before the start of the treatment. The dominant strategy to prevent the evolution of resistance is combination therapy. Our analytical results suggest that in most patients, dual therapy, but not monotherapy, can result in long-term disease control. However, long-term control can only occur if there are no possible mutations in the genome that can cause cross-resistance to both drugs. Furthermore, we showed that simultaneous therapy with two drugs is much more likely to result in long-term disease control than sequential therapy with the same drugs. To improve our understanding of the underlying subclonal evolution we reconstruct the evolutionary history of a patient's cancer from next-generation sequencing data of spatially-distinct DNA samples. Using a quantitative measure of genetic relatedness, we found that pancreatic cancers and their metastases demonstrated a higher level of relatedness than that expected for any two cells randomly taken from a normal tissue. This minimal amount of genetic divergence among advanced lesions indicates that genetic heterogeneity, when quantitatively defined, is not a fundamental feature of the natural history of untreated pancreatic cancers. Our newly developed, phylogenomic tool Treeomics finds evidence for seeding patterns of metastases and can directly be used to discover rules governing the evolution of solid malignancies to transform cancer into a more predictable disease.}, author = {Reiter, Johannes}, issn = {2663-337X}, pages = {183}, publisher = {Institute of Science and Technology Austria}, title = {{The subclonal evolution of cancer}}, year = {2015}, } @phdthesis{1401, abstract = {The human ability to recognize objects in complex scenes has driven research in the computer vision field over couple of decades. This thesis focuses on the object recognition task in images. That is, given the image, we want the computer system to be able to predict the class of the object that appears in the image. A recent successful attempt to bridge semantic understanding of the image perceived by humans and by computers uses attribute-based models. Attributes are semantic properties of the objects shared across different categories, which humans and computers can decide on. To explore the attribute-based models we take a statistical machine learning approach, and address two key learning challenges in view of object recognition task: learning augmented attributes as mid-level discriminative feature representation, and learning with attributes as privileged information. Our main contributions are parametric and non-parametric models and algorithms to solve these frameworks. In the parametric approach, we explore an autoencoder model combined with the large margin nearest neighbor principle for mid-level feature learning, and linear support vector machines for learning with privileged information. In the non-parametric approach, we propose a supervised Indian Buffet Process for automatic augmentation of semantic attributes, and explore the Gaussian Processes classification framework for learning with privileged information. A thorough experimental analysis shows the effectiveness of the proposed models in both parametric and non-parametric views.}, author = {Sharmanska, Viktoriia}, issn = {2663-337X}, pages = {144}, publisher = {Institute of Science and Technology Austria}, title = {{Learning with attributes for object recognition: Parametric and non-parametrics views}}, doi = {10.15479/at:ista:1401}, year = {2015}, } @article{14013, abstract = {The ultrafast motion of electrons and holes after light-matter interaction is fundamental to a broad range of chemical and biophysical processes. We advanced high-harmonic spectroscopy to resolve spatially and temporally the migration of an electron hole immediately after ionization of iodoacetylene while simultaneously demonstrating extensive control over the process. A multidimensional approach, based on the measurement and accurate theoretical description of both even and odd harmonic orders, enabled us to reconstruct both quantum amplitudes and phases of the electronic states with a resolution of ~100 attoseconds. We separately reconstructed quasi-field-free and laser-controlled charge migration as a function of the spatial orientation of the molecule and determined the shape of the hole created by ionization. Our technique opens the prospect of laser control over electronic primary processes.}, author = {Kraus, P. M. and Mignolet, B. and Baykusheva, Denitsa Rangelova and Rupenyan, A. and Horný, L. and Penka, E. F. and Grassi, G. and Tolstikhin, O. I. and Schneider, J. and Jensen, F. and Madsen, L. B. and Bandrauk, A. D. and Remacle, F. and Wörner, H. J.}, issn = {1095-9203}, journal = {Science}, keywords = {Multidisciplinary}, number = {6262}, pages = {790--795}, publisher = {American Association for the Advancement of Science}, title = {{Measurement and laser control of attosecond charge migration in ionized iodoacetylene}}, doi = {10.1126/science.aab2160}, volume = {350}, year = {2015}, } @article{14014, abstract = {We have studied a coupled electronic-nuclear wave packet in nitric oxide using time-resolved strong-field photoelectron holography and rescattering. We show that the electronic dynamics mainly appears in the holographic structures whereas nuclear motion strongly modulates the angular distribution of the rescattered photoelectrons.}, author = {Walt, Samuel G and Ram, N Bhargava and von Conta, Aaron and Baykusheva, Denitsa Rangelova and Atala, Marcos and Wörner, Hans Jakob}, issn = {1742-6596}, journal = {Journal of Physics: Conference Series}, keywords = {General Physics and Astronomy}, number = {11}, publisher = {IOP Publishing}, title = {{Resolving the dynamics of valence-shell electrons and nuclei through laser-induced diffraction and holography}}, doi = {10.1088/1742-6596/635/11/112135}, volume = {635}, year = {2015}, } @article{14015, abstract = {We advance high-harmonic spectroscopy to resolve molecular charge migration in time and space and simultaneously demonstrate extensive control over the process. A multidimensional approach enables us to reconstruct both quantum amplitudes and phases with a resolution of better than 100 attoseconds and to separately reconstruct field-free and laser- driven charge migration. Our techniques make charge migration in molecules measurable on the attosecond time scale and open new avenues for laser control of electronic primary processes.}, author = {Kraus, P M and Mignolet, B and Baykusheva, Denitsa Rangelova and Rupenyan, A and Horný, L and Penka, E F and Tolstikhin, O I and Schneider, J and Jensen, F and Madsen, L B and Bandrauk, A D and Remacle, F and Wörner, H J}, issn = {1742-6596}, journal = {Journal of Physics: Conference Series}, keywords = {General Physics and Astronomy}, number = {11}, publisher = {IOP Publishing}, title = {{Attosecond charge migration and its laser control}}, doi = {10.1088/1742-6596/635/11/112136}, volume = {635}, year = {2015}, } @article{14016, abstract = {All attosecond time-resolved measurements have so far relied on the use of intense near-infrared laser pulses. In particular, attosecond streaking, laser-induced electron diffraction and high-harmonic generation all make use of non-perturbative light–matter interactions. Remarkably, the effect of the strong laser field on the studied sample has often been neglected in previous studies. Here we use high-harmonic spectroscopy to measure laser-induced modifications of the electronic structure of molecules. We study high-harmonic spectra of spatially oriented CH3F and CH3Br as generic examples of polar polyatomic molecules. We accurately measure intensity ratios of even and odd-harmonic orders, and of the emission from aligned and unaligned molecules. We show that these robust observables reveal a substantial modification of the molecular electronic structure by the external laser field. Our insights offer new challenges and opportunities for a range of emerging strong-field attosecond spectroscopies.}, author = {Kraus, P. M. and Tolstikhin, O. I. and Baykusheva, Denitsa Rangelova and Rupenyan, A. and Schneider, J. and Bisgaard, C. Z. and Morishita, T. and Jensen, F. and Madsen, L. B. and Wörner, H. J.}, issn = {2041-1723}, journal = {Nature Communications}, keywords = {General Physics and Astronomy, General Biochemistry, Genetics and Molecular Biology, General Chemistry, Multidisciplinary}, publisher = {Springer Nature}, title = {{Observation of laser-induced electronic structure in oriented polyatomic molecules}}, doi = {10.1038/ncomms8039}, volume = {6}, year = {2015}, } @article{14017, abstract = {The detection of electron motion and electronic wave-packet dynamics is one of the core goals of attosecond science. Recently, choosing the nitric oxide molecule as an example, we have introduced and demonstrated an experimental approach to measure coupled valence electronic and rotational wave packets using high-order-harmonic-generation (HHG) spectroscopy [Kraus et al., Phys. Rev. Lett. 111, 243005 (2013)]. A short outline of the theory to describe the combination of the pump and HHG probe process was published together with an extensive discussion of experimental results [Baykusheva et al., Faraday Discuss. 171, 113 (2014)]. The comparison of theory and experiment showed good agreement on a quantitative level. Here, we present the theory in detail, which is based on a generalized density-matrix approach that describes the pump process and the subsequent probing of the wave packets by a semiclassical quantitative rescattering approach. An in-depth analysis of the different Raman scattering contributions to the creation of the coupled rotational and electronic spin-orbit wave packets is made. We present results for parallel and perpendicular linear polarizations of the pump and probe laser pulses. Furthermore, an analysis of the combined rotational-electronic density matrix in terms of irreducible components is presented that facilitates interpretation of the results.}, author = {Zhang, Song Bin and Baykusheva, Denitsa Rangelova and Kraus, Peter M. and Wörner, Hans Jakob and Rohringer, Nina}, issn = {1094-1622}, journal = {Physical Review A}, keywords = {Atomic and Molecular Physics, and Optics}, number = {2}, publisher = {American Physical Society}, title = {{Theoretical study of molecular electronic and rotational coherences by high-order-harmonic generation}}, doi = {10.1103/physreva.91.023421}, volume = {91}, year = {2015}, } @inproceedings{1424, abstract = {We consider the problem of statistical computations with persistence diagrams, a summary representation of topological features in data. These diagrams encode persistent homology, a widely used invariant in topological data analysis. While several avenues towards a statistical treatment of the diagrams have been explored recently, we follow an alternative route that is motivated by the success of methods based on the embedding of probability measures into reproducing kernel Hilbert spaces. In fact, a positive definite kernel on persistence diagrams has recently been proposed, connecting persistent homology to popular kernel-based learning techniques such as support vector machines. However, important properties of that kernel enabling a principled use in the context of probability measure embeddings remain to be explored. Our contribution is to close this gap by proving universality of a variant of the original kernel, and to demonstrate its effective use in twosample hypothesis testing on synthetic as well as real-world data.}, author = {Kwitt, Roland and Huber, Stefan and Niethammer, Marc and Lin, Weili and Bauer, Ulrich}, location = {Montreal, Canada}, pages = {3070 -- 3078}, publisher = {Neural Information Processing Systems}, title = {{Statistical topological data analysis-A kernel perspective}}, volume = {28}, year = {2015}, } @inproceedings{1425, abstract = {In this work we aim at extending the theoretical foundations of lifelong learning. Previous work analyzing this scenario is based on the assumption that learning tasks are sampled i.i.d. from a task environment or limited to strongly constrained data distributions. Instead, we study two scenarios when lifelong learning is possible, even though the observed tasks do not form an i.i.d. sample: first, when they are sampled from the same environment, but possibly with dependencies, and second, when the task environment is allowed to change over time in a consistent way. In the first case we prove a PAC-Bayesian theorem that can be seen as a direct generalization of the analogous previous result for the i.i.d. case. For the second scenario we propose to learn an inductive bias in form of a transfer procedure. We present a generalization bound and show on a toy example how it can be used to identify a beneficial transfer algorithm.}, author = {Pentina, Anastasia and Lampert, Christoph}, location = {Montreal, Canada}, pages = {1540 -- 1548}, publisher = {Neural Information Processing Systems}, title = {{Lifelong learning with non-i.i.d. tasks}}, volume = {2015}, year = {2015}, } @inproceedings{1430, abstract = {Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.}, author = {Paixao, Tiago and Sudholt, Dirk and Heredia, Jorge and Trubenova, Barbora}, booktitle = {Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation}, location = {Madrid, Spain}, pages = {1455 -- 1462}, publisher = {ACM}, title = {{First steps towards a runtime comparison of natural and artificial evolution}}, doi = {10.1145/2739480.2754758}, year = {2015}, } @article{14303, abstract = {Scaffolded DNA origami enables the fabrication of a variety of complex nanostructures that promise utility in diverse fields of application, ranging from biosensing over advanced therapeutics to metamaterials. The broad applicability of DNA origami as a material beyond the level of proof-of-concept studies critically depends, among other factors, on the availability of large amounts of pure single-stranded scaffold DNA. Here, we present a method for the efficient production of M13 bacteriophage-derived genomic DNA using high-cell-density fermentation of Escherichia coli in stirred-tank bioreactors. We achieve phage titers of up to 1.6 × 1014 plaque-forming units per mL. Downstream processing yields up to 410 mg of high-quality single-stranded DNA per one liter reaction volume, thus upgrading DNA origami-based nanotechnology from the milligram to the gram scale.}, author = {Kick, B and Praetorius, Florian M and Dietz, H and Weuster-Botz, D}, issn = {1530-6992}, journal = {Nano Letters}, number = {7}, pages = {4672--4676}, publisher = {ACS Publications}, title = {{Efficient production of single-stranded phage DNA as scaffolds for DNA origami}}, doi = {10.1021/acs.nanolett.5b01461}, volume = {15}, year = {2015}, } @misc{1473, abstract = {In this paper we survey geometric and arithmetic techniques to study the cohomology of semiprojective hyperkähler manifolds including toric hyperkähler varieties, Nakajima quiver varieties and moduli spaces of Higgs bundles on Riemann surfaces. The resulting formulae for their Poincaré polynomials are combinatorial and representation theoretical in nature. In particular we will look at their Betti numbers and will establish some results and state some expectations on their asymptotic shape.}, author = {Tamas Hausel and Rodríguez Villegas, Fernando}, booktitle = {Asterisque}, number = {370}, pages = {113 -- 156}, publisher = {Societe Mathematique de France}, title = {{Cohomology of large semiprojective hyperkähler varieties}}, volume = {2015}, year = {2015}, } @inproceedings{1474, abstract = {Cryptographic access control offers selective access to encrypted data via a combination of key management and functionality-rich cryptographic schemes, such as attribute-based encryption. Using this approach, publicly available meta-data may inadvertently leak information on the access policy that is enforced by cryptography, which renders cryptographic access control unusable in settings where this information is highly sensitive. We begin to address this problem by presenting rigorous definitions for policy privacy in cryptographic access control. For concreteness we set our results in the model of Role-Based Access Control (RBAC), where we identify and formalize several different flavors of privacy, however, our framework should serve as inspiration for other models of access control. Based on our insights we propose a new system which significantly improves on the privacy properties of state-of-the-art constructions. Our design is based on a novel type of privacy-preserving attribute-based encryption, which we introduce and show how to instantiate. We present our results in the context of a cryptographic RBAC system by Ferrara et al. (CSF'13), which uses cryptography to control read access to files, while write access is still delegated to trusted monitors. We give an extension of the construction that permits cryptographic control over write access. Our construction assumes that key management uses out-of-band channels between the policy enforcer and the users but eliminates completely the need for monitoring read/write access to the data.}, author = {Ferrara, Anna and Fuchsbauer, Georg and Liu, Bin and Warinschi, Bogdan}, location = {Verona, Italy}, pages = {46--60}, publisher = {IEEE}, title = {{Policy privacy in cryptographic access control}}, doi = {10.1109/CSF.2015.11}, year = {2015}, } @misc{5429, abstract = {We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee). Our main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.}, author = {Chatterjee, Krishnendu and Komarkova, Zuzana and Kretinsky, Jan}, issn = {2664-1690}, pages = {41}, publisher = {IST Austria}, title = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}}, doi = {10.15479/AT:IST-2015-318-v1-1}, year = {2015}, } @misc{5430, abstract = {We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, 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 constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas}, issn = {2664-1690}, pages = {31}, publisher = {IST Austria}, title = {{Faster algorithms for quantitative verification in constant treewidth graphs}}, doi = {10.15479/AT:IST-2015-319-v1-1}, year = {2015}, } @misc{5431, abstract = {We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed. Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential.}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Hansen, Kristoffer}, issn = {2664-1690}, pages = {25}, publisher = {IST Austria}, title = {{The patience of concurrent stochastic games with safety and reachability objectives}}, doi = {10.15479/AT:IST-2015-322-v1-1}, year = {2015}, } @misc{5432, abstract = {Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution.The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time. }, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Nowak, Martin}, issn = {2664-1690}, pages = {29}, publisher = {IST Austria}, title = {{The complexity of evolutionary games on graphs}}, doi = {10.15479/AT:IST-2015-323-v1-1}, year = {2015}, } @misc{5434, abstract = {DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new method to solve the problem that extends methods for finite-horizon DEC- POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show our approach presents promising results.}, author = {Anonymous, 1 and Anonymous, 2}, issn = {2664-1690}, pages = {16}, publisher = {IST Austria}, title = {{Optimal cost indefinite-horizon reachability in goal DEC-POMDPs}}, year = {2015}, } @misc{5435, abstract = {We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee). Our main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.}, author = {Chatterjee, Krishnendu and Komarkova, Zuzana and Kretinsky, Jan}, issn = {2664-1690}, pages = {51}, publisher = {IST Austria}, title = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}}, doi = {10.15479/AT:IST-2015-318-v2-1}, year = {2015}, } @misc{5436, abstract = {Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time. In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan}, issn = {2664-1690}, pages = {29}, publisher = {IST Austria}, title = {{Nested weighted automata}}, doi = {10.15479/AT:IST-2015-170-v2-2}, year = {2015}, }