Index appearance record with preorders

被引：1
|
作者：
Kretinsky, Jan [1 ]
Meggendorfer, Tobias [2 ]
Waldmann, Clara [3 ]
Weininger, Maximilian [1 ]
机构：
[1] Tech Univ Munich, Munich, Germany
[2] IST Austria, Klosterneuburg, Austria
[3] Tech Univ Munich, Operat Res Grp, Munich, Germany
来源：
ACTA INFORMATICA | 2022年 / 59卷 / 05期
关键词：
AUTOMATA; GAMES; BUCHI;
D O I：
10.1007/s00236-021-00412-y
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Transforming omega-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.
引用
收藏
页码：585 / 618
页数：34
相关论文
共 30 条
  • [1] Index Appearance Record for Transforming Rabin Automata into Parity Automata
    Kretinsky, Jan
    Meggendorfer, Tobias
    Waldmann, Clara
    Weininger, Maximilian
    TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, TACAS 2017, PT I, 2017, 10205 : 443 - 460
  • [2] Cooking Your Own Parity Game Preorders Through Matching Plays
    Gazda, M. W.
    Willemse, T. A. C.
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2018, 29 (04) : 571 - 590
  • [3] Handgun Detection Using Combined Human Pose and Weapon Appearance
    Ruiz-Santaquiteria, Jesus
    Velasco-Mata, Alberto
    Vallez, Noelia
    Bueno, Gloria
    Alvarez-Garcia, Juan A.
    Deniz, Oscar
    IEEE ACCESS, 2021, 9 : 123815 - 123826
  • [4] Record-Keeping and Cooperation in Large Societies
    Clark, Daniel
    Fudenberg, Drew
    Wolitzky, Alexander
    REVIEW OF ECONOMIC STUDIES, 2021, 88 (05): : 2179 - 2209
  • [5] Behavioral Clustering of Non-Stationary IP Flow Record Data
    Hammerschmidt, Christian
    Marchal, Samuel
    State, Radu
    Verwer, Sicco
    2016 12TH INTERNATIONAL CONFERENCE ON NETWORK AND SERVICE MANAGEMENT AND WORKSHOPS(CNSM 2016), 2016, : 297 - 301
  • [6] The complexity of power-index comparison
    Faliszewski, Piotr
    Hemaspaandra, Lane A.
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2008, 5034 : 177 - 187
  • [7] Strong Chromatic Index of Sparse Graphs
    Yang, Daqing
    Zhu, Xuding
    JOURNAL OF GRAPH THEORY, 2016, 83 (04) : 334 - 339
  • [8] Index-wise comparative statics
    Koch, Caleb M.
    MATHEMATICAL SOCIAL SCIENCES, 2019, 102 : 35 - 41
  • [9] The complexity of power-index comparison
    Faliszewski, Piotr
    Hemaspaandra, Lane
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (01) : 101 - 107
  • [10] An axiomatic characterization of the potential decisiveness index
    Freixas, Josep
    Pons, Montserrat
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2015, 66 (03) : 353 - 359
123