[{"language":[{"iso":"eng"}],"type":"book_chapter","_id":"3311","publication_status":"inpress","abstract":[{"lang":"eng","text":"Alpha shapes have been conceived in 1981 as an attempt to define the shape of a finite set of point in the plane. Since then, connections to diverse areas in the sciences and engineering have developed, including to pattern recognition, digital shape sampling and processing, and structural molecular biology. This survey begins with a historical account and discusses geometric, algorithmic, topological, and combinatorial aspects of alpha shapes in this sequence."}],"citation":{"short":"H. Edelsbrunner, in:, R. van de Weygaert, G. Vegter, J. Ritzerveld, V. Icke (Eds.), Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings, Springer, n.d.","ama":"Edelsbrunner H. Alpha shapes - a survey. In: van de Weygaert R, Vegter G, Ritzerveld J, Icke V, eds. <i>Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings</i>. Springer.","ieee":"H. Edelsbrunner, “Alpha shapes - a survey,” in <i>Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings</i>, R. van de Weygaert, G. Vegter, J. Ritzerveld, and V. Icke, Eds. Springer.","chicago":"Edelsbrunner, Herbert. “Alpha Shapes - a Survey.” In <i>Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings</i>, edited by R van de Weygaert, G Vegter, J Ritzerveld, and V Icke. Springer, n.d.","mla":"Edelsbrunner, Herbert. “Alpha Shapes - a Survey.” <i>Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings</i>, edited by R van de Weygaert et al., Springer.","ista":"Edelsbrunner H.Alpha shapes - a survey. In: Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings. .","apa":"Edelsbrunner, H. (n.d.). Alpha shapes - a survey. In R. van de Weygaert, G. Vegter, J. Ritzerveld, &#38; V. Icke (Eds.), <i>Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings</i>. Springer."},"oa_version":"Submitted Version","publisher":"Springer","department":[{"_id":"HeEd"}],"status":"public","month":"12","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner"}],"quality_controlled":"1","ddc":["510"],"date_published":"2011-12-31T00:00:00Z","file_date_updated":"2022-05-24T07:55:05Z","oa":1,"publication":"Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings","article_processing_charge":"No","editor":[{"first_name":"R","full_name":"van de Weygaert, R","last_name":"van de Weygaert"},{"first_name":"G","full_name":"Vegter, G","last_name":"Vegter"},{"last_name":"Ritzerveld","full_name":"Ritzerveld, J","first_name":"J"},{"full_name":"Icke, V","first_name":"V","last_name":"Icke"}],"title":"Alpha shapes - a survey","date_updated":"2024-10-09T20:54:33Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:02:36Z","corr_author":"1","day":"31","has_accepted_license":"1","publist_id":"3329","file":[{"checksum":"a592ea438351e7280eea993a7713ab8f","date_updated":"2022-05-24T07:55:05Z","relation":"main_file","creator":"dernst","file_id":"11408","success":1,"date_created":"2022-05-24T07:55:05Z","access_level":"open_access","file_size":475254,"file_name":"2010_AlphaShapes.pdf","content_type":"application/pdf"}],"year":"2011"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","day":"31","year":"2011","conference":{"start_date":"2011-11-06","end_date":"2011-11-13","location":"Barcelona, Spain","name":"ICCV: International Conference on Computer Vision"},"has_accepted_license":"1","oa":1,"file_date_updated":"2020-07-14T12:46:07Z","ddc":["000"],"date_published":"2011-12-31T00:00:00Z","publication":"Proceedings of the IEEE International Conference on Computer Vision","acknowledgement":"This research is supported by the National Science Foundation (NSF) under grant DBI-0820624.","date_updated":"2024-10-21T06:03:02Z","oa_version":"Submitted Version","citation":{"ista":"Zheng Y, Gu S, Edelsbrunner H, Tomasi C, Benfey P. 2011. Detailed reconstruction of 3D plant root shape, IEEE,p.","apa":"Zheng, Y., Gu, S., Edelsbrunner, H., Tomasi, C., &#38; Benfey, P. (2011). <i>Detailed reconstruction of 3D plant root shape</i>. <i>Proceedings of the IEEE International Conference on Computer Vision</i>. Barcelona, Spain: IEEE. <a href=\"https://doi.org/10.1109/ICCV.2011.6126475\">https://doi.org/10.1109/ICCV.2011.6126475</a>","chicago":"Zheng, Ying, Steve Gu, Herbert Edelsbrunner, Carlo Tomasi, and Philip Benfey. <i>Detailed Reconstruction of 3D Plant Root Shape</i>. <i>Proceedings of the IEEE International Conference on Computer Vision</i>. IEEE, 2011. <a href=\"https://doi.org/10.1109/ICCV.2011.6126475\">https://doi.org/10.1109/ICCV.2011.6126475</a>.","mla":"Zheng, Ying, et al. “Detailed Reconstruction of 3D Plant Root Shape.” <i>Proceedings of the IEEE International Conference on Computer Vision</i>, 6126475, IEEE, 2011, doi:<a href=\"https://doi.org/10.1109/ICCV.2011.6126475\">10.1109/ICCV.2011.6126475</a>.","ieee":"Y. Zheng, S. Gu, H. Edelsbrunner, C. Tomasi, and P. Benfey, <i>Detailed reconstruction of 3D plant root shape</i>. IEEE, 2011.","short":"Y. Zheng, S. Gu, H. Edelsbrunner, C. Tomasi, P. Benfey, Detailed Reconstruction of 3D Plant Root Shape, IEEE, 2011.","ama":"Zheng Y, Gu S, Edelsbrunner H, Tomasi C, Benfey P. <i>Detailed Reconstruction of 3D Plant Root Shape</i>. IEEE; 2011. doi:<a href=\"https://doi.org/10.1109/ICCV.2011.6126475\">10.1109/ICCV.2011.6126475</a>"},"status":"public","month":"12","publication_status":"published","abstract":[{"text":"We study the 3D reconstruction of plant roots from multiple 2D images. To meet the challenge caused by the delicate nature of thin branches, we make three innovations to cope with the sensitivity to image quality and calibration. First, we model the background as a harmonic function to improve the segmentation of the root in each 2D image. Second, we develop the concept of the regularized visual hull which reduces the effect of jittering and refraction by ensuring consistency with one 2D image. Third, we guarantee connectedness through adjustments to the 3D reconstruction that minimize global error. Our software is part of a biological phenotype/genotype study of agricultural root systems. It has been tested on more than 40 plant roots and results are promising in terms of reconstruction quality and efficiency.","lang":"eng"}],"doi":"10.1109/ICCV.2011.6126475","date_created":"2018-12-11T12:02:36Z","file":[{"creator":"system","file_id":"4727","date_created":"2018-12-12T10:09:04Z","file_name":"IST-2016-541-v1+1_2011-P-07-RootReconstruction.pdf","file_size":5622728,"access_level":"open_access","content_type":"application/pdf","checksum":"30a33564b7b45a7ee31610898267fd0e","date_updated":"2020-07-14T12:46:07Z","relation":"main_file"}],"publist_id":"3328","title":"Detailed reconstruction of 3D plant root shape","article_processing_charge":"No","pubrep_id":"541","department":[{"_id":"HeEd"}],"publisher":"IEEE","article_number":"6126475","quality_controlled":"1","author":[{"last_name":"Zheng","first_name":"Ying","full_name":"Zheng, Ying"},{"first_name":"Steve","full_name":"Gu, Steve","last_name":"Gu"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner"},{"last_name":"Tomasi","full_name":"Tomasi, Carlo","first_name":"Carlo"},{"full_name":"Benfey, Philip","first_name":"Philip","last_name":"Benfey"}],"type":"conference_poster","language":[{"iso":"eng"}],"_id":"3312"},{"quality_controlled":"1","article_number":"6126271","author":[{"full_name":"Chen, Chao","first_name":"Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen"},{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"}],"publisher":"IEEE","department":[{"_id":"HeEd"}],"type":"conference","language":[{"iso":"eng"}],"_id":"3313","file":[{"creator":"system","content_type":"application/pdf","access_level":"open_access","file_size":614050,"file_name":"IST-2016-540-v1+1_2011-P-08-RunEmpty.pdf","date_created":"2018-12-12T10:17:28Z","file_id":"5282","date_updated":"2020-07-14T12:46:07Z","checksum":"6984684081ba123808b344f9f2e64a8f","relation":"main_file"}],"publist_id":"3327","date_created":"2018-12-11T12:02:37Z","corr_author":"1","title":"Diffusion runs low on persistence fast","pubrep_id":"540","status":"public","month":"11","oa_version":"Submitted Version","citation":{"chicago":"Chen, Chao, and Herbert Edelsbrunner. “Diffusion Runs Low on Persistence Fast.” In <i>Proceedings of the IEEE International Conference on Computer Vision</i>. IEEE, 2011. <a href=\"https://doi.org/10.1109/ICCV.2011.6126271\">https://doi.org/10.1109/ICCV.2011.6126271</a>.","mla":"Chen, Chao, and Herbert Edelsbrunner. “Diffusion Runs Low on Persistence Fast.” <i>Proceedings of the IEEE International Conference on Computer Vision</i>, 6126271, IEEE, 2011, doi:<a href=\"https://doi.org/10.1109/ICCV.2011.6126271\">10.1109/ICCV.2011.6126271</a>.","ista":"Chen C, Edelsbrunner H. 2011. Diffusion runs low on persistence fast. Proceedings of the IEEE International Conference on Computer Vision. ICCV: International Conference on Computer Vision, 6126271.","apa":"Chen, C., &#38; Edelsbrunner, H. (2011). Diffusion runs low on persistence fast. In <i>Proceedings of the IEEE International Conference on Computer Vision</i>. Barcelona, Spain: IEEE. <a href=\"https://doi.org/10.1109/ICCV.2011.6126271\">https://doi.org/10.1109/ICCV.2011.6126271</a>","short":"C. Chen, H. Edelsbrunner, in:, Proceedings of the IEEE International Conference on Computer Vision, IEEE, 2011.","ama":"Chen C, Edelsbrunner H. Diffusion runs low on persistence fast. In: <i>Proceedings of the IEEE International Conference on Computer Vision</i>. IEEE; 2011. doi:<a href=\"https://doi.org/10.1109/ICCV.2011.6126271\">10.1109/ICCV.2011.6126271</a>","ieee":"C. Chen and H. Edelsbrunner, “Diffusion runs low on persistence fast,” in <i>Proceedings of the IEEE International Conference on Computer Vision</i>, Barcelona, Spain, 2011."},"doi":"10.1109/ICCV.2011.6126271","abstract":[{"text":"Interpreting an image as a function on a compact sub- set of the Euclidean plane, we get its scale-space by diffu- sion, spreading the image over the entire plane. This gener- ates a 1-parameter family of functions alternatively defined as convolutions with a progressively wider Gaussian ker- nel. We prove that the corresponding 1-parameter family of persistence diagrams have norms that go rapidly to zero as time goes to infinity. This result rationalizes experimental observations about scale-space. We hope this will lead to targeted improvements of related computer vision methods.","lang":"eng"}],"publication_status":"published","day":"06","year":"2011","conference":{"name":"ICCV: International Conference on Computer Vision","location":"Barcelona, Spain","end_date":"2011-11-13","start_date":"2011-11-06"},"has_accepted_license":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"date_updated":"2024-10-09T20:54:33Z","oa":1,"file_date_updated":"2020-07-14T12:46:07Z","date_published":"2011-11-06T00:00:00Z","ddc":["000"],"publication":"Proceedings of the IEEE International Conference on Computer Vision"},{"quality_controlled":"1","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A"},{"first_name":"Vinayak","full_name":"Prabhu, Vinayak","last_name":"Prabhu"}],"issue":"4","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publisher":"International Federation of Computational Logic","project":[{"call_identifier":"FP7","name":"COMponent-Based Embedded Systems design Techniques","_id":"25EFB36C-B435-11E9-9278-68D0E5697425","grant_number":"215543"}],"type":"journal_article","language":[{"iso":"eng"}],"intvolume":"         7","ec_funded":1,"_id":"3315","tmp":{"short":"CC BY-ND (4.0)","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","image":"/image/cc_by_nd.png"},"file":[{"relation":"main_file","checksum":"3480e1594bbef25ff7462fa93a8a814e","date_updated":"2020-07-14T12:46:07Z","file_id":"5231","date_created":"2018-12-12T10:16:42Z","file_name":"IST-2016-86-v2+1_1011.0688_3_.pdf","access_level":"open_access","file_size":588863,"content_type":"application/pdf","creator":"system"}],"publist_id":"3324","date_created":"2018-12-11T12:02:37Z","corr_author":"1","title":"Timed parity games: Complexity and robustness","pubrep_id":"506","month":"12","status":"public","related_material":{"record":[{"id":"3876","status":"public","relation":"earlier_version"}]},"oa_version":"Published Version","citation":{"apa":"Chatterjee, K., Henzinger, T. A., &#38; Prabhu, V. (2011). Timed parity games: Complexity and robustness. <i>Logical Methods in Computer Science</i>. International Federation of Computational Logic. <a href=\"https://doi.org/10.2168/LMCS-7(4:8)2011\">https://doi.org/10.2168/LMCS-7(4:8)2011</a>","ista":"Chatterjee K, Henzinger TA, Prabhu V. 2011. Timed parity games: Complexity and robustness. Logical Methods in Computer Science. 7(4).","mla":"Chatterjee, Krishnendu, et al. “Timed Parity Games: Complexity and Robustness.” <i>Logical Methods in Computer Science</i>, vol. 7, no. 4, International Federation of Computational Logic, 2011, doi:<a href=\"https://doi.org/10.2168/LMCS-7(4:8)2011\">10.2168/LMCS-7(4:8)2011</a>.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Timed Parity Games: Complexity and Robustness.” <i>Logical Methods in Computer Science</i>. International Federation of Computational Logic, 2011. <a href=\"https://doi.org/10.2168/LMCS-7(4:8)2011\">https://doi.org/10.2168/LMCS-7(4:8)2011</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Timed parity games: Complexity and robustness,” <i>Logical Methods in Computer Science</i>, vol. 7, no. 4. International Federation of Computational Logic, 2011.","short":"K. Chatterjee, T.A. Henzinger, V. Prabhu, Logical Methods in Computer Science 7 (2011).","ama":"Chatterjee K, Henzinger TA, Prabhu V. Timed parity games: Complexity and robustness. <i>Logical Methods in Computer Science</i>. 2011;7(4). doi:<a href=\"https://doi.org/10.2168/LMCS-7(4:8)2011\">10.2168/LMCS-7(4:8)2011</a>"},"abstract":[{"text":"We consider two-player games played in real time on game structures with clocks where the objectives of players are described using parity conditions. The games are concurrent in that at each turn, both players independently propose a time delay and an action, and the action with the shorter delay is chosen. To prevent a player from winning by blocking time, we restrict each player to play strategies that ensure that the player cannot be responsible for causing a zeno run. First, we present an efficient reduction of these games to turn-based (i.e., not concurrent) finite-state (i.e., untimed) parity games. Our reduction improves the best known complexity for solving timed parity games. Moreover, the rich class of algorithms for classical parity games can now be applied to timed parity games. The states of the resulting game are based on clock regions of the original game, and the state space of the finite game is linear in the size of the region graph. Second, we consider two restricted classes of strategies for the player that represents the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust winning strategies. Using a limit-robust winning strategy, the controller cannot choose an exact real-valued time delay but must allow for some nonzero jitter in each of its actions. If there is a given lower bound on the jitter, then the strategy is bounded-robust winning. We show that exact strategies are more powerful than limit-robust strategies, which are more powerful than bounded-robust winning strategies for any bound. For both kinds of robust strategies, we present efficient reductions to standard timed automaton games. These reductions provide algorithms for the synthesis of robust real-time controllers.","lang":"eng"}],"doi":"10.2168/LMCS-7(4:8)2011","publication_status":"published","day":"14","year":"2011","has_accepted_license":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"volume":7,"date_updated":"2024-10-09T20:54:33Z","file_date_updated":"2020-07-14T12:46:07Z","oa":1,"date_published":"2011-12-14T00:00:00Z","ddc":["000","005"],"publication":"Logical Methods in Computer Science"},{"project":[{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23"},{"call_identifier":"FP7","name":"Design for Embedded Systems","grant_number":"214373","_id":"25F1337C-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"_id":"3316","ec_funded":1,"language":[{"iso":"eng"}],"type":"conference","author":[{"last_name":"Bloem","first_name":"Roderick","full_name":"Bloem, Roderick"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Greimel","full_name":"Greimel, Karin","first_name":"Karin"},{"full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger"},{"last_name":"Jobstmann","full_name":"Jobstmann, Barbara","first_name":"Barbara"}],"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://openlib.tugraz.at/download.php?id=5cb57c8a49344&location=browse"}],"publisher":"IEEE","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"article_processing_charge":"No","title":"Specification-centered robustness","publist_id":"3323","date_created":"2018-12-11T12:02:38Z","doi":"10.1109/SIES.2011.5953660","abstract":[{"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.","lang":"eng"}],"publication_status":"published","page":"176 - 185","status":"public","month":"07","citation":{"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.","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>.","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>.","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.","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.","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>"},"oa_version":"Published Version","date_updated":"2025-07-10T11:52:29Z","publication":"6th IEEE International Symposium on Industrial and Embedded Systems","date_published":"2011-07-14T00:00:00Z","oa":1,"year":"2011","conference":{"start_date":"2011-06-15","end_date":"2011-06-17","location":"Vasteras, Sweden","name":"SIES: International Symposium on Industrial Embedded Systems"},"day":"14","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"status":"public","month":"12","oa_version":"Submitted Version","citation":{"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.","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>","short":"E. Eggermann, P.M. Jonas, Nature Neuroscience 15 (2011) 20–22.","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>","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.","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>.","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>."},"doi":"10.1038/nn.3002","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."}],"publication_status":"published","page":"20 - 22","year":"2011","day":"04","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-30T09:20:05Z","volume":15,"isi":1,"publication":"Nature Neuroscience","oa":1,"date_published":"2011-12-04T00:00:00Z","quality_controlled":"1","author":[{"last_name":"Eggermann","full_name":"Eggermann, Emmanuel","first_name":"Emmanuel"},{"orcid":"0000-0001-5001-4804","id":"353C1B58-F248-11E8-B48F-1D18A9856A87","last_name":"Jonas","full_name":"Jonas, Peter M","first_name":"Peter M"}],"main_file_link":[{"url":"http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3631701/","open_access":"1"}],"publisher":"Nature Publishing Group","department":[{"_id":"PeJo"}],"intvolume":"        15","_id":"3318","type":"journal_article","language":[{"iso":"eng"}],"publist_id":"3321","corr_author":"1","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","article_processing_charge":"No","external_id":{"isi":["000298414400008"]}},{"year":"2011","conference":{"name":"ICML: International Conference on Machine Learning","location":"Bellevue, United States","end_date":"2011-07-02","start_date":"2011-06-28"},"publist_id":"3316","day":"01","corr_author":"1","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:02:39Z","date_updated":"2024-10-09T20:54:32Z","title":"Learning multi-view neighborhood preserving projections","article_processing_charge":"No","date_published":"2011-01-01T00:00:00Z","author":[{"first_name":"Novi","full_name":"Quadrianto, Novi","last_name":"Quadrianto"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","last_name":"Lampert","full_name":"Lampert, Christoph","first_name":"Christoph"}],"month":"01","status":"public","publisher":"ML Research Press","oa_version":"None","department":[{"_id":"ChLa"}],"citation":{"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.","ama":"Quadrianto N, Lampert C. Learning multi-view neighborhood preserving projections. In: ML Research Press; 2011:425-432.","short":"N. Quadrianto, C. Lampert, in:, ML Research Press, 2011, pp. 425–432.","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.","ista":"Quadrianto N, Lampert C. 2011. Learning multi-view neighborhood preserving projections. ICML: International Conference on Machine Learning, 425–432.","mla":"Quadrianto, Novi, and Christoph Lampert. <i>Learning Multi-View Neighborhood Preserving Projections</i>. ML Research Press, 2011, pp. 425–32.","chicago":"Quadrianto, Novi, and Christoph Lampert. “Learning Multi-View Neighborhood Preserving Projections,” 425–32. ML Research Press, 2011."},"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"}],"page":"425 - 432","publication_status":"published","_id":"3319","type":"conference","language":[{"iso":"eng"}]},{"day":"23","year":"2011","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","volume":6,"date_updated":"2024-10-09T20:54:32Z","file_date_updated":"2020-07-14T12:46:07Z","oa":1,"date_published":"2011-05-23T00:00:00Z","ddc":["000"],"publication":"Foundations and Trends in Computer Graphics and Vision","month":"05","status":"public","oa_version":"Published Version","citation":{"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.","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>","short":"S. Nowozin, C. Lampert, Foundations and Trends in Computer Graphics and Vision 6 (2011) 185–365.","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>","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>.","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>."},"abstract":[{"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.","lang":"eng"}],"doi":"10.1561/0600000033","page":"185 - 365","publication_status":"published","file":[{"creator":"dernst","file_id":"7837","date_created":"2020-05-14T14:34:47Z","access_level":"open_access","file_name":"2011_CompGraphicsVision_Nowozin.pdf","file_size":3745064,"content_type":"application/pdf","checksum":"f1043ef389f1558e2a226bb51568511f","date_updated":"2020-07-14T12:46:07Z","relation":"main_file"}],"publist_id":"3315","date_created":"2018-12-11T12:02:39Z","corr_author":"1","title":"Structured learning and prediction in computer vision","article_processing_charge":"No","article_type":"original","quality_controlled":"1","author":[{"last_name":"Nowozin","first_name":"Sebastian","full_name":"Nowozin, Sebastian"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","last_name":"Lampert","full_name":"Lampert, Christoph","first_name":"Christoph"}],"issue":"3-4","department":[{"_id":"ChLa"}],"publisher":"Now Publishers","type":"journal_article","language":[{"iso":"eng"}],"intvolume":"         6","_id":"3320"},{"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"}],"type":"conference_poster","language":[{"iso":"eng"}],"publication_status":"published","_id":"3322","status":"public","month":"12","related_material":{"record":[{"status":"public","id":"3163","relation":"earlier_version"}]},"author":[{"full_name":"Lampert, Christoph","first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","last_name":"Lampert"}],"oa_version":"None","department":[{"_id":"ChLa"}],"publisher":"Neural Information Processing Systems Foundation","citation":{"short":"C. Lampert, Maximum Margin Multi Label Structured Prediction, Neural Information Processing Systems Foundation, 2011.","ama":"Lampert C. <i>Maximum Margin Multi Label Structured Prediction</i>. Neural Information Processing Systems Foundation; 2011.","ieee":"C. Lampert, <i>Maximum margin multi label structured prediction</i>. Neural Information Processing Systems Foundation, 2011.","chicago":"Lampert, Christoph. <i>Maximum Margin Multi Label Structured Prediction</i>. <i>NIPS: Neural Information Processing Systems</i>. 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.","ista":"Lampert C. 2011. Maximum margin multi label structured prediction, Neural Information Processing Systems Foundation,p.","apa":"Lampert, C. (2011). <i>Maximum margin multi label structured prediction</i>. <i>NIPS: Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation."},"title":"Maximum margin multi label structured prediction","article_processing_charge":"No","date_updated":"2025-06-03T11:47:47Z","date_published":"2011-12-13T00:00:00Z","publication":"NIPS: Neural Information Processing Systems","day":"13","year":"2011","publist_id":"3313","date_created":"2018-12-11T12:02:40Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"date_published":"2011-07-19T00:00:00Z","date_updated":"2024-10-09T20:54:31Z","volume":6803,"title":"An efficient decision procedure for imperative tree data structures","scopus_import":1,"corr_author":"1","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:02:40Z","publist_id":"3312","year":"2011","conference":{"name":"CADE 23: Automated Deduction ","location":"Wrocław, Poland","end_date":"2011-08-05","start_date":"2011-07-31"},"day":"19","_id":"3323","page":"476 - 491","intvolume":"      6803","publication_status":"published","language":[{"iso":"eng"}],"type":"conference","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"}],"alternative_title":["LNAI "],"doi":"10.1007/978-3-642-22438-6_36","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.","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>","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>.","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>.","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.","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>","short":"T. Wies, M. Muñiz, V. Kuncak, in:, Springer, 2011, pp. 476–491."},"department":[{"_id":"ToHe"}],"oa_version":"None","publisher":"Springer","author":[{"last_name":"Wies","id":"447BFB88-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas","full_name":"Wies, Thomas"},{"last_name":"Muñiz","first_name":"Marco","full_name":"Muñiz, Marco"},{"last_name":"Kuncak","first_name":"Viktor","full_name":"Kuncak, Viktor"}],"quality_controlled":"1","related_material":{"record":[{"status":"public","id":"5383","relation":"earlier_version"}]},"status":"public","month":"07"},{"oa_version":"Submitted Version","citation":{"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>.","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>.","ista":"Piskac R, Wies T. 2011. Decision procedures for automating termination proofs. VMCAI: Verification Model Checking and Abstract Interpretation, LNCS, vol. 6538, 371–386.","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>","short":"R. Piskac, T. Wies, in:, R. Jhala, D. Schmidt (Eds.), Springer, 2011, pp. 371–386.","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>","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."},"status":"public","month":"01","page":"371 - 386","publication_status":"published","abstract":[{"lang":"eng","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."}],"alternative_title":["LNCS"],"doi":"10.1007/978-3-642-18275-4_26","scopus_import":1,"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Texas, USA","name":"VMCAI: Verification Model Checking and Abstract Interpretation","start_date":"2011-01-23","end_date":"2011-01-25"},"year":"2011","day":"01","oa":1,"date_published":"2011-01-01T00:00:00Z","date_updated":"2021-01-12T07:42:39Z","volume":6538,"publisher":"Springer","department":[{"_id":"ToHe"}],"quality_controlled":"1","author":[{"last_name":"Piskac","first_name":"Ruzica","full_name":"Piskac, Ruzica"},{"full_name":"Wies, Thomas","first_name":"Thomas","id":"447BFB88-F248-11E8-B48F-1D18A9856A87","last_name":"Wies"}],"main_file_link":[{"url":"https://infoscience.epfl.ch/record/170697/","open_access":"1"}],"intvolume":"      6538","_id":"3324","type":"conference","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:02:40Z","publist_id":"3311","editor":[{"last_name":"Jhala","first_name":"Ranjit","full_name":"Jhala, Ranjit"},{"first_name":"David","full_name":"Schmidt, David","last_name":"Schmidt"}],"title":"Decision procedures for automating termination proofs"},{"scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2011","conference":{"end_date":"2011-01-28","start_date":"2011-01-26","name":"POPL: Principles of Programming Languages","location":"Texas, USA"},"day":"26","isi":1,"date_published":"2011-01-26T00:00:00Z","date_updated":"2025-09-30T09:10:38Z","volume":46,"citation":{"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>","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.","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>.","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>.","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.","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>","short":"R. Alur, P. Cerny, in:, ACM, 2011, pp. 599–610."},"oa_version":"None","status":"public","month":"01","publication_status":"published","page":"599 - 610","abstract":[{"lang":"eng","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."}],"doi":"10.1145/1926385.1926454","date_created":"2018-12-11T12:02:41Z","publist_id":"3310","external_id":{"isi":["000289656100050"]},"article_processing_charge":"No","title":"Streaming transducers for algorithmic verification of single pass list processing programs","publisher":"ACM","department":[{"_id":"ToHe"}],"issue":"1","author":[{"first_name":"Rajeev","full_name":"Alur, Rajeev","last_name":"Alur"},{"full_name":"Cerny, Pavol","first_name":"Pavol","id":"4DCBEFFE-F248-11E8-B48F-1D18A9856A87","last_name":"Cerny"}],"quality_controlled":"1","_id":"3325","intvolume":"        46","language":[{"iso":"eng"}],"type":"conference"},{"title":"What’s decidable about weighted automata","article_processing_charge":"No","date_created":"2018-12-11T12:02:41Z","file":[{"creator":"dernst","file_id":"7868","date_created":"2020-05-19T16:08:32Z","file_size":182309,"file_name":"2011_LNCS_Almagor.pdf","access_level":"open_access","content_type":"application/pdf","checksum":"a7ca08a2cb1b6925f4c18a3034ae5659","date_updated":"2020-07-14T12:46:07Z","relation":"main_file"}],"publist_id":"3309","type":"conference","language":[{"iso":"eng"}],"intvolume":"      6996","_id":"3326","department":[{"_id":"ToHe"}],"publisher":"Springer","quality_controlled":"1","author":[{"first_name":"Shaull","full_name":"Almagor, Shaull","last_name":"Almagor"},{"full_name":"Boker, Udi","first_name":"Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","last_name":"Boker"},{"first_name":"Orna","full_name":"Kupferman, Orna","last_name":"Kupferman"}],"oa":1,"file_date_updated":"2020-07-14T12:46:07Z","ddc":["000"],"date_published":"2011-10-14T00:00:00Z","volume":6996,"date_updated":"2025-01-14T12:09:37Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","day":"14","year":"2011","conference":{"name":"ATVA: Automated Technology for Verification and Analysis","location":"Taipei, Taiwan","end_date":"2011-10-14","start_date":"2011-10-11"},"has_accepted_license":"1","publication_status":"published","page":"482 - 491","doi":"10.1007/978-3-642-24372-1_37","alternative_title":["LNCS"],"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."}],"oa_version":"Submitted Version","citation":{"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>","short":"S. Almagor, U. Boker, O. Kupferman, in:, Springer, 2011, pp. 482–491.","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.","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>.","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>.","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>","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."},"month":"10","status":"public"},{"publication_status":"published","intvolume":"      6604","page":"184 - 198","_id":"3327","extern":"1","type":"conference","language":[{"iso":"eng"}],"abstract":[{"text":"We solve the open problems of translating, when possible, all common classes of nondeterministic word automata to deterministic and nondeterministic co-Büchi word automata. The handled classes include Büchi, parity, Rabin, Streett and Muller automata. The translations follow a unified approach and are all asymptotically tight. The problem of translating Büchi automata to equivalent co-Büchi automata was solved in [2], leaving open the problems of translating automata with richer acceptance conditions. For these classes, one cannot easily extend or use the construction in [2]. In particular, going via an intermediate Büchi automaton is not optimal and might involve a blow-up exponentially higher than the known lower bound. Other known translations are also not optimal and involve a doubly exponential blow-up. We describe direct, simple, and asymptotically tight constructions, involving a 2Θ(n) blow-up. The constructions are variants of the subset construction, and allow for symbolic implementations. Beyond the theoretical importance of the results, the new constructions have various applications, among which is an improved algorithm for translating, when possible, LTL formulas to deterministic Büchi word automata.","lang":"eng"}],"alternative_title":["LNCS"],"doi":"10.1007/978-3-642-19805-2_13","publisher":"Springer","oa_version":"None","citation":{"ieee":"U. Boker and O. Kupferman, “Co-Büching them all,” presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Saarbrücken, Germany, 2011, vol. 6604, pp. 184–198.","short":"U. Boker, O. Kupferman, in:, M. Hofmann (Ed.), Springer, 2011, pp. 184–198.","ama":"Boker U, Kupferman O. Co-Büching them all. In: Hofmann M, ed. Vol 6604. Springer; 2011:184-198. doi:<a href=\"https://doi.org/10.1007/978-3-642-19805-2_13\">10.1007/978-3-642-19805-2_13</a>","ista":"Boker U, Kupferman O. 2011. Co-Büching them all. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS, vol. 6604, 184–198.","apa":"Boker, U., &#38; Kupferman, O. (2011). Co-Büching them all. In M. Hofmann (Ed.) (Vol. 6604, pp. 184–198). Presented at the FoSSaCS: Foundations of Software Science and Computation Structures, Saarbrücken, Germany: Springer. <a href=\"https://doi.org/10.1007/978-3-642-19805-2_13\">https://doi.org/10.1007/978-3-642-19805-2_13</a>","chicago":"Boker, Udi, and Orna Kupferman. “Co-Büching Them All.” edited by Martin Hofmann, 6604:184–98. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-19805-2_13\">https://doi.org/10.1007/978-3-642-19805-2_13</a>.","mla":"Boker, Udi, and Orna Kupferman. <i>Co-Büching Them All</i>. Edited by Martin Hofmann, vol. 6604, Springer, 2011, pp. 184–98, doi:<a href=\"https://doi.org/10.1007/978-3-642-19805-2_13\">10.1007/978-3-642-19805-2_13</a>."},"quality_controlled":"1","author":[{"id":"31E297B6-F248-11E8-B48F-1D18A9856A87","last_name":"Boker","full_name":"Boker, Udi","first_name":"Udi"},{"full_name":"Kupferman, Orna","first_name":"Orna","last_name":"Kupferman"}],"month":"03","status":"public","date_published":"2011-03-29T00:00:00Z","date_updated":"2021-01-12T07:42:41Z","title":"Co-Büching them all","editor":[{"first_name":"Martin","full_name":"Hofmann, Martin","last_name":"Hofmann"}],"volume":6604,"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:02:41Z","year":"2011","conference":{"name":"FoSSaCS: Foundations of Software Science and Computation Structures","location":"Saarbrücken, Germany","end_date":"2011-04-03","start_date":"2011-03-26"},"publist_id":"3308","day":"29"},{"language":[{"iso":"eng"}],"type":"conference","_id":"3328","page":"179 - 186","publication_status":"published","doi":"10.1145/1998196.1998224","abstract":[{"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.","lang":"eng"}],"citation":{"ista":"Berberich E, Hemmer M, Kerber M. 2011. A generic algebraic kernel for non linear geometric applications. SCG: Symposium on Computational Geometry, 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>","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>.","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.","short":"E. Berberich, M. Hemmer, M. Kerber, in:, ACM, 2011, pp. 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>"},"department":[{"_id":"HeEd"}],"oa_version":"Published Version","publisher":"ACM","main_file_link":[{"url":"https://hal.inria.fr/inria-00480031/file/RR-7274.pdf","open_access":"1"}],"month":"06","status":"public","author":[{"full_name":"Berberich, Eric","first_name":"Eric","last_name":"Berberich"},{"last_name":"Hemmer","full_name":"Hemmer, Michael","first_name":"Michael"},{"orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","full_name":"Kerber, Michael","first_name":"Michael"}],"quality_controlled":"1","date_published":"2011-06-13T00:00:00Z","oa":1,"article_processing_charge":"No","title":"A generic algebraic kernel for non linear geometric applications","date_updated":"2021-01-12T07:42:41Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:02:42Z","scopus_import":1,"day":"13","publist_id":"3307","year":"2011","conference":{"name":"SCG: Symposium on Computational Geometry","location":"Paris, France","end_date":"2011-06-15","start_date":"2011-06-13"}},{"oa":1,"date_published":"2011-06-13T00:00:00Z","arxiv":1,"publication":"Proceedings of the twenty-seventh annual symposium on Computational geometry","date_updated":"2025-09-30T08:01:35Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","day":"13","year":"2011","conference":{"location":"Paris, France","name":"SCG: Symposium on Computational Geometry","start_date":"2011-06-13","end_date":"2011-06-15"},"page":"187 - 196","publication_status":"published","abstract":[{"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.","lang":"eng"}],"doi":"10.1145/1998196.1998225","oa_version":"Preprint","citation":{"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>","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.","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>.","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>.","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>","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."},"status":"public","month":"06","related_material":{"record":[{"id":"3115","status":"public","relation":"later_version"}]},"external_id":{"arxiv":["1109.2158"]},"title":"Deconstructing approximate offsets","article_processing_charge":"No","date_created":"2018-12-11T12:02:42Z","publist_id":"3306","type":"conference","language":[{"iso":"eng"}],"_id":"3329","department":[{"_id":"HeEd"}],"publisher":"ACM","main_file_link":[{"url":"http://arxiv.org/abs/1109.2158","open_access":"1"}],"quality_controlled":"1","author":[{"last_name":"Berberich","full_name":"Berberich, Eric","first_name":"Eric"},{"last_name":"Halperin","first_name":"Dan","full_name":"Halperin, Dan"},{"last_name":"Kerber","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Kerber, Michael"},{"last_name":"Pogalnikova","first_name":"Roza","full_name":"Pogalnikova, Roza"}]},{"conference":{"location":"California, USA","name":"ISSAC: International Symposium on Symbolic and Algebraic Computation","start_date":"2011-06-08","end_date":"2011-06-11"},"year":"2011","publist_id":"3304","day":"08","scopus_import":1,"date_created":"2018-12-11T12:02:43Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T07:42:42Z","title":"Root refinement for real polynomials","article_processing_charge":"No","oa":1,"external_id":{"arxiv":["1104.1362"]},"arxiv":1,"date_published":"2011-06-08T00:00:00Z","quality_controlled":"1","author":[{"orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","full_name":"Kerber, Michael","first_name":"Michael"},{"last_name":"Sagraloff","full_name":"Sagraloff, Michael","first_name":"Michael"}],"month":"06","status":"public","main_file_link":[{"url":"http://arxiv.org/abs/1104.1362","open_access":"1"}],"department":[{"_id":"HeEd"}],"publisher":"Springer","oa_version":"Preprint","citation":{"short":"M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.","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>","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.","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>.","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>.","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>","ista":"Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC: International Symposium on Symbolic and Algebraic Computation, 209–216."},"doi":"10.1145/1993886.1993920","abstract":[{"lang":"eng","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."}],"page":"209 - 216","publication_status":"published","_id":"3330","type":"conference","language":[{"iso":"eng"}]},{"month":"03","status":"public","citation":{"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.","short":"M. Kerber, M. Sagraloff, Graphs and Combinatorics 27 (2011) 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>","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.","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>.","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>."},"oa_version":"Submitted Version","doi":"10.1007/s00373-011-1020-7","abstract":[{"lang":"eng","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."}],"page":"419 - 430","publication_status":"published","day":"17","has_accepted_license":"1","year":"2011","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","volume":27,"date_updated":"2025-09-30T09:09:33Z","ddc":["500"],"date_published":"2011-03-17T00:00:00Z","oa":1,"file_date_updated":"2020-07-14T12:46:08Z","publication":"Graphs and Combinatorics","isi":1,"author":[{"last_name":"Kerber","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Kerber, Michael"},{"last_name":"Sagraloff","first_name":"Michael","full_name":"Sagraloff, Michael"}],"quality_controlled":"1","issue":"3","publisher":"Springer","department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}],"type":"journal_article","_id":"3332","intvolume":"        27","publist_id":"3301","file":[{"checksum":"a63a1e3e885dcc68f1e3dea68dfbe213","date_updated":"2020-07-14T12:46:08Z","relation":"main_file","creator":"dernst","date_created":"2020-05-19T16:11:36Z","file_id":"7869","content_type":"application/pdf","access_level":"open_access","file_size":143976,"file_name":"2011_GraphsCombi_Kerber.pdf"}],"date_created":"2018-12-11T12:02:43Z","corr_author":"1","article_processing_charge":"No","title":"A note on the complexity of real algebraic hypersurfaces","article_type":"original","external_id":{"isi":["000289438700011"]}},{"day":"01","year":"2011","publist_id":"3297","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T12:02:44Z","scopus_import":"1","title":"Letter from the new editors-in-chief","article_processing_charge":"No","volume":45,"date_updated":"2025-05-20T06:02:58Z","date_published":"2011-01-01T00:00:00Z","article_type":"editorial","publication":"Discrete & Computational Geometry","status":"public","month":"01","quality_controlled":"1","author":[{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"last_name":"Pach","full_name":"Pach, János","first_name":"János"},{"last_name":"Ziegler","full_name":"Ziegler, Günter","first_name":"Günter"}],"issue":"1","OA_type":"closed access","publisher":"Springer","oa_version":"None","department":[{"_id":"HeEd"}],"citation":{"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.","short":"H. Edelsbrunner, J. Pach, G. Ziegler, Discrete &#38; Computational Geometry 45 (2011) 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>","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>","ista":"Edelsbrunner H, Pach J, Ziegler G. 2011. Letter from the new editors-in-chief. Discrete &#38; Computational Geometry. 45(1), 1–2.","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>.","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>."},"doi":"10.1007/s00454-010-9313-9","type":"journal_article","language":[{"iso":"eng"}],"intvolume":"        45","publication_status":"published","page":"1 - 2","_id":"3334"},{"month":"11","status":"public","oa_version":"Preprint","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.","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>","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.","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>.","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>.","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.","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>"},"abstract":[{"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.","lang":"eng"}],"alternative_title":["LNCS"],"doi":"10.1007/978-3-642-25249-5_3","page":"60 - 101","publication_status":"published","year":"2011","day":"09","scopus_import":1,"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T07:42:44Z","volume":6970,"publication":"Transactions on Computational Science XIV","oa":1,"arxiv":1,"date_published":"2011-11-09T00:00:00Z","quality_controlled":"1","author":[{"last_name":"Van De Weygaert","first_name":"Rien","full_name":"Van De Weygaert, Rien"},{"first_name":"Gert","full_name":"Vegter, Gert","last_name":"Vegter"},{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"last_name":"Jones","full_name":"Jones, Bernard","first_name":"Bernard"},{"first_name":"Pratyush","full_name":"Pranav, Pratyush","last_name":"Pranav"},{"last_name":"Park","first_name":"Changbom","full_name":"Park, Changbom"},{"last_name":"Hellwing","first_name":"Wojciech","full_name":"Hellwing, Wojciech"},{"last_name":"Eldering","first_name":"Bob","full_name":"Eldering, Bob"},{"full_name":"Kruithof, Nico","first_name":"Nico","last_name":"Kruithof"},{"last_name":"Bos","full_name":"Bos, Patrick","first_name":"Patrick"},{"first_name":"Johan","full_name":"Hidding, Johan","last_name":"Hidding"},{"last_name":"Feldbrugge","first_name":"Job","full_name":"Feldbrugge, Job"},{"last_name":"Ten Have","full_name":"Ten Have, Eline","first_name":"Eline"},{"last_name":"Van Engelen","full_name":"Van Engelen, Matti","first_name":"Matti"},{"full_name":"Caroli, Manuel","first_name":"Manuel","last_name":"Caroli"},{"last_name":"Teillaud","first_name":"Monique","full_name":"Teillaud, Monique"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1306.3640"}],"publisher":"Springer","department":[{"_id":"HeEd"}],"series_title":"Special Issue on Voronoi Diagrams and Delaunay Triangulation","intvolume":"      6970","_id":"3335","type":"book_chapter","language":[{"iso":"eng"}],"publist_id":"3295","date_created":"2018-12-11T12:02:44Z","editor":[{"last_name":"Gavrilova","full_name":"Gavrilova, Marina","first_name":"Marina"},{"last_name":"Tan","full_name":"Tan, Kenneth","first_name":"Kenneth"},{"last_name":"Mostafavi","first_name":"Mir","full_name":"Mostafavi, Mir"}],"title":"Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web","external_id":{"arxiv":["1306.3640"]}}]