[{"ec_funded":1,"issue":"6","related_material":{"record":[{"id":"12897","status":"public","relation":"dissertation_contains"}]},"volume":38,"publication_status":"published","publication_identifier":{"issn":["0730-0301"]},"language":[{"iso":"eng"}],"file":[{"file_id":"7119","checksum":"56a2fb019adcb556d2b022f5e5acb68c","relation":"supplementary_material","access_level":"open_access","content_type":"application/pdf","file_name":"xcad_sup_mat_siga19.pdf","date_created":"2019-11-26T14:24:26Z","title":"X-CAD Supplemental Material","creator":"bbickel","file_size":1673176,"date_updated":"2020-07-14T12:47:49Z"},{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","description":"This is the author's version of the work.","file_id":"7120","checksum":"5f29d76aceb5102e766cbab9b17d776e","creator":"bbickel","file_size":14563618,"date_updated":"2020-07-14T12:47:49Z","file_name":"XCAD_authors_version.pdf","date_created":"2019-11-26T14:24:27Z","title":"X-CAD: Optimizing CAD Models with Extended Finite Elements"},{"date_created":"2019-11-26T14:27:37Z","file_name":"XCAD_video.mp4","date_updated":"2020-07-14T12:47:49Z","file_size":259979129,"creator":"bbickel","checksum":"0d31e123286cbec9e28b2001c2bb0d55","file_id":"7121","content_type":"video/mp4","access_level":"open_access","relation":"main_file"}],"scopus_import":"1","intvolume":" 38","month":"11","abstract":[{"text":"We propose a novel generic shape optimization method for CAD models based on the eXtended Finite Element Method (XFEM). Our method works directly on the intersection between the model and a regular simulation grid, without the need to mesh or remesh, thus removing a bottleneck of classical shape optimization strategies. This is made possible by a novel hierarchical integration scheme that accurately integrates finite element quantities with sub-element precision. For optimization, we efficiently compute analytical shape derivatives of the entire framework, from model intersection to integration rule generation and XFEM simulation. Moreover, we describe a differentiable projection of shape parameters onto a constraint manifold spanned by user-specified shape preservation, consistency, and manufacturability constraints. We demonstrate the utility of our approach by optimizing mass distribution, strength-to-weight ratio, and inverse elastic shape design objectives directly on parameterized 3D CAD models.","lang":"eng"}],"oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:47:49Z","department":[{"_id":"BeBi"}],"date_updated":"2024-03-27T23:30:46Z","ddc":["000"],"article_type":"original","type":"journal_article","status":"public","_id":"7117","date_created":"2019-11-26T14:22:09Z","doi":"10.1145/3355089.3356576","date_published":"2019-11-06T00:00:00Z","year":"2019","isi":1,"has_accepted_license":"1","publication":"ACM Transactions on Graphics","day":"06","oa":1,"quality_controlled":"1","publisher":"ACM","external_id":{"isi":["000498397300007"]},"article_processing_charge":"No","author":[{"id":"400429CC-F248-11E8-B48F-1D18A9856A87","first_name":"Christian","full_name":"Hafner, Christian","last_name":"Hafner"},{"full_name":"Schumacher, Christian","last_name":"Schumacher","first_name":"Christian"},{"first_name":"Espen","last_name":"Knoop","full_name":"Knoop, Espen"},{"full_name":"Auzinger, Thomas","orcid":"0000-0002-1546-3265","last_name":"Auzinger","id":"4718F954-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas"},{"id":"49876194-F248-11E8-B48F-1D18A9856A87","first_name":"Bernd","full_name":"Bickel, Bernd","orcid":"0000-0001-6511-9385","last_name":"Bickel"},{"full_name":"Bächer, Moritz","last_name":"Bächer","first_name":"Moritz"}],"title":"X-CAD: Optimizing CAD Models with Extended Finite Elements","citation":{"chicago":"Hafner, Christian, Christian Schumacher, Espen Knoop, Thomas Auzinger, Bernd Bickel, and Moritz Bächer. “X-CAD: Optimizing CAD Models with Extended Finite Elements.” ACM Transactions on Graphics. ACM, 2019. https://doi.org/10.1145/3355089.3356576.","ista":"Hafner C, Schumacher C, Knoop E, Auzinger T, Bickel B, Bächer M. 2019. X-CAD: Optimizing CAD Models with Extended Finite Elements. ACM Transactions on Graphics. 38(6), 157.","mla":"Hafner, Christian, et al. “X-CAD: Optimizing CAD Models with Extended Finite Elements.” ACM Transactions on Graphics, vol. 38, no. 6, 157, ACM, 2019, doi:10.1145/3355089.3356576.","short":"C. Hafner, C. Schumacher, E. Knoop, T. Auzinger, B. Bickel, M. Bächer, ACM Transactions on Graphics 38 (2019).","ieee":"C. Hafner, C. Schumacher, E. Knoop, T. Auzinger, B. Bickel, and M. Bächer, “X-CAD: Optimizing CAD Models with Extended Finite Elements,” ACM Transactions on Graphics, vol. 38, no. 6. ACM, 2019.","ama":"Hafner C, Schumacher C, Knoop E, Auzinger T, Bickel B, Bächer M. X-CAD: Optimizing CAD Models with Extended Finite Elements. ACM Transactions on Graphics. 2019;38(6). doi:10.1145/3355089.3356576","apa":"Hafner, C., Schumacher, C., Knoop, E., Auzinger, T., Bickel, B., & Bächer, M. (2019). X-CAD: Optimizing CAD Models with Extended Finite Elements. ACM Transactions on Graphics. ACM. https://doi.org/10.1145/3355089.3356576"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"name":"MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling","grant_number":"715767","call_identifier":"H2020","_id":"24F9549A-B435-11E9-9278-68D0E5697425"}],"article_number":"157"},{"oa_version":"Preprint","abstract":[{"text":"Suspended particles can alter the properties of fluids and in particular also affect the transition fromlaminar to turbulent flow. An earlier study [Mataset al.,Phys. Rev. Lett.90, 014501 (2003)] reported howthe subcritical (i.e., hysteretic) transition to turbulent puffs is affected by the addition of particles. Here weshow that in addition to this known transition, with increasing concentration a supercritical (i.e.,continuous) transition to a globally fluctuating state is found. At the same time the Newtonian-typetransition to puffs is delayed to larger Reynolds numbers. At even higher concentration only the globallyfluctuating state is found. The dynamics of particle laden flows are hence determined by two competinginstabilities that give rise to three flow regimes: Newtonian-type turbulence at low, a particle inducedglobally fluctuating state at high, and a coexistence state at intermediate concentrations.","lang":"eng"}],"month":"03","intvolume":" 122","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1809.06358"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["10797114"],"issn":["00319007"]},"publication_status":"published","issue":"11","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"9728"}]},"volume":122,"_id":"6189","status":"public","type":"journal_article","date_updated":"2024-03-27T23:30:47Z","department":[{"_id":"BjHo"}],"publisher":"American Physical Society","quality_controlled":"1","oa":1,"day":"22","publication":"Physical Review Letters","isi":1,"year":"2019","doi":"10.1103/PhysRevLett.122.114502","date_published":"2019-03-22T00:00:00Z","date_created":"2019-03-31T21:59:12Z","article_number":"114502","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Agrawal, Nishchal, et al. “Transition to Turbulence in Particle Laden Flows.” Physical Review Letters, vol. 122, no. 11, 114502, American Physical Society, 2019, doi:10.1103/PhysRevLett.122.114502.","ieee":"N. Agrawal, G. H. Choueiri, and B. Hof, “Transition to turbulence in particle laden flows,” Physical Review Letters, vol. 122, no. 11. American Physical Society, 2019.","short":"N. Agrawal, G.H. Choueiri, B. Hof, Physical Review Letters 122 (2019).","ama":"Agrawal N, Choueiri GH, Hof B. Transition to turbulence in particle laden flows. Physical Review Letters. 2019;122(11). doi:10.1103/PhysRevLett.122.114502","apa":"Agrawal, N., Choueiri, G. H., & Hof, B. (2019). Transition to turbulence in particle laden flows. Physical Review Letters. American Physical Society. https://doi.org/10.1103/PhysRevLett.122.114502","chicago":"Agrawal, Nishchal, George H Choueiri, and Björn Hof. “Transition to Turbulence in Particle Laden Flows.” Physical Review Letters. American Physical Society, 2019. https://doi.org/10.1103/PhysRevLett.122.114502.","ista":"Agrawal N, Choueiri GH, Hof B. 2019. Transition to turbulence in particle laden flows. Physical Review Letters. 122(11), 114502."},"title":"Transition to turbulence in particle laden flows","author":[{"full_name":"Agrawal, Nishchal","last_name":"Agrawal","first_name":"Nishchal","id":"469E6004-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Choueiri","full_name":"Choueiri, George H","first_name":"George H","id":"448BD5BC-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Hof","full_name":"Hof, Björn","orcid":"0000-0003-2057-2754","id":"3A374330-F248-11E8-B48F-1D18A9856A87","first_name":"Björn"}],"article_processing_charge":"No","external_id":{"arxiv":["1809.06358"],"isi":["000461922000006"]}},{"project":[{"_id":"251EE76E-B435-11E9-9278-68D0E5697425","name":"Design principles underlying genetic switch architecture (DOC Fellowship)","grant_number":"24573"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Igler, Claudia. “On the Nature of Gene Regulatory Design - The Biophysics of Transcription Factor Binding Shapes Gene Regulation.” Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6371.","ista":"Igler C. 2019. On the nature of gene regulatory design - The biophysics of transcription factor binding shapes gene regulation. Institute of Science and Technology Austria.","mla":"Igler, Claudia. On the Nature of Gene Regulatory Design - The Biophysics of Transcription Factor Binding Shapes Gene Regulation. Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6371.","ama":"Igler C. On the nature of gene regulatory design - The biophysics of transcription factor binding shapes gene regulation. 2019. doi:10.15479/AT:ISTA:6371","apa":"Igler, C. (2019). On the nature of gene regulatory design - The biophysics of transcription factor binding shapes gene regulation. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6371","ieee":"C. Igler, “On the nature of gene regulatory design - The biophysics of transcription factor binding shapes gene regulation,” Institute of Science and Technology Austria, 2019.","short":"C. Igler, On the Nature of Gene Regulatory Design - The Biophysics of Transcription Factor Binding Shapes Gene Regulation, Institute of Science and Technology Austria, 2019."},"title":"On the nature of gene regulatory design - The biophysics of transcription factor binding shapes gene regulation","article_processing_charge":"No","author":[{"full_name":"Igler, Claudia","last_name":"Igler","first_name":"Claudia","id":"46613666-F248-11E8-B48F-1D18A9856A87"}],"oa":1,"publisher":"Institute of Science and Technology Austria","day":"03","year":"2019","has_accepted_license":"1","date_created":"2019-05-03T11:55:51Z","doi":"10.15479/AT:ISTA:6371","date_published":"2019-05-03T00:00:00Z","page":"152","_id":"6371","keyword":["gene regulation","biophysics","transcription factor binding","bacteria"],"status":"public","type":"dissertation","ddc":["576","579"],"date_updated":"2024-02-21T13:45:52Z","supervisor":[{"first_name":"Calin C","id":"47F8433E-F248-11E8-B48F-1D18A9856A87","last_name":"Guet","full_name":"Guet, Calin C","orcid":"0000-0001-6220-2052"}],"file_date_updated":"2021-02-11T11:17:13Z","department":[{"_id":"CaGu"}],"oa_version":"Published Version","abstract":[{"text":"Decades of studies have revealed the mechanisms of gene regulation in molecular detail. We make use of such well-described regulatory systems to explore how the molecular mechanisms of protein-protein and protein-DNA interactions shape the dynamics and evolution of gene regulation. \r\n\r\ni) We uncover how the biophysics of protein-DNA binding determines the potential of regulatory networks to evolve and adapt, which can be captured using a simple mathematical model. \r\nii) The evolution of regulatory connections can lead to a significant amount of crosstalk between binding proteins. We explore the effect of crosstalk on gene expression from a target promoter, which seems to be modulated through binding competition at non-specific DNA sites. \r\niii) We investigate how the very same biophysical characteristics as in i) can generate significant fitness costs for cells through global crosstalk, meaning non-specific DNA binding across the genomic background. \r\niv) Binding competition between proteins at a target promoter is a prevailing regulatory feature due to the prevalence of co-regulation at bacterial promoters. However, the dynamics of these systems are not always straightforward to determine even if the molecular mechanisms of regulation are known. A detailed model of the biophysical interactions reveals that interference between the regulatory proteins can constitute a new, generic form of system memory that records the history of the input signals at the promoter. \r\n\r\nWe demonstrate how the biophysics of protein-DNA binding can be harnessed to investigate the principles that shape and ultimately limit cellular gene regulation. These results provide a basis for studies of higher-level functionality, which arises from the underlying regulation. \r\n","lang":"eng"}],"month":"05","alternative_title":["ISTA Thesis"],"language":[{"iso":"eng"}],"file":[{"creator":"cigler","file_size":12597663,"date_updated":"2021-02-11T11:17:13Z","file_name":"IglerClaudia_OntheNatureofGeneRegulatoryDesign.pdf","date_created":"2019-05-03T11:54:52Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","embargo":"2020-05-02","file_id":"6373","checksum":"c0085d47c58c9cbcab1b0a783480f6da"},{"embargo_to":"open_access","content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document","relation":"source_file","access_level":"closed","file_id":"6374","checksum":"2eac954de1c8bbf7e6fb35ed0221ae8c","file_size":34644426,"date_updated":"2020-07-14T12:47:28Z","creator":"cigler","file_name":"IglerClaudia_OntheNatureofGeneRegulatoryDesign.docx","date_created":"2019-05-03T11:54:54Z"}],"degree_awarded":"PhD","publication_status":"published","publication_identifier":{"issn":["2663-337X"]},"related_material":{"record":[{"status":"public","id":"67","relation":"part_of_dissertation"},{"relation":"popular_science","status":"public","id":"5585"}]}},{"oa_version":"Published Version","abstract":[{"text":"In this paper, we evaluate clock signals generated in ring oscillators and self-timed rings and the way their jitter can be transformed into random numbers. We show that counting the periods of the jittery clock signal produces random numbers of significantly better quality than the methods in which the jittery signal is simply sampled (the case in almost all current methods). Moreover, we use the counter values to characterize and continuously monitor the source of randomness. However, instead of using the widely used statistical variance, we propose to use Allan variance to do so. There are two main advantages: Allan variance is insensitive to low frequency noises such as flicker noise that are known to be autocorrelated and significantly less circuitry is required for its computation than that used to compute commonly used variance. We also show that it is essential to use a differential principle of randomness extraction from the jitter based on the use of two identical oscillators to avoid autocorrelations originating from external and internal global jitter sources and that this fact is valid for both kinds of rings. Last but not least, we propose a method of statistical testing based on high order Markov model to show the reduced dependencies when the proposed randomness extraction is applied.","lang":"eng"}],"month":"01","intvolume":" 2018","scopus_import":"1","file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"file_id":"10289","checksum":"b816b848f046c48a8357700d9305dce5","creator":"cchlebak","file_size":955755,"date_updated":"2021-11-15T10:27:29Z","file_name":"2018_IACR_Allini.pdf","date_created":"2021-11-15T10:27:29Z"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["2569-2925"]},"publication_status":"published","volume":2018,"issue":"3","_id":"10286","status":"public","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["000"],"date_updated":"2021-11-15T10:48:49Z","department":[{"_id":"KrPi"}],"file_date_updated":"2021-11-15T10:27:29Z","publisher":"International Association for Cryptologic Research","quality_controlled":"1","oa":1,"day":"01","publication":"IACR Transactions on Cryptographic Hardware and Embedded Systems","has_accepted_license":"1","year":"2018","doi":"10.13154/tches.v2018.i3.214-242","date_published":"2018-01-01T00:00:00Z","date_created":"2021-11-14T23:01:25Z","page":"214-242","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"mla":"Allini, Elie Noumon, et al. “Evaluation and Monitoring of Free Running Oscillators Serving as Source of Randomness.” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, no. 3, International Association for Cryptologic Research, 2018, pp. 214–42, doi:10.13154/tches.v2018.i3.214-242.","apa":"Allini, E. N., Skórski, M., Petura, O., Bernard, F., Laban, M., & Fischer, V. (2018). Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. International Association for Cryptologic Research. https://doi.org/10.13154/tches.v2018.i3.214-242","ama":"Allini EN, Skórski M, Petura O, Bernard F, Laban M, Fischer V. Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2018;2018(3):214-242. doi:10.13154/tches.v2018.i3.214-242","ieee":"E. N. Allini, M. Skórski, O. Petura, F. Bernard, M. Laban, and V. Fischer, “Evaluation and monitoring of free running oscillators serving as source of randomness,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2018, no. 3. International Association for Cryptologic Research, pp. 214–242, 2018.","short":"E.N. Allini, M. Skórski, O. Petura, F. Bernard, M. Laban, V. Fischer, IACR Transactions on Cryptographic Hardware and Embedded Systems 2018 (2018) 214–242.","chicago":"Allini, Elie Noumon, Maciej Skórski, Oto Petura, Florent Bernard, Marek Laban, and Viktor Fischer. “Evaluation and Monitoring of Free Running Oscillators Serving as Source of Randomness.” IACR Transactions on Cryptographic Hardware and Embedded Systems. International Association for Cryptologic Research, 2018. https://doi.org/10.13154/tches.v2018.i3.214-242.","ista":"Allini EN, Skórski M, Petura O, Bernard F, Laban M, Fischer V. 2018. Evaluation and monitoring of free running oscillators serving as source of randomness. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2018(3), 214–242."},"title":"Evaluation and monitoring of free running oscillators serving as source of randomness","author":[{"first_name":"Elie Noumon","full_name":"Allini, Elie Noumon","last_name":"Allini"},{"first_name":"Maciej","id":"EC09FA6A-02D0-11E9-8223-86B7C91467DD","full_name":"Skórski, Maciej","last_name":"Skórski"},{"full_name":"Petura, Oto","last_name":"Petura","first_name":"Oto"},{"first_name":"Florent","last_name":"Bernard","full_name":"Bernard, Florent"},{"full_name":"Laban, Marek","last_name":"Laban","first_name":"Marek"},{"last_name":"Fischer","full_name":"Fischer, Viktor","first_name":"Viktor"}],"article_processing_charge":"No"},{"project":[{"name":"Game Theory","grant_number":"S11407","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"}],"user_id":"72615eeb-f1f3-11ec-aa25-d4573ddc34fd","citation":{"chicago":"Chatterjee, Krishnendu, Wolfgang Dvořák, Monika H Henzinger, and Alexander Svozil. “Quasipolynomial Set-Based Symbolic Algorithms for Parity Games.” In 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, 57:233–53. EasyChair, 2018. https://doi.org/10.29007/5z5k.","ista":"Chatterjee K, Dvořák W, Henzinger MH, Svozil A. 2018. Quasipolynomial set-based symbolic algorithms for parity games. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. LPAR: Conference on Logic for Programming, Artificial Intelligence and Reasoning, EPiC Series in Computing, vol. 57, 233–253.","mla":"Chatterjee, Krishnendu, et al. “Quasipolynomial Set-Based Symbolic Algorithms for Parity Games.” 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, vol. 57, EasyChair, 2018, pp. 233–53, doi:10.29007/5z5k.","apa":"Chatterjee, K., Dvořák, W., Henzinger, M. H., & Svozil, A. (2018). Quasipolynomial set-based symbolic algorithms for parity games. In 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning (Vol. 57, pp. 233–253). Awassa, Ethiopia: EasyChair. https://doi.org/10.29007/5z5k","ama":"Chatterjee K, Dvořák W, Henzinger MH, Svozil A. Quasipolynomial set-based symbolic algorithms for parity games. In: 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. Vol 57. EasyChair; 2018:233-253. doi:10.29007/5z5k","short":"K. Chatterjee, W. Dvořák, M.H. Henzinger, A. Svozil, in:, 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, EasyChair, 2018, pp. 233–253.","ieee":"K. Chatterjee, W. Dvořák, M. H. Henzinger, and A. Svozil, “Quasipolynomial set-based symbolic algorithms for parity games,” in 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, Awassa, Ethiopia, 2018, vol. 57, pp. 233–253."},"title":"Quasipolynomial set-based symbolic algorithms for parity games","article_processing_charge":"No","external_id":{"arxiv":["1909.04983"]},"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"full_name":"Dvořák, Wolfgang","last_name":"Dvořák","first_name":"Wolfgang"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"full_name":"Svozil, Alexander","last_name":"Svozil","first_name":"Alexander"}],"acknowledgement":"A. S. is fully supported by the Vienna Science and Technology Fund (WWTF) through project ICT15-003. K.C. is supported by the Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE) and an ERC Starting grant (279307: Graph Games). For M.H the research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) /ERC Grant Agreement no. 340506.","oa":1,"publisher":"EasyChair","quality_controlled":"1","publication":"22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning","day":"23","year":"2018","has_accepted_license":"1","date_created":"2022-03-18T12:46:32Z","date_published":"2018-10-23T00:00:00Z","doi":"10.29007/5z5k","page":"233-253","_id":"10883","status":"public","conference":{"name":"LPAR: Conference on Logic for Programming, Artificial Intelligence and Reasoning","start_date":"2018-11-17","location":"Awassa, Ethiopia","end_date":"2018-11-21"},"type":"conference","ddc":["000"],"date_updated":"2022-07-29T09:24:31Z","department":[{"_id":"KrCh"}],"file_date_updated":"2022-05-17T07:51:08Z","oa_version":"Published Version","abstract":[{"text":"Solving parity games, which are equivalent to modal μ-calculus model checking, is a central algorithmic problem in formal methods, with applications in reactive synthesis, program repair, verification of branching-time properties, etc. Besides the standard compu- tation model with the explicit representation of games, another important theoretical model of computation is that of set-based symbolic algorithms. Set-based symbolic algorithms use basic set operations and one-step predecessor operations on the implicit description of games, rather than the explicit representation. The significance of symbolic algorithms is that they provide scalable algorithms for large finite-state systems, as well as for infinite-state systems with finite quotient. Consider parity games on graphs with n vertices and parity conditions with d priorities. While there is a rich literature of explicit algorithms for parity games, the main results for set-based symbolic algorithms are as follows: (a) the basic algorithm that requires O(nd) symbolic operations and O(d) symbolic space; and (b) an improved algorithm that requires O(nd/3+1) symbolic operations and O(n) symbolic space. In this work, our contributions are as follows: (1) We present a black-box set-based symbolic algorithm based on the explicit progress measure algorithm. Two important consequences of our algorithm are as follows: (a) a set-based symbolic algorithm for parity games that requires quasi-polynomially many symbolic operations and O(n) symbolic space; and (b) any future improvement in progress measure based explicit algorithms immediately imply an efficiency improvement in our set-based symbolic algorithm for parity games. (2) We present a set-based symbolic algorithm that requires quasi-polynomially many symbolic operations and O(d · log n) symbolic space. Moreover, for the important special case of d ≤ log n, our algorithm requires only polynomially many symbolic operations and poly-logarithmic symbolic space.","lang":"eng"}],"intvolume":" 57","month":"10","alternative_title":["EPiC Series in Computing"],"scopus_import":"1","language":[{"iso":"eng"}],"file":[{"creator":"dernst","date_updated":"2022-05-17T07:51:08Z","file_size":720893,"date_created":"2022-05-17T07:51:08Z","file_name":"2018_EPiCs_Chatterjee.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"11392","checksum":"1229aa8640bd6db610c85decf2265480","success":1}],"publication_status":"published","publication_identifier":{"issn":["2398-7340"]},"ec_funded":1,"volume":57}]