--- _id: '5438' abstract: - lang: eng text: "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.\r\nThe 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. " alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop citation: ama: Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit Distance for Pushdown Automata. IST Austria; 2015. doi:10.15479/AT:IST-2015-334-v1-1 apa: Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit distance for pushdown automata. IST Austria. https://doi.org/10.15479/AT:IST-2015-334-v1-1 chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. Edit Distance for Pushdown Automata. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-334-v1-1. ieee: K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, Edit distance for pushdown automata. IST Austria, 2015. ista: Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p. mla: Chatterjee, Krishnendu, et al. Edit Distance for Pushdown Automata. IST Austria, 2015, doi:10.15479/AT:IST-2015-334-v1-1. short: K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015. date_created: 2018-12-12T11:39:20Z date_published: 2015-05-05T00:00:00Z date_updated: 2023-02-23T12:20:08Z day: '05' ddc: - '004' department: - _id: KrCh doi: 10.15479/AT:IST-2015-334-v1-1 file: - access_level: open_access checksum: 8a5f2d77560e552af87eb1982437a43b content_type: application/pdf creator: system date_created: 2018-12-12T11:53:56Z date_updated: 2020-07-14T12:46:55Z file_id: '5518' file_name: IST-2015-334-v1+1_report.pdf file_size: 422573 relation: main_file file_date_updated: 2020-07-14T12:46:55Z has_accepted_license: '1' language: - iso: eng month: '05' oa: 1 oa_version: Published Version page: '15' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '334' related_material: record: - id: '1610' relation: later_version status: public - id: '465' relation: later_version status: public status: public title: Edit distance for pushdown automata type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '5440' abstract: - lang: eng text: '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 for payoff 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. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. 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 as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive.' alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Chatterjee K, Ibsen-Jensen R, Nowak M. The Complexity of Evolutionary Games on Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-323-v2-2 apa: Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2015). The complexity of evolutionary games on graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-323-v2-2 chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. The Complexity of Evolutionary Games on Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-323-v2-2. ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, The complexity of evolutionary games on graphs. IST Austria, 2015. ista: Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p. mla: Chatterjee, Krishnendu, et al. The Complexity of Evolutionary Games on Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-323-v2-2. short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015. date_created: 2018-12-12T11:39:21Z date_published: 2015-06-16T00:00:00Z date_updated: 2023-02-23T12:26:10Z day: '16' ddc: - '005' - '576' department: - _id: KrCh doi: 10.15479/AT:IST-2015-323-v2-2 file: - access_level: open_access checksum: 66aace7d367032af97c15e35c9be9636 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:23Z date_updated: 2020-07-14T12:46:56Z file_id: '5484' file_name: IST-2015-323-v2+2_main.pdf file_size: 466161 relation: main_file file_date_updated: 2020-07-14T12:46:56Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: '18' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '338' related_material: record: - id: '5421' relation: earlier_version status: public - id: '5432' relation: earlier_version status: public status: public title: The complexity of evolutionary games on graphs type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '5432' abstract: - lang: eng text: "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. \r\nThe 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. \r\nOur main results are:\r\n(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).\r\n(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.\r\n" alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Rasmus full_name: Ibsen-Jensen, Rasmus id: 3B699956-F248-11E8-B48F-1D18A9856A87 last_name: Ibsen-Jensen orcid: 0000-0003-4783-0389 - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Chatterjee K, Ibsen-Jensen R, Nowak M. The Complexity of Evolutionary Games on Graphs. IST Austria; 2015. doi:10.15479/AT:IST-2015-323-v1-1 apa: Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2015). The complexity of evolutionary games on graphs. IST Austria. https://doi.org/10.15479/AT:IST-2015-323-v1-1 chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. The Complexity of Evolutionary Games on Graphs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-323-v1-1. ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, The complexity of evolutionary games on graphs. IST Austria, 2015. ista: Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p. mla: Chatterjee, Krishnendu, et al. The Complexity of Evolutionary Games on Graphs. IST Austria, 2015, doi:10.15479/AT:IST-2015-323-v1-1. short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015. date_created: 2018-12-12T11:39:18Z date_published: 2015-02-19T00:00:00Z date_updated: 2023-02-23T12:26:33Z day: '19' ddc: - '005' - '576' department: - _id: KrCh doi: 10.15479/AT:IST-2015-323-v1-1 file: - access_level: open_access checksum: 546c1b291d545e7b24aaaf4199dac671 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:57Z date_updated: 2020-07-14T12:46:53Z file_id: '5519' file_name: IST-2015-323-v1+1_main.pdf file_size: 576347 relation: main_file file_date_updated: 2020-07-14T12:46:53Z has_accepted_license: '1' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: '29' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '323' related_material: record: - id: '5421' relation: earlier_version status: public - id: '5440' relation: later_version status: public status: public title: The complexity of evolutionary games on graphs type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '5444' abstract: - lang: eng text: A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal. alternative_title: - IST Austria Technical Report author: - first_name: Johannes full_name: Reiter, Johannes id: 4A918E98-F248-11E8-B48F-1D18A9856A87 last_name: Reiter orcid: 0000-0002-0170-7353 - first_name: Alvin full_name: Makohon-Moore, Alvin last_name: Makohon-Moore - first_name: Jeffrey full_name: Gerold, Jeffrey last_name: Gerold - first_name: Ivana full_name: Bozic, Ivana last_name: Bozic - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Christine full_name: Iacobuzio-Donahue, Christine last_name: Iacobuzio-Donahue - first_name: Bert full_name: Vogelstein, Bert last_name: Vogelstein - first_name: Martin full_name: Nowak, Martin last_name: Nowak citation: ama: Reiter J, Makohon-Moore A, Gerold J, et al. Reconstructing Robust Phylogenies of Metastatic Cancers. IST Austria; 2015. doi:10.15479/AT:IST-2015-399-v1-1 apa: Reiter, J., Makohon-Moore, A., Gerold, J., Bozic, I., Chatterjee, K., Iacobuzio-Donahue, C., … Nowak, M. (2015). Reconstructing robust phylogenies of metastatic cancers. IST Austria. https://doi.org/10.15479/AT:IST-2015-399-v1-1 chicago: Reiter, Johannes, Alvin Makohon-Moore, Jeffrey Gerold, Ivana Bozic, Krishnendu Chatterjee, Christine Iacobuzio-Donahue, Bert Vogelstein, and Martin Nowak. Reconstructing Robust Phylogenies of Metastatic Cancers. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-399-v1-1. ieee: J. Reiter et al., Reconstructing robust phylogenies of metastatic cancers. IST Austria, 2015. ista: Reiter J, Makohon-Moore A, Gerold J, Bozic I, Chatterjee K, Iacobuzio-Donahue C, Vogelstein B, Nowak M. 2015. Reconstructing robust phylogenies of metastatic cancers, IST Austria, 25p. mla: Reiter, Johannes, et al. Reconstructing Robust Phylogenies of Metastatic Cancers. IST Austria, 2015, doi:10.15479/AT:IST-2015-399-v1-1. short: J. Reiter, A. Makohon-Moore, J. Gerold, I. Bozic, K. Chatterjee, C. Iacobuzio-Donahue, B. Vogelstein, M. Nowak, Reconstructing Robust Phylogenies of Metastatic Cancers, IST Austria, 2015. date_created: 2018-12-12T11:39:22Z date_published: 2015-12-30T00:00:00Z date_updated: 2020-07-14T23:05:07Z day: '30' ddc: - '000' - '576' department: - _id: KrCh doi: 10.15479/AT:IST-2015-399-v1-1 file: - access_level: open_access checksum: c47d33bdda06181753c0af36f16e7b5d content_type: application/pdf creator: system date_created: 2018-12-12T11:53:24Z date_updated: 2020-07-14T12:46:58Z file_id: '5485' file_name: IST-2015-399-v1+1_treeomics.pdf file_size: 3533200 relation: main_file file_date_updated: 2020-07-14T12:46:58Z has_accepted_license: '1' language: - iso: eng month: '12' oa: 1 oa_version: Published Version page: '25' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '399' status: public title: Reconstructing robust phylogenies of metastatic cancers type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '5443' abstract: - lang: eng text: POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Martin full_name: Chmelik, Martin id: 3624234E-F248-11E8-B48F-1D18A9856A87 last_name: Chmelik - first_name: Jessica full_name: Davies, Jessica id: 378E0060-F248-11E8-B48F-1D18A9856A87 last_name: Davies citation: ama: Chatterjee K, Chmelik M, Davies J. A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs. IST Austria; 2015. doi:10.15479/AT:IST-2015-325-v2-1 apa: Chatterjee, K., Chmelik, M., & Davies, J. (2015). A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs. IST Austria. https://doi.org/10.15479/AT:IST-2015-325-v2-1 chicago: Chatterjee, Krishnendu, Martin Chmelik, and Jessica Davies. A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-325-v2-1. ieee: K. Chatterjee, M. Chmelik, and J. Davies, A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs. IST Austria, 2015. ista: Chatterjee K, Chmelik M, Davies J. 2015. A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs, IST Austria, 23p. mla: Chatterjee, Krishnendu, et al. A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs. IST Austria, 2015, doi:10.15479/AT:IST-2015-325-v2-1. short: K. Chatterjee, M. Chmelik, J. Davies, A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs, IST Austria, 2015. date_created: 2018-12-12T11:39:22Z date_published: 2015-11-06T00:00:00Z date_updated: 2023-02-21T16:24:05Z day: '06' ddc: - '000' department: - _id: KrCh doi: 10.15479/AT:IST-2015-325-v2-1 file: - access_level: open_access checksum: f0fa31ad8161ed655137e94012123ef9 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:05Z date_updated: 2020-07-14T12:46:57Z file_id: '5466' file_name: IST-2015-325-v2+1_main.pdf file_size: 412379 relation: main_file file_date_updated: 2020-07-14T12:46:57Z has_accepted_license: '1' language: - iso: eng month: '11' oa: 1 oa_version: Published Version page: '23' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '362' related_material: record: - id: '1166' relation: later_version status: public status: public title: A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ...