--- _id: '2295' abstract: - lang: eng text: We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal EXPTIME-complete complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite-memory strategies. We also establish asymptotically optimal (exponential) memory bounds. alternative_title: - LIPIcs 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: Mathieu full_name: Tracol, Mathieu id: 3F54FA38-F248-11E8-B48F-1D18A9856A87 last_name: Tracol citation: ama: Chatterjee K, Chmelik M, Tracol M. What is decidable about partially observable Markov decision processes with omega-regular objectives. 2013;23:165-180. doi:10.4230/LIPIcs.CSL.2013.165 apa: 'Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable about partially observable Markov decision processes with omega-regular objectives. Presented at the CSL: Computer Science Logic, Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2013.165' chicago: Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. “What Is Decidable about Partially Observable Markov Decision Processes with Omega-Regular Objectives.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.165. ieee: K. Chatterjee, M. Chmelik, and M. Tracol, “What is decidable about partially observable Markov decision processes with omega-regular objectives,” vol. 23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 165–180, 2013. ista: Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with omega-regular objectives. 23, 165–180. mla: Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable Markov Decision Processes with Omega-Regular Objectives. Vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 165–80, doi:10.4230/LIPIcs.CSL.2013.165. short: K. Chatterjee, M. Chmelik, M. Tracol, 23 (2013) 165–180. conference: end_date: 2013-09-05 location: Torino, Italy name: 'CSL: Computer Science Logic' start_date: 2013-09-02 date_created: 2018-12-11T11:56:50Z date_published: 2013-08-27T00:00:00Z date_updated: 2023-02-23T12:24:38Z day: '27' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.CSL.2013.165 ec_funded: 1 file: - access_level: open_access checksum: ba2828322955574d9283bea0e17a37a6 content_type: application/pdf creator: system date_created: 2018-12-12T10:09:42Z date_updated: 2020-07-14T12:45:37Z file_id: '4766' file_name: IST-2017-756-v1+1_2.pdf file_size: 345171 relation: main_file file_date_updated: 2020-07-14T12:45:37Z has_accepted_license: '1' intvolume: ' 23' language: - iso: eng month: '08' oa: 1 oa_version: Published Version page: 165 - 180 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '4633' pubrep_id: '756' quality_controlled: '1' related_material: record: - id: '1477' relation: later_version status: public - id: '5400' relation: earlier_version status: public scopus_import: 1 series_title: Leibniz International Proceedings in Informatics status: public title: What is decidable about partially observable Markov decision processes with omega-regular objectives tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 23 year: '2013' ... --- _id: '5403' abstract: - lang: eng text: 'We consider concurrent games played by two-players on a finite state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to every transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of mean-payoff games) that is not known to be in polynomial time.' 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 citation: ama: Chatterjee K, Ibsen-Jensen R. Qualitative Analysis of Concurrent Mean-Payoff Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-126-v1-1 apa: Chatterjee, K., & Ibsen-Jensen, R. (2013). Qualitative analysis of concurrent mean-payoff games. IST Austria. https://doi.org/10.15479/AT:IST-2013-126-v1-1 chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. Qualitative Analysis of Concurrent Mean-Payoff Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-126-v1-1. ieee: K. Chatterjee and R. Ibsen-Jensen, Qualitative analysis of concurrent mean-payoff games. IST Austria, 2013. ista: Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff games, IST Austria, 33p. mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. Qualitative Analysis of Concurrent Mean-Payoff Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-126-v1-1. short: K. Chatterjee, R. Ibsen-Jensen, Qualitative Analysis of Concurrent Mean-Payoff Games, IST Austria, 2013. date_created: 2018-12-12T11:39:08Z date_published: 2013-07-03T00:00:00Z date_updated: 2023-02-23T12:22:53Z day: '03' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2013-126-v1-1 file: - access_level: open_access checksum: 063868c665beec37bf28160e2a695746 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:49Z date_updated: 2020-07-14T12:46:45Z file_id: '5510' file_name: IST-2013-126-v1+1_soda_full.pdf file_size: 434523 relation: main_file file_date_updated: 2020-07-14T12:46:45Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '33' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '126' related_material: record: - id: '524' relation: later_version status: public status: public title: Qualitative analysis of concurrent mean-payoff games type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5402' abstract: - lang: eng text: "Linearizability requires that the outcome of calls by competing threads to a concurrent data structure is the same as some sequential execution where each thread has exclusive access to the data structure. In an ordered data structure, such as a queue or a stack, linearizability is ensured by requiring threads commit in the order dictated by the sequential semantics of the data structure; e.g., in a concurrent queue implementation a dequeue can only remove the oldest element. \r\nIn this paper, we investigate the impact of this strict ordering, by comparing what linearizability allows to what existing implementations do. We first give an operational definition for linearizability which allows us to build the most general linearizable implementation as a transition system for any given sequential specification. We then use this operational definition to categorize linearizable implementations based on whether they are bound or free. In a bound implementation, whenever all threads observe the same logical state, the updates to the logical state and the temporal order of commits coincide. All existing queue implementations we know of are bound. We then proceed to present, to the best of our knowledge, the first ever free queue implementation. Our experiments show that free implementations have the potential for better performance by suffering less from contention." alternative_title: - IST Austria Technical Report author: - 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: Ali full_name: Sezgin, Ali id: 4C7638DA-F248-11E8-B48F-1D18A9856A87 last_name: Sezgin citation: ama: Henzinger TA, Sezgin A. How Free Is Your Linearizable Concurrent Data Structure? IST Austria; 2013. doi:10.15479/AT:IST-2013-123-v1-1 apa: Henzinger, T. A., & Sezgin, A. (2013). How free is your linearizable concurrent data structure? IST Austria. https://doi.org/10.15479/AT:IST-2013-123-v1-1 chicago: Henzinger, Thomas A, and Ali Sezgin. How Free Is Your Linearizable Concurrent Data Structure? IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-123-v1-1. ieee: T. A. Henzinger and A. Sezgin, How free is your linearizable concurrent data structure? IST Austria, 2013. ista: Henzinger TA, Sezgin A. 2013. How free is your linearizable concurrent data structure?, IST Austria, 16p. mla: Henzinger, Thomas A., and Ali Sezgin. How Free Is Your Linearizable Concurrent Data Structure? IST Austria, 2013, doi:10.15479/AT:IST-2013-123-v1-1. short: T.A. Henzinger, A. Sezgin, How Free Is Your Linearizable Concurrent Data Structure?, IST Austria, 2013. date_created: 2018-12-12T11:39:07Z date_published: 2013-06-12T00:00:00Z date_updated: 2020-07-14T23:04:47Z day: '12' ddc: - '000' - '004' department: - _id: ToHe doi: 10.15479/AT:IST-2013-123-v1-1 file: - access_level: open_access checksum: ce580605ae9756a8c99d7b403ebb8eed content_type: application/pdf creator: system date_created: 2018-12-12T11:53:19Z date_updated: 2020-07-14T12:46:45Z file_id: '5480' file_name: IST-2013-123-v1+1_main-concur2013.pdf file_size: 249790 relation: main_file file_date_updated: 2020-07-14T12:46:45Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: '16' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '123' status: public title: How free is your linearizable concurrent data structure? type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5400' abstract: - lang: eng text: We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish asymptotically optimal (exponential) memory bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. 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: Mathieu full_name: Tracol, Mathieu id: 3F54FA38-F248-11E8-B48F-1D18A9856A87 last_name: Tracol citation: ama: Chatterjee K, Chmelik M, Tracol M. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria; 2013. doi:10.15479/AT:IST-2013-109-v1-1 apa: Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable about partially observable Markov decision processes with ω-regular objectives. IST Austria. https://doi.org/10.15479/AT:IST-2013-109-v1-1 chicago: Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-109-v1-1. ieee: K. Chatterjee, M. Chmelik, and M. Tracol, What is decidable about partially observable Markov decision processes with ω-regular objectives. IST Austria, 2013. ista: Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially observable Markov decision processes with ω-regular objectives, IST Austria, 41p. mla: Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives. IST Austria, 2013, doi:10.15479/AT:IST-2013-109-v1-1. short: K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013. date_created: 2018-12-12T11:39:07Z date_published: 2013-02-20T00:00:00Z date_updated: 2023-02-23T10:36:45Z day: '20' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2013-109-v1-1 file: - access_level: open_access checksum: cbba40210788a1b22c6cf06433b5ed6f content_type: application/pdf creator: system date_created: 2018-12-12T11:53:06Z date_updated: 2020-07-14T12:46:44Z file_id: '5467' file_name: IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf file_size: 483407 relation: main_file file_date_updated: 2020-07-14T12:46:44Z has_accepted_license: '1' language: - iso: eng month: '02' oa: 1 oa_version: Published Version page: '41' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '109' related_material: record: - id: '1477' relation: later_version status: public - id: '2295' relation: later_version status: public status: public title: What is decidable about partially observable Markov decision processes with ω-regular objectives type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5404' abstract: - lang: eng text: 'We study finite-state two-player (zero-sum) concurrent mean-payoff games played on a graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lie in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP and coNP is the long-standing best known bound). We show that the exact value can be expressed in the existential theory of the reals, and also establish square-root sum hardness for a related class of games.' 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 citation: ama: Chatterjee K, Ibsen-Jensen R. The Complexity of Ergodic Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-127-v1-1 apa: Chatterjee, K., & Ibsen-Jensen, R. (2013). The complexity of ergodic games. IST Austria. https://doi.org/10.15479/AT:IST-2013-127-v1-1 chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-127-v1-1. ieee: K. Chatterjee and R. Ibsen-Jensen, The complexity of ergodic games. IST Austria, 2013. ista: Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria, 29p. mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-127-v1-1. short: K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria, 2013. date_created: 2018-12-12T11:39:08Z date_published: 2013-07-03T00:00:00Z date_updated: 2023-02-23T10:30:55Z day: '03' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2013-127-v1-1 file: - access_level: open_access checksum: 79ee5e677a82611ce06e0360c69d494a content_type: application/pdf creator: system date_created: 2018-12-12T11:53:35Z date_updated: 2020-07-14T12:46:45Z file_id: '5496' file_name: IST-2013-127-v1+1_ergodic.pdf file_size: 517275 relation: main_file file_date_updated: 2020-07-14T12:46:45Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '29' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '127' related_material: record: - id: '2162' relation: later_version status: public status: public title: The complexity of ergodic games type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5401' abstract: - lang: eng text: This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the actual initiatives, projects and standards related to the project. It supports the preparation of standards and specifications for the project, which should be considered and followed to ensure interoperability and visibility of the uploaded data. author: - first_name: Jana full_name: Porsche, Jana id: 3252EDC2-F248-11E8-B48F-1D18A9856A87 last_name: Porsche citation: ama: Porsche J. Initiatives and Projects Related to RD. IST Austria; 2013. apa: Porsche, J. (2013). Initiatives and projects related to RD. IST Austria. chicago: Porsche, Jana. Initiatives and Projects Related to RD. IST Austria, 2013. ieee: J. Porsche, Initiatives and projects related to RD. IST Austria, 2013. ista: Porsche J. 2013. Initiatives and projects related to RD, IST Austria,p. mla: Porsche, Jana. Initiatives and Projects Related to RD. IST Austria, 2013. short: J. Porsche, Initiatives and Projects Related to RD, IST Austria, 2013. date_created: 2018-12-12T11:39:07Z date_published: 2013-03-20T00:00:00Z date_updated: 2020-07-14T23:04:47Z day: '20' ddc: - '020' department: - _id: E-Lib file: - access_level: open_access checksum: d68712db838432ecdacf9ffb1de8f8a6 content_type: application/pdf creator: system date_created: 2018-12-12T11:54:14Z date_updated: 2020-07-14T12:46:45Z file_id: '5536' file_name: IST-2013-113-v1+1_Initiatives_and_projects_related_to_RD.pdf file_size: 151208 relation: main_file file_date_updated: 2020-07-14T12:46:45Z has_accepted_license: '1' language: - iso: eng month: '03' oa: 1 oa_version: Published Version publication_status: published publisher: IST Austria pubrep_id: '113' status: public title: Initiatives and projects related to RD type: report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5405' abstract: - lang: eng text: "The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running\r\nin time O(d · n^{2d}·MeanGame) to compute the set of almost-sure winning states from which the objective\r\ncan be ensured with probability 1, where n is the number of states of the game, d the number of priorities\r\nof the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states\r\nin 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems\r\nwith both functional requirement (given as a qualitative objective) and performance requirement (given\r\nas a quantitative objective)." 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: Laurent full_name: Doyen, Laurent last_name: Doyen - first_name: Hugo full_name: Gimbert, Hugo last_name: Gimbert - first_name: Youssouf full_name: Oualhadj, Youssouf last_name: Oualhadj citation: ama: Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. Perfect-Information Stochastic Mean-Payoff Parity Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-128-v1-1 apa: Chatterjee, K., Doyen, L., Gimbert, H., & Oualhadj, Y. (2013). Perfect-information stochastic mean-payoff parity games. IST Austria. https://doi.org/10.15479/AT:IST-2013-128-v1-1 chicago: Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. Perfect-Information Stochastic Mean-Payoff Parity Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-128-v1-1. ieee: K. Chatterjee, L. Doyen, H. Gimbert, and Y. Oualhadj, Perfect-information stochastic mean-payoff parity games. IST Austria, 2013. ista: Chatterjee K, Doyen L, Gimbert H, Oualhadj Y. 2013. Perfect-information stochastic mean-payoff parity games, IST Austria, 22p. mla: Chatterjee, Krishnendu, et al. Perfect-Information Stochastic Mean-Payoff Parity Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-128-v1-1. short: K. Chatterjee, L. Doyen, H. Gimbert, Y. Oualhadj, Perfect-Information Stochastic Mean-Payoff Parity Games, IST Austria, 2013. date_created: 2018-12-12T11:39:09Z date_published: 2013-07-08T00:00:00Z date_updated: 2023-02-23T10:33:08Z day: '08' ddc: - '000' - '005' - '510' department: - _id: KrCh doi: 10.15479/AT:IST-2013-128-v1-1 file: - access_level: open_access checksum: ede787a10e74e4f7db302fab8f12f3ca content_type: application/pdf creator: system date_created: 2018-12-12T11:53:54Z date_updated: 2020-07-14T12:46:45Z file_id: '5516' file_name: IST-2013-128-v1+1_full_stoch_mpp.pdf file_size: 387467 relation: main_file file_date_updated: 2020-07-14T12:46:45Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '22' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '128' related_material: record: - id: '2212' relation: later_version status: public status: public title: Perfect-information stochastic mean-payoff parity games type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5409' abstract: - lang: eng text: "The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. \r\nIn this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in timestamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than delta away from the parameter, for delta>0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and we show analogous decidability results for rectangular automata." 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: Rupak full_name: Majumdar, Rupak last_name: Majumdar citation: ama: Chatterjee K, Ibsen-Jensen R, Majumdar R. Edit Distance for Timed Automata. IST Austria; 2013. doi:10.15479/AT:IST-2013-144-v1-1 apa: Chatterjee, K., Ibsen-Jensen, R., & Majumdar, R. (2013). Edit distance for timed automata. IST Austria. https://doi.org/10.15479/AT:IST-2013-144-v1-1 chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Rupak Majumdar. Edit Distance for Timed Automata. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-144-v1-1. ieee: K. Chatterjee, R. Ibsen-Jensen, and R. Majumdar, Edit distance for timed automata. IST Austria, 2013. ista: Chatterjee K, Ibsen-Jensen R, Majumdar R. 2013. Edit distance for timed automata, IST Austria, 12p. mla: Chatterjee, Krishnendu, et al. Edit Distance for Timed Automata. IST Austria, 2013, doi:10.15479/AT:IST-2013-144-v1-1. short: K. Chatterjee, R. Ibsen-Jensen, R. Majumdar, Edit Distance for Timed Automata, IST Austria, 2013. date_created: 2018-12-12T11:39:10Z date_published: 2013-10-30T00:00:00Z date_updated: 2023-02-23T10:33:18Z day: '30' ddc: - '000' department: - _id: KrCh doi: 10.15479/AT:IST-2013-144-v1-1 file: - access_level: open_access checksum: 0f7633081ba8299c543322f0ad08571f content_type: application/pdf creator: system date_created: 2018-12-12T11:53:08Z date_updated: 2020-07-14T12:46:46Z file_id: '5469' file_name: IST-2013-144-v1+1_main.pdf file_size: 336377 relation: main_file file_date_updated: 2020-07-14T12:46:46Z has_accepted_license: '1' language: - iso: eng month: '10' oa: 1 oa_version: Published Version page: '12' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '144' related_material: record: - id: '2216' relation: later_version status: public status: public title: Edit distance for timed automata type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '1376' abstract: - lang: eng text: 'We consider the distributed synthesis problem for temporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTL and our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3) Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.' 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: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 citation: ama: 'Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed synthesis for LTL fragments. In: 13th International Conference on Formal Methods in Computer-Aided Design. IEEE; 2013:18-25. doi:10.1109/FMCAD.2013.6679386' apa: 'Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013). Distributed synthesis for LTL fragments. In 13th International Conference on Formal Methods in Computer-Aided Design (pp. 18–25). Portland, OR, United States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679386' chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. “Distributed Synthesis for LTL Fragments.” In 13th International Conference on Formal Methods in Computer-Aided Design, 18–25. IEEE, 2013. https://doi.org/10.1109/FMCAD.2013.6679386. ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, “Distributed synthesis for LTL fragments,” in 13th International Conference on Formal Methods in Computer-Aided Design, Portland, OR, United States, 2013, pp. 18–25. ista: 'Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis for LTL fragments. 13th International Conference on Formal Methods in Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design, 18–25.' mla: Chatterjee, Krishnendu, et al. “Distributed Synthesis for LTL Fragments.” 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25, doi:10.1109/FMCAD.2013.6679386. short: K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25. conference: end_date: 2013-10-23 location: Portland, OR, United States name: 'FMCAD: Formal Methods in Computer-Aided Design' start_date: 2013-10-20 date_created: 2018-12-11T11:51:40Z date_published: 2013-12-11T00:00:00Z date_updated: 2023-02-23T12:24:53Z day: '11' department: - _id: KrCh - _id: ToHe doi: 10.1109/FMCAD.2013.6679386 ec_funded: 1 language: - iso: eng month: '12' oa_version: None page: 18 - 25 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 25EE3708-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '267989' name: Quantitative Reactive Modeling - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: 13th International Conference on Formal Methods in Computer-Aided Design publication_status: published publisher: IEEE publist_id: '5835' quality_controlled: '1' related_material: record: - id: '5406' relation: earlier_version status: public status: public title: Distributed synthesis for LTL fragments type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5406' abstract: - lang: eng text: 'We consider the distributed synthesis problem fortemporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTLand our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3)Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.' 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: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 citation: ama: Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed Synthesis for LTL Fragments. IST Austria; 2013. doi:10.15479/AT:IST-2013-130-v1-1 apa: Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013). Distributed synthesis for LTL Fragments. IST Austria. https://doi.org/10.15479/AT:IST-2013-130-v1-1 chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis. Distributed Synthesis for LTL Fragments. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-130-v1-1. ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, Distributed synthesis for LTL Fragments. IST Austria, 2013. ista: Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis for LTL Fragments, IST Austria, 11p. mla: Chatterjee, Krishnendu, et al. Distributed Synthesis for LTL Fragments. IST Austria, 2013, doi:10.15479/AT:IST-2013-130-v1-1. short: K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, Distributed Synthesis for LTL Fragments, IST Austria, 2013. date_created: 2018-12-12T11:39:09Z date_published: 2013-07-08T00:00:00Z date_updated: 2023-02-21T17:01:26Z day: '08' ddc: - '005' department: - _id: KrCh - _id: ToHe doi: 10.15479/AT:IST-2013-130-v1-1 file: - access_level: open_access checksum: 855513ebaf6f72228800c5fdb522f93c content_type: application/pdf creator: system date_created: 2018-12-12T11:54:18Z date_updated: 2020-07-14T12:46:45Z file_id: '5540' file_name: IST-2013-130-v1+1_Distributed_Synthesis.pdf file_size: 467895 relation: main_file file_date_updated: 2020-07-14T12:46:45Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '11' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '130' related_material: record: - id: '1376' relation: later_version status: public status: public title: Distributed synthesis for LTL Fragments type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5408' abstract: - lang: eng text: "We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are \r\nEXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. " 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: Laurent full_name: Doyen, Laurent last_name: Doyen - first_name: Sumit full_name: Nain, Sumit last_name: Nain - first_name: Moshe full_name: Vardi, Moshe last_name: Vardi citation: ama: Chatterjee K, Doyen L, Nain S, Vardi M. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria; 2013. doi:10.15479/AT:IST-2013-141-v1-1 apa: Chatterjee, K., Doyen, L., Nain, S., & Vardi, M. (2013). The complexity of partial-observation stochastic parity games with finite-memory strategies. IST Austria. https://doi.org/10.15479/AT:IST-2013-141-v1-1 chicago: Chatterjee, Krishnendu, Laurent Doyen, Sumit Nain, and Moshe Vardi. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-141-v1-1. ieee: K. Chatterjee, L. Doyen, S. Nain, and M. Vardi, The complexity of partial-observation stochastic parity games with finite-memory strategies. IST Austria, 2013. ista: Chatterjee K, Doyen L, Nain S, Vardi M. 2013. The complexity of partial-observation stochastic parity games with finite-memory strategies, IST Austria, 17p. mla: Chatterjee, Krishnendu, et al. The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies. IST Austria, 2013, doi:10.15479/AT:IST-2013-141-v1-1. short: K. Chatterjee, L. Doyen, S. Nain, M. Vardi, The Complexity of Partial-Observation Stochastic Parity Games with Finite-Memory Strategies, IST Austria, 2013. date_created: 2018-12-12T11:39:10Z date_published: 2013-09-12T00:00:00Z date_updated: 2023-02-23T10:33:11Z day: '12' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2013-141-v1-1 file: - access_level: open_access checksum: 226bc791124f8d3138379778ce834e86 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:16Z date_updated: 2020-07-14T12:46:46Z file_id: '5477' file_name: IST-2013-141-v1+1_main-tech-rpt.pdf file_size: 300481 relation: main_file file_date_updated: 2020-07-14T12:46:46Z has_accepted_license: '1' language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: '17' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '141' related_material: record: - id: '2213' relation: later_version status: public status: public title: The complexity of partial-observation stochastic parity games with finite-memory strategies type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5407' abstract: - lang: eng text: This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the mandatory features, which need to be fulfilled to provide an institutional repository as a platform and also a service to the scientists at the institute. It also includes optional features, which would be of strong benefit for the scientists and would increase the usage of the repository, and hence the visibility of research at IST Austria. author: - first_name: Jana full_name: Porsche, Jana id: 3252EDC2-F248-11E8-B48F-1D18A9856A87 last_name: Porsche citation: ama: Porsche J. Technical Requirements and Features. IST Austria; 2013. apa: Porsche, J. (2013). Technical requirements and features. IST Austria. chicago: Porsche, Jana. Technical Requirements and Features. IST Austria, 2013. ieee: J. Porsche, Technical requirements and features. IST Austria, 2013. ista: Porsche J. 2013. Technical requirements and features, IST Austria,p. mla: Porsche, Jana. Technical Requirements and Features. IST Austria, 2013. short: J. Porsche, Technical Requirements and Features, IST Austria, 2013. date_created: 2018-12-12T11:39:09Z date_published: 2013-07-13T00:00:00Z date_updated: 2020-07-14T23:07:51Z day: '13' ddc: - '020' department: - _id: E-Lib file: - access_level: open_access checksum: 9e4f9abf79a56f651f0012a34909880f content_type: application/pdf creator: system date_created: 2018-12-12T11:53:02Z date_updated: 2020-07-14T12:46:46Z file_id: '5463' file_name: IST-2013-135-v1+1_Features.pdf file_size: 90311 relation: main_file file_date_updated: 2020-07-14T12:46:46Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version publication_status: published publisher: IST Austria pubrep_id: '135' status: public title: Technical requirements and features type: report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '5410' abstract: - lang: eng text: "Board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in development of mathematical and logical skills, but also in emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. \r\nOur approach generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. Also, the presence of such states for standard game variants like Tic-Tac-Toe on board size 4x4 opens up new games to be played that have not been played for ages since the default start state is heavily biased. " alternative_title: - IST Austria Technical Report author: - first_name: Umair full_name: Ahmed, Umair last_name: Ahmed - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Sumit full_name: Gulwani, Sumit last_name: Gulwani citation: ama: Ahmed U, Chatterjee K, Gulwani S. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-146-v1-1 apa: Ahmed, U., Chatterjee, K., & Gulwani, S. (2013). Automatic generation of alternative starting positions for traditional board games. IST Austria. https://doi.org/10.15479/AT:IST-2013-146-v1-1 chicago: Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-146-v1-1. ieee: U. Ahmed, K. Chatterjee, and S. Gulwani, Automatic generation of alternative starting positions for traditional board games. IST Austria, 2013. ista: Ahmed U, Chatterjee K, Gulwani S. 2013. Automatic generation of alternative starting positions for traditional board games, IST Austria, 13p. mla: Ahmed, Umair, et al. Automatic Generation of Alternative Starting Positions for Traditional Board Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-146-v1-1. short: U. Ahmed, K. Chatterjee, S. Gulwani, Automatic Generation of Alternative Starting Positions for Traditional Board Games, IST Austria, 2013. date_created: 2018-12-12T11:39:10Z date_published: 2013-12-03T00:00:00Z date_updated: 2023-02-23T10:00:50Z day: '03' ddc: - '000' - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2013-146-v1-1 file: - access_level: open_access checksum: 409f3aaaf1184e4057b89cbb449dac80 content_type: application/pdf creator: system date_created: 2018-12-12T11:54:06Z date_updated: 2020-07-14T12:46:46Z file_id: '5528' file_name: IST-2013-146-v1+1_main.pdf file_size: 818189 relation: main_file file_date_updated: 2020-07-14T12:46:46Z has_accepted_license: '1' language: - iso: eng month: '12' oa: 1 oa_version: Published Version page: '13' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '146' related_material: record: - id: '1481' relation: later_version status: public status: public title: Automatic generation of alternative starting positions for traditional board games type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2327' abstract: - lang: eng text: 'We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M′ within distance ρ from M satisfy (or violate) φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification. We show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved. We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications.' alternative_title: - LNCS author: - 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: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop citation: ama: Henzinger TA, Otop J. From model checking to model measuring. 2013;8052:273-287. doi:10.1007/978-3-642-40184-8_20 apa: 'Henzinger, T. A., & Otop, J. (2013). From model checking to model measuring. Presented at the CONCUR: Concurrency Theory, Buenos Aires, Argentina: Springer. https://doi.org/10.1007/978-3-642-40184-8_20' chicago: Henzinger, Thomas A, and Jan Otop. “From Model Checking to Model Measuring.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40184-8_20. ieee: T. A. Henzinger and J. Otop, “From model checking to model measuring,” vol. 8052. Springer, pp. 273–287, 2013. ista: Henzinger TA, Otop J. 2013. From model checking to model measuring. 8052, 273–287. mla: Henzinger, Thomas A., and Jan Otop. From Model Checking to Model Measuring. Vol. 8052, Springer, 2013, pp. 273–87, doi:10.1007/978-3-642-40184-8_20. short: T.A. Henzinger, J. Otop, 8052 (2013) 273–287. conference: end_date: 2013-08-30 location: Buenos Aires, Argentina name: 'CONCUR: Concurrency Theory' start_date: 2013-08-27 date_created: 2018-12-11T11:57:00Z date_published: 2013-08-01T00:00:00Z date_updated: 2023-02-23T12:25:26Z day: '01' ddc: - '005' - '000' department: - _id: ToHe doi: 10.1007/978-3-642-40184-8_20 file: - access_level: open_access checksum: 4c04695c4bfdf2119cd4f5d1babc3e8a content_type: application/pdf creator: system date_created: 2018-12-12T10:17:45Z date_updated: 2020-07-14T12:45:38Z file_id: '5301' file_name: IST-2013-129-v1+1_concur.pdf file_size: 378587 relation: main_file file_date_updated: 2020-07-14T12:45:38Z has_accepted_license: '1' intvolume: ' 8052' language: - iso: eng month: '08' oa: 1 oa_version: Submitted Version page: 273 - 287 publication_status: published publisher: Springer publist_id: '4599' pubrep_id: '129' quality_controlled: '1' related_material: record: - id: '5417' relation: earlier_version status: public series_title: Lecture Notes in Computer Science status: public title: From model checking to model measuring type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8052 year: '2013' ... --- _id: '590' abstract: - lang: eng text: We present two methods of creating two orthogonally-polarized focal points at customizable relative locations. These schemes may be critical for enhancing entanglement sources and other applications. alternative_title: - Optics InfoBase Conference Papers author: - first_name: David full_name: Schmid, David last_name: Schmid - first_name: Ting full_name: Huang, Ting-Yu last_name: Huang - first_name: Radhika full_name: Dirks, Radhika last_name: Dirks - first_name: Onur full_name: Onur Hosten id: 4C02D85E-F248-11E8-B48F-1D18A9856A87 last_name: Hosten orcid: 0000-0002-2031-204X - first_name: Paul full_name: Kwiat, Paul G last_name: Kwiat citation: ama: 'Schmid D, Huang T, Dirks R, Hosten O, Kwiat P. Polarization dependent focusing. In: OSA; 2013. doi:10.1364/QIM.2013.W6.23' apa: 'Schmid, D., Huang, T., Dirks, R., Hosten, O., & Kwiat, P. (2013). Polarization dependent focusing. Presented at the QIM: Quantum Information and Measurement, OSA. https://doi.org/10.1364/QIM.2013.W6.23' chicago: Schmid, David, Ting Huang, Radhika Dirks, Onur Hosten, and Paul Kwiat. “Polarization Dependent Focusing.” OSA, 2013. https://doi.org/10.1364/QIM.2013.W6.23. ieee: 'D. Schmid, T. Huang, R. Dirks, O. Hosten, and P. Kwiat, “Polarization dependent focusing,” presented at the QIM: Quantum Information and Measurement, 2013.' ista: 'Schmid D, Huang T, Dirks R, Hosten O, Kwiat P. 2013. Polarization dependent focusing. QIM: Quantum Information and Measurement, Optics InfoBase Conference Papers, .' mla: Schmid, David, et al. Polarization Dependent Focusing. OSA, 2013, doi:10.1364/QIM.2013.W6.23. short: D. Schmid, T. Huang, R. Dirks, O. Hosten, P. Kwiat, in:, OSA, 2013. conference: name: 'QIM: Quantum Information and Measurement' date_created: 2018-12-11T11:47:22Z date_published: 2013-01-01T00:00:00Z date_updated: 2021-01-12T08:05:10Z day: '01' doi: 10.1364/QIM.2013.W6.23 extern: 1 month: '01' publication_status: published publisher: OSA publist_id: '7217' quality_controlled: 0 status: public title: Polarization dependent focusing type: conference year: '2013' ... --- _id: '5920' abstract: - lang: eng text: We study chains of lattice ideals that are invariant under a symmetric group action. In our setting, the ambient rings for these ideals are polynomial rings which are increasing in (Krull) dimension. Thus, these chains will fail to stabilize in the traditional commutative algebra sense. However, we prove a theorem which says that “up to the action of the group”, these chains locally stabilize. We also give an algorithm, which we have implemented in software, for explicitly constructing these stabilization generators for a family of Laurent toric ideals involved in applications to algebraic statistics. We close with several open problems and conjectures arising from our theoretical and computational investigations. article_processing_charge: No article_type: original author: - first_name: Christopher J. full_name: Hillar, Christopher J. last_name: Hillar - first_name: Abraham full_name: Martin del Campo Sanchez, Abraham id: 4CF47F6A-F248-11E8-B48F-1D18A9856A87 last_name: Martin del Campo Sanchez citation: ama: Hillar CJ, Martin del Campo Sanchez A. Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals. Journal of Symbolic Computation. 2013;50:314-334. doi:10.1016/j.jsc.2012.06.006 apa: Hillar, C. J., & Martin del Campo Sanchez, A. (2013). Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals. Journal of Symbolic Computation. Elsevier. https://doi.org/10.1016/j.jsc.2012.06.006 chicago: Hillar, Christopher J., and Abraham Martin del Campo Sanchez. “Finiteness Theorems and Algorithms for Permutation Invariant Chains of Laurent Lattice Ideals.” Journal of Symbolic Computation. Elsevier, 2013. https://doi.org/10.1016/j.jsc.2012.06.006. ieee: C. J. Hillar and A. Martin del Campo Sanchez, “Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals,” Journal of Symbolic Computation, vol. 50. Elsevier, pp. 314–334, 2013. ista: Hillar CJ, Martin del Campo Sanchez A. 2013. Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals. Journal of Symbolic Computation. 50, 314–334. mla: Hillar, Christopher J., and Abraham Martin del Campo Sanchez. “Finiteness Theorems and Algorithms for Permutation Invariant Chains of Laurent Lattice Ideals.” Journal of Symbolic Computation, vol. 50, Elsevier, 2013, pp. 314–34, doi:10.1016/j.jsc.2012.06.006. short: C.J. Hillar, A. Martin del Campo Sanchez, Journal of Symbolic Computation 50 (2013) 314–334. date_created: 2019-02-05T08:48:24Z date_published: 2013-03-01T00:00:00Z date_updated: 2021-01-12T08:05:15Z day: '01' doi: 10.1016/j.jsc.2012.06.006 extern: '1' intvolume: ' 50' language: - iso: eng month: '03' oa_version: None page: 314-334 publication: Journal of Symbolic Computation publication_identifier: issn: - 0747-7171 publication_status: published publisher: Elsevier quality_controlled: '1' related_material: link: - relation: erratum url: https://doi.org/10.1016/j.jsc.2015.09.002 status: public title: Finiteness theorems and algorithms for permutation invariant chains of Laurent lattice ideals type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 50 year: '2013' ... --- _id: '591' abstract: - lang: eng text: We present two methods for the precise independent focusing of orthogonal linear polarizations of light at arbitrary relative locations. Our first scheme uses a displaced lens in a polarization Sagnac interferometer to provide adjustable longitudinal and lateral focal displacements via simple geometry; the second uses uniaxial crystals to achieve the same effect in a compact collinear setup. We develop the theoretical applications and limitations of our schemes, and provide experimental confirmation of our calculations. author: - first_name: David full_name: Schmid, David last_name: Schmid - first_name: Ting full_name: Huang, Ting-Yu last_name: Huang - first_name: Shiraz full_name: Hazrat, Shiraz last_name: Hazrat - first_name: Radhika full_name: Dirks, Radhika last_name: Dirks - first_name: Onur full_name: Onur Hosten id: 4C02D85E-F248-11E8-B48F-1D18A9856A87 last_name: Hosten orcid: 0000-0002-2031-204X - first_name: Stephan full_name: Quint, Stephan last_name: Quint - first_name: Dickson full_name: Thian, Dickson last_name: Thian - first_name: Paul full_name: Kwiat, Paul G last_name: Kwiat citation: ama: Schmid D, Huang T, Hazrat S, et al. Adjustable and robust methods for polarization-dependent focusing. Optics Express. 2013;21(13):15538-15552. doi:10.1364/OE.21.015538 apa: Schmid, D., Huang, T., Hazrat, S., Dirks, R., Hosten, O., Quint, S., … Kwiat, P. (2013). Adjustable and robust methods for polarization-dependent focusing. Optics Express. Optical Society of America. https://doi.org/10.1364/OE.21.015538 chicago: Schmid, David, Ting Huang, Shiraz Hazrat, Radhika Dirks, Onur Hosten, Stephan Quint, Dickson Thian, and Paul Kwiat. “Adjustable and Robust Methods for Polarization-Dependent Focusing.” Optics Express. Optical Society of America, 2013. https://doi.org/10.1364/OE.21.015538. ieee: D. Schmid et al., “Adjustable and robust methods for polarization-dependent focusing,” Optics Express, vol. 21, no. 13. Optical Society of America, pp. 15538–15552, 2013. ista: Schmid D, Huang T, Hazrat S, Dirks R, Hosten O, Quint S, Thian D, Kwiat P. 2013. Adjustable and robust methods for polarization-dependent focusing. Optics Express. 21(13), 15538–15552. mla: Schmid, David, et al. “Adjustable and Robust Methods for Polarization-Dependent Focusing.” Optics Express, vol. 21, no. 13, Optical Society of America, 2013, pp. 15538–52, doi:10.1364/OE.21.015538. short: D. Schmid, T. Huang, S. Hazrat, R. Dirks, O. Hosten, S. Quint, D. Thian, P. Kwiat, Optics Express 21 (2013) 15538–15552. date_created: 2018-12-11T11:47:22Z date_published: 2013-07-01T00:00:00Z date_updated: 2021-01-12T08:05:12Z day: '01' doi: 10.1364/OE.21.015538 extern: 1 intvolume: ' 21' issue: '13' month: '07' page: 15538 - 15552 publication: Optics Express publication_status: published publisher: Optical Society of America publist_id: '7218' quality_controlled: 0 status: public title: Adjustable and robust methods for polarization-dependent focusing type: journal_article volume: 21 year: '2013' ... --- _id: '595' article_processing_charge: No author: - first_name: Carrie A full_name: Bernecky, Carrie A id: 2CB9DFE2-F248-11E8-B48F-1D18A9856A87 last_name: Bernecky orcid: 0000-0003-0893-7036 - first_name: Patrick full_name: Cramer, Patrick last_name: Cramer citation: ama: 'Bernecky C, Cramer P. Struggling to let go: A non-coding RNA directs its own extension and destruction. EMBO Journal. 2013;32(6):771-772. doi:10.1038/emboj.2013.36' apa: 'Bernecky, C., & Cramer, P. (2013). Struggling to let go: A non-coding RNA directs its own extension and destruction. EMBO Journal. Wiley-Blackwell. https://doi.org/10.1038/emboj.2013.36' chicago: 'Bernecky, Carrie, and Patrick Cramer. “Struggling to Let Go: A Non-Coding RNA Directs Its Own Extension and Destruction.” EMBO Journal. Wiley-Blackwell, 2013. https://doi.org/10.1038/emboj.2013.36.' ieee: 'C. Bernecky and P. Cramer, “Struggling to let go: A non-coding RNA directs its own extension and destruction,” EMBO Journal, vol. 32, no. 6. Wiley-Blackwell, pp. 771–772, 2013.' ista: 'Bernecky C, Cramer P. 2013. Struggling to let go: A non-coding RNA directs its own extension and destruction. EMBO Journal. 32(6), 771–772.' mla: 'Bernecky, Carrie, and Patrick Cramer. “Struggling to Let Go: A Non-Coding RNA Directs Its Own Extension and Destruction.” EMBO Journal, vol. 32, no. 6, Wiley-Blackwell, 2013, pp. 771–72, doi:10.1038/emboj.2013.36.' short: C. Bernecky, P. Cramer, EMBO Journal 32 (2013) 771–772. date_created: 2018-12-11T11:47:23Z date_published: 2013-03-20T00:00:00Z date_updated: 2021-01-12T08:05:20Z day: '20' doi: 10.1038/emboj.2013.36 extern: '1' intvolume: ' 32' issue: '6' language: - iso: eng main_file_link: - open_access: '1' url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3604726/ month: '03' oa: 1 oa_version: None page: 771 - 772 publication: EMBO Journal publication_status: published publisher: Wiley-Blackwell publist_id: '7207' status: public title: 'Struggling to let go: A non-coding RNA directs its own extension and destruction' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 32 year: '2013' ... --- _id: '6128' abstract: - lang: eng text: Different interoceptive systems must be integrated to ensure that multiple homeostatic insults evoke appropriate behavioral and physiological responses. Little is known about how this is achieved. Using C. elegans, we dissect cross-modulation between systems that monitor temperature, O2 and CO2. CO2 is less aversive to animals acclimated to 15°C than those grown at 22°C. This difference requires the AFD neurons, which respond to both temperature and CO2 changes. CO2 evokes distinct AFD Ca2+ responses in animals acclimated at 15°C or 22°C. Mutants defective in synaptic transmission can reprogram AFD CO2 responses according to temperature experience, suggesting reprogramming occurs cell autonomously. AFD is exquisitely sensitive to CO2. Surprisingly, gradients of 0.01% CO2/second evoke very different Ca2+ responses from gradients of 0.04% CO2/second. Ambient O2 provides further contextual modulation of CO2 avoidance. At 21% O2 tonic signalling from the O2-sensing neuron URX inhibits CO2 avoidance. This inhibition can be graded according to O2 levels. In a natural wild isolate, a switch from 21% to 19% O2 is sufficient to convert CO2 from a neutral to an aversive cue. This sharp tuning is conferred partly by the neuroglobin GLB-5. The modulatory effects of O2 on CO2 avoidance involve the RIA interneurons, which are post-synaptic to URX and exhibit CO2-evoked Ca2+ responses. Ambient O2 and acclimation temperature act combinatorially to modulate CO2 responsiveness. Our work highlights the integrated architecture of homeostatic responses in C. elegans. article_number: e1004011 author: - first_name: Eiji full_name: Kodama-Namba, Eiji last_name: Kodama-Namba - first_name: Lorenz A. full_name: Fenk, Lorenz A. last_name: Fenk - first_name: Andrew J. full_name: Bretscher, Andrew J. last_name: Bretscher - first_name: Einav full_name: Gross, Einav last_name: Gross - first_name: K. Emanuel full_name: Busch, K. Emanuel last_name: Busch - first_name: Mario full_name: de Bono, Mario id: 4E3FF80E-F248-11E8-B48F-1D18A9856A87 last_name: de Bono orcid: 0000-0001-8347-0443 citation: ama: Kodama-Namba E, Fenk LA, Bretscher AJ, Gross E, Busch KE, de Bono M. Cross-modulation of homeostatic responses to temperature, oxygen and carbon dioxide in C. elegans. PLoS Genetics. 2013;9(12). doi:10.1371/journal.pgen.1004011 apa: Kodama-Namba, E., Fenk, L. A., Bretscher, A. J., Gross, E., Busch, K. E., & de Bono, M. (2013). Cross-modulation of homeostatic responses to temperature, oxygen and carbon dioxide in C. elegans. PLoS Genetics. Public Library of Science (PLoS). https://doi.org/10.1371/journal.pgen.1004011 chicago: Kodama-Namba, Eiji, Lorenz A. Fenk, Andrew J. Bretscher, Einav Gross, K. Emanuel Busch, and Mario de Bono. “Cross-Modulation of Homeostatic Responses to Temperature, Oxygen and Carbon Dioxide in C. Elegans.” PLoS Genetics. Public Library of Science (PLoS), 2013. https://doi.org/10.1371/journal.pgen.1004011. ieee: E. Kodama-Namba, L. A. Fenk, A. J. Bretscher, E. Gross, K. E. Busch, and M. de Bono, “Cross-modulation of homeostatic responses to temperature, oxygen and carbon dioxide in C. elegans,” PLoS Genetics, vol. 9, no. 12. Public Library of Science (PLoS), 2013. ista: Kodama-Namba E, Fenk LA, Bretscher AJ, Gross E, Busch KE, de Bono M. 2013. Cross-modulation of homeostatic responses to temperature, oxygen and carbon dioxide in C. elegans. PLoS Genetics. 9(12), e1004011. mla: Kodama-Namba, Eiji, et al. “Cross-Modulation of Homeostatic Responses to Temperature, Oxygen and Carbon Dioxide in C. Elegans.” PLoS Genetics, vol. 9, no. 12, e1004011, Public Library of Science (PLoS), 2013, doi:10.1371/journal.pgen.1004011. short: E. Kodama-Namba, L.A. Fenk, A.J. Bretscher, E. Gross, K.E. Busch, M. de Bono, PLoS Genetics 9 (2013). date_created: 2019-03-19T14:58:51Z date_published: 2013-12-19T00:00:00Z date_updated: 2021-01-12T08:06:15Z day: '19' ddc: - '570' doi: 10.1371/journal.pgen.1004011 extern: '1' external_id: pmid: - '24385919' file: - access_level: open_access checksum: 299b6321be79931c7c17c5db6e69c711 content_type: application/pdf creator: kschuh date_created: 2019-03-19T15:14:51Z date_updated: 2020-07-14T12:47:20Z file_id: '6129' file_name: 2013_PLOS_Kodama-Namba.PDF file_size: 4499039 relation: main_file file_date_updated: 2020-07-14T12:47:20Z has_accepted_license: '1' intvolume: ' 9' issue: '12' language: - iso: eng month: '12' oa: 1 oa_version: Published Version pmid: 1 publication: PLoS Genetics publication_identifier: issn: - 1553-7404 publication_status: published publisher: Public Library of Science (PLoS) quality_controlled: '1' status: public title: Cross-modulation of homeostatic responses to temperature, oxygen and carbon dioxide in C. elegans tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 9 year: '2013' ... --- _id: '6130' abstract: - lang: eng text: 'Cas9 is an RNA-guided double-stranded DNA nuclease that participates in clustered regularly interspaced short palindromic repeats (CRISPR)-mediated adaptive immunity in prokaryotes. CRISPR–Cas9 has recently been used to generate insertion and deletion mutations in Caenorhabditis elegans, but not to create tailored changes (knock-ins). We show that the CRISPR–CRISPR-associated (Cas) system can be adapted for efficient and precise editing of the C. elegans genome. The targeted double-strand breaks generated by CRISPR are substrates for transgene-instructed gene conversion. This allows customized changes in the C. elegans genome by homologous recombination: sequences contained in the repair template (the transgene) are copied by gene conversion into the genome. The possibility to edit the C. elegans genome at selected locations will facilitate the systematic study of gene function in this widely used model organism.' article_number: e193 author: - first_name: Changchun full_name: Chen, Changchun last_name: Chen - first_name: Lorenz A. full_name: Fenk, Lorenz A. last_name: Fenk - first_name: Mario full_name: de Bono, Mario id: 4E3FF80E-F248-11E8-B48F-1D18A9856A87 last_name: de Bono orcid: 0000-0001-8347-0443 citation: ama: Chen C, Fenk LA, de Bono M. Efficient genome editing in Caenorhabditis elegans by CRISPR-targeted homologous recombination. Nucleic Acids Research. 2013;41(20). doi:10.1093/nar/gkt805 apa: Chen, C., Fenk, L. A., & de Bono, M. (2013). Efficient genome editing in Caenorhabditis elegans by CRISPR-targeted homologous recombination. Nucleic Acids Research. Oxford University Press. https://doi.org/10.1093/nar/gkt805 chicago: Chen, Changchun, Lorenz A. Fenk, and Mario de Bono. “Efficient Genome Editing in Caenorhabditis Elegans by CRISPR-Targeted Homologous Recombination.” Nucleic Acids Research. Oxford University Press, 2013. https://doi.org/10.1093/nar/gkt805. ieee: C. Chen, L. A. Fenk, and M. de Bono, “Efficient genome editing in Caenorhabditis elegans by CRISPR-targeted homologous recombination,” Nucleic Acids Research, vol. 41, no. 20. Oxford University Press, 2013. ista: Chen C, Fenk LA, de Bono M. 2013. Efficient genome editing in Caenorhabditis elegans by CRISPR-targeted homologous recombination. Nucleic Acids Research. 41(20), e193. mla: Chen, Changchun, et al. “Efficient Genome Editing in Caenorhabditis Elegans by CRISPR-Targeted Homologous Recombination.” Nucleic Acids Research, vol. 41, no. 20, e193, Oxford University Press, 2013, doi:10.1093/nar/gkt805. short: C. Chen, L.A. Fenk, M. de Bono, Nucleic Acids Research 41 (2013). date_created: 2019-03-19T15:17:40Z date_published: 2013-11-01T00:00:00Z date_updated: 2021-01-12T08:06:16Z day: '01' ddc: - '570' doi: 10.1093/nar/gkt805 extern: '1' external_id: pmid: - '24013562' file: - access_level: open_access checksum: 0f1f127cefd043cb922b292e1cd16f02 content_type: application/pdf creator: kschuh date_created: 2019-03-19T15:25:42Z date_updated: 2020-07-14T12:47:20Z file_id: '6131' file_name: 2013_OUP_Chen.pdf file_size: 340225 relation: main_file file_date_updated: 2020-07-14T12:47:20Z has_accepted_license: '1' intvolume: ' 41' issue: '20' language: - iso: eng month: '11' oa: 1 oa_version: Published Version pmid: 1 publication: Nucleic Acids Research publication_identifier: issn: - 1362-4962 - 0305-1048 publication_status: published publisher: Oxford University Press quality_controlled: '1' status: public title: Efficient genome editing in Caenorhabditis elegans by CRISPR-targeted homologous recombination tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 41 year: '2013' ...