---
_id: '10602'
abstract:
- lang: eng
  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.
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.
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Jan
  full_name: Kretinsky, Jan
  id: 44CEF464-F248-11E8-B48F-1D18A9856A87
  last_name: Kretinsky
  orcid: 0000-0002-8122-2881
- first_name: Tobias
  full_name: Meggendorfer, Tobias
  id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
  last_name: Meggendorfer
  orcid: 0000-0002-1712-2165
- first_name: Clara
  full_name: Waldmann, Clara
  last_name: Waldmann
- first_name: Maximilian
  full_name: Weininger, Maximilian
  last_name: Weininger
citation:
  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>
  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>
  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>.
  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.
  ista: Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2022. Index appearance
    record with preorders. Acta Informatica. 59, 585–618.
  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>.
  short: J. Kretinsky, T. Meggendorfer, C. Waldmann, M. Weininger, Acta Informatica
    59 (2022) 585–618.
date_created: 2022-01-06T12:37:27Z
date_published: 2022-10-01T00:00:00Z
date_updated: 2023-08-02T13:49:28Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/s00236-021-00412-y
external_id:
  isi:
  - '000735765500001'
file:
- access_level: open_access
  checksum: bf1c195b6aaf59e8530cf9e3a9d731f7
  content_type: application/pdf
  creator: cchlebak
  date_created: 2022-01-07T07:50:31Z
  date_updated: 2022-01-07T07:50:31Z
  file_id: '10603'
  file_name: 2021_ActaInfor_Křetínský.pdf
  file_size: 1066082
  relation: main_file
  success: 1
file_date_updated: 2022-01-07T07:50:31Z
has_accepted_license: '1'
intvolume: '        59'
isi: 1
keyword:
- computer networks and communications
- information systems
- software
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 585-618
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
  name: IST Austria Open Access Fund
publication: Acta Informatica
publication_identifier:
  eissn:
  - 1432-0525
  issn:
  - 0001-5903
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Index appearance record with preorders
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 59
year: '2022'
...