[{"month":"04","department":[{"_id":"KrCh"}],"publisher":"World Scientific Publishing","publication_status":"published","abstract":[{"lang":"eng","text":"We introduce two-level discounted and mean-payoff games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted or mean-payoff game and the lower level game is a (undiscounted) reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. For both discounted and mean-payoff two-level games, we show the existence of pure memoryless optimal strategies for both players and an ordered field property. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted or mean-payoff games can be decided in NP ∩ coNP. We also give an alternate strategy improvement algorithm to compute the value. © 2012 World Scientific Publishing Company."}],"quality_controlled":"1","oa_version":"None","page":"609 - 625","date_created":"2018-12-11T12:02:37Z","_id":"3314","scopus_import":1,"year":"2012","date_published":"2012-04-01T00:00:00Z","doi":"10.1142/S0129054112400308","status":"public","title":"Discounting and averaging in games across time scales","project":[{"call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"issue":"3","intvolume":"        23","type":"journal_article","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Majumdar, Ritankar","first_name":"Ritankar","last_name":"Majumdar"}],"citation":{"short":"K. Chatterjee, R. Majumdar, International Journal of Foundations of Computer Science 23 (2012) 609–625.","mla":"Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” <i>International Journal of Foundations of Computer Science</i>, vol. 23, no. 3, World Scientific Publishing, 2012, pp. 609–25, doi:<a href=\"https://doi.org/10.1142/S0129054112400308\">10.1142/S0129054112400308</a>.","ama":"Chatterjee K, Majumdar R. Discounting and averaging in games across time scales. <i>International Journal of Foundations of Computer Science</i>. 2012;23(3):609-625. doi:<a href=\"https://doi.org/10.1142/S0129054112400308\">10.1142/S0129054112400308</a>","ieee":"K. Chatterjee and R. Majumdar, “Discounting and averaging in games across time scales,” <i>International Journal of Foundations of Computer Science</i>, vol. 23, no. 3. World Scientific Publishing, pp. 609–625, 2012.","apa":"Chatterjee, K., &#38; Majumdar, R. (2012). Discounting and averaging in games across time scales. <i>International Journal of Foundations of Computer Science</i>. World Scientific Publishing. <a href=\"https://doi.org/10.1142/S0129054112400308\">https://doi.org/10.1142/S0129054112400308</a>","chicago":"Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in Games across Time Scales.” <i>International Journal of Foundations of Computer Science</i>. World Scientific Publishing, 2012. <a href=\"https://doi.org/10.1142/S0129054112400308\">https://doi.org/10.1142/S0129054112400308</a>.","ista":"Chatterjee K, Majumdar R. 2012. Discounting and averaging in games across time scales. International Journal of Foundations of Computer Science. 23(3), 609–625."},"date_updated":"2021-01-12T07:42:35Z","volume":23,"publist_id":"3326","day":"01","publication":"International Journal of Foundations of Computer Science","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},{"abstract":[{"text":"The physical distance between presynaptic Ca2+ channels and the Ca2+ sensors that trigger exocytosis of neurotransmitter-containing vesicles is a key determinant of the signalling properties of synapses in the nervous system. Recent functional analysis indicates that in some fast central synapses, transmitter release is triggered by a small number of Ca2+ channels that are coupled to Ca2+ sensors at the nanometre scale. Molecular analysis suggests that this tight coupling is generated by protein–protein interactions involving Ca2+ channels, Ca2+ sensors and various other synaptic proteins. Nanodomain coupling has several functional advantages, as it increases the efficacy, speed and energy efficiency of synaptic transmission.","lang":"eng"}],"file":[{"file_name":"IST-2017-820-v1+1_17463_3_art_file_109404_ltmxbw.pdf","relation":"main_file","date_created":"2018-12-12T10:12:13Z","file_id":"4931","date_updated":"2020-07-14T12:46:07Z","checksum":"4c1c86b2f6e4e1562f5bb800b457ea9f","content_type":"application/pdf","file_size":314246,"creator":"system","access_level":"open_access"},{"file_name":"IST-2017-820-v1+2_17463_3_figure_109402_ltmwlp.pdf","file_id":"4932","relation":"main_file","date_created":"2018-12-12T10:12:14Z","date_updated":"2020-07-14T12:46:07Z","checksum":"bceb2efdd49d115f4dde8486bc1be3f2","content_type":"application/pdf","file_size":1840216,"access_level":"open_access","creator":"system"}],"publication_status":"published","oa_version":"Submitted Version","quality_controlled":"1","_id":"3317","year":"2012","date_created":"2018-12-11T12:02:38Z","title":"Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses","project":[{"grant_number":"JO_780/A5","_id":"25BC64A8-B435-11E9-9278-68D0E5697425","name":"Synaptic Mechanisms of Neuronal Network Function"},{"name":"Glutamaterge synaptische Übertragung und Plastizität in hippocampalen Mikroschaltkreisen","grant_number":"SFB-TR3-TP10B","_id":"25BDE9A4-B435-11E9-9278-68D0E5697425"}],"issue":"1","has_accepted_license":"1","citation":{"apa":"Eggermann, E., Bucurenciu, I., Goswami, S., &#38; Jonas, P. M. (2012). Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. <i>Nature Reviews Neuroscience</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nrn3125\">https://doi.org/10.1038/nrn3125</a>","ama":"Eggermann E, Bucurenciu I, Goswami S, Jonas PM. Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. <i>Nature Reviews Neuroscience</i>. 2012;13(1):7-21. doi:<a href=\"https://doi.org/10.1038/nrn3125\">10.1038/nrn3125</a>","ieee":"E. Eggermann, I. Bucurenciu, S. Goswami, and P. M. Jonas, “Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses,” <i>Nature Reviews Neuroscience</i>, vol. 13, no. 1. Nature Publishing Group, pp. 7–21, 2012.","mla":"Eggermann, Emmanuel, et al. “Nanodomain Coupling between Ca(2+) Channels and Sensors of Exocytosis at Fast Mammalian Synapses.” <i>Nature Reviews Neuroscience</i>, vol. 13, no. 1, Nature Publishing Group, 2012, pp. 7–21, doi:<a href=\"https://doi.org/10.1038/nrn3125\">10.1038/nrn3125</a>.","ista":"Eggermann E, Bucurenciu I, Goswami S, Jonas PM. 2012. Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. Nature Reviews Neuroscience. 13(1), 7–21.","chicago":"Eggermann, Emmanuel, Iancu Bucurenciu, Sarit Goswami, and Peter M Jonas. “Nanodomain Coupling between Ca(2+) Channels and Sensors of Exocytosis at Fast Mammalian Synapses.” <i>Nature Reviews Neuroscience</i>. Nature Publishing Group, 2012. <a href=\"https://doi.org/10.1038/nrn3125\">https://doi.org/10.1038/nrn3125</a>.","short":"E. Eggermann, I. Bucurenciu, S. Goswami, P.M. Jonas, Nature Reviews Neuroscience 13 (2012) 7–21."},"author":[{"id":"34DACA34-E9AE-11E9-849C-D35BD8ADC20C","full_name":"Eggermann, Emmanuel","first_name":"Emmanuel","last_name":"Eggermann"},{"last_name":"Bucurenciu","first_name":"Iancu","full_name":"Bucurenciu, Iancu","id":"4BD1D872-E9AE-11E9-9EE9-8BF4597A9E2A"},{"last_name":"Goswami","first_name":"Sarit","id":"3A578F32-F248-11E8-B48F-1D18A9856A87","full_name":"Goswami, Sarit"},{"last_name":"Jonas","first_name":"Peter M","orcid":"0000-0001-5001-4804","id":"353C1B58-F248-11E8-B48F-1D18A9856A87","full_name":"Jonas, Peter M"}],"date_updated":"2021-01-12T07:42:36Z","oa":1,"publication":"Nature Reviews Neuroscience","publist_id":"3322","day":"01","month":"01","publisher":"Nature Publishing Group","department":[{"_id":"PeJo"}],"page":"7 - 21","scopus_import":1,"acknowledgement":"Work of the authors was funded by grants of the Deutsche Forschungsgemeinschaft to P.J. (grants SFB 780/A5, TR 3/B10 and the Leibniz programme), a European Research Council Advanced grant to P.J. and a Swiss National Foundation fellowship to E.E.\r\nWe thank D. Tsien and E. Neher for their comments on this Review, J. Guzmán and A. Pernía-Andrade for reading earlier versions and E. Kramberger for perfect editorial support. We apologize that owing to space constraints, not all relevant papers could be cited.\r\n","status":"public","language":[{"iso":"eng"}],"date_published":"2012-01-01T00:00:00Z","doi":"10.1038/nrn3125","intvolume":"        13","ddc":["570"],"volume":13,"type":"journal_article","pubrep_id":"820","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:07Z"},{"abstract":[{"text":"Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with  bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve.","lang":"eng"}],"department":[{"_id":"HeEd"}],"publication_status":"published","publisher":"Elsevier","month":"03","oa_version":"Preprint","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1104.1510","open_access":"1"}],"page":"239 - 258","scopus_import":1,"year":"2012","_id":"3331","date_created":"2018-12-11T12:02:43Z","language":[{"iso":"eng"}],"title":"A worst case bound for topology computation of algebraic curves","status":"public","doi":"10.1016/j.jsc.2011.11.001","date_published":"2012-03-01T00:00:00Z","intvolume":"        47","issue":"3","volume":47,"type":"journal_article","citation":{"short":"M. Kerber, M. Sagraloff,  Journal of Symbolic Computation 47 (2012) 239–258.","ista":"Kerber M, Sagraloff M. 2012. A worst case bound for topology computation of algebraic curves.  Journal of Symbolic Computation. 47(3), 239–258.","chicago":"Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology Computation of Algebraic Curves.” <i> Journal of Symbolic Computation</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.jsc.2011.11.001\">https://doi.org/10.1016/j.jsc.2011.11.001</a>.","ieee":"M. Kerber and M. Sagraloff, “A worst case bound for topology computation of algebraic curves,” <i> Journal of Symbolic Computation</i>, vol. 47, no. 3. Elsevier, pp. 239–258, 2012.","ama":"Kerber M, Sagraloff M. A worst case bound for topology computation of algebraic curves. <i> Journal of Symbolic Computation</i>. 2012;47(3):239-258. doi:<a href=\"https://doi.org/10.1016/j.jsc.2011.11.001\">10.1016/j.jsc.2011.11.001</a>","apa":"Kerber, M., &#38; Sagraloff, M. (2012). A worst case bound for topology computation of algebraic curves. <i> Journal of Symbolic Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jsc.2011.11.001\">https://doi.org/10.1016/j.jsc.2011.11.001</a>","mla":"Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology Computation of Algebraic Curves.” <i> Journal of Symbolic Computation</i>, vol. 47, no. 3, Elsevier, 2012, pp. 239–58, doi:<a href=\"https://doi.org/10.1016/j.jsc.2011.11.001\">10.1016/j.jsc.2011.11.001</a>."},"date_updated":"2021-01-12T07:42:43Z","author":[{"last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael"},{"full_name":"Sagraloff, Michael","first_name":"Michael","last_name":"Sagraloff"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication":" Journal of Symbolic Computation","oa":1,"day":"01","publist_id":"3303"},{"external_id":{"arxiv":["1107.2009"]},"title":"Robustness of structurally equivalent concurrent parity games","project":[{"grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"oa":1,"publist_id":"3284","day":"22","date_updated":"2023-02-23T12:23:46Z","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"}],"citation":{"short":"K. Chatterjee, in:, Springer, 2012, pp. 270–285.","chicago":"Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent Parity Games,” 7213:270–85. Springer, 2012. <a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">https://doi.org/10.1007/978-3-642-28729-9_18</a>.","ista":"Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 7213, 270–285.","mla":"Chatterjee, Krishnendu. <i>Robustness of Structurally Equivalent Concurrent Parity Games</i>. Vol. 7213, Springer, 2012, pp. 270–85, doi:<a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">10.1007/978-3-642-28729-9_18</a>.","ama":"Chatterjee K. Robustness of structurally equivalent concurrent parity games. In: Vol 7213. Springer; 2012:270-285. doi:<a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">10.1007/978-3-642-28729-9_18</a>","apa":"Chatterjee, K. (2012). Robustness of structurally equivalent concurrent parity games (Vol. 7213, pp. 270–285). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-28729-9_18\">https://doi.org/10.1007/978-3-642-28729-9_18</a>","ieee":"K. Chatterjee, “Robustness of structurally equivalent concurrent parity games,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Tallinn, Estonia, 2012, vol. 7213, pp. 270–285."},"oa_version":"Preprint","quality_controlled":"1","abstract":[{"lang":"eng","text":"We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \\omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal)."}],"publication_status":"published","related_material":{"record":[{"status":"public","id":"5382","relation":"earlier_version"}]},"_id":"3341","year":"2012","date_created":"2018-12-11T12:02:46Z","ec_funded":1,"alternative_title":["LNCS"],"intvolume":"      7213","status":"public","language":[{"iso":"eng"}],"date_published":"2012-03-22T00:00:00Z","doi":"10.1007/978-3-642-28729-9_18","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":7213,"type":"conference","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1107.2009"}],"month":"03","department":[{"_id":"KrCh"}],"publisher":"Springer","scopus_import":1,"page":"270 - 285","conference":{"start_date":"2012-03-24","name":"FoSSaCS: Foundations of Software Science and Computation Structures","location":"Tallinn, Estonia","end_date":"2012-04-01"},"arxiv":1},{"author":[{"full_name":"Ghosal, Arkadeb","last_name":"Ghosal","first_name":"Arkadeb"},{"first_name":"Daniel","last_name":"Iercan","full_name":"Iercan, Daniel"},{"full_name":"Kirsch, Christoph","last_name":"Kirsch","first_name":"Christoph"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Sangiovanni Vincentelli, Alberto","last_name":"Sangiovanni Vincentelli","first_name":"Alberto"}],"citation":{"short":"A. Ghosal, D. Iercan, C. Kirsch, T.A. Henzinger, A. Sangiovanni Vincentelli, Science of Computer Programming 77 (2012) 96–112.","mla":"Ghosal, Arkadeb, et al. “Separate Compilation of Hierarchical Real-Time Programs into Linear-Bounded Embedded Machine Code.” <i>Science of Computer Programming</i>, vol. 77, no. 2, Elsevier, 2012, pp. 96–112, doi:<a href=\"https://doi.org/10.1016/j.scico.2010.06.004\">10.1016/j.scico.2010.06.004</a>.","ama":"Ghosal A, Iercan D, Kirsch C, Henzinger TA, Sangiovanni Vincentelli A. Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code. <i>Science of Computer Programming</i>. 2012;77(2):96-112. doi:<a href=\"https://doi.org/10.1016/j.scico.2010.06.004\">10.1016/j.scico.2010.06.004</a>","apa":"Ghosal, A., Iercan, D., Kirsch, C., Henzinger, T. A., &#38; Sangiovanni Vincentelli, A. (2012). Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code. <i>Science of Computer Programming</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.scico.2010.06.004\">https://doi.org/10.1016/j.scico.2010.06.004</a>","ieee":"A. Ghosal, D. Iercan, C. Kirsch, T. A. Henzinger, and A. Sangiovanni Vincentelli, “Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code,” <i>Science of Computer Programming</i>, vol. 77, no. 2. Elsevier, pp. 96–112, 2012.","chicago":"Ghosal, Arkadeb, Daniel Iercan, Christoph Kirsch, Thomas A Henzinger, and Alberto Sangiovanni Vincentelli. “Separate Compilation of Hierarchical Real-Time Programs into Linear-Bounded Embedded Machine Code.” <i>Science of Computer Programming</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.scico.2010.06.004\">https://doi.org/10.1016/j.scico.2010.06.004</a>.","ista":"Ghosal A, Iercan D, Kirsch C, Henzinger TA, Sangiovanni Vincentelli A. 2012. Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code. Science of Computer Programming. 77(2), 96–112."},"type":"journal_article","date_updated":"2021-01-12T07:52:32Z","volume":77,"publist_id":"2370","day":"01","publication":"Science of Computer Programming","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_published":"2012-02-01T00:00:00Z","doi":"10.1016/j.scico.2010.06.004","status":"public","title":"Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code","language":[{"iso":"eng"}],"issue":"2","intvolume":"        77","page":"96 - 112","date_created":"2018-12-11T12:05:26Z","_id":"3836","year":"2012","scopus_import":1,"month":"02","publisher":"Elsevier","publication_status":"published","department":[{"_id":"ToHe"}],"abstract":[{"lang":"eng","text":"Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine (or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram structure needs to be flattened; the flattening makes separatecompilation difficult, and may result in E machinecode of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchicalprogram structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order."}],"quality_controlled":"1","oa_version":"None"},{"month":"03","publisher":"Elsevier","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"main_file_link":[{"url":"https://doi.org/10.1016/j.jcss.2011.05.002","open_access":"1"}],"page":"394 - 413","scopus_import":"1","acknowledgement":"This research was supported in part by the ONR grant N00014-02-1-0671, by the AFOSR MURI grant F49620-00-1-0327, and by the NSF grants CCR-9988172, CCR-0085949, and CCR-0225610.","status":"public","language":[{"iso":"eng"}],"date_published":"2012-03-02T00:00:00Z","doi":"10.1016/j.jcss.2011.05.002","ddc":["000"],"intvolume":"        78","volume":78,"type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:17Z","abstract":[{"lang":"eng","text":"We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications."}],"file":[{"file_size":336450,"content_type":"application/pdf","checksum":"241b939deb4517cdd4426d49c67e3fa2","creator":"kschuh","access_level":"open_access","relation":"main_file","date_created":"2019-01-29T10:54:28Z","file_id":"5897","file_name":"a_survey_of_stochastic_omega-regular_games.pdf","date_updated":"2020-07-14T12:46:17Z"}],"article_type":"original","publication_status":"published","article_processing_charge":"No","oa_version":"Submitted Version","quality_controlled":"1","_id":"3846","year":"2012","date_created":"2018-12-11T12:05:29Z","title":"A survey of stochastic ω regular games","issue":"2","has_accepted_license":"1","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"}],"citation":{"short":"K. Chatterjee, T.A. Henzinger, Journal of Computer and System Sciences 78 (2012) 394–413.","ista":"Chatterjee K, Henzinger TA. 2012. A survey of stochastic ω regular games. Journal of Computer and System Sciences. 78(2), 394–413.","chicago":"Chatterjee, Krishnendu, and Thomas A Henzinger. “A Survey of Stochastic ω Regular Games.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2012. <a href=\"https://doi.org/10.1016/j.jcss.2011.05.002\">https://doi.org/10.1016/j.jcss.2011.05.002</a>.","ieee":"K. Chatterjee and T. A. Henzinger, “A survey of stochastic ω regular games,” <i>Journal of Computer and System Sciences</i>, vol. 78, no. 2. Elsevier, pp. 394–413, 2012.","apa":"Chatterjee, K., &#38; Henzinger, T. A. (2012). A survey of stochastic ω regular games. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcss.2011.05.002\">https://doi.org/10.1016/j.jcss.2011.05.002</a>","ama":"Chatterjee K, Henzinger TA. A survey of stochastic ω regular games. <i>Journal of Computer and System Sciences</i>. 2012;78(2):394-413. doi:<a href=\"https://doi.org/10.1016/j.jcss.2011.05.002\">10.1016/j.jcss.2011.05.002</a>","mla":"Chatterjee, Krishnendu, and Thomas A. Henzinger. “A Survey of Stochastic ω Regular Games.” <i>Journal of Computer and System Sciences</i>, vol. 78, no. 2, Elsevier, 2012, pp. 394–413, doi:<a href=\"https://doi.org/10.1016/j.jcss.2011.05.002\">10.1016/j.jcss.2011.05.002</a>."},"date_updated":"2022-05-24T08:00:54Z","oa":1,"publication":"Journal of Computer and System Sciences","publist_id":"2341","day":"02"},{"status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"language":[{"iso":"eng"}],"date_published":"2012-07-13T00:00:00Z","doi":"10.3389/fnins.2012.00055","intvolume":"         6","ddc":["004"],"volume":6,"type":"journal_article","pubrep_id":"945","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:35Z","month":"07","department":[{"_id":"ScienComp"},{"_id":"PeJo"}],"publisher":"Frontiers Research Foundation","scopus_import":1,"acknowledgement":"The studies were in part or completely supported by the Bundesministerium für Bildung und Forschung (BMBF), Fkz 01IB001A, 01GQ0850, by the German Science Foundation (DFG, contract MU 987/3-2), by the European ICT Programme Projects FP7-224631 and 216886, the World Class University Program through the National Research Foundation of Korea funded by the Ministry of Education, Science, and Technology (Grant R31-10008), the US Army Research Office [W911NF-08-1-0216 (Gerwin Schalk) and W911NF-07-1-0415 (Gerwin Schalk)] and the NIH [EB006356 (Gerwin Schalk) and EB000856 (Gerwin Schalk), the WIN-Kolleg of the Heidelberg Academy of Sciences and Humanities, German Federal Ministry of Education and Research grants 01GQ0420, 01GQ0761, 01GQ0762, and 01GQ0830, German Research Foundation grants 550/B5 and C6, and by a scholarship from the German National Academic Foundation. This paper only reflects the authors’ views and funding agencies are not liable for any use that may be made of the information contained herein.\r\n","title":"Review of the BCI competition IV","article_number":"55","has_accepted_license":"1","date_updated":"2021-01-12T08:01:03Z","citation":{"short":"M. Tangermann, K. Müller, A. Aertsen, N. Birbaumer, C. Braun, C. Brunner, R. Leeb, C. Mehring, K. Miller, G. Müller Putz, G. Nolte, G. Pfurtscheller, H. Preissl, G. Schalk, A. Schlögl, C. Vidaurre, S. Waldert, B. Blankertz, Frontiers in Neuroscience 6 (2012).","ama":"Tangermann M, Müller K, Aertsen A, et al. Review of the BCI competition IV. <i>Frontiers in Neuroscience</i>. 2012;6. doi:<a href=\"https://doi.org/10.3389/fnins.2012.00055\">10.3389/fnins.2012.00055</a>","ieee":"M. Tangermann <i>et al.</i>, “Review of the BCI competition IV,” <i>Frontiers in Neuroscience</i>, vol. 6. Frontiers Research Foundation, 2012.","apa":"Tangermann, M., Müller, K., Aertsen, A., Birbaumer, N., Braun, C., Brunner, C., … Blankertz, B. (2012). Review of the BCI competition IV. <i>Frontiers in Neuroscience</i>. Frontiers Research Foundation. <a href=\"https://doi.org/10.3389/fnins.2012.00055\">https://doi.org/10.3389/fnins.2012.00055</a>","mla":"Tangermann, Michael, et al. “Review of the BCI Competition IV.” <i>Frontiers in Neuroscience</i>, vol. 6, 55, Frontiers Research Foundation, 2012, doi:<a href=\"https://doi.org/10.3389/fnins.2012.00055\">10.3389/fnins.2012.00055</a>.","ista":"Tangermann M, Müller K, Aertsen A, Birbaumer N, Braun C, Brunner C, Leeb R, Mehring C, Miller K, Müller Putz G, Nolte G, Pfurtscheller G, Preissl H, Schalk G, Schlögl A, Vidaurre C, Waldert S, Blankertz B. 2012. Review of the BCI competition IV. Frontiers in Neuroscience. 6, 55.","chicago":"Tangermann, Michael, Klaus Müller, Ad Aertsen, Niels Birbaumer, Christoph Braun, Clemens Brunner, Robert Leeb, et al. “Review of the BCI Competition IV.” <i>Frontiers in Neuroscience</i>. Frontiers Research Foundation, 2012. <a href=\"https://doi.org/10.3389/fnins.2012.00055\">https://doi.org/10.3389/fnins.2012.00055</a>."},"author":[{"full_name":"Tangermann, Michael","first_name":"Michael","last_name":"Tangermann"},{"full_name":"Müller, Klaus","first_name":"Klaus","last_name":"Müller"},{"last_name":"Aertsen","first_name":"Ad","full_name":"Aertsen, Ad"},{"first_name":"Niels","last_name":"Birbaumer","full_name":"Birbaumer, Niels"},{"full_name":"Braun, Christoph","first_name":"Christoph","last_name":"Braun"},{"first_name":"Clemens","last_name":"Brunner","full_name":"Brunner, Clemens"},{"full_name":"Leeb, Robert","first_name":"Robert","last_name":"Leeb"},{"full_name":"Mehring, Carsten","first_name":"Carsten","last_name":"Mehring"},{"full_name":"Miller, Kai","first_name":"Kai","last_name":"Miller"},{"first_name":"Gernot","last_name":"Müller Putz","full_name":"Müller Putz, Gernot"},{"first_name":"Guido","last_name":"Nolte","full_name":"Nolte, Guido"},{"full_name":"Pfurtscheller, Gert","last_name":"Pfurtscheller","first_name":"Gert"},{"last_name":"Preissl","first_name":"Hubert","full_name":"Preissl, Hubert"},{"last_name":"Schalk","first_name":"Gerwin","full_name":"Schalk, Gerwin"},{"first_name":"Alois","last_name":"Schlögl","orcid":"0000-0002-5621-8100","full_name":"Schlögl, Alois","id":"45BF87EE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Vidaurre, Carmen","first_name":"Carmen","last_name":"Vidaurre"},{"full_name":"Waldert, Stephan","last_name":"Waldert","first_name":"Stephan"},{"full_name":"Blankertz, Benjamin","first_name":"Benjamin","last_name":"Blankertz"}],"oa":1,"publication":"Frontiers in Neuroscience","publist_id":"7327","day":"13","abstract":[{"text":"The BCI competition IV stands in the tradition of prior BCI competitions that aim to provide high quality neuroscientific data for open access to the scientific community. As experienced already in prior competitions not only scientists from the narrow field of BCI compete, but scholars with a broad variety of backgrounds and nationalities. They include high specialists as well as students.The goals of all BCI competitions have always been to challenge with respect to novel paradigms and complex data. We report on the following challenges: (1) asynchronous data, (2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer, (5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after past competitions, our hope is that winning entries may enhance the analysis methods of future BCIs.","lang":"eng"}],"file":[{"date_updated":"2020-07-14T12:46:35Z","relation":"main_file","date_created":"2018-12-12T10:18:34Z","file_id":"5356","file_name":"IST-2018-945-v1+1_2012_Schloegl_Review_of.pdf","creator":"system","access_level":"open_access","file_size":2693701,"content_type":"application/pdf","checksum":"195238221c4b0b0f4035f6f6c16ea17c"}],"publication_status":"published","oa_version":"Published Version","quality_controlled":"1","_id":"493","year":"2012","date_created":"2018-12-11T11:46:46Z"},{"_id":"494","scopus_import":1,"year":"2012","date_created":"2018-12-11T11:46:47Z","abstract":[{"lang":"eng","text":"We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is 2o(nlog n) and the lower bound is 1.5n. We improve the upper bound to n2n and describe a matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We continue and solve the open problems of translating nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to DCW. Going via an intermediate NBW is not optimal and we describe direct, simple, and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions are variants of the subset construction, providing a unified approach for translating all common classes of automata to NCW and DCW. Beyond the theoretical importance of the results, we point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation, when possible, of LTL to deterministic Büchi word automata."}],"month":"10","publication_status":"published","department":[{"_id":"ToHe"}],"publisher":"ACM","oa_version":"None","quality_controlled":"1","volume":13,"type":"journal_article","date_updated":"2021-01-12T08:01:03Z","citation":{"short":"U. Boker, O. Kupferman, ACM Transactions on Computational Logic (TOCL) 13 (2012).","chicago":"Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified, and Useful.” <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM, 2012. <a href=\"https://doi.org/10.1145/2362355.2362357\">https://doi.org/10.1145/2362355.2362357</a>.","ista":"Boker U, Kupferman O. 2012. Translating to Co-Büchi made tight, unified, and useful. ACM Transactions on Computational Logic (TOCL). 13(4), 29.","mla":"Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified, and Useful.” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 13, no. 4, 29, ACM, 2012, doi:<a href=\"https://doi.org/10.1145/2362355.2362357\">10.1145/2362355.2362357</a>.","ieee":"U. Boker and O. Kupferman, “Translating to Co-Büchi made tight, unified, and useful,” <i>ACM Transactions on Computational Logic (TOCL)</i>, vol. 13, no. 4. ACM, 2012.","apa":"Boker, U., &#38; Kupferman, O. (2012). Translating to Co-Büchi made tight, unified, and useful. <i>ACM Transactions on Computational Logic (TOCL)</i>. ACM. <a href=\"https://doi.org/10.1145/2362355.2362357\">https://doi.org/10.1145/2362355.2362357</a>","ama":"Boker U, Kupferman O. Translating to Co-Büchi made tight, unified, and useful. <i>ACM Transactions on Computational Logic (TOCL)</i>. 2012;13(4). doi:<a href=\"https://doi.org/10.1145/2362355.2362357\">10.1145/2362355.2362357</a>"},"author":[{"first_name":"Udi","last_name":"Boker","full_name":"Boker, Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kupferman","first_name":"Orna","full_name":"Kupferman, Orna"}],"publication":"ACM Transactions on Computational Logic (TOCL)","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"7326","day":"01","status":"public","title":"Translating to Co-Büchi made tight, unified, and useful","language":[{"iso":"eng"}],"date_published":"2012-10-01T00:00:00Z","doi":"10.1145/2362355.2362357","issue":"4","article_number":"29","intvolume":"        13"},{"month":"10","publisher":"Open Publishing Association","department":[{"_id":"KrCh"}],"conference":{"end_date":"2012-09-08","location":"Napoli, Italy","start_date":"2012-09-06","name":"GandALF: Games, Automata, Logics and Formal Verification"},"page":"238 - 246","scopus_import":1,"date_published":"2012-10-07T00:00:00Z","doi":"10.4204/EPTCS.96.18","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public","language":[{"iso":"eng"}],"alternative_title":["EPTCS"],"ddc":["004"],"intvolume":"        96","type":"conference","pubrep_id":"944","volume":96,"file_date_updated":"2020-07-14T12:46:35Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"text":"An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.","lang":"eng"}],"file":[{"creator":"system","access_level":"open_access","content_type":"application/pdf","file_size":97736,"checksum":"56277f95edc9d531fa3bdc5f9579fda8","date_updated":"2020-07-14T12:46:35Z","relation":"main_file","date_created":"2018-12-12T10:15:31Z","file_id":"5152","file_name":"IST-2018-944-v1+1_2012_Rubin_A_Myhill.pdf"}],"quality_controlled":"1","oa_version":"Published Version","ec_funded":1,"date_created":"2018-12-11T11:46:47Z","_id":"495","year":"2012","title":"A Myhill Nerode theorem for automata with advice","project":[{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"has_accepted_license":"1","author":[{"last_name":"Kruckman","first_name":"Alex","full_name":"Kruckman, Alex"},{"full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87","first_name":"Sasha","last_name":"Rubin"},{"first_name":"John","last_name":"Sheridan","full_name":"Sheridan, John"},{"first_name":"Ben","last_name":"Zax","full_name":"Zax, Ben"}],"date_updated":"2021-01-12T08:01:04Z","citation":{"chicago":"Kruckman, Alex, Sasha Rubin, John Sheridan, and Ben Zax. “A Myhill Nerode Theorem for Automata with Advice.” In <i>Proceedings GandALF 2012</i>, 96:238–46. Open Publishing Association, 2012. <a href=\"https://doi.org/10.4204/EPTCS.96.18\">https://doi.org/10.4204/EPTCS.96.18</a>.","ista":"Kruckman A, Rubin S, Sheridan J, Zax B. 2012. A Myhill Nerode theorem for automata with advice. Proceedings GandALF 2012. GandALF: Games, Automata, Logics and Formal Verification, EPTCS, vol. 96, 238–246.","mla":"Kruckman, Alex, et al. “A Myhill Nerode Theorem for Automata with Advice.” <i>Proceedings GandALF 2012</i>, vol. 96, Open Publishing Association, 2012, pp. 238–46, doi:<a href=\"https://doi.org/10.4204/EPTCS.96.18\">10.4204/EPTCS.96.18</a>.","apa":"Kruckman, A., Rubin, S., Sheridan, J., &#38; Zax, B. (2012). A Myhill Nerode theorem for automata with advice. In <i>Proceedings GandALF 2012</i> (Vol. 96, pp. 238–246). Napoli, Italy: Open Publishing Association. <a href=\"https://doi.org/10.4204/EPTCS.96.18\">https://doi.org/10.4204/EPTCS.96.18</a>","ieee":"A. Kruckman, S. Rubin, J. Sheridan, and B. Zax, “A Myhill Nerode theorem for automata with advice,” in <i>Proceedings GandALF 2012</i>, Napoli, Italy, 2012, vol. 96, pp. 238–246.","ama":"Kruckman A, Rubin S, Sheridan J, Zax B. A Myhill Nerode theorem for automata with advice. In: <i>Proceedings GandALF 2012</i>. Vol 96. Open Publishing Association; 2012:238-246. doi:<a href=\"https://doi.org/10.4204/EPTCS.96.18\">10.4204/EPTCS.96.18</a>","short":"A. Kruckman, S. Rubin, J. Sheridan, B. Zax, in:, Proceedings GandALF 2012, Open Publishing Association, 2012, pp. 238–246."},"publist_id":"7325","day":"07","oa":1,"publication":"Proceedings GandALF 2012"},{"day":"01","publist_id":"7324","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa":1,"type":"conference","date_updated":"2021-01-12T08:01:05Z","citation":{"short":"A. Rabinovich, S. Rubin, in:, IEEE, 2012.","chicago":"Rabinovich, Alexander, and Sasha Rubin. “Interpretations in Trees with Countably Many Branches.” IEEE, 2012. <a href=\"https://doi.org/10.1109/LICS.2012.65\">https://doi.org/10.1109/LICS.2012.65</a>.","ista":"Rabinovich A, Rubin S. 2012. Interpretations in trees with countably many branches. LICS: Symposium on Logic in Computer Science, LICS, , 6280474.","mla":"Rabinovich, Alexander, and Sasha Rubin. <i>Interpretations in Trees with Countably Many Branches</i>. 6280474, IEEE, 2012, doi:<a href=\"https://doi.org/10.1109/LICS.2012.65\">10.1109/LICS.2012.65</a>.","apa":"Rabinovich, A., &#38; Rubin, S. (2012). Interpretations in trees with countably many branches. Presented at the LICS: Symposium on Logic in Computer Science, Dubrovnik, Croatia: IEEE. <a href=\"https://doi.org/10.1109/LICS.2012.65\">https://doi.org/10.1109/LICS.2012.65</a>","ieee":"A. Rabinovich and S. Rubin, “Interpretations in trees with countably many branches,” presented at the LICS: Symposium on Logic in Computer Science, Dubrovnik, Croatia, 2012.","ama":"Rabinovich A, Rubin S. Interpretations in trees with countably many branches. In: IEEE; 2012. doi:<a href=\"https://doi.org/10.1109/LICS.2012.65\">10.1109/LICS.2012.65</a>"},"author":[{"first_name":"Alexander","last_name":"Rabinovich","full_name":"Rabinovich, Alexander"},{"last_name":"Rubin","first_name":"Sasha","full_name":"Rubin, Sasha","id":"2EC51194-F248-11E8-B48F-1D18A9856A87"}],"article_number":"6280474","alternative_title":["LICS"],"doi":"10.1109/LICS.2012.65","date_published":"2012-01-01T00:00:00Z","language":[{"iso":"eng"}],"project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23"}],"status":"public","title":"Interpretations in trees with countably many branches","ec_funded":1,"date_created":"2018-12-11T11:46:47Z","year":"2012","scopus_import":1,"_id":"496","conference":{"start_date":"2012-06-25","location":"Dubrovnik, Croatia","name":"LICS: Symposium on Logic in Computer Science","end_date":"2012-06-28"},"quality_controlled":"1","main_file_link":[{"url":"https://arise.or.at/pubpdf/Interpretations_in_Trees_with_Countably_Many_Branches.pdf","open_access":"1"}],"oa_version":"Preprint","publication_status":"published","publisher":"IEEE","department":[{"_id":"KrCh"}],"month":"01","abstract":[{"text":"We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations.","lang":"eng"}]},{"scopus_import":1,"page":"167 - 182","conference":{"end_date":"2012-09-06","start_date":"2012-09-03","location":"Fontainebleau, France","name":"EACSL: European Association for Computer Science Logic"},"license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","month":"09","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"KrCh"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:35Z","volume":16,"type":"conference","pubrep_id":"943","alternative_title":["LIPIcs"],"ddc":["004"],"intvolume":"        16","status":"public","tmp":{"image":"/images/cc_by_nc_nd.png","short":"CC BY-NC-ND (4.0)","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode"},"language":[{"iso":"eng"}],"date_published":"2012-09-01T00:00:00Z","doi":"10.4230/LIPIcs.CSL.2012.167","_id":"497","year":"2012","date_created":"2018-12-11T11:46:48Z","ec_funded":1,"oa_version":"Published Version","quality_controlled":"1","abstract":[{"lang":"eng","text":"One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath."}],"file":[{"file_name":"IST-2018-943-v1+1_2012_Chatterjee_Faster_Algorithms.pdf","relation":"main_file","date_created":"2018-12-12T10:08:50Z","file_id":"4712","date_updated":"2020-07-14T12:46:35Z","checksum":"f1b0dd99240800db2d7dbf9b5131fe5e","content_type":"application/pdf","file_size":471236,"creator":"system","access_level":"open_access"}],"publication_status":"published","related_material":{"record":[{"relation":"earlier_version","id":"5378","status":"public"}]},"oa":1,"publist_id":"7323","day":"01","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Chaubal, Siddhesh","first_name":"Siddhesh","last_name":"Chaubal"},{"full_name":"Kamath, Pritish","first_name":"Pritish","last_name":"Kamath"}],"date_updated":"2023-02-23T12:23:32Z","citation":{"short":"K. Chatterjee, S. Chaubal, P. Kamath, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 167–182.","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Alternating Refinement Relations</i>. Vol. 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 167–82, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2012.167\">10.4230/LIPIcs.CSL.2012.167</a>.","ieee":"K. Chatterjee, S. Chaubal, and P. Kamath, “Faster algorithms for alternating refinement relations,” presented at the EACSL: European Association for Computer Science Logic, Fontainebleau, France, 2012, vol. 16, pp. 167–182.","ama":"Chatterjee K, Chaubal S, Kamath P. Faster algorithms for alternating refinement relations. In: Vol 16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:167-182. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CSL.2012.167\">10.4230/LIPIcs.CSL.2012.167</a>","apa":"Chatterjee, K., Chaubal, S., &#38; Kamath, P. (2012). Faster algorithms for alternating refinement relations (Vol. 16, pp. 167–182). Presented at the EACSL: European Association for Computer Science Logic, Fontainebleau, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2012.167\">https://doi.org/10.4230/LIPIcs.CSL.2012.167</a>","chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Pritish Kamath. “Faster Algorithms for Alternating Refinement Relations,” 16:167–82. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. <a href=\"https://doi.org/10.4230/LIPIcs.CSL.2012.167\">https://doi.org/10.4230/LIPIcs.CSL.2012.167</a>.","ista":"Chatterjee K, Chaubal S, Kamath P. 2012. Faster algorithms for alternating refinement relations. EACSL: European Association for Computer Science Logic, LIPIcs, vol. 16, 167–182."},"has_accepted_license":"1","title":"Faster algorithms for alternating refinement relations","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}]},{"department":[{"_id":"NiBa"}],"publisher":"Wiley-Blackwell","month":"12","page":"913 - 924","acknowledgement":"We thank Graham Pickup, David Steer, Linda Broadhurst, Lan Li and Carole Elliott for technical assistance. The New\r\nSouth Wales Department of Environment and Climate Change, ACT Parks, Conservation and Lands and the\r\nDepartment of Sustainability and Environment in Victoria provided permits for seed and soil collection. We thank\r\nSpencer C. H. Barrett for comments that improved the quality of the manuscript.\r\n","language":[{"iso":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)"},"status":"public","doi":"10.1111/j.1752-4571.2012.00284.x","date_published":"2012-12-01T00:00:00Z","ddc":["576"],"intvolume":"         5","volume":5,"pubrep_id":"942","type":"journal_article","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:35Z","file":[{"file_name":"IST-2018-942-v1+1_Pickup_et_al-2012-Evolutionary_Applications.pdf","file_id":"4821","relation":"main_file","date_created":"2018-12-12T10:10:33Z","date_updated":"2020-07-14T12:46:35Z","checksum":"233007138606aca5a2f75f7ae1742f43","content_type":"application/pdf","file_size":396136,"access_level":"open_access","creator":"system"}],"abstract":[{"lang":"eng","text":"Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration."}],"publication_status":"published","oa_version":"Published Version","quality_controlled":"1","year":"2012","_id":"498","date_created":"2018-12-11T11:46:48Z","title":"Predicting local adaptation in fragmented plant populations: Implications for restoration genetics","issue":"8","has_accepted_license":"1","citation":{"chicago":"Pickup, Melinda, David Field, David Rowell, and Andrew Young. “Predicting Local Adaptation in Fragmented Plant Populations: Implications for Restoration Genetics.” <i>Evolutionary Applications</i>. Wiley-Blackwell, 2012. <a href=\"https://doi.org/10.1111/j.1752-4571.2012.00284.x\">https://doi.org/10.1111/j.1752-4571.2012.00284.x</a>.","ista":"Pickup M, Field D, Rowell D, Young A. 2012. Predicting local adaptation in fragmented plant populations: Implications for restoration genetics. Evolutionary Applications. 5(8), 913–924.","mla":"Pickup, Melinda, et al. “Predicting Local Adaptation in Fragmented Plant Populations: Implications for Restoration Genetics.” <i>Evolutionary Applications</i>, vol. 5, no. 8, Wiley-Blackwell, 2012, pp. 913–24, doi:<a href=\"https://doi.org/10.1111/j.1752-4571.2012.00284.x\">10.1111/j.1752-4571.2012.00284.x</a>.","apa":"Pickup, M., Field, D., Rowell, D., &#38; Young, A. (2012). Predicting local adaptation in fragmented plant populations: Implications for restoration genetics. <i>Evolutionary Applications</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/j.1752-4571.2012.00284.x\">https://doi.org/10.1111/j.1752-4571.2012.00284.x</a>","ieee":"M. Pickup, D. Field, D. Rowell, and A. Young, “Predicting local adaptation in fragmented plant populations: Implications for restoration genetics,” <i>Evolutionary Applications</i>, vol. 5, no. 8. Wiley-Blackwell, pp. 913–924, 2012.","ama":"Pickup M, Field D, Rowell D, Young A. Predicting local adaptation in fragmented plant populations: Implications for restoration genetics. <i>Evolutionary Applications</i>. 2012;5(8):913-924. doi:<a href=\"https://doi.org/10.1111/j.1752-4571.2012.00284.x\">10.1111/j.1752-4571.2012.00284.x</a>","short":"M. Pickup, D. Field, D. Rowell, A. Young, Evolutionary Applications 5 (2012) 913–924."},"date_updated":"2021-01-12T08:01:06Z","author":[{"last_name":"Pickup","first_name":"Melinda","full_name":"Pickup, Melinda","id":"2C78037E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6118-0541"},{"last_name":"Field","first_name":"David","full_name":"Field, David","id":"419049E2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4014-8478"},{"last_name":"Rowell","first_name":"David","full_name":"Rowell, David"},{"full_name":"Young, Andrew","first_name":"Andrew","last_name":"Young"}],"publication":"Evolutionary Applications","oa":1,"day":"01","publist_id":"7322"},{"date_published":"2012-04-30T00:00:00Z","doi":"10.1083/jcb.201204039","tmp":{"image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode"},"status":"public","language":[{"iso":"eng"}],"ddc":["570"],"intvolume":"       197","type":"journal_article","volume":197,"file_date_updated":"2020-07-14T12:46:36Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"04","publisher":"Rockefeller University Press","department":[{"_id":"MiSi"}],"license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","page":"347 - 349","scopus_import":1,"title":"Cell migration: Fibroblasts find a new way to get ahead","has_accepted_license":"1","issue":"3","author":[{"first_name":"Michael K","last_name":"Sixt","full_name":"Sixt, Michael K","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6620-9179"}],"citation":{"chicago":"Sixt, Michael K. “Cell Migration: Fibroblasts Find a New Way to Get Ahead.” <i>Journal of Cell Biology</i>. Rockefeller University Press, 2012. <a href=\"https://doi.org/10.1083/jcb.201204039\">https://doi.org/10.1083/jcb.201204039</a>.","ista":"Sixt MK. 2012. Cell migration: Fibroblasts find a new way to get ahead. Journal of Cell Biology. 197(3), 347–349.","mla":"Sixt, Michael K. “Cell Migration: Fibroblasts Find a New Way to Get Ahead.” <i>Journal of Cell Biology</i>, vol. 197, no. 3, Rockefeller University Press, 2012, pp. 347–49, doi:<a href=\"https://doi.org/10.1083/jcb.201204039\">10.1083/jcb.201204039</a>.","ama":"Sixt MK. Cell migration: Fibroblasts find a new way to get ahead. <i>Journal of Cell Biology</i>. 2012;197(3):347-349. doi:<a href=\"https://doi.org/10.1083/jcb.201204039\">10.1083/jcb.201204039</a>","ieee":"M. K. Sixt, “Cell migration: Fibroblasts find a new way to get ahead,” <i>Journal of Cell Biology</i>, vol. 197, no. 3. Rockefeller University Press, pp. 347–349, 2012.","apa":"Sixt, M. K. (2012). Cell migration: Fibroblasts find a new way to get ahead. <i>Journal of Cell Biology</i>. Rockefeller University Press. <a href=\"https://doi.org/10.1083/jcb.201204039\">https://doi.org/10.1083/jcb.201204039</a>","short":"M.K. Sixt, Journal of Cell Biology 197 (2012) 347–349."},"date_updated":"2021-01-12T08:01:11Z","publist_id":"7314","day":"30","oa":1,"publication":"Journal of Cell Biology","publication_status":"published","article_type":"original","file":[{"date_updated":"2020-07-14T12:46:36Z","file_name":"2012_CellBiology_Sixt.pdf","relation":"main_file","date_created":"2019-02-12T09:03:09Z","file_id":"5957","creator":"kschuh","access_level":"open_access","checksum":"45c02be33ebd99fc3077d60b9c90bdfa","content_type":"application/pdf","file_size":986566}],"quality_controlled":"1","article_processing_charge":"No","oa_version":"Published Version","date_created":"2018-12-11T11:46:51Z","_id":"506","year":"2012"},{"month":"07","department":[{"_id":"KrCh"}],"related_material":{"record":[{"status":"public","id":"2956","relation":"later_version"}]},"publisher":"IST Austria","publication_status":"published","abstract":[{"lang":"eng","text":"Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and ω-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two- player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP- hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two- player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded."}],"file":[{"content_type":"application/pdf","file_size":592098,"checksum":"a03c08c1589dbb0c96183a8bcf3ab240","creator":"system","access_level":"open_access","date_created":"2018-12-12T11:54:00Z","relation":"main_file","file_id":"5522","file_name":"IST-2012-002_IST-2012-0002.pdf","date_updated":"2020-07-14T12:46:38Z"}],"oa_version":"Published Version","page":"33","date_created":"2018-12-12T11:38:59Z","_id":"5377","year":"2012","date_published":"2012-07-02T00:00:00Z","doi":"10.15479/AT:IST-2012-0002","status":"public","title":"Mean-payoff pushdown games","language":[{"iso":"eng"}],"has_accepted_license":"1","ddc":["000","005"],"alternative_title":["IST Austria Technical Report"],"citation":{"mla":"Chatterjee, Krishnendu, and Yaron Velner. <i>Mean-Payoff Pushdown Games</i>. IST Austria, 2012, doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0002\">10.15479/AT:IST-2012-0002</a>.","ieee":"K. Chatterjee and Y. Velner, <i>Mean-payoff pushdown games</i>. IST Austria, 2012.","ama":"Chatterjee K, Velner Y. <i>Mean-Payoff Pushdown Games</i>. IST Austria; 2012. doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0002\">10.15479/AT:IST-2012-0002</a>","apa":"Chatterjee, K., &#38; Velner, Y. (2012). <i>Mean-payoff pushdown games</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2012-0002\">https://doi.org/10.15479/AT:IST-2012-0002</a>","chicago":"Chatterjee, Krishnendu, and Yaron Velner. <i>Mean-Payoff Pushdown Games</i>. IST Austria, 2012. <a href=\"https://doi.org/10.15479/AT:IST-2012-0002\">https://doi.org/10.15479/AT:IST-2012-0002</a>.","ista":"Chatterjee K, Velner Y. 2012. Mean-payoff pushdown games, IST Austria, 33p.","short":"K. Chatterjee, Y. Velner, Mean-Payoff Pushdown Games, IST Austria, 2012."},"date_updated":"2023-02-23T11:05:50Z","type":"technical_report","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Yaron","last_name":"Velner","full_name":"Velner, Yaron"}],"pubrep_id":"10","file_date_updated":"2020-07-14T12:46:38Z","day":"02","oa":1,"publication_identifier":{"issn":["2664-1690"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"date_created":"2018-12-12T11:38:59Z","year":"2012","_id":"5378","page":"21","oa_version":"Published Version","publication_status":"published","department":[{"_id":"KrCh"}],"publisher":"IST Austria","related_material":{"record":[{"relation":"later_version","id":"497","status":"public"}]},"month":"07","file":[{"access_level":"open_access","creator":"system","content_type":"application/pdf","file_size":394256,"checksum":"ec8d1857cc7095d3de5107a0162ced37","date_updated":"2020-07-14T12:46:39Z","file_id":"5489","relation":"main_file","date_created":"2018-12-12T11:53:28Z","file_name":"IST-2012-0001_IST-2012-0001.pdf"}],"abstract":[{"text":"One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.","lang":"eng"}],"file_date_updated":"2020-07-14T12:46:39Z","day":"04","publication_identifier":{"issn":["2664-1690"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"pubrep_id":"14","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Chaubal, Siddhesh","last_name":"Chaubal","first_name":"Siddhesh"},{"first_name":"Pritish","last_name":"Kamath","full_name":"Kamath, Pritish"}],"type":"technical_report","date_updated":"2023-02-23T12:21:38Z","citation":{"short":"K. Chatterjee, S. Chaubal, P. Kamath, Faster Algorithms for Alternating Refinement Relations, IST Austria, 2012.","chicago":"Chatterjee, Krishnendu, Siddhesh Chaubal, and Pritish Kamath. <i>Faster Algorithms for Alternating Refinement Relations</i>. IST Austria, 2012. <a href=\"https://doi.org/10.15479/AT:IST-2012-0001\">https://doi.org/10.15479/AT:IST-2012-0001</a>.","ista":"Chatterjee K, Chaubal S, Kamath P. 2012. Faster algorithms for alternating refinement relations, IST Austria, 21p.","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Alternating Refinement Relations</i>. IST Austria, 2012, doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0001\">10.15479/AT:IST-2012-0001</a>.","apa":"Chatterjee, K., Chaubal, S., &#38; Kamath, P. (2012). <i>Faster algorithms for alternating refinement relations</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2012-0001\">https://doi.org/10.15479/AT:IST-2012-0001</a>","ieee":"K. Chatterjee, S. Chaubal, and P. Kamath, <i>Faster algorithms for alternating refinement relations</i>. IST Austria, 2012.","ama":"Chatterjee K, Chaubal S, Kamath P. <i>Faster Algorithms for Alternating Refinement Relations</i>. IST Austria; 2012. doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0001\">10.15479/AT:IST-2012-0001</a>"},"has_accepted_license":"1","ddc":["000","005"],"alternative_title":["IST Austria Technical Report"],"doi":"10.15479/AT:IST-2012-0001","date_published":"2012-07-04T00:00:00Z","language":[{"iso":"eng"}],"title":"Faster algorithms for alternating refinement relations","status":"public"},{"type":"technical_report","citation":{"mla":"Korc, Filip, et al. <i>Approximating Marginals Using Discrete Energy Minimization</i>. IST Austria, 2012, doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0003\">10.15479/AT:IST-2012-0003</a>.","ieee":"F. Korc, V. Kolmogorov, and C. Lampert, <i>Approximating marginals using discrete energy minimization</i>. IST Austria, 2012.","ama":"Korc F, Kolmogorov V, Lampert C. <i>Approximating Marginals Using Discrete Energy Minimization</i>. IST Austria; 2012. doi:<a href=\"https://doi.org/10.15479/AT:IST-2012-0003\">10.15479/AT:IST-2012-0003</a>","apa":"Korc, F., Kolmogorov, V., &#38; Lampert, C. (2012). <i>Approximating marginals using discrete energy minimization</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2012-0003\">https://doi.org/10.15479/AT:IST-2012-0003</a>","chicago":"Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. <i>Approximating Marginals Using Discrete Energy Minimization</i>. IST Austria, 2012. <a href=\"https://doi.org/10.15479/AT:IST-2012-0003\">https://doi.org/10.15479/AT:IST-2012-0003</a>.","ista":"Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization, IST Austria, 13p.","short":"F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete Energy Minimization, IST Austria, 2012."},"date_updated":"2023-02-23T11:13:22Z","author":[{"first_name":"Filip","last_name":"Korc","full_name":"Korc, Filip","id":"476A2FD6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"},{"orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","last_name":"Lampert"}],"pubrep_id":"36","oa":1,"publication_identifier":{"issn":["2664-1690"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:46:44Z","day":"23","status":"public","title":"Approximating marginals using discrete energy minimization","language":[{"iso":"eng"}],"date_published":"2012-07-23T00:00:00Z","doi":"10.15479/AT:IST-2012-0003","ddc":["000"],"alternative_title":["IST Austria Technical Report"],"has_accepted_license":"1","page":"13","_id":"5396","year":"2012","date_created":"2018-12-12T11:39:06Z","abstract":[{"text":"We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete  Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it  from training data. Experimental results show that for certain types of graphs a learned function can out-perform the  Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.","lang":"eng"}],"file":[{"date_updated":"2020-07-14T12:46:44Z","file_name":"IST-2012-0003_IST-2012-0003.pdf","file_id":"5490","relation":"main_file","date_created":"2018-12-12T11:53:29Z","access_level":"open_access","creator":"system","checksum":"7e0ba85ad123b13223aaf6cdde2d288c","file_size":618744,"content_type":"application/pdf"}],"month":"07","department":[{"_id":"VlKo"},{"_id":"ChLa"}],"related_material":{"record":[{"status":"public","id":"3124","relation":"earlier_version"}]},"publication_status":"published","publisher":"IST Austria","oa_version":"Published Version"},{"department":[{"_id":"ToHe"}],"publisher":"Springer Berlin Heidelberg","conference":{"location":"Thiruvananthapuram, Kerala, India","start_date":"2012-10-03","name":"ATVA 2012","end_date":"2012-10-06"},"page":"107-121","place":"Berlin, Heidelberg","language":[{"iso":"eng"}],"status":"public","doi":"10.1007/978-3-642-33386-6_10","date_published":"2012-01-01T00:00:00Z","ddc":["005"],"intvolume":"      7561","volume":7561,"pubrep_id":"180","type":"book_chapter","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-14T12:47:10Z","file":[{"access_level":"open_access","creator":"dernst","file_size":465502,"content_type":"application/pdf","checksum":"68415837a315de3cc4d120f6019d752c","date_updated":"2020-07-14T12:47:10Z","file_id":"5746","date_created":"2018-12-18T13:07:35Z","relation":"main_file","file_name":"2012_ATVA_Gupta.pdf"}],"publication_status":"published","oa_version":"None","article_processing_charge":"No","quality_controlled":"1","year":"2012","_id":"5745","date_created":"2018-12-18T13:01:46Z","ec_funded":1,"series_title":"LNCS","project":[{"name":"Quantitative Reactive Modeling","call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"}],"title":"Improved Single Pass Algorithms for Resolution Proof Reduction","has_accepted_license":"1","citation":{"short":"A. Gupta, in:, Automated Technology for Verification and Analysis, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 107–121.","chicago":"Gupta, Ashutosh. “Improved Single Pass Algorithms for Resolution Proof Reduction.” In <i>Automated Technology for Verification and Analysis</i>, 7561:107–21. LNCS. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. <a href=\"https://doi.org/10.1007/978-3-642-33386-6_10\">https://doi.org/10.1007/978-3-642-33386-6_10</a>.","ista":"Gupta A. 2012.Improved Single Pass Algorithms for Resolution Proof Reduction. In: Automated Technology for Verification and Analysis. vol. 7561, 107–121.","mla":"Gupta, Ashutosh. “Improved Single Pass Algorithms for Resolution Proof Reduction.” <i>Automated Technology for Verification and Analysis</i>, vol. 7561, Springer Berlin Heidelberg, 2012, pp. 107–21, doi:<a href=\"https://doi.org/10.1007/978-3-642-33386-6_10\">10.1007/978-3-642-33386-6_10</a>.","ieee":"A. Gupta, “Improved Single Pass Algorithms for Resolution Proof Reduction,” in <i>Automated Technology for Verification and Analysis</i>, vol. 7561, Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 107–121.","apa":"Gupta, A. (2012). Improved Single Pass Algorithms for Resolution Proof Reduction. In <i>Automated Technology for Verification and Analysis</i> (Vol. 7561, pp. 107–121). Berlin, Heidelberg: Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-642-33386-6_10\">https://doi.org/10.1007/978-3-642-33386-6_10</a>","ama":"Gupta A. Improved Single Pass Algorithms for Resolution Proof Reduction. In: <i>Automated Technology for Verification and Analysis</i>. Vol 7561. LNCS. Berlin, Heidelberg: Springer Berlin Heidelberg; 2012:107-121. doi:<a href=\"https://doi.org/10.1007/978-3-642-33386-6_10\">10.1007/978-3-642-33386-6_10</a>"},"author":[{"last_name":"Gupta","first_name":"Ashutosh","full_name":"Gupta, Ashutosh"}],"date_updated":"2023-09-05T14:15:29Z","publication":"Automated Technology for Verification and Analysis","publication_identifier":{"issn":["0302-9743"],"isbn":["9783642333859","9783642333866"],"eissn":["1611-3349"]},"oa":1},{"quality_controlled":"1","article_processing_charge":"No","oa_version":"Published Version","publication_status":"published","article_type":"original","abstract":[{"lang":"eng","text":"First we note that the best polynomial approximation to vertical bar x vertical bar on the set, which consists of an interval on the positive half-axis and a point on the negative half-axis, can be given by means of the classical Chebyshev polynomials. Then we explore the cases when a solution of the related problem on two intervals can be given in elementary functions."}],"date_created":"2019-06-27T08:16:56Z","_id":"6588","year":"2012","issue":"1","title":"Elementary solutions of the Bernstein problem on two intervals","external_id":{"isi":["000301173600004"]},"day":"01","oa":1,"publication":"Journal of Mathematical Physics, Analysis, Geometry","publication_identifier":{"issn":["1812-9471"]},"citation":{"short":"F. Pausinger, Journal of Mathematical Physics, Analysis, Geometry 8 (2012) 63–78.","ista":"Pausinger F. 2012. Elementary solutions of the Bernstein problem on two intervals. Journal of Mathematical Physics, Analysis, Geometry. 8(1), 63–78.","chicago":"Pausinger, Florian. “Elementary Solutions of the Bernstein Problem on Two Intervals.” <i>Journal of Mathematical Physics, Analysis, Geometry</i>. B. Verkin Institute for Low Temperature Physics and Engineering, 2012.","apa":"Pausinger, F. (2012). Elementary solutions of the Bernstein problem on two intervals. <i>Journal of Mathematical Physics, Analysis, Geometry</i>. B. Verkin Institute for Low Temperature Physics and Engineering.","ama":"Pausinger F. Elementary solutions of the Bernstein problem on two intervals. <i>Journal of Mathematical Physics, Analysis, Geometry</i>. 2012;8(1):63-78.","ieee":"F. Pausinger, “Elementary solutions of the Bernstein problem on two intervals,” <i>Journal of Mathematical Physics, Analysis, Geometry</i>, vol. 8, no. 1. B. Verkin Institute for Low Temperature Physics and Engineering, pp. 63–78, 2012.","mla":"Pausinger, Florian. “Elementary Solutions of the Bernstein Problem on Two Intervals.” <i>Journal of Mathematical Physics, Analysis, Geometry</i>, vol. 8, no. 1, B. Verkin Institute for Low Temperature Physics and Engineering, 2012, pp. 63–78."},"date_updated":"2023-10-16T09:41:31Z","author":[{"orcid":"0000-0002-8379-3768","full_name":"Pausinger, Florian","id":"2A77D7A2-F248-11E8-B48F-1D18A9856A87","last_name":"Pausinger","first_name":"Florian"}],"main_file_link":[{"url":"http://mi.mathnet.ru/eng/jmag525","open_access":"1"}],"isi":1,"month":"01","publisher":"B. Verkin Institute for Low Temperature Physics and Engineering","department":[{"_id":"HeEd"}],"acknowledgement":"This work is supported by the Austrian Science Fund (FWF), Project P22025-N18.\r\n","scopus_import":"1","page":"63-78","intvolume":"         8","date_published":"2012-01-01T00:00:00Z","status":"public","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","volume":8},{"article_processing_charge":"No","oa_version":"Published Version","quality_controlled":"1","abstract":[{"lang":"eng","text":"The Arabidopsis thaliana central cell, the companion cell of the egg, undergoes DNA demethylation before fertilization, but the targeting preferences, mechanism, and biological significance of this process remain unclear. Here, we show that active DNA demethylation mediated by the DEMETER DNA glycosylase accounts for all of the demethylation in the central cell and preferentially targets small, AT-rich, and nucleosome-depleted euchromatic transposable elements. The vegetative cell, the companion cell of sperm, also undergoes DEMETER-dependent demethylation of similar sequences, and lack of DEMETER in vegetative cells causes reduced small RNA–directed DNA methylation of transposons in sperm. Our results demonstrate that demethylation in companion cells reinforces transposon methylation in plant gametes and likely contributes to stable silencing of transposable elements across generations."}],"article_type":"original","publication_status":"published","_id":"9451","year":"2012","date_created":"2021-06-04T07:51:31Z","pmid":1,"issue":"6100","has_accepted_license":"1","external_id":{"pmid":["22984074"]},"title":"Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes","oa":1,"publication":"Science","publication_identifier":{"eissn":["1095-9203"],"issn":["0036-8075"]},"day":"14","citation":{"chicago":"Ibarra, Christian A., Xiaoqi Feng, Vera K. Schoft, Tzung-Fu Hsieh, Rie Uzawa, Jessica A. Rodrigues, Assaf Zemach, et al. “Active DNA Demethylation in Plant Companion Cells Reinforces Transposon Methylation in Gametes.” <i>Science</i>. American Association for the Advancement of Science, 2012. <a href=\"https://doi.org/10.1126/science.1224839\">https://doi.org/10.1126/science.1224839</a>.","ista":"Ibarra CA, Feng X, Schoft VK, Hsieh T-F, Uzawa R, Rodrigues JA, Zemach A, Chumak N, Machlicova A, Nishimura T, Rojas D, Fischer RL, Tamaru H, Zilberman D. 2012. Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes. Science. 337(6100), 1360–1364.","mla":"Ibarra, Christian A., et al. “Active DNA Demethylation in Plant Companion Cells Reinforces Transposon Methylation in Gametes.” <i>Science</i>, vol. 337, no. 6100, American Association for the Advancement of Science, 2012, pp. 1360–64, doi:<a href=\"https://doi.org/10.1126/science.1224839\">10.1126/science.1224839</a>.","ama":"Ibarra CA, Feng X, Schoft VK, et al. Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes. <i>Science</i>. 2012;337(6100):1360-1364. doi:<a href=\"https://doi.org/10.1126/science.1224839\">10.1126/science.1224839</a>","ieee":"C. A. Ibarra <i>et al.</i>, “Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes,” <i>Science</i>, vol. 337, no. 6100. American Association for the Advancement of Science, pp. 1360–1364, 2012.","apa":"Ibarra, C. A., Feng, X., Schoft, V. K., Hsieh, T.-F., Uzawa, R., Rodrigues, J. A., … Zilberman, D. (2012). Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes. <i>Science</i>. American Association for the Advancement of Science. <a href=\"https://doi.org/10.1126/science.1224839\">https://doi.org/10.1126/science.1224839</a>","short":"C.A. Ibarra, X. Feng, V.K. Schoft, T.-F. Hsieh, R. Uzawa, J.A. Rodrigues, A. Zemach, N. Chumak, A. Machlicova, T. Nishimura, D. Rojas, R.L. Fischer, H. Tamaru, D. Zilberman, Science 337 (2012) 1360–1364."},"author":[{"first_name":"Christian A.","last_name":"Ibarra","full_name":"Ibarra, Christian A."},{"last_name":"Feng","first_name":"Xiaoqi","full_name":"Feng, Xiaoqi"},{"last_name":"Schoft","first_name":"Vera K.","full_name":"Schoft, Vera K."},{"full_name":"Hsieh, Tzung-Fu","first_name":"Tzung-Fu","last_name":"Hsieh"},{"first_name":"Rie","last_name":"Uzawa","full_name":"Uzawa, Rie"},{"full_name":"Rodrigues, Jessica A.","last_name":"Rodrigues","first_name":"Jessica A."},{"full_name":"Zemach, Assaf","first_name":"Assaf","last_name":"Zemach"},{"first_name":"Nina","last_name":"Chumak","full_name":"Chumak, Nina"},{"first_name":"Adriana","last_name":"Machlicova","full_name":"Machlicova, Adriana"},{"full_name":"Nishimura, Toshiro","last_name":"Nishimura","first_name":"Toshiro"},{"full_name":"Rojas, Denisse","first_name":"Denisse","last_name":"Rojas"},{"last_name":"Fischer","first_name":"Robert L.","full_name":"Fischer, Robert L."},{"full_name":"Tamaru, Hisashi","last_name":"Tamaru","first_name":"Hisashi"},{"orcid":"0000-0002-0123-8649","full_name":"Zilberman, Daniel","id":"6973db13-dd5f-11ea-814e-b3e5455e9ed1","last_name":"Zilberman","first_name":"Daniel"}],"date_updated":"2021-12-14T08:28:51Z","main_file_link":[{"open_access":"1","url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4034762/"}],"month":"09","publisher":"American Association for the Advancement of Science","department":[{"_id":"DaZi"}],"scopus_import":"1","page":"1360-1364","extern":"1","intvolume":"       337","ddc":["580"],"status":"public","language":[{"iso":"eng"}],"date_published":"2012-09-14T00:00:00Z","doi":"10.1126/science.1224839","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","volume":337,"type":"journal_article"},{"scopus_import":"1","month":"10","department":[{"_id":"DaZi"}],"publisher":"Public Library of Science","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1371/journal.pgen.1002988"}],"volume":8,"type":"journal_article","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","status":"public","language":[{"iso":"eng"}],"date_published":"2012-10-11T00:00:00Z","doi":"10.1371/journal.pgen.1002988","extern":"1","intvolume":"         8","_id":"9497","year":"2012","pmid":1,"date_created":"2021-06-07T10:55:27Z","abstract":[{"lang":"eng","text":"The regulation of eukaryotic chromatin relies on interactions between many epigenetic factors, including histone modifications, DNA methylation, and the incorporation of histone variants. H2A.Z, one of the most conserved but enigmatic histone variants that is enriched at the transcriptional start sites of genes, has been implicated in a variety of chromosomal processes. Recently, we reported a genome-wide anticorrelation between H2A.Z and DNA methylation, an epigenetic hallmark of heterochromatin that has also been found in the bodies of active genes in plants and animals. Here, we investigate the basis of this anticorrelation using a novel h2a.z loss-of-function line in Arabidopsis thaliana. Through genome-wide bisulfite sequencing, we demonstrate that loss of H2A.Z in Arabidopsis has only a minor effect on the level or profile of DNA methylation in genes, and we propose that the global anticorrelation between DNA methylation and H2A.Z is primarily caused by the exclusion of H2A.Z from methylated DNA. RNA sequencing and genomic mapping of H2A.Z show that H2A.Z enrichment across gene bodies, rather than at the TSS, is correlated with lower transcription levels and higher measures of gene responsiveness. Loss of H2A.Z causes misregulation of many genes that are disproportionately associated with response to environmental and developmental stimuli. We propose that H2A.Z deposition in gene bodies promotes variability in levels and patterns of gene expression, and that a major function of genic DNA methylation is to exclude H2A.Z from constitutively expressed genes."}],"publication_status":"published","article_type":"original","article_processing_charge":"No","oa_version":"Published Version","quality_controlled":"1","author":[{"full_name":"Coleman-Derr, Devin","first_name":"Devin","last_name":"Coleman-Derr"},{"id":"6973db13-dd5f-11ea-814e-b3e5455e9ed1","full_name":"Zilberman, Daniel","orcid":"0000-0002-0123-8649","last_name":"Zilberman","first_name":"Daniel"}],"date_updated":"2021-12-14T08:29:57Z","citation":{"short":"D. Coleman-Derr, D. Zilberman, PLoS Genetics 8 (2012).","ista":"Coleman-Derr D, Zilberman D. 2012. Deposition of histone variant H2A.Z within gene bodies regulates responsive genes. PLoS Genetics. 8(10), e1002988.","chicago":"Coleman-Derr, Devin, and Daniel Zilberman. “Deposition of Histone Variant H2A.Z within Gene Bodies Regulates Responsive Genes.” <i>PLoS Genetics</i>. Public Library of Science, 2012. <a href=\"https://doi.org/10.1371/journal.pgen.1002988\">https://doi.org/10.1371/journal.pgen.1002988</a>.","ieee":"D. Coleman-Derr and D. Zilberman, “Deposition of histone variant H2A.Z within gene bodies regulates responsive genes,” <i>PLoS Genetics</i>, vol. 8, no. 10. Public Library of Science, 2012.","ama":"Coleman-Derr D, Zilberman D. Deposition of histone variant H2A.Z within gene bodies regulates responsive genes. <i>PLoS Genetics</i>. 2012;8(10). doi:<a href=\"https://doi.org/10.1371/journal.pgen.1002988\">10.1371/journal.pgen.1002988</a>","apa":"Coleman-Derr, D., &#38; Zilberman, D. (2012). Deposition of histone variant H2A.Z within gene bodies regulates responsive genes. <i>PLoS Genetics</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pgen.1002988\">https://doi.org/10.1371/journal.pgen.1002988</a>","mla":"Coleman-Derr, Devin, and Daniel Zilberman. “Deposition of Histone Variant H2A.Z within Gene Bodies Regulates Responsive Genes.” <i>PLoS Genetics</i>, vol. 8, no. 10, e1002988, Public Library of Science, 2012, doi:<a href=\"https://doi.org/10.1371/journal.pgen.1002988\">10.1371/journal.pgen.1002988</a>."},"oa":1,"publication":"PLoS Genetics","publication_identifier":{"issn":["1553-7390"],"eissn":["1553-7404"]},"day":"11","external_id":{"pmid":["23071449"]},"title":"Deposition of histone variant H2A.Z within gene bodies regulates responsive genes","article_number":"e1002988","issue":"10"}]