| 講演名 | 2023-03-15 データ木書換え系の正則保存性 坂尾 優斗(名大), 関 浩之(名大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 言語クラス$mathcal{L}$上の変換$T$が正則保存性を持つとは，任意の正則な言語$L in mathcal{L}$に対して$T$を任意回適用することで得られる言語$T^*(L)$も正則となることをいう．正則保存性はシステムのモデル検査に応用することができる．本稿では，記号とデータ値の対の木構造であるデータ木を変換する系であるDTRSの部分クラスとして，単項DTRSおよびその標準形を定義する．また，データ木言語が正則であるとは，それがレジスタ木オートマトンによって認識されることであると定義する．続いて，標準形DTRSの正則保存性の証明および，単項DTRSの部分クラスである強単項DTRSから標準形への等価変換法を示す． |
| 抄録(英) | Let $T$ be a transformation over a class $mathcal{L}$ of languages. If for any regular language $L in mathcal{L}$, $T^*(L)$ obtained by applying $T$ finite times to $L$ is regular, we say that $T$ has the regularity preservation property. This property can be applied to model checking. In this paper, we first define monadic DTRS (abbreviated as m-DTRS) and its normal form. A DTRS is a finite set of rules that rewrite data trees, which are trees where a node is labeled with a pair of a symbol and a data value. A data tree language is regular if it is recognized by a register tree automaton. Next, we prove the regularity preservation property of normal form m-DTRS and provide an equivalence translation from strong m-DTRS into normal form m-DTRS. |
| キーワード(和) | 正則保存性 / モデル検査 / レジスタ木オートマトン / 単項データ木書換え系 |
| キーワード(英) | regularity preservation property / model checking / register tree automaton / monadic data tree rewrite system |
| 資料番号 | SS2022-62 |
| 発行日 | 2023-03-07 (SS) |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 2023/3/14(から2日開催) |
| 開催地（和） | 名護市産業支援センター |
| 開催地（英） | |
| テーマ（和） | ソフトウェアサイエンスおよび一般 |
| テーマ（英） | |
| 委員長氏名（和） | 岡野 浩三(信州大) |
| 委員長氏名（英） | Kozo Okano(Shinshu Univ.) |
| 副委員長氏名（和） | 肥後 芳樹(阪大) |
| 副委員長氏名（英） | Yoshiki Higo(Osaka Univ.) |
| 幹事氏名（和） | 小形 真平(信州大) / 林 晋平(東工大) |
| 幹事氏名（英） | Shinpei Ogata(Shinshu Univ.) / Shinpei Hayashi(Tokyo Inst. of Tech.) |
| 幹事補佐氏名（和） | ?本 真佑(阪大) |
| 幹事補佐氏名（英） | Shinsuke Matsumoto(Osaka Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Software Science |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | データ木書換え系の正則保存性 |
| サブタイトル（和） | 線形単項標準形に分解可能なクラス |
| タイトル（英） | Regularity Preservation Property of Data Tree Rewrite Systems |
| サブタイトル（和） | A Subclass Decomposable into Linear Monadic Normal Form |
| キーワード(1)（和/英） | 正則保存性 / regularity preservation property |
| キーワード(2)（和/英） | モデル検査 / model checking |
| キーワード(3)（和/英） | レジスタ木オートマトン / register tree automaton |
| キーワード(4)（和/英） | 単項データ木書換え系 / monadic data tree rewrite system |
| 第 1 著者 氏名（和/英） | 坂尾 優斗 / Yuto Sakao |
| 第 1 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 第 2 著者 氏名（和/英） | 関 浩之 / Hiroyuki Seki |
| 第 2 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 発表年月日 | 2023-03-15 |
| 資料番号 | SS2022-62 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | SS-432 |
| ページ範囲 | pp.91-96(SS), |
| ページ数 | 6 |
| 発行日 | 2023-03-07 (SS) |