@phdthesis{992, abstract = {An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of variables, a finite domain of labels, and a set of constraints, each constraint acting on a subset of the variables. The goal is to find an assignment of labels to its variables that satisfies all constraints (or decide whether one exists). If we allow more general “soft” constraints, which come with (possibly infinite) costs of particular assignments, we obtain instances from a richer class called Valued Constraint Satisfaction Problem (VCSP). There the goal is to find an assignment with minimum total cost. In this thesis, we focus (assuming that P 6 = NP) on classifying computational com- plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core content of the work. In one of them, we consider VCSPs parametrized by a constraint language, that is the set of “soft” constraints allowed to form the instances, and finish the complexity classification modulo (missing pieces of) complexity classification for analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect matching algorithm. This generalization contributes to complexity classfications in two ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean CSPs in which every variable may appear in at most two constraints and second, it settles full classification of Boolean CSPs with planar drawing (again parametrized by a constraint language).}, author = {Rolinek, Michal}, issn = {2663-337X}, pages = {97}, publisher = {Institute of Science and Technology Austria}, title = {{Complexity of constraint satisfaction}}, doi = {10.15479/AT:ISTA:th_815}, year = {2017}, } @article{993, abstract = {In real-world applications, observations are often constrained to a small fraction of a system. Such spatial subsampling can be caused by the inaccessibility or the sheer size of the system, and cannot be overcome by longer sampling. Spatial subsampling can strongly bias inferences about a system’s aggregated properties. To overcome the bias, we derive analytically a subsampling scaling framework that is applicable to different observables, including distributions of neuronal avalanches, of number of people infected during an epidemic outbreak, and of node degrees. We demonstrate how to infer the correct distributions of the underlying full system, how to apply it to distinguish critical from subcritical systems, and how to disentangle subsampling and finite size effects. Lastly, we apply subsampling scaling to neuronal avalanche models and to recordings from developing neural networks. We show that only mature, but not young networks follow power-law scaling, indicating self-organization to criticality during development.}, author = {Levina (Martius), Anna and Priesemann, Viola}, issn = {20411723}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Subsampling scaling}}, doi = {10.1038/ncomms15140}, volume = {8}, year = {2017}, } @article{994, abstract = {The formation of vortices is usually considered to be the main mechanism of angular momentum disposal in superfluids. Recently, it was predicted that a superfluid can acquire angular momentum via an alternative, microscopic route -- namely, through interaction with rotating impurities, forming so-called `angulon quasiparticles' [Phys. Rev. Lett. 114, 203001 (2015)]. The angulon instabilities correspond to transfer of a small number of angular momentum quanta from the impurity to the superfluid, as opposed to vortex instabilities, where angular momentum is quantized in units of ℏ per atom. Furthermore, since conventional impurities (such as molecules) represent three-dimensional (3D) rotors, the angular momentum transferred is intrinsically 3D as well, as opposed to a merely planar rotation which is inherent to vortices. Herein we show that the angulon theory can explain the anomalous broadening of the spectroscopic lines observed for CH 3 and NH 3 molecules in superfluid helium nanodroplets, thereby providing a fingerprint of the emerging angulon instabilities in experiment.}, author = {Cherepanov, Igor and Lemeshko, Mikhail}, journal = {Physical Review Materials}, number = {3}, publisher = {American Physical Society}, title = {{Fingerprints of angulon instabilities in the spectra of matrix-isolated molecules}}, doi = {10.1103/PhysRevMaterials.1.035602}, volume = {1}, year = {2017}, } @article{995, abstract = {Recently it was shown that an impurity exchanging orbital angular momentum with a surrounding bath can be described in terms of the angulon quasiparticle [Phys. Rev. Lett. 118, 095301 (2017)]. The angulon consists of a quantum rotor dressed by a many-particle field of boson excitations, and can be formed out of, for example, a molecule or a nonspherical atom in superfluid helium, or out of an electron coupled to lattice phonons or a Bose condensate. Here we develop an approach to the angulon based on the path-integral formalism, which sets the ground for a systematic, perturbative treatment of the angulon problem. The resulting perturbation series can be interpreted in terms of Feynman diagrams, from which, in turn, one can derive a set of diagrammatic rules. These rules extend the machinery of the graphical theory of angular momentum - well known from theoretical atomic spectroscopy - to the case where an environment with an infinite number of degrees of freedom is present. In particular, we show that each diagram can be interpreted as a 'skeleton', which enforces angular momentum conservation, dressed by an additional many-body contribution. This connection between the angulon theory and the graphical theory of angular momentum is particularly important as it allows to systematically and substantially simplify the analytical representation of each diagram. In order to exemplify the technique, we calculate the 1- and 2-loop contributions to the angulon self-energy, the spectral function, and the quasiparticle weight. The diagrammatic theory we develop paves the way to investigate next-to-leading order quantities in a more compact way compared to the variational approaches.}, author = {Bighin, Giacomo and Lemeshko, Mikhail}, issn = {24699950}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {8}, publisher = {American Physical Society}, title = {{Diagrammatic approach to orbital quantum impurities interacting with a many-particle environment}}, doi = {10.1103/PhysRevB.96.085410}, volume = {96}, year = {2017}, } @article{996, abstract = {Iodine (I 2 ) molecules embedded in He nanodroplets are aligned by a 160 ps long laser pulse. The highest degree of alignment, occurring at the peak of the pulse and quantified by ⟨cos 2 θ 2D ⟩ , is measured as a function of the laser intensity. The results are well described by ⟨cos 2 θ 2D ⟩ calculated for a gas of isolated molecules each with an effective rotational constant of 0.6 times the gas-phase value, and at a temperature of 0.4 K. Theoretical analysis using the angulon quasiparticle to describe rotating molecules in superfluid helium rationalizes why the alignment mechanism is similar to that of isolated molecules with an effective rotational constant. A major advantage of molecules in He droplets is that their 0.4 K temperature leads to stronger alignment than what can generally be achieved for gas phase molecules -- here demonstrated by a direct comparison of the droplet results to measurements on a ∼ 1 K supersonic beam of isolated molecules. This point is further illustrated for more complex system by measurements on 1,4-diiodobenzene and 1,4-dibromobenzene. For all three molecular species studied the highest values of ⟨cos 2 θ 2D ⟩ achieved in He droplets exceed 0.96. }, author = {Shepperson, Benjamin and Chatterley, Adam and Søndergaard, Anders and Christiansen, Lars and Lemeshko, Mikhail and Stapelfeldt, Henrik}, issn = {00219606}, journal = {The Journal of Chemical Physics}, number = {1}, publisher = {AIP Publishing}, title = {{Strongly aligned molecules inside helium droplets in the near-adiabatic regime}}, doi = {10.1063/1.4983703}, volume = {147}, year = {2017}, } @article{997, abstract = {Recently it was shown that molecules rotating in superfluid helium can be described in terms of the angulon quasiparticles (Phys. Rev. Lett. 118, 095301 (2017)). Here we demonstrate that in the experimentally realized regime the angulon can be seen as a point charge on a 2-sphere interacting with a gauge field of a non-abelian magnetic monopole. Unlike in several other settings, the gauge fields of the angulon problem emerge in the real coordinate space, as opposed to the momentum space or some effective parameter space. Furthermore, we find a topological transition associated with making the monopole abelian, which takes place in the vicinity of the previously reported angulon instabilities. These results pave the way for studying topological phenomena in experiments on molecules trapped in superfluid helium nanodroplets, as well as on other realizations of orbital impurity problems.}, author = {Yakaboylu, Enderalp and Deuchert, Andreas and Lemeshko, Mikhail}, issn = {0031-9007}, journal = {Physical Review Letters}, number = {23}, publisher = {American Physical Society}, title = {{Emergence of non-abelian magnetic monopoles in a quantum impurity problem}}, doi = {10.1103/PhysRevLett.119.235301}, volume = {119}, year = {2017}, } @inproceedings{998, abstract = {A major open problem on the road to artificial intelligence is the development of incrementally learning systems that learn about more and more concepts over time from a stream of data. In this work, we introduce a new training strategy, iCaRL, that allows learning in such a class-incremental way: only the training data for a small number of classes has to be present at the same time and new classes can be added progressively. iCaRL learns strong classifiers and a data representation simultaneously. This distinguishes it from earlier works that were fundamentally limited to fixed data representations and therefore incompatible with deep learning architectures. We show by experiments on CIFAR-100 and ImageNet ILSVRC 2012 data that iCaRL can learn many classes incrementally over a long period of time where other strategies quickly fail. }, author = {Rebuffi, Sylvestre Alvise and Kolesnikov, Alexander and Sperl, Georg and Lampert, Christoph}, isbn = {978-153860457-1}, location = {Honolulu, HA, United States}, pages = {5533 -- 5542}, publisher = {IEEE}, title = {{iCaRL: Incremental classifier and representation learning}}, doi = {10.1109/CVPR.2017.587}, volume = {2017}, year = {2017}, } @inproceedings{999, abstract = {In multi-task learning, a learner is given a collection of prediction tasks and needs to solve all of them. In contrast to previous work, which required that annotated training data must be available for all tasks, we consider a new setting, in which for some tasks, potentially most of them, only unlabeled training data is provided. Consequently, to solve all tasks, information must be transferred between tasks with labels and tasks without labels. Focusing on an instance-based transfer method we analyze two variants of this setting: when the set of labeled tasks is fixed, and when it can be actively selected by the learner. We state and prove a generalization bound that covers both scenarios and derive from it an algorithm for making the choice of labeled tasks (in the active case) and for transferring information between the tasks in a principled way. We also illustrate the effectiveness of the algorithm on synthetic and real data. }, author = {Pentina, Anastasia and Lampert, Christoph}, isbn = {9781510855144}, location = {Sydney, Australia}, pages = {2807 -- 2816}, publisher = {ML Research Press}, title = {{Multi-task learning with labeled and unlabeled tasks}}, volume = {70}, year = {2017}, } @inbook{424, abstract = {We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b, d) such that the following holds. If F is a finite family of subsets of Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤ i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced Z2-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these [d/2] first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map C*(K)→C*(Rd).}, author = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli}, booktitle = {A Journey through Discrete Mathematics: A Tribute to Jiri Matousek}, editor = {Loebl, Martin and Nešetřil, Jaroslav and Thomas, Robin}, isbn = {978-331944479-6}, pages = {407 -- 447}, publisher = {Springer}, title = {{Bounding helly numbers via betti numbers}}, doi = {10.1007/978-3-319-44479-6_17}, year = {2017}, } @inproceedings{431, abstract = {Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to its excellent scalability properties. A fundamental barrier when parallelizing SGD is the high bandwidth cost of communicating gradient updates between nodes; consequently, several lossy compresion heuristics have been proposed, by which nodes only communicate quantized gradients. Although effective in practice, these heuristics do not always converge. In this paper, we propose Quantized SGD (QSGD), a family of compression schemes with convergence guarantees and good practical performance. QSGD allows the user to smoothly trade off communication bandwidth and convergence time: nodes can adjust the number of bits sent per iteration, at the cost of possibly higher variance. We show that this trade-off is inherent, in the sense that improving it past some threshold would violate information-theoretic lower bounds. QSGD guarantees convergence for convex and non-convex objectives, under asynchrony, and can be extended to stochastic variance-reduced techniques. When applied to training deep neural networks for image classification and automated speech recognition, QSGD leads to significant reductions in end-to-end training time. For instance, on 16GPUs, we can train the ResNet-152 network to full accuracy on ImageNet 1.8 × faster than the full-precision variant. }, author = {Alistarh, Dan-Adrian and Grubic, Demjan and Li, Jerry and Tomioka, Ryota and Vojnović, Milan}, issn = {10495258}, location = {Long Beach, CA, United States}, pages = {1710--1721}, publisher = {Neural Information Processing Systems Foundation}, title = {{QSGD: Communication-efficient SGD via gradient quantization and encoding}}, volume = {2017}, year = {2017}, } @inproceedings{432, abstract = {Recently there has been significant interest in training machine-learning models at low precision: by reducing precision, one can reduce computation and communication by one order of magnitude. We examine training at reduced precision, both from a theoretical and practical perspective, and ask: is it possible to train models at end-to-end low precision with provable guarantees? Can this lead to consistent order-of-magnitude speedups? We mainly focus on linear models, and the answer is yes for linear models. We develop a simple framework called ZipML based on one simple but novel strategy called double sampling. Our ZipML framework is able to execute training at low precision with no bias, guaranteeing convergence, whereas naive quanti- zation would introduce significant bias. We val- idate our framework across a range of applica- tions, and show that it enables an FPGA proto- type that is up to 6.5 × faster than an implemen- tation using full 32-bit precision. We further de- velop a variance-optimal stochastic quantization strategy and show that it can make a significant difference in a variety of settings. When applied to linear models together with double sampling, we save up to another 1.7 × in data movement compared with uniform quantization. When training deep networks with quantized models, we achieve higher accuracy than the state-of-the- art XNOR-Net. }, author = {Zhang, Hantian and Li, Jerry and Kara, Kaan and Alistarh, Dan-Adrian and Liu, Ji and Zhang, Ce}, booktitle = {Proceedings of Machine Learning Research}, isbn = {978-151085514-4}, location = {Sydney, Australia}, pages = {4035 -- 4043}, publisher = {ML Research Press}, title = {{ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning}}, volume = { 70}, year = {2017}, } @inbook{444, abstract = {Complex I (NADH:ubiquinone oxidoreductase) plays a central role in cellular energy generation, contributing to the proton motive force used to produce ATP. It couples the transfer of two electrons between NADH and quinone to translocation of four protons across the membrane. It is the largest protein assembly of bacterial and mitochondrial respiratory chains, composed, in mammals, of up to 45 subunits with a total molecular weight of ∼1 MDa. Bacterial enzyme is about half the size, providing the important “minimal” model of complex I. The l-shaped complex consists of a hydrophilic arm, where electron transfer occurs, and a membrane arm, where proton translocation takes place. Previously, we have solved the crystal structures of the hydrophilic domain of complex I from Thermus thermophilus and of the membrane domain from Escherichia coli, followed by the atomic structure of intact, entire complex I from T. thermophilus. Recently, we have solved by cryo-EM a first complete atomic structure of mammalian (ovine) mitochondrial complex I. Core subunits are well conserved from the bacterial version, whilst supernumerary subunits form an interlinked, stabilizing shell around the core. Subunits containing additional cofactors, including Zn ion, NADPH and phosphopantetheine, probably have regulatory roles. Dysfunction of mitochondrial complex I is implicated in many human neurodegenerative diseases. The structure of mammalian enzyme provides many insights into complex I mechanism, assembly, maturation and dysfunction, allowing detailed molecular analysis of disease-causing mutations.}, author = {Sazanov, Leonid A}, booktitle = {Mechanisms of primary energy transduction in biology }, editor = {Wikström, Mårten}, isbn = {978-1-78262-865-1}, pages = {25 -- 59}, publisher = {Royal Society of Chemistry}, title = {{Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions}}, doi = {10.1039/9781788010405-00025}, year = {2017}, } @article{447, abstract = {We consider last passage percolation (LPP) models with exponentially distributed random variables, which are linked to the totally asymmetric simple exclusion process (TASEP). The competition interface for LPP was introduced and studied in Ferrari and Pimentel (2005a) for cases where the corresponding exclusion process had a rarefaction fan. Here we consider situations with a shock and determine the law of the fluctuations of the competition interface around its deter- ministic law of large number position. We also study the multipoint distribution of the LPP around the shock, extending our one-point result of Ferrari and Nejjar (2015).}, author = {Ferrari, Patrik and Nejjar, Peter}, journal = {Revista Latino-Americana de Probabilidade e Estatística}, pages = {299 -- 325}, publisher = {Instituto Nacional de Matematica Pura e Aplicada}, title = {{Fluctuations of the competition interface in presence of shocks}}, doi = {10.30757/ALEA.v14-17}, volume = {9}, year = {2017}, } @article{453, abstract = {Most kinesin motors move in only one direction along microtubules. Members of the kinesin-5 subfamily were initially described as unidirectional plus-end-directed motors and shown to produce piconewton forces. However, some fungal kinesin-5 motors are bidirectional. The force production of a bidirectional kinesin-5 has not yet been measured. Therefore, it remains unknown whether the mechanism of the unconventional minus-end-directed motility differs fundamentally from that of plus-end-directed stepping. Using force spectroscopy, we have measured here the forces that ensembles of purified budding yeast kinesin-5 Cin8 produce in microtubule gliding assays in both plus- and minus-end direction. Correlation analysis of pause forces demonstrated that individual Cin8 molecules produce additive forces in both directions of movement. In ensembles, Cin8 motors were able to produce single-motor forces up to a magnitude of ∼1.5 pN. Hence, these properties appear to be conserved within the kinesin-5 subfamily. Force production was largely independent of the directionality of movement, indicating similarities between the motility mechanisms for both directions. These results provide constraints for the development of models for the bidirectional motility mechanism of fission yeast kinesin-5 and provide insight into the function of this mitotic motor.}, author = {Fallesen, Todd and Roostalu, Johanna and Düllberg, Christian F and Pruessner, Gunnar and Surrey, Thomas}, journal = {Biophysical Journal}, number = {9}, pages = {2055 -- 2067}, publisher = {Biophysical Society}, title = {{Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement}}, doi = {10.1016/j.bpj.2017.09.006}, volume = {113}, year = {2017}, } @article{459, abstract = {The social insects bees, wasps, ants, and termites are species-rich, occur in many habitats, and often constitute a large part of the biomass. Many are also invasive, including species of termites, the red imported fire ant, and the Argentine ant. While invasive social insects have been a problem in Southern Europe for some time, Central Europa was free of invasive ant species until recently because most ants are adapted to warmer climates. Only in the 1990s, did Lasius neglectus, a close relative of the common black garden ant, arrive in Germany. First described in 1990 based on individuals collected in Budapest, the species has since been detected for example in France, Germany, Spain, England, and Kyrgyzstan. The species is spread with soil during construction work or plantings, and L. neglectus therefore is often found in parks and botanical gardens. Another invasive ant now spreading in southern Germany is Formica fuscocinerea, which occurs along rivers, including in the sandy floodplains of the river Isar. As is typical of pioneer species, F. fuscocinerea quickly becomes extremely abundant and therefore causes problems for example on playgrounds in Munich. All invasive ant species are characterized by cooperation across nests, leading to strongly interconnected, very large super-colonies. The resulting dominance results in the extinction of native ant species as well as other arthropod species and thus in the reduction of biodiversity.}, author = {Cremer, Sylvia}, issn = {2366-2875}, journal = {Rundgespräche Forum Ökologie}, pages = {105 -- 116}, publisher = {Verlag Dr. Friedrich Pfeil}, title = {{Invasive Ameisen in Europa: Wie sie sich ausbreiten und die heimische Fauna verändern}}, volume = {46}, year = {2017}, } @article{463, abstract = {We investigate transient behaviors induced by magnetic fields on the dynamics of the flow of a ferrofluid in the gap between two concentric, independently rotating cylinders. Without applying any magnetic fields, we uncover emergence of flow states constituted by a combination of a localized spiral state (SPIl) in the top and bottom of the annulus and different multi-cell flow states (SPI2v, SPI3v) with toroidally closed vortices in the interior of the bulk (SPIl+2v = SPIl + SPI2v and SPIl+3v = SPIl + SPI3v). However, when a magnetic field is presented, we observe the transient behaviors between multi-cell states passing through two critical thresholds in a strength of an axial (transverse) magnetic field. Before the first critical threshold of a magnetic field strength, multi-stable states with different number of cells could be observed. After the first critical threshold, we find the transient behavior between the three- and two-cell flow states. For more strength of magnetic field or after the second critical threshold, we discover that multi-cell states are disappeared and a localized spiral state remains to be stimulated. The studied transient behavior could be understood by the investigation of various quantities including a modal kinetic energy, a mode amplitude of the radial velocity, wavenumber, angular momentum, and torque. In addition, the emergence of new flow states and the transient behavior between their states in ferrofluidic flows indicate that richer and potentially controllable dynamics through magnetic fields could be possible in ferrofluic flow.}, author = {Altmeyer, Sebastian and Do, Younghae and Ryu, Soorok}, issn = {10541500}, journal = {Chaos}, number = {11}, publisher = {AIP Publishing}, title = {{Transient behavior between multi-cell flow states in ferrofluidic Taylor-Couette flow}}, doi = {10.1063/1.5002771}, volume = {27}, year = {2017}, } @article{464, abstract = {The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formedness of specifications, and the synthesis of reactive systems. We show how to compute the winning set on n vertices for (1) parity-3 (aka one-pair Streett) objectives in game graphs in time O(n5/2) and for (2) k-pair Streett objectives in graphs in time O(n2+nklogn). For both problems this gives faster algorithms for dense graphs and represents the first improvement in asymptotic running time in 15 years.}, author = {Chatterjee, Krishnendu and Henzinger, Monika H and Loitzenbauer, Veronika}, issn = {1860-5974}, journal = {Logical Methods in Computer Science}, number = {3}, publisher = {International Federation of Computational Logic}, title = {{Improved algorithms for parity and Streett objectives}}, doi = {10.23638/LMCS-13(3:26)2017}, volume = {13}, year = {2017}, } @article{465, abstract = {The edit distance between two words w 1 , w 2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w 1 to w 2 . The edit distance generalizes to languages L 1 , L 2 , where the edit distance from L 1 to L 2 is the minimal number k such that for every word from L 1 there exists a word in L 2 with edit distance at most k . We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for the following problems: (1) deciding whether, for a given threshold k , the edit distance from a pushdown automaton to a finite automaton is at most k , and (2) deciding whether the edit distance from a pushdown automaton to a finite automaton is finite. }, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Otop, Jan}, issn = {18605974}, journal = {Logical Methods in Computer Science}, number = {3}, publisher = {International Federation of Computational Logic}, title = {{Edit distance for pushdown automata}}, doi = {10.23638/LMCS-13(3:23)2017}, volume = {13}, year = {2017}, } @article{466, abstract = {We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist 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 optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems 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. Second, 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 Křetínská, Zuzana and Kretinsky, Jan}, issn = {18605974}, journal = {Logical Methods in Computer Science}, number = {2}, publisher = {International Federation of Computational Logic}, title = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}}, doi = {10.23638/LMCS-13(2:15)2017}, volume = {13}, year = {2017}, } @article{467, 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 or in any other known 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 runtime 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 = {15293785}, journal = {ACM Transactions on Computational Logic (TOCL)}, number = {4}, publisher = {ACM}, title = {{Nested weighted automata}}, doi = {10.1145/3152769}, volume = {18}, year = {2017}, }