@inproceedings{1839,
  abstract     = {We present MultiGain, a tool to synthesize strategies for Markov decision processes (MDPs) with multiple mean-payoff objectives. Our models are described in PRISM, and our tool uses the existing interface and simulator of PRISM. Our tool extends PRISM by adding novel algorithms for multiple mean-payoff objectives, and also provides features such as (i) generating strategies and exploring them for simulation, and checking them with respect to other properties; and (ii) generating an approximate Pareto curve for two mean-payoff objectives. In addition, we present a new practical algorithm for the analysis of MDPs with multiple mean-payoff objectives under memoryless strategies.},
  author       = {Brázdil, Tomáš and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín},
  location     = {London, United Kingdom},
  pages        = {181 -- 187},
  publisher    = {Springer},
  title        = {{Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives}},
  doi          = {10.1007/978-3-662-46681-0_12},
  volume       = {9035},
  year         = {2015},
}

@article{1840,
  abstract     = {In this paper, we present a method for reducing a regular, discrete-time Markov chain (DTMC) to another DTMC with a given, typically much smaller number of states. The cost of reduction is defined as the Kullback-Leibler divergence rate between a projection of the original process through a partition function and a DTMC on the correspondingly partitioned state space. Finding the reduced model with minimal cost is computationally expensive, as it requires an exhaustive search among all state space partitions, and an exact evaluation of the reduction cost for each candidate partition. Our approach deals with the latter problem by minimizing an upper bound on the reduction cost instead of minimizing the exact cost. The proposed upper bound is easy to compute and it is tight if the original chain is lumpable with respect to the partition. Then, we express the problem in the form of information bottleneck optimization, and propose using the agglomerative information bottleneck algorithm for searching a suboptimal partition greedily, rather than exhaustively. The theory is illustrated with examples and one application scenario in the context of modeling bio-molecular interactions.},
  author       = {Geiger, Bernhard and Petrov, Tatjana and Kubin, Gernot and Koeppl, Heinz},
  issn         = {0018-9286},
  journal      = {IEEE Transactions on Automatic Control},
  number       = {4},
  pages        = {1010 -- 1022},
  publisher    = {IEEE},
  title        = {{Optimal Kullback-Leibler aggregation via information bottleneck}},
  doi          = {10.1109/TAC.2014.2364971},
  volume       = {60},
  year         = {2015},
}

@article{1841,
  abstract     = {We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diffusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. The new family of algorithms can be viewed as a generalization of TRW-S from pairwise to higher-order graphical models. We test SRMP on several real-world problems with promising results.},
  author       = {Kolmogorov, Vladimir},
  journal      = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  number       = {5},
  pages        = {919 -- 930},
  publisher    = {IEEE},
  title        = {{A new look at reweighted message passing}},
  doi          = {10.1109/TPAMI.2014.2363465},
  volume       = {37},
  year         = {2015},
}

@article{1508,
  abstract     = {We consider generalized Wigner ensembles and general β-ensembles with analytic potentials for any β ≥ 1. The recent universality results in particular assert that the local averages of consecutive eigenvalue gaps in the bulk of the spectrum are universal in the sense that they coincide with those of the corresponding Gaussian β-ensembles. In this article, we show that local averaging is not necessary for this result, i.e. we prove that the single gap distributions in the bulk are universal. In fact, with an additional step, our result can be extended to any C4(ℝ) potential.},
  author       = {Erdös, László and Yau, Horng},
  journal      = {Journal of the European Mathematical Society},
  number       = {8},
  pages        = {1927 -- 2036},
  publisher    = {EMS Press},
  title        = {{Gap universality of generalized Wigner and β ensembles}},
  doi          = {10.4171/JEMS/548},
  volume       = {17},
  year         = {2015},
}

@article{1832,
  abstract     = {Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on the identification of the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof. },
  author       = {Chakraborty, Soham and Henzinger, Thomas A and Sezgin, Ali and Vafeiadis, Viktor},
  journal      = {Logical Methods in Computer Science},
  number       = {1},
  publisher    = {International Federation for Computational Logic},
  title        = {{Aspect-oriented linearizability proofs}},
  doi          = {10.2168/LMCS-11(1:20)2015},
  volume       = {11},
  year         = {2015},
}

@inproceedings{1610,
  abstract     = {The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1,L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 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 pushdown automata 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 deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k.},
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Otop, Jan},
  booktitle    = {42nd International Colloquium on Automata, Languages, and Programming},
  isbn         = {978-3-662-47665-9},
  location     = {Kyoto, Japan},
  number       = {Part II},
  pages        = {121 -- 133},
  publisher    = {Springer Nature},
  title        = {{Edit distance for pushdown automata}},
  doi          = {10.1007/978-3-662-47666-6_10},
  volume       = {9135},
  year         = {2015},
}

@inproceedings{1657,
  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 Komárková, Zuzana and Kretinsky, Jan},
  location     = {Kyoto, Japan},
  pages        = {244 -- 256},
  publisher    = {IEEE},
  title        = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}},
  doi          = {10.1109/LICS.2015.32},
  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{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{5438,
  abstract     = {The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 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 deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k. },
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Otop, Jan},
  issn         = {2664-1690},
  pages        = {15},
  publisher    = {IST Austria},
  title        = {{Edit distance for pushdown automata}},
  doi          = {10.15479/AT:IST-2015-334-v1-1},
  year         = {2015},
}

@inproceedings{1661,
  abstract     = {The computation of the winning set for one-pair Streett objectives and for k-pair Streett objectives in (standard) 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-formed ness of specifications, and the synthesis of reactive systems. We give faster algorithms for the computation of the winning set for (1) one-pair Streett objectives (aka parity-3 problem) in game graphs and (2) for k-pair Streett objectives in graphs. For both problems this represents the first improvement in asymptotic running time in 15 years.},
  author       = {Chatterjee, Krishnendu and Henzinger, Monika H and Loitzenbauer, Veronika},
  booktitle    = {Proceedings - Symposium on Logic in Computer Science},
  location     = {Kyoto, Japan},
  publisher    = {IEEE},
  title        = {{Improved algorithms for one-pair and k-pair Streett objectives}},
  doi          = {10.1109/LICS.2015.34},
  volume       = {2015-July},
  year         = {2015},
}

@article{1566,
  abstract     = {Deposits of misfolded proteins in the human brain are associated with the development of many neurodegenerative diseases. Recent studies show that these proteins have common traits even at the monomer level. Among them, a polyglutamine region that is present in huntingtin is known to exhibit a correlation between the length of the chain and the severity as well as the earliness of the onset of Huntington disease. Here, we apply bias exchange molecular dynamics to generate structures of polyglutamine expansions of several lengths and characterize the resulting independent conformations. We compare the properties of these conformations to those of the standard proteins, as well as to other homopolymeric tracts. We find that, similar to the previously studied polyvaline chains, the set of possible transient folds is much broader than the set of known-to-date folds, although the conformations have different structures. We show that the mechanical stability is not related to any simple geometrical characteristics of the structures. We demonstrate that long polyglutamine expansions result in higher mechanical stability than the shorter ones. They also have a longer life span and are substantially more prone to form knotted structures. The knotted region has an average length of 35 residues, similar to the typical threshold for most polyglutamine-related diseases. Similarly, changes in shape and mechanical stability appear once the total length of the peptide exceeds this threshold of 35 glutamine residues. We suggest that knotted conformers may also harm the cellular machinery and thus lead to disease.},
  author       = {Gómez Sicilia, Àngel and Sikora, Mateusz K and Cieplak, Marek and Carrión Vázquez, Mariano},
  journal      = {PLoS Computational Biology},
  number       = {10},
  publisher    = {Public Library of Science},
  title        = {{An exploration of the universe of polyglutamine structures}},
  doi          = {10.1371/journal.pcbi.1004541},
  volume       = {11},
  year         = {2015},
}

@misc{9714,
  author       = {Gómez Sicilia, Àngel and Sikora, Mateusz K and Cieplak, Marek and Carrión Vázquez, Mariano},
  publisher    = {Public Library of Science},
  title        = {{An exploration of the universe of polyglutamine structures - submission to PLOS journals}},
  doi          = {10.1371/journal.pcbi.1004541.s001},
  year         = {2015},
}

@article{1555,
  abstract     = {We show that incorporating spatial dispersal of individuals into a simple vaccination epidemic model may give rise to a model that exhibits rich dynamical behavior. Using an SIVS (susceptible-infected-vaccinated-susceptible) model as a basis, we describe the spread of an infectious disease in a population split into two regions. In each subpopulation, both forward and backward bifurcations can occur. This implies that for disconnected regions the two-patch system may admit several steady states. We consider traveling between the regions and investigate the impact of spatial dispersal of individuals on the model dynamics. We establish conditions for the existence of multiple nontrivial steady states in the system, and we study the structure of the equilibria. The mathematical analysis reveals an unusually rich dynamical behavior, not normally found in the simple epidemic models. In addition to the disease-free equilibrium, eight endemic equilibria emerge from backward transcritical and saddle-node bifurcation points, forming an interesting bifurcation diagram. Stability of steady states, their bifurcations, and the global dynamics are investigated with analytical tools, numerical simulations, and rigorous set-oriented numerical computations.},
  author       = {Knipl, Diána and Pilarczyk, Pawel and Röst, Gergely},
  issn         = {1536-0040},
  journal      = {SIAM Journal on Applied Dynamical Systems},
  number       = {2},
  pages        = {980 -- 1017},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Rich bifurcation structure in a two patch vaccination model}},
  doi          = {10.1137/140993934},
  volume       = {14},
  year         = {2015},
}

@article{1525,
  abstract     = {Based on 16 recommendations, efforts should be made to achieve the following goal: By 2025, all scholarly publication activity in Austria should be Open Access. In other words, the final versions of all scholarly publications resulting from the support of public resources must be freely accessible on the Internet without delay (Gold Open Access). The resources required to meet this obligation shall be provided to the authors, or the cost of the publication venues shall be borne directly by the research organisations.},
  author       = {Bauer, Bruno and Blechl, Guido and Bock, Christoph and Danowski, Patrick and Ferus, Andreas and Graschopf, Anton and König, Thomas and Mayer, Katja and Reckling, Falk and Rieck, Katharina and Seitz, Peter and Stöger, Herwig and Welzig, Elvira},
  journal      = {VÖB Mitteilungen},
  number       = {3},
  pages        = {580 -- 607},
  publisher    = {Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare},
  title        = {{Arbeitsgruppe „Nationale Strategie“ des Open Access Network Austria OANA}},
  doi          = {10.5281/zenodo.33178},
  volume       = {68},
  year         = {2015},
}

@article{2034,
  abstract     = {Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.},
  author       = {Bérard, Béatrice and Chatterjee, Krishnendu and Sznajder, Nathalie},
  journal      = {Information Processing Letters},
  number       = {1},
  pages        = {52 -- 59},
  publisher    = {Elsevier},
  title        = {{Probabilistic opacity for Markov decision processes}},
  doi          = {10.1016/j.ipl.2014.09.001},
  volume       = {115},
  year         = {2015},
}

@article{1542,
  abstract     = {The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields. },
  author       = {Paixao, Tiago and Badkobeh, Golnaz and Barton, Nicholas H and Çörüş, Doğan and Dang, Duccuong and Friedrich, Tobias and Lehre, Per and Sudholt, Dirk and Sutton, Andrew and Trubenova, Barbora},
  journal      = {Journal of Theoretical Biology},
  pages        = {28 -- 43},
  publisher    = {Elsevier},
  title        = {{Toward a unifying framework for evolutionary processes}},
  doi          = {10.1016/j.jtbi.2015.07.011},
  volume       = {383},
  year         = {2015},
}

@inproceedings{1656,
  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},
  booktitle    = {Proceedings - Symposium on Logic in Computer Science},
  location     = {Kyoto, Japan},
  publisher    = {IEEE},
  title        = {{Nested weighted automata}},
  doi          = {10.1109/LICS.2015.72},
  volume       = {2015-July},
  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},
}

@article{1792,
  abstract     = {Motivated by recent ideas of Harman (Unif. Distrib. Theory, 2010) we develop a new concept of variation of multivariate functions on a compact Hausdorff space with respect to a collection D of subsets. We prove a general version of the Koksma-Hlawka theorem that holds for this notion of variation and discrepancy with respect to D. As special cases, we obtain Koksma-Hlawka inequalities for classical notions, such as extreme or isotropic discrepancy. For extreme discrepancy, our result coincides with the usual Koksma-Hlawka theorem. We show that the space of functions of bounded D-variation contains important discontinuous functions and is closed under natural algebraic operations. Finally, we illustrate the results on concrete integration problems from integral geometry and stereology.},
  author       = {Pausinger, Florian and Svane, Anne},
  journal      = {Journal of Complexity},
  number       = {6},
  pages        = {773 -- 797},
  publisher    = {Academic Press},
  title        = {{A Koksma-Hlawka inequality for general discrepancy systems}},
  doi          = {10.1016/j.jco.2015.06.002},
  volume       = {31},
  year         = {2015},
}