文献

J-GLOBAL ID：202202288759142513   整理番号：22A1105024

SkyはBuechiオートマトン相補性におけるエレベータオートマトンのための限界より厳しいランク限界ではない【JST・京大機械翻訳】

Sky Is Not the Limit Tighter Rank Bounds for Elevator Automata in Buechi Automata Complementation

著者 (3件)： Havlena Vojtech (Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic) ,  Lengal Ondrej (Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic) ,  Smahlikova Barbora (Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 13244  ページ： 118-136  発行年： 2022年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 著者らは,Buechiオートマトン(BA)のランクベース相補性における組合せ爆発の主原因の1つを緩和するためのいくつかの発見的方法,即ち,状態のランクに関する不必要な高い限界を提案した。第1に,大きなクラスのBA(半決定論的BAを一般化する)であるエレベータオートマトンを同定し,そこでは,しばしば,状態のランクが強く接続された成分の構造に従って有界である。エレベータオートマトンに対する限界は,サブ構造としてエレベータオートマトンを含む一般的なBAsにまたがる。第2に,著者らは,オートマトンのデータフロー解析を用いて,BA状態のランクに関する限界を精製するための2つの技術を導入した。著者らは,BA相補性のためのツールRankerの拡張として技術を実行し,それらが実際に生成された状態空間を非常に良く除去して,かなり良い結果を得て,ベンチマークの大規模集合に関して他の最先端のツールを凌ぐことを示した。Copyright The Author(s) 2022 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *オートマトン ,  分類 ,  *エレベータ ,  発見的方法 ,  集合 ,  相補性 ,  ベンチマーク ,  データフロー解析
準シソーラス用語： 状態空間 ,  決定論 ,  有界 , 【Automatic Indexing@JST】

分類 (1件)： オートマトン理論  (JB04000O)

タイトルに関連する用語 (4件)： オートマトン ,  相補性 ,  エレベータ ,  限界