Index appearance record with preorders

Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2021. Index appearance record with preorders. Acta Informatica.

Download
OA 2021_ActaInfor_Křetínský.pdf 1.07 MB

Journal Article | Published | English
Author
Kretinsky, JanIST Austria ; Meggendorfer, TobiasIST Austria ; Waldmann, Clara; Weininger, Maximilian
Department
Abstract
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.
Publishing Year
Date Published
2021-12-30
Journal Title
Acta Informatica
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.
ISSN
eISSN
IST-REx-ID

Cite this

Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. Index appearance record with preorders. Acta Informatica. 2021. doi:10.1007/s00236-021-00412-y
Kretinsky, J., Meggendorfer, T., Waldmann, C., & Weininger, M. (2021). Index appearance record with preorders. Acta Informatica. Springer Science and Business Media LLC. https://doi.org/10.1007/s00236-021-00412-y
Kretinsky, Jan, Tobias Meggendorfer, Clara Waldmann, and Maximilian Weininger. “Index Appearance Record with Preorders.” Acta Informatica. Springer Science and Business Media LLC, 2021. https://doi.org/10.1007/s00236-021-00412-y.
J. Kretinsky, T. Meggendorfer, C. Waldmann, and M. Weininger, “Index appearance record with preorders,” Acta Informatica. Springer Science and Business Media LLC, 2021.
Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2021. Index appearance record with preorders. Acta Informatica.
Kretinsky, Jan, et al. “Index Appearance Record with Preorders.” Acta Informatica, Springer Science and Business Media LLC, 2021, doi:10.1007/s00236-021-00412-y.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2022-01-07
MD5 Checksum
bf1c195b6aaf59e8530cf9e3a9d731f7


External material:
Shorter Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar