--- _id: '10892' abstract: - lang: eng text: "In this paper, we introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist.\r\nUsing our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings." acknowledgement: 'T. Biedl was supported by NSERC and the Ross and Muriel Cheriton Fellowship. P. Palfrader was supported by Austrian Science Fund (FWF): P25816-N15.' alternative_title: - LNCS article_processing_charge: No author: - first_name: Therese full_name: Biedl, Therese last_name: Biedl - first_name: Stefan full_name: Huber, Stefan id: 4700A070-F248-11E8-B48F-1D18A9856A87 last_name: Huber orcid: 0000-0002-8871-5814 - first_name: Peter full_name: Palfrader, Peter last_name: Palfrader citation: ama: 'Biedl T, Huber S, Palfrader P. Planar matchings for weighted straight skeletons. In: 25th International Symposium, ISAAC 2014. Vol 8889. Springer Nature; 2014:117-127. doi:10.1007/978-3-319-13075-0_10' apa: 'Biedl, T., Huber, S., & Palfrader, P. (2014). Planar matchings for weighted straight skeletons. In 25th International Symposium, ISAAC 2014 (Vol. 8889, pp. 117–127). Jeonju, Korea: Springer Nature. https://doi.org/10.1007/978-3-319-13075-0_10' chicago: Biedl, Therese, Stefan Huber, and Peter Palfrader. “Planar Matchings for Weighted Straight Skeletons.” In 25th International Symposium, ISAAC 2014, 8889:117–27. Springer Nature, 2014. https://doi.org/10.1007/978-3-319-13075-0_10. ieee: T. Biedl, S. Huber, and P. Palfrader, “Planar matchings for weighted straight skeletons,” in 25th International Symposium, ISAAC 2014, Jeonju, Korea, 2014, vol. 8889, pp. 117–127. ista: 'Biedl T, Huber S, Palfrader P. 2014. Planar matchings for weighted straight skeletons. 25th International Symposium, ISAAC 2014. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 8889, 117–127.' mla: Biedl, Therese, et al. “Planar Matchings for Weighted Straight Skeletons.” 25th International Symposium, ISAAC 2014, vol. 8889, Springer Nature, 2014, pp. 117–27, doi:10.1007/978-3-319-13075-0_10. short: T. Biedl, S. Huber, P. Palfrader, in:, 25th International Symposium, ISAAC 2014, Springer Nature, 2014, pp. 117–127. conference: end_date: 2014-12-17 location: Jeonju, Korea name: 'ISAAC: International Symposium on Algorithms and Computation' start_date: 2014-12-15 date_created: 2022-03-21T07:09:03Z date_published: 2014-11-08T00:00:00Z date_updated: 2023-02-23T12:20:55Z day: '08' department: - _id: HeEd doi: 10.1007/978-3-319-13075-0_10 intvolume: ' 8889' language: - iso: eng month: '11' oa_version: None page: 117-127 publication: 25th International Symposium, ISAAC 2014 publication_identifier: eisbn: - '9783319130750' eissn: - 1611-3349 isbn: - '9783319130743' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '481' relation: later_version status: public scopus_import: '1' status: public title: Planar matchings for weighted straight skeletons type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8889 year: '2014' ... --- _id: '537' abstract: - lang: eng text: Transgenerational effects are broader than only parental relationships. Despite mounting evidence that multigenerational effects alter phenotypic and life-history traits, our understanding of how they combine to determine fitness is not well developed because of the added complexity necessary to study them. Here, we derive a quantitative genetic model of adaptation to an extraordinary new environment by an additive genetic component, phenotypic plasticity, maternal and grandmaternal effects. We show how, at equilibrium, negative maternal and negative grandmaternal effects maximize expected population mean fitness. We define negative transgenerational effects as those that have a negative effect on trait expression in the subsequent generation, that is, they slow, or potentially reverse, the expected evolutionary dynamic. When maternal effects are positive, negative grandmaternal effects are preferred. As expected under Mendelian inheritance, the grandmaternal effects have a lower impact on fitness than the maternal effects, but this dual inheritance model predicts a more complex relationship between maternal and grandmaternal effects to constrain phenotypic variance and so maximize expected population mean fitness in the offspring. author: - first_name: Roshan full_name: Prizak, Roshan id: 4456104E-F248-11E8-B48F-1D18A9856A87 last_name: Prizak - first_name: Thomas full_name: Ezard, Thomas last_name: Ezard - first_name: Rebecca full_name: Hoyle, Rebecca last_name: Hoyle citation: ama: Prizak R, Ezard T, Hoyle R. Fitness consequences of maternal and grandmaternal effects. Ecology and Evolution. 2014;4(15):3139-3145. doi:10.1002/ece3.1150 apa: Prizak, R., Ezard, T., & Hoyle, R. (2014). Fitness consequences of maternal and grandmaternal effects. Ecology and Evolution. Wiley-Blackwell. https://doi.org/10.1002/ece3.1150 chicago: Prizak, Roshan, Thomas Ezard, and Rebecca Hoyle. “Fitness Consequences of Maternal and Grandmaternal Effects.” Ecology and Evolution. Wiley-Blackwell, 2014. https://doi.org/10.1002/ece3.1150. ieee: R. Prizak, T. Ezard, and R. Hoyle, “Fitness consequences of maternal and grandmaternal effects,” Ecology and Evolution, vol. 4, no. 15. Wiley-Blackwell, pp. 3139–3145, 2014. ista: Prizak R, Ezard T, Hoyle R. 2014. Fitness consequences of maternal and grandmaternal effects. Ecology and Evolution. 4(15), 3139–3145. mla: Prizak, Roshan, et al. “Fitness Consequences of Maternal and Grandmaternal Effects.” Ecology and Evolution, vol. 4, no. 15, Wiley-Blackwell, 2014, pp. 3139–45, doi:10.1002/ece3.1150. short: R. Prizak, T. Ezard, R. Hoyle, Ecology and Evolution 4 (2014) 3139–3145. date_created: 2018-12-11T11:47:02Z date_published: 2014-07-19T00:00:00Z date_updated: 2021-01-12T08:01:30Z day: '19' ddc: - '530' - '571' department: - _id: NiBa - _id: GaTk doi: 10.1002/ece3.1150 file: - access_level: open_access checksum: e32abf75a248e7a11811fd7f60858769 content_type: application/pdf creator: system date_created: 2018-12-12T10:11:31Z date_updated: 2020-07-14T12:46:38Z file_id: '4886' file_name: IST-2018-934-v1+1_Prizak_et_al-2014-Ecology_and_Evolution.pdf file_size: 621582 relation: main_file file_date_updated: 2020-07-14T12:46:38Z has_accepted_license: '1' intvolume: ' 4' issue: '15' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '07' oa: 1 oa_version: Published Version page: 3139 - 3145 publication: Ecology and Evolution publication_status: published publisher: Wiley-Blackwell publist_id: '7280' pubrep_id: '934' scopus_import: 1 status: public title: Fitness consequences of maternal and grandmaternal effects 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: 4 year: '2014' ... --- _id: '1903' abstract: - lang: eng text: 'We consider two-player zero-sum partial-observation stochastic games on graphs. Based on the information available to the players these games can be classified as follows: (a) general partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) perfect-observation (both players have complete view of the game). The one-sided partial-observation games subsumes the important special case of one-player partial-observation stochastic games (or partial-observation Markov decision processes (POMDPs)). Based on the randomization available for the strategies, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. We consider all these classes of games with reachability, and parity objectives that can express all ω-regular objectives. The analysis problems are classified into the qualitative analysis that asks for the existence of a strategy that ensures the objective with probability 1; and the quantitative analysis that asks for the existence of a strategy that ensures the objective with probability at least λ (0,1). In this talk we will cover a wide range of results: for perfect-observation games; for POMDPs; for one-sided partial-observation games; and for general partial-observation games.' alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X citation: ama: 'Chatterjee K. Partial-observation stochastic reachability and parity games. In: Vol 8634. Springer; 2014:1-4. doi:10.1007/978-3-662-44522-8_1' apa: 'Chatterjee, K. (2014). Partial-observation stochastic reachability and parity games (Vol. 8634, pp. 1–4). Presented at the MFCS: Mathematical Foundations of Computer Science, Budapest, Hungary: Springer. https://doi.org/10.1007/978-3-662-44522-8_1' chicago: Chatterjee, Krishnendu. “Partial-Observation Stochastic Reachability and Parity Games,” 8634:1–4. Springer, 2014. https://doi.org/10.1007/978-3-662-44522-8_1. ieee: 'K. Chatterjee, “Partial-observation stochastic reachability and parity games,” presented at the MFCS: Mathematical Foundations of Computer Science, Budapest, Hungary, 2014, vol. 8634, no. PART 1, pp. 1–4.' ista: 'Chatterjee K. 2014. Partial-observation stochastic reachability and parity games. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 8634, 1–4.' mla: Chatterjee, Krishnendu. Partial-Observation Stochastic Reachability and Parity Games. Vol. 8634, no. PART 1, Springer, 2014, pp. 1–4, doi:10.1007/978-3-662-44522-8_1. short: K. Chatterjee, in:, Springer, 2014, pp. 1–4. conference: end_date: 2014-08-29 location: Budapest, Hungary name: 'MFCS: Mathematical Foundations of Computer Science' start_date: 2014-08-25 date_created: 2018-12-11T11:54:38Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T12:23:43Z day: '01' department: - _id: KrCh doi: 10.1007/978-3-662-44522-8_1 ec_funded: 1 intvolume: ' 8634' issue: PART 1 language: - iso: eng month: '01' oa_version: None page: 1 - 4 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: Springer publist_id: '5192' pubrep_id: '141' quality_controlled: '1' related_material: record: - id: '2211' relation: later_version status: public - id: '5381' relation: earlier_version status: public scopus_import: 1 status: public title: Partial-observation stochastic reachability and parity games type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8634 year: '2014' ... --- _id: '2211' abstract: - lang: eng text: 'In two-player finite-state stochastic games of partial observation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distribution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Our main results for pure strategies are as follows: (1) For one-sided games with player 2 having perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algorithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 having perfect observation we show that nonelementarymemory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least nonelementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibit serious flaws in previous results of the literature: we show a nonelementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.' article_number: '16' 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 citation: ama: 'Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when belief fails. ACM Transactions on Computational Logic (TOCL). 2014;15(2). doi:10.1145/2579821' apa: 'Chatterjee, K., & Doyen, L. (2014). Partial-observation stochastic games: How to win when belief fails. ACM Transactions on Computational Logic (TOCL). ACM. https://doi.org/10.1145/2579821' chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” ACM Transactions on Computational Logic (TOCL). ACM, 2014. https://doi.org/10.1145/2579821.' ieee: 'K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to win when belief fails,” ACM Transactions on Computational Logic (TOCL), vol. 15, no. 2. ACM, 2014.' ista: 'Chatterjee K, Doyen L. 2014. Partial-observation stochastic games: How to win when belief fails. ACM Transactions on Computational Logic (TOCL). 15(2), 16.' mla: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” ACM Transactions on Computational Logic (TOCL), vol. 15, no. 2, 16, ACM, 2014, doi:10.1145/2579821.' short: K. Chatterjee, L. Doyen, ACM Transactions on Computational Logic (TOCL) 15 (2014). date_created: 2018-12-11T11:56:21Z date_published: 2014-04-01T00:00:00Z date_updated: 2023-02-23T12:23:43Z day: '01' department: - _id: KrCh doi: 10.1145/2579821 external_id: arxiv: - '1107.2141' intvolume: ' 15' issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1107.2141 month: '04' oa: 1 oa_version: Preprint publication: ACM Transactions on Computational Logic (TOCL) publication_status: published publisher: ACM publist_id: '4759' quality_controlled: '1' related_material: record: - id: '1903' relation: earlier_version status: public - id: '2955' relation: earlier_version status: public - id: '5381' relation: earlier_version status: public scopus_import: 1 status: public title: 'Partial-observation stochastic games: How to win when belief fails' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 15 year: '2014' ... --- _id: '2038' abstract: - lang: eng text: Recently, there has been an effort to add quantitative objectives to formal verification and synthesis. We introduce and investigate the extension of temporal logics with quantitative atomic assertions. At the heart of quantitative objectives lies the accumulation of values along a computation. It is often the accumulated sum, as with energy objectives, or the accumulated average, as with mean-payoff objectives. We investigate the extension of temporal logics with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is a numeric (or Boolean) variable of the system, c is a constant rational number, and Sum(v) and Avg(v) denote the accumulated sum and average of the values of v from the beginning of the computation up to the current point in time. We also allow the path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring to the average value along an entire infinite computation. We study the border of decidability for such quantitative extensions of various temporal logics. In particular, we show that extending the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities with both prefix-accumulation assertions, or extending LTL with both path-accumulation assertions, results in temporal logics whose model-checking problem is decidable. Moreover, the prefix-accumulation assertions may be generalized with "controlled accumulation," allowing, for example, to specify constraints on the average waiting time between a request and a grant. On the negative side, we show that this branching-time logic is, in a sense, the maximal logic with one or both of the prefix-accumulation assertions that permits a decidable model-checking procedure. Extending a temporal logic that has the EG or EU modalities, such as CTL or LTL, makes the problem undecidable. acknowledgement: The research was supported in part by ERC Starting grant 278410 (QUALITY). article_number: '27' article_processing_charge: No article_type: original author: - first_name: Udi full_name: Boker, Udi id: 31E297B6-F248-11E8-B48F-1D18A9856A87 last_name: Boker - 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: Orna full_name: Kupferman, Orna last_name: Kupferman citation: ama: Boker U, Chatterjee K, Henzinger TA, Kupferman O. Temporal specifications with accumulative values. ACM Transactions on Computational Logic (TOCL). 2014;15(4). doi:10.1145/2629686 apa: Boker, U., Chatterjee, K., Henzinger, T. A., & Kupferman, O. (2014). Temporal specifications with accumulative values. ACM Transactions on Computational Logic (TOCL). ACM. https://doi.org/10.1145/2629686 chicago: Boker, Udi, Krishnendu Chatterjee, Thomas A Henzinger, and Orna Kupferman. “Temporal Specifications with Accumulative Values.” ACM Transactions on Computational Logic (TOCL). ACM, 2014. https://doi.org/10.1145/2629686. ieee: U. Boker, K. Chatterjee, T. A. Henzinger, and O. Kupferman, “Temporal specifications with accumulative values,” ACM Transactions on Computational Logic (TOCL), vol. 15, no. 4. ACM, 2014. ista: Boker U, Chatterjee K, Henzinger TA, Kupferman O. 2014. Temporal specifications with accumulative values. ACM Transactions on Computational Logic (TOCL). 15(4), 27. mla: Boker, Udi, et al. “Temporal Specifications with Accumulative Values.” ACM Transactions on Computational Logic (TOCL), vol. 15, no. 4, 27, ACM, 2014, doi:10.1145/2629686. short: U. Boker, K. Chatterjee, T.A. Henzinger, O. Kupferman, ACM Transactions on Computational Logic (TOCL) 15 (2014). date_created: 2018-12-11T11:55:21Z date_published: 2014-09-16T00:00:00Z date_updated: 2023-02-23T12:23:54Z day: '16' ddc: - '000' - '004' department: - _id: ToHe - _id: KrCh doi: 10.1145/2629686 ec_funded: 1 file: - access_level: open_access checksum: 354c41d37500b56320afce94cf9a99c2 content_type: application/pdf creator: system date_created: 2018-12-12T10:10:59Z date_updated: 2020-07-14T12:45:26Z file_id: '4851' file_name: IST-2014-192-v1+1_AccumulativeValues.pdf file_size: 346184 relation: main_file file_date_updated: 2020-07-14T12:45:26Z has_accepted_license: '1' intvolume: ' 15' issue: '4' language: - iso: eng month: '09' oa: 1 oa_version: Submitted Version project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25F5A88A-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Moderne Concurrency Paradigms - _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: 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: ACM Transactions on Computational Logic (TOCL) publication_status: published publisher: ACM publist_id: '5013' pubrep_id: '192' quality_controlled: '1' related_material: record: - id: '3356' relation: earlier_version status: public - id: '5385' relation: earlier_version status: public scopus_import: 1 status: public title: Temporal specifications with accumulative values type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 15 year: '2014' ...