[{"title":"Specification-centered robustness","date_published":"2011-07-14T00:00:00Z","publisher":"IEEE","abstract":[{"lang":"eng","text":"In addition to being correct, a system should be robust, that is, it should behave reasonably even after receiving unexpected inputs. In this paper, we summarize two formal notions of robustness that we have introduced previously for reactive systems. One of the notions is based on assigning costs for failures on a user-provided notion of incorrect transitions in a specification. Here, we define a system to be robust if a finite number of incorrect inputs does not lead to an infinite number of incorrect outputs. We also give a more refined notion of robustness that aims to minimize the ratio of output failures to input failures. The second notion is aimed at liveness. In contrast to the previous notion, it has no concept of recovery from an error. Instead, it compares the ratio of the number of liveness constraints that the system violates to the number of liveness constraints that the environment violates."}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Bloem, Roderick, et al. “Specification-Centered Robustness.” <i>6th IEEE International Symposium on Industrial and Embedded Systems</i>, IEEE, 2011, pp. 176–85, doi:<a href=\"https://doi.org/10.1109/SIES.2011.5953660\">10.1109/SIES.2011.5953660</a>.","short":"R. Bloem, K. Chatterjee, K. Greimel, T.A. Henzinger, B. Jobstmann, in:, 6th IEEE International Symposium on Industrial and Embedded Systems, IEEE, 2011, pp. 176–185.","apa":"Bloem, R., Chatterjee, K., Greimel, K., Henzinger, T. A., &#38; Jobstmann, B. (2011). Specification-centered robustness. In <i>6th IEEE International Symposium on Industrial and Embedded Systems</i> (pp. 176–185). Vasteras, Sweden: IEEE. <a href=\"https://doi.org/10.1109/SIES.2011.5953660\">https://doi.org/10.1109/SIES.2011.5953660</a>","ista":"Bloem R, Chatterjee K, Greimel K, Henzinger TA, Jobstmann B. 2011. Specification-centered robustness. 6th IEEE International Symposium on Industrial and Embedded Systems.  SIES: International Symposium on Industrial Embedded Systems, 176–185.","chicago":"Bloem, Roderick, Krishnendu Chatterjee, Karin Greimel, Thomas A Henzinger, and Barbara Jobstmann. “Specification-Centered Robustness.” In <i>6th IEEE International Symposium on Industrial and Embedded Systems</i>, 176–85. IEEE, 2011. <a href=\"https://doi.org/10.1109/SIES.2011.5953660\">https://doi.org/10.1109/SIES.2011.5953660</a>.","ama":"Bloem R, Chatterjee K, Greimel K, Henzinger TA, Jobstmann B. Specification-centered robustness. In: <i>6th IEEE International Symposium on Industrial and Embedded Systems</i>. IEEE; 2011:176-185. doi:<a href=\"https://doi.org/10.1109/SIES.2011.5953660\">10.1109/SIES.2011.5953660</a>","ieee":"R. Bloem, K. Chatterjee, K. Greimel, T. A. Henzinger, and B. Jobstmann, “Specification-centered robustness,” in <i>6th IEEE International Symposium on Industrial and Embedded Systems</i>, Vasteras, Sweden, 2011, pp. 176–185."},"date_updated":"2021-01-12T07:42:36Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication":"6th IEEE International Symposium on Industrial and Embedded Systems","publist_id":"3323","scopus_import":1,"year":"2011","page":"176 - 185","doi":"10.1109/SIES.2011.5953660","day":"14","oa":1,"article_processing_charge":"No","language":[{"iso":"eng"}],"month":"07","author":[{"full_name":"Bloem, Roderick","first_name":"Roderick","last_name":"Bloem"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"full_name":"Greimel, Karin","last_name":"Greimel","first_name":"Karin"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724"},{"full_name":"Jobstmann, Barbara","first_name":"Barbara","last_name":"Jobstmann"}],"oa_version":"Published Version","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23"},{"_id":"25F1337C-B435-11E9-9278-68D0E5697425","grant_number":"214373","name":"Design for Embedded Systems","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","ec_funded":1,"conference":{"end_date":"2011-06-17","start_date":"2011-06-15","location":"Vasteras, Sweden","name":" SIES: International Symposium on Industrial Embedded Systems"},"main_file_link":[{"open_access":"1","url":"https://openlib.tugraz.at/download.php?id=5cb57c8a49344&location=browse"}],"status":"public","_id":"3316","type":"conference","date_created":"2018-12-11T12:02:38Z"},{"title":"How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses","volume":15,"date_published":"2011-12-04T00:00:00Z","language":[{"iso":"eng"}],"publisher":"Nature Publishing Group","abstract":[{"lang":"eng","text":"Parvalbumin is thought to act in a manner similar to EGTA, but how a slow Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear. Direct measurements of parvalbumin concentration and paired recordings in rodent hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics only when expressed at high levels. Modeling suggests that, in high concentrations, parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition with local saturation of endogenous fixed buffers."}],"month":"12","publication_status":"published","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Eggermann","first_name":"Emmanuel","full_name":"Eggermann, Emmanuel"},{"full_name":"Jonas, Peter M","id":"353C1B58-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5001-4804","last_name":"Jonas","first_name":"Peter M"}],"citation":{"short":"E. Eggermann, P.M. Jonas, Nature Neuroscience 15 (2011) 20–22.","mla":"Eggermann, Emmanuel, and Peter M. Jonas. “How the ‘Slow’ Ca(2+) Buffer Parvalbumin Affects Transmitter Release in Nanodomain Coupling Regimes at GABAergic Synapses.” <i>Nature Neuroscience</i>, vol. 15, Nature Publishing Group, 2011, pp. 20–22, doi:<a href=\"https://doi.org/10.1038/nn.3002\">10.1038/nn.3002</a>.","ieee":"E. Eggermann and P. M. Jonas, “How the ‘slow’ Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses,” <i>Nature Neuroscience</i>, vol. 15. Nature Publishing Group, pp. 20–22, 2011.","ista":"Eggermann E, Jonas PM. 2011. How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses. Nature Neuroscience. 15, 20–22.","ama":"Eggermann E, Jonas PM. How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses. <i>Nature Neuroscience</i>. 2011;15:20-22. doi:<a href=\"https://doi.org/10.1038/nn.3002\">10.1038/nn.3002</a>","chicago":"Eggermann, Emmanuel, and Peter M Jonas. “How the ‘Slow’ Ca(2+) Buffer Parvalbumin Affects Transmitter Release in Nanodomain Coupling Regimes at GABAergic Synapses.” <i>Nature Neuroscience</i>. Nature Publishing Group, 2011. <a href=\"https://doi.org/10.1038/nn.3002\">https://doi.org/10.1038/nn.3002</a>.","apa":"Eggermann, E., &#38; Jonas, P. M. (2011). How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses. <i>Nature Neuroscience</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/nn.3002\">https://doi.org/10.1038/nn.3002</a>"},"oa_version":"Submitted Version","date_updated":"2021-01-12T07:42:37Z","department":[{"_id":"PeJo"}],"quality_controlled":"1","publication":"Nature Neuroscience","intvolume":"        15","publist_id":"3321","scopus_import":1,"page":"20 - 22","doi":"10.1038/nn.3002","main_file_link":[{"open_access":"1","url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3631701/"}],"year":"2011","status":"public","day":"04","_id":"3318","type":"journal_article","oa":1,"date_created":"2018-12-11T12:02:38Z"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Quadrianto","first_name":"Novi","full_name":"Quadrianto, Novi"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","first_name":"Christoph","last_name":"Lampert","orcid":"0000-0001-8622-7887"}],"citation":{"ista":"Quadrianto N, Lampert C. 2011. Learning multi-view neighborhood preserving projections. ICML: International Conference on Machine Learning, 425–432.","ama":"Quadrianto N, Lampert C. Learning multi-view neighborhood preserving projections. In: ML Research Press; 2011:425-432.","chicago":"Quadrianto, Novi, and Christoph Lampert. “Learning Multi-View Neighborhood Preserving Projections,” 425–32. ML Research Press, 2011.","apa":"Quadrianto, N., &#38; Lampert, C. (2011). Learning multi-view neighborhood preserving projections (pp. 425–432). Presented at the ICML: International Conference on Machine Learning, Bellevue, United States: ML Research Press.","ieee":"N. Quadrianto and C. Lampert, “Learning multi-view neighborhood preserving projections,” presented at the ICML: International Conference on Machine Learning, Bellevue, United States, 2011, pp. 425–432.","mla":"Quadrianto, Novi, and Christoph Lampert. <i>Learning Multi-View Neighborhood Preserving Projections</i>. ML Research Press, 2011, pp. 425–32.","short":"N. Quadrianto, C. Lampert, in:, ML Research Press, 2011, pp. 425–432."},"oa_version":"None","department":[{"_id":"ChLa"}],"date_updated":"2023-10-17T11:59:50Z","title":"Learning multi-view neighborhood preserving projections","article_processing_charge":"No","publisher":"ML Research Press","language":[{"iso":"eng"}],"date_published":"2011-01-01T00:00:00Z","publication_status":"published","month":"01","abstract":[{"text":"We address the problem of metric learning for multi-view data, namely the construction of embedding projections from data in different representations into a shared feature space, such that the Euclidean distance in this space provides a meaningful within-view as well as between-view similarity. Our motivation stems from the problem of cross-media retrieval tasks, where the availability of a joint Euclidean distance function is a pre-requisite to allow fast, in particular hashing-based, nearest neighbor queries. We formulate an objective function that expresses the intuitive concept that matching samples are mapped closely together in the output space, whereas non-matching samples are pushed apart, no matter in which view they are available. The resulting optimization problem is not convex, but it can be decomposed explicitly into a convex and a concave part, thereby allowing efficient optimization using the convex-concave procedure. Experiments on an image retrieval task show that nearest-neighbor based cross-view retrieval is indeed possible, and the proposed technique improves the retrieval accuracy over baseline techniques.","lang":"eng"}],"year":"2011","page":"425 - 432","status":"public","day":"01","_id":"3319","type":"conference","date_created":"2018-12-11T12:02:39Z","publist_id":"3316","conference":{"location":"Bellevue, United States","name":"ICML: International Conference on Machine Learning","start_date":"2011-06-28","end_date":"2011-07-02"},"scopus_import":"1"},{"ddc":["000"],"abstract":[{"lang":"eng","text":"Powerful statistical models that can be learned efficiently from large amounts of data are currently revolutionizing computer vision. These models possess a rich internal structure reflecting task-specific relations and constraints. This monograph introduces the reader to the most popular classes of structured models in computer vision. Our focus is discrete undirected graphical models which we cover in detail together with a description of algorithms for both probabilistic inference and maximum a posteriori inference. We discuss separately recently successful techniques for prediction in general structured models. In the second part of this monograph we describe methods for parameter learning where we distinguish the classic maximum likelihood based methods from the more recent prediction-based parameter learning methods. We highlight developments to enhance current models and discuss kernelized models and latent variable models. To make the monograph more practical and to provide links to further study we provide examples of successful application of many methods in the computer vision literature."}],"publication_status":"published","title":"Structured learning and prediction in computer vision","publisher":"Now Publishers","date_published":"2011-05-23T00:00:00Z","file_date_updated":"2020-07-14T12:46:07Z","citation":{"ama":"Nowozin S, Lampert C. Structured learning and prediction in computer vision. <i>Foundations and Trends in Computer Graphics and Vision</i>. 2011;6(3-4):185-365. doi:<a href=\"https://doi.org/10.1561/0600000033\">10.1561/0600000033</a>","chicago":"Nowozin, Sebastian, and Christoph Lampert. “Structured Learning and Prediction in Computer Vision.” <i>Foundations and Trends in Computer Graphics and Vision</i>. Now Publishers, 2011. <a href=\"https://doi.org/10.1561/0600000033\">https://doi.org/10.1561/0600000033</a>.","ista":"Nowozin S, Lampert C. 2011. Structured learning and prediction in computer vision. Foundations and Trends in Computer Graphics and Vision. 6(3–4), 185–365.","apa":"Nowozin, S., &#38; Lampert, C. (2011). Structured learning and prediction in computer vision. <i>Foundations and Trends in Computer Graphics and Vision</i>. Now Publishers. <a href=\"https://doi.org/10.1561/0600000033\">https://doi.org/10.1561/0600000033</a>","ieee":"S. Nowozin and C. Lampert, “Structured learning and prediction in computer vision,” <i>Foundations and Trends in Computer Graphics and Vision</i>, vol. 6, no. 3–4. Now Publishers, pp. 185–365, 2011.","short":"S. Nowozin, C. Lampert, Foundations and Trends in Computer Graphics and Vision 6 (2011) 185–365.","mla":"Nowozin, Sebastian, and Christoph Lampert. “Structured Learning and Prediction in Computer Vision.” <i>Foundations and Trends in Computer Graphics and Vision</i>, vol. 6, no. 3–4, Now Publishers, 2011, pp. 185–365, doi:<a href=\"https://doi.org/10.1561/0600000033\">10.1561/0600000033</a>."},"date_updated":"2023-10-17T11:52:46Z","department":[{"_id":"ChLa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","publication":"Foundations and Trends in Computer Graphics and Vision","intvolume":"         6","publist_id":"3315","oa":1,"doi":"10.1561/0600000033","day":"23","page":"185 - 365","year":"2011","issue":"3-4","file":[{"creator":"dernst","checksum":"f1043ef389f1558e2a226bb51568511f","file_id":"7837","file_size":3745064,"access_level":"open_access","relation":"main_file","file_name":"2011_CompGraphicsVision_Nowozin.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:07Z","date_created":"2020-05-14T14:34:47Z"}],"has_accepted_license":"1","month":"05","article_processing_charge":"No","volume":6,"language":[{"iso":"eng"}],"oa_version":"Published Version","quality_controlled":"1","author":[{"full_name":"Nowozin, Sebastian","last_name":"Nowozin","first_name":"Sebastian"},{"orcid":"0000-0001-8622-7887","first_name":"Christoph","last_name":"Lampert","full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"type":"journal_article","_id":"3320","article_type":"original","date_created":"2018-12-11T12:02:39Z","status":"public"},{"abstract":[{"text":"We study multi-label prediction for structured output spaces, a problem that occurs, for example, in object detection in images, secondary structure prediction in computational biology, and graph matching with symmetries. Conventional multi-label classification techniques are typically not applicable in this situation, because they require explicit enumeration of the label space, which is infeasible in case of structured outputs. Relying on techniques originally designed for single- label structured prediction, in particular structured support vector machines, results in reduced prediction accuracy, or leads to infeasible optimization problems. In this work we derive a maximum-margin training formulation for multi-label structured prediction that remains computationally tractable while achieving high prediction accuracy. It also shares most beneficial properties with single-label maximum-margin approaches, in particular a formulation as a convex optimization problem, efficient working set training, and PAC-Bayesian generalization bounds.","lang":"eng"}],"month":"12","publication_status":"published","language":[{"iso":"eng"}],"publisher":"Neural Information Processing Systems Foundation","date_published":"2011-12-13T00:00:00Z","article_processing_charge":"No","title":"Maximum margin multi label structured prediction","date_updated":"2023-10-17T11:47:36Z","department":[{"_id":"ChLa"}],"oa_version":"None","citation":{"ieee":"C. Lampert, <i>Maximum margin multi label structured prediction</i>. Neural Information Processing Systems Foundation, 2011.","ama":"Lampert C. <i>Maximum Margin Multi Label Structured Prediction</i>. Neural Information Processing Systems Foundation; 2011.","ista":"Lampert C. 2011. Maximum margin multi label structured prediction, Neural Information Processing Systems Foundation,p.","chicago":"Lampert, Christoph. <i>Maximum Margin Multi Label Structured Prediction</i>. <i>NIPS: Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation, 2011.","apa":"Lampert, C. (2011). <i>Maximum margin multi label structured prediction</i>. <i>NIPS: Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation.","short":"C. Lampert, Maximum Margin Multi Label Structured Prediction, Neural Information Processing Systems Foundation, 2011.","mla":"Lampert, Christoph. “Maximum Margin Multi Label Structured Prediction.” <i>NIPS: Neural Information Processing Systems</i>, Neural Information Processing Systems Foundation, 2011."},"author":[{"last_name":"Lampert","first_name":"Christoph","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"earlier_version","id":"3163","status":"public"}]},"publist_id":"3313","publication":"NIPS: Neural Information Processing Systems","date_created":"2018-12-11T12:02:40Z","type":"conference_poster","_id":"3322","year":"2011","day":"13","status":"public"},{"abstract":[{"text":"We present a new decidable logic called TREX for expressing constraints about imperative tree data structures. In particular, TREX supports a transitive closure operator that can express reachability constraints, which often appear in data structure invariants. We show that our logic is closed under weakest precondition computation, which enables its use for automated software verification. We further show that satisfiability of formulas in TREX is decidable in NP. The low complexity makes it an attractive alternative to more expensive logics such as monadic second-order logic (MSOL) over trees, which have been traditionally used for reasoning about tree data structures.","lang":"eng"}],"publication_status":"published","month":"07","language":[{"iso":"eng"}],"date_published":"2011-07-19T00:00:00Z","publisher":"Springer","volume":6803,"title":"An efficient decision procedure for imperative tree data structures","date_updated":"2023-02-23T12:23:48Z","quality_controlled":"1","department":[{"_id":"ToHe"}],"citation":{"ista":"Wies T, Muñiz M, Kuncak V. 2011. An efficient decision procedure for imperative tree data structures. CADE 23: Automated Deduction , LNAI , vol. 6803, 476–491.","ama":"Wies T, Muñiz M, Kuncak V. An efficient decision procedure for imperative tree data structures. In: Vol 6803. Springer; 2011:476-491. doi:<a href=\"https://doi.org/10.1007/978-3-642-22438-6_36\">10.1007/978-3-642-22438-6_36</a>","chicago":"Wies, Thomas, Marco Muñiz, and Viktor Kuncak. “An Efficient Decision Procedure for Imperative Tree Data Structures,” 6803:476–91. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-22438-6_36\">https://doi.org/10.1007/978-3-642-22438-6_36</a>.","apa":"Wies, T., Muñiz, M., &#38; Kuncak, V. (2011). An efficient decision procedure for imperative tree data structures (Vol. 6803, pp. 476–491). Presented at the CADE 23: Automated Deduction , Wrocław, Poland: Springer. <a href=\"https://doi.org/10.1007/978-3-642-22438-6_36\">https://doi.org/10.1007/978-3-642-22438-6_36</a>","ieee":"T. Wies, M. Muñiz, and V. Kuncak, “An efficient decision procedure for imperative tree data structures,” presented at the CADE 23: Automated Deduction , Wrocław, Poland, 2011, vol. 6803, pp. 476–491.","short":"T. Wies, M. Muñiz, V. Kuncak, in:, Springer, 2011, pp. 476–491.","mla":"Wies, Thomas, et al. <i>An Efficient Decision Procedure for Imperative Tree Data Structures</i>. Vol. 6803, Springer, 2011, pp. 476–91, doi:<a href=\"https://doi.org/10.1007/978-3-642-22438-6_36\">10.1007/978-3-642-22438-6_36</a>."},"oa_version":"None","author":[{"id":"447BFB88-F248-11E8-B48F-1D18A9856A87","full_name":"Wies, Thomas","last_name":"Wies","first_name":"Thomas"},{"full_name":"Muñiz, Marco","first_name":"Marco","last_name":"Muñiz"},{"full_name":"Kuncak, Viktor","first_name":"Viktor","last_name":"Kuncak"}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNAI "],"related_material":{"record":[{"relation":"earlier_version","id":"5383","status":"public"}]},"scopus_import":1,"intvolume":"      6803","publist_id":"3312","conference":{"location":"Wrocław, Poland","name":"CADE 23: Automated Deduction ","start_date":"2011-07-31","end_date":"2011-08-05"},"date_created":"2018-12-11T12:02:40Z","_id":"3323","type":"conference","doi":"10.1007/978-3-642-22438-6_36","year":"2011","page":"476 - 491","status":"public","day":"19"},{"title":"Decision procedures for automating termination proofs","date_published":"2011-01-01T00:00:00Z","publisher":"Springer","abstract":[{"text":"Automated termination provers often use the following schema to prove that a program terminates: construct a relational abstraction of the program's transition relation and then show that the relational abstraction is well-founded. The focus of current tools has been on developing sophisticated techniques for constructing the abstractions while relying on known decidable logics (such as linear arithmetic) to express them. We believe we can significantly increase the class of programs that are amenable to automated termination proofs by identifying more expressive decidable logics for reasoning about well-founded relations. We therefore present a new decision procedure for reasoning about multiset orderings, which are among the most powerful orderings used to prove termination. We show that, using our decision procedure, one can automatically prove termination of natural abstractions of programs.","lang":"eng"}],"publication_status":"published","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"citation":{"apa":"Piskac, R., &#38; Wies, T. (2011). Decision procedures for automating termination proofs. In R. Jhala &#38; D. Schmidt (Eds.) (Vol. 6538, pp. 371–386). Presented at the VMCAI: Verification Model Checking and Abstract Interpretation, Texas, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-18275-4_26\">https://doi.org/10.1007/978-3-642-18275-4_26</a>","ama":"Piskac R, Wies T. Decision procedures for automating termination proofs. In: Jhala R, Schmidt D, eds. Vol 6538. Springer; 2011:371-386. doi:<a href=\"https://doi.org/10.1007/978-3-642-18275-4_26\">10.1007/978-3-642-18275-4_26</a>","chicago":"Piskac, Ruzica, and Thomas Wies. “Decision Procedures for Automating Termination Proofs.” edited by Ranjit Jhala and David Schmidt, 6538:371–86. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-18275-4_26\">https://doi.org/10.1007/978-3-642-18275-4_26</a>.","ista":"Piskac R, Wies T. 2011. Decision procedures for automating termination proofs. VMCAI: Verification Model Checking and Abstract Interpretation, LNCS, vol. 6538, 371–386.","ieee":"R. Piskac and T. Wies, “Decision procedures for automating termination proofs,” presented at the VMCAI: Verification Model Checking and Abstract Interpretation, Texas, USA, 2011, vol. 6538, pp. 371–386.","mla":"Piskac, Ruzica, and Thomas Wies. <i>Decision Procedures for Automating Termination Proofs</i>. Edited by Ranjit Jhala and David Schmidt, vol. 6538, Springer, 2011, pp. 371–86, doi:<a href=\"https://doi.org/10.1007/978-3-642-18275-4_26\">10.1007/978-3-642-18275-4_26</a>.","short":"R. Piskac, T. Wies, in:, R. Jhala, D. Schmidt (Eds.), Springer, 2011, pp. 371–386."},"date_updated":"2021-01-12T07:42:39Z","department":[{"_id":"ToHe"}],"intvolume":"      6538","publist_id":"3311","scopus_import":1,"editor":[{"first_name":"Ranjit","last_name":"Jhala","full_name":"Jhala, Ranjit"},{"full_name":"Schmidt, David","first_name":"David","last_name":"Schmidt"}],"page":"371 - 386","doi":"10.1007/978-3-642-18275-4_26","year":"2011","day":"01","oa":1,"volume":6538,"language":[{"iso":"eng"}],"month":"01","author":[{"full_name":"Piskac, Ruzica","first_name":"Ruzica","last_name":"Piskac"},{"id":"447BFB88-F248-11E8-B48F-1D18A9856A87","full_name":"Wies, Thomas","first_name":"Thomas","last_name":"Wies"}],"oa_version":"Submitted Version","quality_controlled":"1","conference":{"end_date":"2011-01-25","start_date":"2011-01-23","name":"VMCAI: Verification Model Checking and Abstract Interpretation","location":"Texas, USA"},"main_file_link":[{"url":"https://infoscience.epfl.ch/record/170697/","open_access":"1"}],"status":"public","type":"conference","_id":"3324","date_created":"2018-12-11T12:02:40Z"},{"scopus_import":"1","intvolume":"        46","publist_id":"3310","conference":{"start_date":"2011-01-26","end_date":"2011-01-28","location":"Texas, USA","name":"POPL: Principles of Programming Languages"},"_id":"3325","type":"conference","date_created":"2018-12-11T12:02:41Z","day":"26","page":"599 - 610","doi":"10.1145/1926385.1926454","status":"public","year":"2011","issue":"1","abstract":[{"text":"We introduce streaming data string transducers that map input data strings to output data strings in a single left-to-right pass in linear time. Data strings are (unbounded) sequences of data values, tagged with symbols from a finite set, over a potentially infinite data do- main that supports only the operations of equality and ordering. The transducer uses a finite set of states, a finite set of variables ranging over the data domain, and a finite set of variables ranging over data strings. At every step, it can make decisions based on the next in- put symbol, updating its state, remembering the input data value in its data variables, and updating data-string variables by concatenat- ing data-string variables and new symbols formed from data vari- ables, while avoiding duplication. We establish that the problems of checking functional equivalence of two streaming transducers, and of checking whether a streaming transducer satisfies pre/post verification conditions specified by streaming acceptors over in- put/output data-strings, are in PSPACE. We identify a class of imperative and a class of functional pro- grams, manipulating lists of data items, which can be effectively translated to streaming data-string transducers. The imperative pro- grams dynamically modify a singly-linked heap by changing next- pointers of heap-nodes and by adding new nodes. The main re- striction specifies how the next-pointers can be used for traversal. We also identify an expressively equivalent fragment of functional programs that traverse a list using syntactically restricted recursive calls. Our results lead to algorithms for assertion checking and for checking functional equivalence of two programs, written possibly in different programming styles, for commonly used routines such as insert, delete, and reverse.","lang":"eng"}],"month":"01","publication_status":"published","article_processing_charge":"No","volume":46,"title":"Streaming transducers for algorithmic verification of single pass list processing programs","date_published":"2011-01-26T00:00:00Z","publisher":"ACM","language":[{"iso":"eng"}],"citation":{"ieee":"R. Alur and P. Cerny, “Streaming transducers for algorithmic verification of single pass list processing programs,” presented at the POPL: Principles of Programming Languages, Texas, USA, 2011, vol. 46, no. 1, pp. 599–610.","chicago":"Alur, Rajeev, and Pavol Cerny. “Streaming Transducers for Algorithmic Verification of Single Pass List Processing Programs,” 46:599–610. ACM, 2011. <a href=\"https://doi.org/10.1145/1926385.1926454\">https://doi.org/10.1145/1926385.1926454</a>.","ama":"Alur R, Cerny P. Streaming transducers for algorithmic verification of single pass list processing programs. In: Vol 46. ACM; 2011:599-610. doi:<a href=\"https://doi.org/10.1145/1926385.1926454\">10.1145/1926385.1926454</a>","ista":"Alur R, Cerny P. 2011. Streaming transducers for algorithmic verification of single pass list processing programs. POPL: Principles of Programming Languages vol. 46, 599–610.","apa":"Alur, R., &#38; Cerny, P. (2011). Streaming transducers for algorithmic verification of single pass list processing programs (Vol. 46, pp. 599–610). Presented at the POPL: Principles of Programming Languages, Texas, USA: ACM. <a href=\"https://doi.org/10.1145/1926385.1926454\">https://doi.org/10.1145/1926385.1926454</a>","short":"R. Alur, P. Cerny, in:, ACM, 2011, pp. 599–610.","mla":"Alur, Rajeev, and Pavol Cerny. <i>Streaming Transducers for Algorithmic Verification of Single Pass List Processing Programs</i>. Vol. 46, no. 1, ACM, 2011, pp. 599–610, doi:<a href=\"https://doi.org/10.1145/1926385.1926454\">10.1145/1926385.1926454</a>."},"oa_version":"None","date_updated":"2022-03-21T08:12:51Z","quality_controlled":"1","department":[{"_id":"ToHe"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Rajeev","last_name":"Alur","full_name":"Alur, Rajeev"},{"first_name":"Pavol","last_name":"Cerny","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","full_name":"Cerny, Pavol"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LNCS"],"citation":{"short":"S. Almagor, U. Boker, O. Kupferman, in:, Springer, 2011, pp. 482–491.","mla":"Almagor, Shaull, et al. <i>What’s Decidable about Weighted Automata </i>. Vol. 6996, Springer, 2011, pp. 482–91, doi:<a href=\"https://doi.org/10.1007/978-3-642-24372-1_37\">10.1007/978-3-642-24372-1_37</a>.","ieee":"S. Almagor, U. Boker, and O. Kupferman, “What’s decidable about weighted automata ,” presented at the ATVA: Automated Technology for Verification and Analysis, Taipei, Taiwan, 2011, vol. 6996, pp. 482–491.","apa":"Almagor, S., Boker, U., &#38; Kupferman, O. (2011). What’s decidable about weighted automata  (Vol. 6996, pp. 482–491). Presented at the ATVA: Automated Technology for Verification and Analysis, Taipei, Taiwan: Springer. <a href=\"https://doi.org/10.1007/978-3-642-24372-1_37\">https://doi.org/10.1007/978-3-642-24372-1_37</a>","chicago":"Almagor, Shaull, Udi Boker, and Orna Kupferman. “What’s Decidable about Weighted Automata ,” 6996:482–91. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-24372-1_37\">https://doi.org/10.1007/978-3-642-24372-1_37</a>.","ista":"Almagor S, Boker U, Kupferman O. 2011. What’s decidable about weighted automata . ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 6996, 482–491.","ama":"Almagor S, Boker U, Kupferman O. What’s decidable about weighted automata . In: Vol 6996. Springer; 2011:482-491. doi:<a href=\"https://doi.org/10.1007/978-3-642-24372-1_37\">10.1007/978-3-642-24372-1_37</a>"},"date_updated":"2021-01-12T07:42:40Z","department":[{"_id":"ToHe"}],"title":"What’s decidable about weighted automata ","file_date_updated":"2020-07-14T12:46:07Z","date_published":"2011-10-14T00:00:00Z","publisher":"Springer","ddc":["000"],"abstract":[{"lang":"eng","text":"Weighted automata map input words to numerical values. Ap- plications of weighted automata include formal verification of quantitative properties, as well as text, speech, and image processing. A weighted au- tomaton is defined with respect to a semiring. For the tropical semiring, the weight of a run is the sum of the weights of the transitions taken along the run, and the value of a word is the minimal weight of an accepting run on it. In the 90’s, Krob studied the decidability of problems on rational series defined with respect to the tropical semiring. Rational series are strongly related to weighted automata, and Krob’s results apply to them. In par- ticular, it follows from Krob’s results that the universality problem (that is, deciding whether the values of all words are below some threshold) is decidable for weighted automata defined with respect to the tropical semir- ing with domain ∪ {∞}, and that the equality problem is undecidable when the domain is ∪ {∞}. In this paper we continue the study of the borders of decidability in weighted automata, describe alternative and direct proofs of the above results, and tighten them further. Unlike the proofs of Krob, which are algebraic in their nature, our proofs stay in the terrain of state machines, and the reduction is from the halting problem of a two-counter machine. This enables us to significantly simplify Krob’s reasoning, make the un- decidability result accessible to the automata-theoretic community, and strengthen it to apply already to a very simple class of automata: all the states are accepting, there are no initial nor final weights, and all the weights on the transitions are from the set {−1, 0, 1}. The fact we work directly with the automata enables us to tighten also the decidability re- sults and to show that the universality problem for weighted automata defined with respect to the tropical semiring with domain ∪ {∞}, and in fact even with domain ≥0 ∪ {∞}, is PSPACE-complete. Our results thus draw a sharper picture about the decidability of decision problems for weighted automata, in both the front of containment vs. universality and the front of the ∪ {∞} vs. the ∪ {∞} domains."}],"publication_status":"published","day":"14","doi":"10.1007/978-3-642-24372-1_37","page":"482 - 491","year":"2011","oa":1,"intvolume":"      6996","publist_id":"3309","author":[{"last_name":"Almagor","first_name":"Shaull","full_name":"Almagor, Shaull"},{"full_name":"Boker, Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","first_name":"Udi","last_name":"Boker"},{"last_name":"Kupferman","first_name":"Orna","full_name":"Kupferman, Orna"}],"oa_version":"Submitted Version","quality_controlled":"1","article_processing_charge":"No","volume":6996,"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:46:07Z","date_created":"2020-05-19T16:08:32Z","file_name":"2011_LNCS_Almagor.pdf","relation":"main_file","creator":"dernst","file_id":"7868","checksum":"a7ca08a2cb1b6925f4c18a3034ae5659","file_size":182309,"access_level":"open_access"}],"has_accepted_license":"1","month":"10","status":"public","_id":"3326","type":"conference","date_created":"2018-12-11T12:02:41Z","conference":{"name":"ATVA: Automated Technology for Verification and Analysis","location":"Taipei, Taiwan","end_date":"2011-10-14","start_date":"2011-10-11"}},{"month":"06","publication_status":"published","abstract":[{"lang":"eng","text":"We report on a generic uni- and bivariate algebraic kernel that is publicly available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art implementations on polynomials, roots of polynomial systems, and the support to analyze algebraic curves defined by bivariate polynomials. The kernel design is generic, that is, various number types and substeps can be exchanged. It is accompanied with a ready-to-use interface to enable arrangements induced by algebraic curves, that have already been used as basis for various geometric applications, as arrangements on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel applications: arrangements of rotated algebraic curves and Boolean set operations on polygons bounded by segments of algebraic curves. We also provide experiments showing that our general implementation is competitive and even often clearly outperforms existing implementations that are explicitly tailored for specific types of non-linear curves that are available in CGAL."}],"title":"A generic algebraic kernel for non linear geometric applications","article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"ACM","date_published":"2011-06-13T00:00:00Z","citation":{"ieee":"E. Berberich, M. Hemmer, and M. Kerber, “A generic algebraic kernel for non linear geometric applications,” presented at the SCG: Symposium on Computational Geometry, Paris, France, 2011, pp. 179–186.","apa":"Berberich, E., Hemmer, M., &#38; Kerber, M. (2011). A generic algebraic kernel for non linear geometric applications (pp. 179–186). Presented at the SCG: Symposium on Computational Geometry, Paris, France: ACM. <a href=\"https://doi.org/10.1145/1998196.1998224\">https://doi.org/10.1145/1998196.1998224</a>","ista":"Berberich E, Hemmer M, Kerber M. 2011. A generic algebraic kernel for non linear geometric applications. SCG: Symposium on Computational Geometry, 179–186.","ama":"Berberich E, Hemmer M, Kerber M. A generic algebraic kernel for non linear geometric applications. In: ACM; 2011:179-186. doi:<a href=\"https://doi.org/10.1145/1998196.1998224\">10.1145/1998196.1998224</a>","chicago":"Berberich, Eric, Michael Hemmer, and Michael Kerber. “A Generic Algebraic Kernel for Non Linear Geometric Applications,” 179–86. ACM, 2011. <a href=\"https://doi.org/10.1145/1998196.1998224\">https://doi.org/10.1145/1998196.1998224</a>.","mla":"Berberich, Eric, et al. <i>A Generic Algebraic Kernel for Non Linear Geometric Applications</i>. ACM, 2011, pp. 179–86, doi:<a href=\"https://doi.org/10.1145/1998196.1998224\">10.1145/1998196.1998224</a>.","short":"E. Berberich, M. Hemmer, M. Kerber, in:, ACM, 2011, pp. 179–186."},"oa_version":"Published Version","department":[{"_id":"HeEd"}],"quality_controlled":"1","date_updated":"2021-01-12T07:42:41Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Berberich, Eric","first_name":"Eric","last_name":"Berberich"},{"first_name":"Michael","last_name":"Hemmer","full_name":"Hemmer, Michael"},{"orcid":"0000-0002-8030-9299","last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":1,"publist_id":"3307","conference":{"start_date":"2011-06-13","end_date":"2011-06-15","name":"SCG: Symposium on Computational Geometry","location":"Paris, France"},"_id":"3328","type":"conference","oa":1,"date_created":"2018-12-11T12:02:42Z","year":"2011","day":"13","status":"public","page":"179 - 186","main_file_link":[{"url":"https://hal.inria.fr/inria-00480031/file/RR-7274.pdf","open_access":"1"}],"doi":"10.1145/1998196.1998224"},{"date_updated":"2023-02-23T11:12:57Z","department":[{"_id":"HeEd"}],"quality_controlled":"1","citation":{"ista":"Berberich E, Halperin D, Kerber M, Pogalnikova R. 2011. Deconstructing approximate offsets. Proceedings of the twenty-seventh annual symposium on Computational geometry. SCG: Symposium on Computational Geometry, 187–196.","chicago":"Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing Approximate Offsets.” In <i>Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry</i>, 187–96. ACM, 2011. <a href=\"https://doi.org/10.1145/1998196.1998225\">https://doi.org/10.1145/1998196.1998225</a>.","ama":"Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate offsets. In: <i>Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry</i>. ACM; 2011:187-196. doi:<a href=\"https://doi.org/10.1145/1998196.1998225\">10.1145/1998196.1998225</a>","apa":"Berberich, E., Halperin, D., Kerber, M., &#38; Pogalnikova, R. (2011). Deconstructing approximate offsets. In <i>Proceedings of the twenty-seventh annual symposium on Computational geometry</i> (pp. 187–196). Paris, France: ACM. <a href=\"https://doi.org/10.1145/1998196.1998225\">https://doi.org/10.1145/1998196.1998225</a>","ieee":"E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing approximate offsets,” in <i>Proceedings of the twenty-seventh annual symposium on Computational geometry</i>, Paris, France, 2011, pp. 187–196.","mla":"Berberich, Eric, et al. “Deconstructing Approximate Offsets.” <i>Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry</i>, ACM, 2011, pp. 187–96, doi:<a href=\"https://doi.org/10.1145/1998196.1998225\">10.1145/1998196.1998225</a>.","short":"E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp. 187–196."},"oa_version":"Preprint","author":[{"last_name":"Berberich","first_name":"Eric","full_name":"Berberich, Eric"},{"first_name":"Dan","last_name":"Halperin","full_name":"Halperin, Dan"},{"last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael"},{"full_name":"Pogalnikova, Roza","first_name":"Roza","last_name":"Pogalnikova"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm."}],"publication_status":"published","month":"06","date_published":"2011-06-13T00:00:00Z","language":[{"iso":"eng"}],"publisher":"ACM","title":"Deconstructing approximate offsets","oa":1,"date_created":"2018-12-11T12:02:42Z","_id":"3329","type":"conference","doi":"10.1145/1998196.1998225","main_file_link":[{"url":"http://arxiv.org/abs/1109.2158","open_access":"1"}],"page":"187 - 196","status":"public","day":"13","year":"2011","related_material":{"record":[{"status":"public","id":"3115","relation":"later_version"}]},"scopus_import":1,"publist_id":"3306","conference":{"name":"SCG: Symposium on Computational Geometry","location":"Paris, France","start_date":"2011-06-13","end_date":"2011-06-15"},"publication":"Proceedings of the twenty-seventh annual symposium on Computational geometry"},{"page":"209 - 216","year":"2011","day":"08","status":"public","doi":"10.1145/1993886.1993920","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1104.1362"}],"_id":"3330","type":"conference","oa":1,"date_created":"2018-12-11T12:02:43Z","publist_id":"3304","arxiv":1,"conference":{"name":"ISSAC: International Symposium on Symbolic and Algebraic Computation","location":"California, USA","start_date":"2011-06-08","end_date":"2011-06-11"},"scopus_import":1,"external_id":{"arxiv":["1104.1362"]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","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","last_name":"Sagraloff","first_name":"Michael"}],"citation":{"mla":"Kerber, Michael, and Michael Sagraloff. <i>Root Refinement for Real Polynomials</i>. Springer, 2011, pp. 209–16, doi:<a href=\"https://doi.org/10.1145/1993886.1993920\">10.1145/1993886.1993920</a>.","short":"M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.","ieee":"M. Kerber and M. Sagraloff, “Root refinement for real polynomials,” presented at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California, USA, 2011, pp. 209–216.","apa":"Kerber, M., &#38; Sagraloff, M. (2011). Root refinement for real polynomials (pp. 209–216). Presented at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California, USA: Springer. <a href=\"https://doi.org/10.1145/1993886.1993920\">https://doi.org/10.1145/1993886.1993920</a>","ama":"Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer; 2011:209-216. doi:<a href=\"https://doi.org/10.1145/1993886.1993920\">10.1145/1993886.1993920</a>","chicago":"Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,” 209–16. Springer, 2011. <a href=\"https://doi.org/10.1145/1993886.1993920\">https://doi.org/10.1145/1993886.1993920</a>.","ista":"Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC: International Symposium on Symbolic and Algebraic Computation, 209–216."},"oa_version":"Preprint","department":[{"_id":"HeEd"}],"quality_controlled":"1","date_updated":"2021-01-12T07:42:42Z","title":"Root refinement for real polynomials","article_processing_charge":"No","date_published":"2011-06-08T00:00:00Z","publisher":"Springer","language":[{"iso":"eng"}],"publication_status":"published","month":"06","abstract":[{"text":"We consider the problem of approximating all real roots of a square-free polynomial f. Given isolating intervals, our algorithm refines each of them to a width at most 2-L, that is, each of the roots is approximated to L bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating f, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms.","lang":"eng"}]},{"oa":1,"doi":"10.1007/s00373-011-1020-7","year":"2011","page":"419 - 430","day":"17","scopus_import":1,"publist_id":"3301","intvolume":"        27","publication":"Graphs and Combinatorics","department":[{"_id":"HeEd"}],"date_updated":"2021-01-12T07:42:43Z","citation":{"short":"M. Kerber, M. Sagraloff, Graphs and Combinatorics 27 (2011) 419–430.","mla":"Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real Algebraic Hypersurfaces.” <i>Graphs and Combinatorics</i>, vol. 27, no. 3, Springer, 2011, pp. 419–30, doi:<a href=\"https://doi.org/10.1007/s00373-011-1020-7\">10.1007/s00373-011-1020-7</a>.","ieee":"M. Kerber and M. Sagraloff, “A note on the complexity of real algebraic hypersurfaces,” <i>Graphs and Combinatorics</i>, vol. 27, no. 3. Springer, pp. 419–430, 2011.","apa":"Kerber, M., &#38; Sagraloff, M. (2011). A note on the complexity of real algebraic hypersurfaces. <i>Graphs and Combinatorics</i>. Springer. <a href=\"https://doi.org/10.1007/s00373-011-1020-7\">https://doi.org/10.1007/s00373-011-1020-7</a>","ista":"Kerber M, Sagraloff M. 2011. A note on the complexity of real algebraic hypersurfaces. Graphs and Combinatorics. 27(3), 419–430.","ama":"Kerber M, Sagraloff M. A note on the complexity of real algebraic hypersurfaces. <i>Graphs and Combinatorics</i>. 2011;27(3):419-430. doi:<a href=\"https://doi.org/10.1007/s00373-011-1020-7\">10.1007/s00373-011-1020-7</a>","chicago":"Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real Algebraic Hypersurfaces.” <i>Graphs and Combinatorics</i>. Springer, 2011. <a href=\"https://doi.org/10.1007/s00373-011-1020-7\">https://doi.org/10.1007/s00373-011-1020-7</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"text":"Given an algebraic hypersurface O in ℝd, how many simplices are necessary for a simplicial complex isotopic to O? We address this problem and the variant where all vertices of the complex must lie on O. We give asymptotically tight worst-case bounds for algebraic plane curves. Our results gradually improve known bounds in higher dimensions; however, the question for tight bounds remains unsolved for d ≥ 3.","lang":"eng"}],"ddc":["500"],"file_date_updated":"2020-07-14T12:46:08Z","date_published":"2011-03-17T00:00:00Z","publisher":"Springer","title":"A note on the complexity of real algebraic hypersurfaces","date_created":"2018-12-11T12:02:43Z","article_type":"original","type":"journal_article","_id":"3332","status":"public","quality_controlled":"1","oa_version":"Submitted Version","author":[{"orcid":"0000-0002-8030-9299","last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Sagraloff","first_name":"Michael","full_name":"Sagraloff, Michael"}],"has_accepted_license":"1","month":"03","file":[{"creator":"dernst","file_id":"7869","checksum":"a63a1e3e885dcc68f1e3dea68dfbe213","file_size":143976,"access_level":"open_access","relation":"main_file","file_name":"2011_GraphsCombi_Kerber.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:08Z","date_created":"2020-05-19T16:11:36Z"}],"issue":"3","language":[{"iso":"eng"}],"volume":27,"article_processing_charge":"No"},{"publication":"Discrete & Computational Geometry","publist_id":"3297","intvolume":"        45","scopus_import":1,"day":"01","year":"2011","doi":"10.1007/s00454-010-9313-9","status":"public","page":"1 - 2","article_type":"letter_note","_id":"3334","type":"journal_article","date_created":"2018-12-11T12:02:44Z","volume":45,"title":"Letter from the new editors-in-chief","language":[{"iso":"eng"}],"date_published":"2011-01-01T00:00:00Z","publisher":"Springer","issue":"1","publication_status":"published","month":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"full_name":"Pach, János","first_name":"János","last_name":"Pach"},{"full_name":"Ziegler, Günter","first_name":"Günter","last_name":"Ziegler"}],"citation":{"ista":"Edelsbrunner H, Pach J, Ziegler G. 2011. Letter from the new editors-in-chief. Discrete &#38; Computational Geometry. 45(1), 1–2.","ama":"Edelsbrunner H, Pach J, Ziegler G. Letter from the new editors-in-chief. <i>Discrete &#38; Computational Geometry</i>. 2011;45(1):1-2. doi:<a href=\"https://doi.org/10.1007/s00454-010-9313-9\">10.1007/s00454-010-9313-9</a>","chicago":"Edelsbrunner, Herbert, János Pach, and Günter Ziegler. “Letter from the New Editors-in-Chief.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2011. <a href=\"https://doi.org/10.1007/s00454-010-9313-9\">https://doi.org/10.1007/s00454-010-9313-9</a>.","apa":"Edelsbrunner, H., Pach, J., &#38; Ziegler, G. (2011). Letter from the new editors-in-chief. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-010-9313-9\">https://doi.org/10.1007/s00454-010-9313-9</a>","ieee":"H. Edelsbrunner, J. Pach, and G. Ziegler, “Letter from the new editors-in-chief,” <i>Discrete &#38; Computational Geometry</i>, vol. 45, no. 1. Springer, pp. 1–2, 2011.","mla":"Edelsbrunner, Herbert, et al. “Letter from the New Editors-in-Chief.” <i>Discrete &#38; Computational Geometry</i>, vol. 45, no. 1, Springer, 2011, pp. 1–2, doi:<a href=\"https://doi.org/10.1007/s00454-010-9313-9\">10.1007/s00454-010-9313-9</a>.","short":"H. Edelsbrunner, J. Pach, G. Ziegler, Discrete &#38; Computational Geometry 45 (2011) 1–2."},"oa_version":"None","department":[{"_id":"HeEd"}],"quality_controlled":"1","date_updated":"2021-01-12T07:42:44Z"},{"alternative_title":["LNCS"],"external_id":{"arxiv":["1306.3640"]},"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","citation":{"short":"R. Van De Weygaert, G. Vegter, H. Edelsbrunner, B. Jones, P. Pranav, C. Park, W. Hellwing, B. Eldering, N. Kruithof, P. Bos, J. Hidding, J. Feldbrugge, E. Ten Have, M. Van Engelen, M. Caroli, M. Teillaud, in:, M. Gavrilova, K. Tan, M. Mostafavi (Eds.), Transactions on Computational Science XIV, Springer, 2011, pp. 60–101.","mla":"Van De Weygaert, Rien, et al. “Alpha, Betti and the Megaparsec Universe: On the Topology of the Cosmic Web.” <i>Transactions on Computational Science XIV</i>, edited by Marina Gavrilova et al., vol. 6970, Springer, 2011, pp. 60–101, doi:<a href=\"https://doi.org/10.1007/978-3-642-25249-5_3\">10.1007/978-3-642-25249-5_3</a>.","ieee":"R. Van De Weygaert <i>et al.</i>, “Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web,” in <i>Transactions on Computational Science XIV</i>, vol. 6970, M. Gavrilova, K. Tan, and M. Mostafavi, Eds. Springer, 2011, pp. 60–101.","apa":"Van De Weygaert, R., Vegter, G., Edelsbrunner, H., Jones, B., Pranav, P., Park, C., … Teillaud, M. (2011). Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web. In M. Gavrilova, K. Tan, &#38; M. Mostafavi (Eds.), <i>Transactions on Computational Science XIV</i> (Vol. 6970, pp. 60–101). Springer. <a href=\"https://doi.org/10.1007/978-3-642-25249-5_3\">https://doi.org/10.1007/978-3-642-25249-5_3</a>","ama":"Van De Weygaert R, Vegter G, Edelsbrunner H, et al. Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web. In: Gavrilova M, Tan K, Mostafavi M, eds. <i>Transactions on Computational Science XIV</i>. Vol 6970. Special Issue on Voronoi Diagrams and Delaunay Triangulation. Springer; 2011:60-101. doi:<a href=\"https://doi.org/10.1007/978-3-642-25249-5_3\">10.1007/978-3-642-25249-5_3</a>","ista":"Van De Weygaert R, Vegter G, Edelsbrunner H, Jones B, Pranav P, Park C, Hellwing W, Eldering B, Kruithof N, Bos P, Hidding J, Feldbrugge J, Ten Have E, Van Engelen M, Caroli M, Teillaud M. 2011.Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web. In: Transactions on Computational Science XIV. LNCS, vol. 6970, 60–101.","chicago":"Van De Weygaert, Rien, Gert Vegter, Herbert Edelsbrunner, Bernard Jones, Pratyush Pranav, Changbom Park, Wojciech Hellwing, et al. “Alpha, Betti and the Megaparsec Universe: On the Topology of the Cosmic Web.” In <i>Transactions on Computational Science XIV</i>, edited by Marina Gavrilova, Kenneth Tan, and Mir Mostafavi, 6970:60–101. Special Issue on Voronoi Diagrams and Delaunay Triangulation. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-25249-5_3\">https://doi.org/10.1007/978-3-642-25249-5_3</a>."},"department":[{"_id":"HeEd"}],"date_updated":"2021-01-12T07:42:44Z","title":"Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web","date_published":"2011-11-09T00:00:00Z","publisher":"Springer","series_title":"Special Issue on Voronoi Diagrams and Delaunay Triangulation","publication_status":"published","abstract":[{"lang":"eng","text":"We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent Betti numbers, which formalize the topological information content of the cosmic mass distribution. While the Betti numbers do not fully quantify topology, they extend the information beyond conventional cosmological studies of topology in terms of genus and Euler characteristic. The richer information content of Betti numbers goes along the availability of fast algorithms to compute them. For continuous density fields, we determine the scale-dependence of Betti numbers by invoking the cosmologically familiar filtration of sublevel or superlevel sets defined by density thresholds. For the discrete galaxy distribution, however, the analysis is based on the alpha shapes of the particles. These simplicial complexes constitute an ordered sequence of nested subsets of the Delaunay tessellation, a filtration defined by the scale parameter, α. As they are homotopy equivalent to the sublevel sets of the distance field, they are an excellent tool for assessing the topological structure of a discrete point distribution. In order to develop an intuitive understanding for the behavior of Betti numbers as a function of α, and their relation to the morphological patterns in the Cosmic Web, we first study them within the context of simple heuristic Voronoi clustering models. These can be tuned to consist of specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or sheets. To elucidate the relative prominence of the various Betti numbers in different stages of morphological evolution, we introduce the concept of alpha tracks. Subsequently, we address the topology of structures emerging in the standard LCDM scenario and in cosmological scenarios with alternative dark energy content. The evolution of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic Web. We also demonstrate that the scale-dependence of the Betti numbers yields a promising measure of cosmological parameters, with a potential to help in determining the nature of dark energy and to probe primordial non-Gaussianities. We also discuss the expected Betti numbers as a function of the density threshold for superlevel sets of a Gaussian random field. Finally, we introduce the concept of persistent homology. It measures scale levels of the mass distribution and allows us to separate small from large scale features. Within the context of the hierarchical cosmic structure formation, persistence provides a natural formalism for a multiscale topology study of the Cosmic Web."}],"year":"2011","doi":"10.1007/978-3-642-25249-5_3","day":"09","page":"60 - 101","oa":1,"publication":"Transactions on Computational Science XIV","arxiv":1,"publist_id":"3295","intvolume":"      6970","editor":[{"full_name":"Gavrilova, Marina","first_name":"Marina","last_name":"Gavrilova"},{"full_name":"Tan, Kenneth","first_name":"Kenneth","last_name":"Tan"},{"full_name":"Mostafavi, Mir","first_name":"Mir","last_name":"Mostafavi"}],"scopus_import":1,"author":[{"full_name":"Van De Weygaert, Rien","first_name":"Rien","last_name":"Van De Weygaert"},{"first_name":"Gert","last_name":"Vegter","full_name":"Vegter, Gert"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Jones, Bernard","first_name":"Bernard","last_name":"Jones"},{"last_name":"Pranav","first_name":"Pratyush","full_name":"Pranav, Pratyush"},{"last_name":"Park","first_name":"Changbom","full_name":"Park, Changbom"},{"first_name":"Wojciech","last_name":"Hellwing","full_name":"Hellwing, Wojciech"},{"full_name":"Eldering, Bob","last_name":"Eldering","first_name":"Bob"},{"full_name":"Kruithof, Nico","last_name":"Kruithof","first_name":"Nico"},{"first_name":"Patrick","last_name":"Bos","full_name":"Bos, Patrick"},{"full_name":"Hidding, Johan","first_name":"Johan","last_name":"Hidding"},{"full_name":"Feldbrugge, Job","last_name":"Feldbrugge","first_name":"Job"},{"full_name":"Ten Have, Eline","last_name":"Ten Have","first_name":"Eline"},{"last_name":"Van Engelen","first_name":"Matti","full_name":"Van Engelen, Matti"},{"first_name":"Manuel","last_name":"Caroli","full_name":"Caroli, Manuel"},{"last_name":"Teillaud","first_name":"Monique","full_name":"Teillaud, Monique"}],"oa_version":"Preprint","quality_controlled":"1","volume":6970,"language":[{"iso":"eng"}],"month":"11","status":"public","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1306.3640"}],"type":"book_chapter","_id":"3335","date_created":"2018-12-11T12:02:44Z"},{"citation":{"short":"C. Chen, D. Freedman, C. Lampert, in:, CVPR: Computer Vision and Pattern Recognition, IEEE, 2011, pp. 2089–2096.","mla":"Chen, Chao, et al. “Enforcing Topological Constraints in Random Field Image Segmentation.” <i>CVPR: Computer Vision and Pattern Recognition</i>, IEEE, 2011, pp. 2089–96, doi:<a href=\"https://doi.org/10.1109/CVPR.2011.5995503\">10.1109/CVPR.2011.5995503</a>.","chicago":"Chen, Chao, Daniel Freedman, and Christoph Lampert. “Enforcing Topological Constraints in Random Field Image Segmentation.” In <i>CVPR: Computer Vision and Pattern Recognition</i>, 2089–96. IEEE, 2011. <a href=\"https://doi.org/10.1109/CVPR.2011.5995503\">https://doi.org/10.1109/CVPR.2011.5995503</a>.","ista":"Chen C, Freedman D, Lampert C. 2011. Enforcing topological constraints in random field image segmentation. CVPR: Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition, 2089–2096.","ama":"Chen C, Freedman D, Lampert C. Enforcing topological constraints in random field image segmentation. In: <i>CVPR: Computer Vision and Pattern Recognition</i>. IEEE; 2011:2089-2096. doi:<a href=\"https://doi.org/10.1109/CVPR.2011.5995503\">10.1109/CVPR.2011.5995503</a>","apa":"Chen, C., Freedman, D., &#38; Lampert, C. (2011). Enforcing topological constraints in random field image segmentation. In <i>CVPR: Computer Vision and Pattern Recognition</i> (pp. 2089–2096). Colorado Springs, CO, United States: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2011.5995503\">https://doi.org/10.1109/CVPR.2011.5995503</a>","ieee":"C. Chen, D. Freedman, and C. Lampert, “Enforcing topological constraints in random field image segmentation,” in <i>CVPR: Computer Vision and Pattern Recognition</i>, Colorado Springs, CO, United States, 2011, pp. 2089–2096."},"oa_version":"None","department":[{"_id":"HeEd"},{"_id":"ChLa"}],"quality_controlled":"1","date_updated":"2023-02-23T12:23:56Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","full_name":"Chen, Chao","last_name":"Chen","first_name":"Chao"},{"first_name":"Daniel","last_name":"Freedman","full_name":"Freedman, Daniel"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","last_name":"Lampert","first_name":"Christoph","orcid":"0000-0001-8622-7887"}],"publication_status":"published","month":"07","abstract":[{"lang":"eng","text":"We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks."}],"title":"Enforcing topological constraints in random field image segmentation","article_processing_charge":"No","language":[{"iso":"eng"}],"publisher":"IEEE","date_published":"2011-07-22T00:00:00Z","_id":"3336","type":"conference","date_created":"2018-12-11T12:02:45Z","day":"22","publication_identifier":{"isbn":["978-1-4577-0394-2"],"eisbn":["978-1-4577-0395-9"]},"doi":"10.1109/CVPR.2011.5995503","page":"2089 - 2096","status":"public","year":"2011","acknowledgement":"The first author is supported by the Austrian Science Fund (FWF) grant No. P20134-N13. The authors would like to thank Sebastian Nowozin for helpful discussions.","scopus_import":"1","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5386"}]},"publication":"CVPR: Computer Vision and Pattern Recognition","conference":{"start_date":"2011-06-20","end_date":"2011-06-25","location":"Colorado Springs, CO, United States","name":"CVPR: Conference on Computer Vision and Pattern Recognition"},"publist_id":"3294"},{"status":"public","doi":"10.1109/IROS.2011.6094892","year":"2011","day":"01","page":"332 - 337","type":"conference","_id":"3337","date_created":"2018-12-11T12:02:45Z","conference":{"location":"San Francisco, USA","name":"IROS: RSJ International Conference on Intelligent Robots and Systems","start_date":"2011-09-25","end_date":"2011-09-30"},"publist_id":"3293","scopus_import":1,"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Zhikun","last_name":"Wang","full_name":"Wang, Zhikun"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","last_name":"Lampert","first_name":"Christoph","orcid":"0000-0001-8622-7887"},{"first_name":"Katharina","last_name":"Mülling","full_name":"Mülling, Katharina"},{"full_name":"Schölkopf, Bernhard","last_name":"Schölkopf","first_name":"Bernhard"},{"full_name":"Peters, Jan","first_name":"Jan","last_name":"Peters"}],"citation":{"ieee":"Z. Wang, C. Lampert, K. Mülling, B. Schölkopf, and J. Peters, “Learning anticipation policies for robot table tennis,” presented at the IROS: RSJ International Conference on Intelligent Robots and Systems, San Francisco, USA, 2011, pp. 332–337.","ista":"Wang Z, Lampert C, Mülling K, Schölkopf B, Peters J. 2011. Learning anticipation policies for robot table tennis. IROS: RSJ International Conference on Intelligent Robots and Systems, 332–337.","ama":"Wang Z, Lampert C, Mülling K, Schölkopf B, Peters J. Learning anticipation policies for robot table tennis. In: IEEE; 2011:332-337. doi:<a href=\"https://doi.org/10.1109/IROS.2011.6094892\">10.1109/IROS.2011.6094892</a>","chicago":"Wang, Zhikun, Christoph Lampert, Katharina Mülling, Bernhard Schölkopf, and Jan Peters. “Learning Anticipation Policies for Robot Table Tennis,” 332–37. IEEE, 2011. <a href=\"https://doi.org/10.1109/IROS.2011.6094892\">https://doi.org/10.1109/IROS.2011.6094892</a>.","apa":"Wang, Z., Lampert, C., Mülling, K., Schölkopf, B., &#38; Peters, J. (2011). Learning anticipation policies for robot table tennis (pp. 332–337). Presented at the IROS: RSJ International Conference on Intelligent Robots and Systems, San Francisco, USA: IEEE. <a href=\"https://doi.org/10.1109/IROS.2011.6094892\">https://doi.org/10.1109/IROS.2011.6094892</a>","short":"Z. Wang, C. Lampert, K. Mülling, B. Schölkopf, J. Peters, in:, IEEE, 2011, pp. 332–337.","mla":"Wang, Zhikun, et al. <i>Learning Anticipation Policies for Robot Table Tennis</i>. IEEE, 2011, pp. 332–37, doi:<a href=\"https://doi.org/10.1109/IROS.2011.6094892\">10.1109/IROS.2011.6094892</a>."},"oa_version":"None","date_updated":"2021-01-12T07:42:45Z","department":[{"_id":"ChLa"}],"quality_controlled":"1","title":"Learning anticipation policies for robot table tennis","date_published":"2011-01-01T00:00:00Z","language":[{"iso":"eng"}],"publisher":"IEEE","abstract":[{"text":"Playing table tennis is a difficult task for robots, especially due to their limitations of acceleration. A key bottleneck is the amount of time needed to reach the desired hitting position and velocity of the racket for returning the incoming ball. Here, it often does not suffice to simply extrapolate the ball's trajectory after the opponent returns it but more information is needed. Humans are able to predict the ball's trajectory based on the opponent's moves and, thus, have a considerable advantage. Hence, we propose to incorporate an anticipation system into robot table tennis players, which enables the robot to react earlier while the opponent is performing the striking movement. Based on visual observation of the opponent's racket movement, the robot can predict the aim of the opponent and adjust its movement generation accordingly. The policies for deciding how and when to react are obtained by reinforcement learning. We conduct experiments with an existing robot player to show that the learned reaction policy can significantly improve the performance of the overall system.","lang":"eng"}],"month":"01","publication_status":"published"},{"_id":"3338","type":"preprint","oa":1,"date_created":"2018-12-11T12:02:45Z","page":"1 - 51","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1107.2146"}],"year":"2011","status":"public","day":"11","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"5380"}]},"publication":"arXiv","publist_id":"3287","arxiv":1,"oa_version":"Preprint","citation":{"short":"K. Chatterjee, ArXiv (2011) 1–51.","mla":"Chatterjee, Krishnendu. “Bounded Rationality in Concurrent Parity Games.” <i>ArXiv</i>, ArXiv, 2011, pp. 1–51.","ieee":"K. Chatterjee, “Bounded rationality in concurrent parity games,” <i>arXiv</i>. ArXiv, pp. 1–51, 2011.","ista":"Chatterjee K. 2011. Bounded rationality in concurrent parity games. arXiv, 1–51, .","chicago":"Chatterjee, Krishnendu. “Bounded Rationality in Concurrent Parity Games.” <i>ArXiv</i>. ArXiv, 2011.","ama":"Chatterjee K. Bounded rationality in concurrent parity games. <i>arXiv</i>. 2011:1-51.","apa":"Chatterjee, K. (2011). Bounded rationality in concurrent parity games. <i>arXiv</i>. ArXiv."},"date_updated":"2023-02-23T12:23:40Z","department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1107.2146"]},"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"}],"abstract":[{"text":"We consider 2-player 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 inde- pendently and simultaneously; the current state and the two moves determine the successor state. We study concurrent games with ω-regular winning conditions specified as parity objectives. We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respec- tively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). We study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies. In terms of precision, strategies can be deterministic, uniform, finite-precision or infinite- precision; and in terms of memory, strategies can be memoryless, finite-memory or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as power- ful as infinite-precision finite-memory strategies. We show that the winning sets can be computed in O(n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms, that are obtained by characterization of the winning sets as μ-calculus formulas, are considerably more involved than those for turn-based games.","lang":"eng"}],"publication_status":"published","month":"07","title":"Bounded rationality in concurrent parity games","language":[{"iso":"eng"}],"date_published":"2011-07-11T00:00:00Z","publisher":"ArXiv"},{"page":"17","main_file_link":[{"url":"http://arxiv.org/abs/1107.2132","open_access":"1"}],"year":"2011","status":"public","day":"11","date_created":"2018-12-11T12:02:46Z","oa":1,"type":"preprint","_id":"3339","publist_id":"3286","arxiv":1,"publication":"arXiv","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"De Alfaro, Luca","first_name":"Luca","last_name":"De Alfaro"},{"full_name":"Pritam, Roy","first_name":"Roy","last_name":"Pritam"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1107.2132"]},"date_updated":"2021-01-12T07:42:46Z","department":[{"_id":"KrCh"}],"citation":{"short":"K. Chatterjee, L. De Alfaro, R. Pritam, ArXiv (2011).","mla":"Chatterjee, Krishnendu, et al. “Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-Run Average Objectives.” <i>ArXiv</i>, ArXiv, 2011.","apa":"Chatterjee, K., De Alfaro, L., &#38; Pritam, R. (2011). Magnifying lens abstraction for stochastic games with discounted and long-run average objectives. <i>arXiv</i>. ArXiv.","chicago":"Chatterjee, Krishnendu, Luca De Alfaro, and Roy Pritam. “Magnifying Lens Abstraction for Stochastic Games with Discounted and Long-Run Average Objectives.” <i>ArXiv</i>. ArXiv, 2011.","ista":"Chatterjee K, De Alfaro L, Pritam R. 2011. Magnifying lens abstraction for stochastic games with discounted and long-run average objectives. arXiv, .","ama":"Chatterjee K, De Alfaro L, Pritam R. Magnifying lens abstraction for stochastic games with discounted and long-run average objectives. <i>arXiv</i>. 2011.","ieee":"K. Chatterjee, L. De Alfaro, and R. Pritam, “Magnifying lens abstraction for stochastic games with discounted and long-run average objectives,” <i>arXiv</i>. ArXiv, 2011."},"oa_version":"Preprint","language":[{"iso":"eng"}],"date_published":"2011-07-11T00:00:00Z","publisher":"ArXiv","title":"Magnifying lens abstraction for stochastic games with discounted and long-run average objectives","abstract":[{"text":"Turn-based stochastic games and its important subclass Markov decision processes (MDPs) provide models for systems with both probabilistic and nondeterministic behaviors. We consider turn-based stochastic games with two classical quantitative objectives: discounted-sum and long-run average objectives. The game models and the quantitative objectives are widely used in probabilistic verification, planning, optimal inventory control, network protocol and performance analysis. Games and MDPs that model realistic systems often have very large state spaces, and probabilistic abstraction techniques are necessary to handle the state-space explosion. The commonly used full-abstraction techniques do not yield space-savings for systems that have many states with similar value, but does not necessarily have similar transition structure. A semi-abstraction technique, namely Magnifying-lens abstractions (MLA), that clusters states based on value only, disregarding differences in their transition relation was proposed for qualitative objectives (reachability and safety objectives). In this paper we extend the MLA technique to solve stochastic games with discounted-sum and long-run average objectives. We present the MLA technique based abstraction-refinement algorithm for stochastic games and MDPs with discounted-sum objectives. For long-run average objectives, our solution works for all MDPs and a sub-class of stochastic games where every state has the same value. ","lang":"eng"}],"publication_status":"published","month":"07"},{"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T11:00:13Z","citation":{"ieee":"K. Chatterjee, M. H. Henzinger, M. Joglekar, and S. Nisarg, “Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives,” presented at the CAV: Computer Aided Verification, Snowbird, USA, 2011, vol. 6806, pp. 260–276.","apa":"Chatterjee, K., Henzinger, M. H., Joglekar, M., &#38; Nisarg, S. (2011). Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. In G. Gopalakrishnan &#38; S. Qadeer (Eds.) (Vol. 6806, pp. 260–276). Presented at the CAV: Computer Aided Verification, Snowbird, USA: Springer. <a href=\"https://doi.org/10.1007/978-3-642-22110-1_21\">https://doi.org/10.1007/978-3-642-22110-1_21</a>","ama":"Chatterjee K, Henzinger MH, Joglekar M, Nisarg S. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. In: Gopalakrishnan G, Qadeer S, eds. Vol 6806. Springer; 2011:260-276. doi:<a href=\"https://doi.org/10.1007/978-3-642-22110-1_21\">10.1007/978-3-642-22110-1_21</a>","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Manas Joglekar, and Shah Nisarg. “Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives.” edited by Ganesh Gopalakrishnan and Shaz Qadeer, 6806:260–76. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-22110-1_21\">https://doi.org/10.1007/978-3-642-22110-1_21</a>.","ista":"Chatterjee K, Henzinger MH, Joglekar M, Nisarg S. 2011. Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives. CAV: Computer Aided Verification, LNCS, vol. 6806, 260–276.","short":"K. Chatterjee, M.H. Henzinger, M. Joglekar, S. Nisarg, in:, G. Gopalakrishnan, S. Qadeer (Eds.), Springer, 2011, pp. 260–276.","mla":"Chatterjee, Krishnendu, et al. <i>Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives</i>. Edited by Ganesh Gopalakrishnan and Shaz Qadeer, vol. 6806, Springer, 2011, pp. 260–76, doi:<a href=\"https://doi.org/10.1007/978-3-642-22110-1_21\">10.1007/978-3-642-22110-1_21</a>."},"alternative_title":["LNCS"],"external_id":{"arxiv":["1104.3348"]},"user_id":"72615eeb-f1f3-11ec-aa25-d4573ddc34fd","publication_status":"published","abstract":[{"text":"We consider Markov decision processes (MDPs) with ω-regular specifications given as parity objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. The algorithms for the computation of the almost-sure winning set for parity objectives iteratively use the solutions for the almost-sure winning set for Büchi objectives (a special case of parity objectives). Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes O(nm)  symbolic steps as compared to the previous known algorithm that takes O(n 2) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs often have constant out-degree, and then our symbolic algorithm takes O(nn)  symbolic steps, as compared to the previous known O(n 2) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires O(nK)  symbolic steps, where K is the maximal number of edges of strongly connected components (scc’s) of the MDP. The win-lose algorithm requires symbolic computation of scc’s. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5·n symbolic steps, whereas our new algorithm takes 4 ·n symbolic steps.","lang":"eng"}],"date_published":"2011-08-11T00:00:00Z","publisher":"Springer","title":"Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives","oa":1,"day":"11","page":"260 - 276","doi":"10.1007/978-3-642-22110-1_21","year":"2011","editor":[{"first_name":"Ganesh","last_name":"Gopalakrishnan","full_name":"Gopalakrishnan, Ganesh"},{"first_name":"Shaz","last_name":"Qadeer","full_name":"Qadeer, Shaz"}],"related_material":{"record":[{"status":"public","id":"2831","relation":"later_version"}]},"publist_id":"3282","arxiv":1,"intvolume":"      6806","quality_controlled":"1","project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"}],"oa_version":"Preprint","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"last_name":"Joglekar","first_name":"Manas","full_name":"Joglekar, Manas"},{"full_name":"Nisarg, Shah","last_name":"Nisarg","first_name":"Shah"}],"month":"08","language":[{"iso":"eng"}],"volume":6806,"article_processing_charge":"No","date_created":"2018-12-11T12:02:47Z","_id":"3342","type":"conference","main_file_link":[{"url":"http://arxiv.org/abs/1104.3348","open_access":"1"}],"status":"public","conference":{"start_date":"2011-07-14","end_date":"2011-07-20","location":"Snowbird, USA","name":"CAV: Computer Aided Verification"}}]