[{"_id":"10602","article_type":"original","file_date_updated":"2022-01-07T07:50:31Z","doi":"10.1007/s00236-021-00412-y","year":"2022","acknowledgement":"This work is partially funded by the German Research Foundation (DFG) projects Verified Model Checkers (No. 317422601) and Statistical Unbounded Verification (No. 383882557), and the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research. It is an extended version of [21], including all proofs together with further explanations and examples. Moreover, we provide a new, more efficient construction based on (total) preorders, unifying previous optimizations. Experiments are performed with a new, performant implementation, comparing our approach to the current state of the art.","keyword":["computer networks and communications","information systems","software"],"citation":{"short":"J. Kretinsky, T. Meggendorfer, C. Waldmann, M. Weininger, Acta Informatica 59 (2022) 585–618.","ama":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. Index appearance record with preorders. <i>Acta Informatica</i>. 2022;59:585-618. doi:<a href=\"https://doi.org/10.1007/s00236-021-00412-y\">10.1007/s00236-021-00412-y</a>","ieee":"J. Kretinsky, T. Meggendorfer, C. Waldmann, and M. Weininger, “Index appearance record with preorders,” <i>Acta Informatica</i>, vol. 59. Springer Nature, pp. 585–618, 2022.","mla":"Kretinsky, Jan, et al. “Index Appearance Record with Preorders.” <i>Acta Informatica</i>, vol. 59, Springer Nature, 2022, pp. 585–618, doi:<a href=\"https://doi.org/10.1007/s00236-021-00412-y\">10.1007/s00236-021-00412-y</a>.","ista":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2022. Index appearance record with preorders. Acta Informatica. 59, 585–618.","chicago":"Kretinsky, Jan, Tobias Meggendorfer, Clara Waldmann, and Maximilian Weininger. “Index Appearance Record with Preorders.” <i>Acta Informatica</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00236-021-00412-y\">https://doi.org/10.1007/s00236-021-00412-y</a>.","apa":"Kretinsky, J., Meggendorfer, T., Waldmann, C., &#38; Weininger, M. (2022). Index appearance record with preorders. <i>Acta Informatica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00236-021-00412-y\">https://doi.org/10.1007/s00236-021-00412-y</a>"},"date_created":"2022-01-06T12:37:27Z","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"date_published":"2022-10-01T00:00:00Z","publisher":"Springer Nature","volume":59,"quality_controlled":"1","page":"585-618","department":[{"_id":"KrCh"}],"publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"abstract":[{"text":"Transforming ω-automata into parity automata is traditionally done using appearance records. We present an efficient variant of this idea, tailored to Rabin automata, and several optimizations applicable to all appearance records. We compare the methods experimentally and show that our method produces significantly smaller automata than previous approaches.","lang":"eng"}],"external_id":{"isi":["000735765500001"]},"language":[{"iso":"eng"}],"publication":"Acta Informatica","article_processing_charge":"Yes (via OA deal)","oa":1,"date_updated":"2023-08-02T13:49:28Z","title":"Index appearance record with preorders","isi":1,"has_accepted_license":"1","scopus_import":"1","intvolume":"        59","type":"journal_article","status":"public","author":[{"full_name":"Kretinsky, Jan","first_name":"Jan","orcid":"0000-0002-8122-2881","last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Meggendorfer, Tobias","first_name":"Tobias","last_name":"Meggendorfer","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165"},{"full_name":"Waldmann, Clara","first_name":"Clara","last_name":"Waldmann"},{"first_name":"Maximilian","full_name":"Weininger, Maximilian","last_name":"Weininger"}],"publication_identifier":{"eissn":["1432-0525"],"issn":["0001-5903"]},"month":"10","file":[{"file_id":"10603","checksum":"bf1c195b6aaf59e8530cf9e3a9d731f7","file_name":"2021_ActaInfor_Křetínský.pdf","success":1,"date_updated":"2022-01-07T07:50:31Z","date_created":"2022-01-07T07:50:31Z","creator":"cchlebak","content_type":"application/pdf","file_size":1066082,"access_level":"open_access","relation":"main_file"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa_version":"Published Version","day":"01"}]