| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2023-03-15 09:55 データ木書換え系の正則保存性 ～ 単項標準形に分解可能なクラス ～ ○坂尾優斗・関 浩之（名大）  SS2022-62 |
|
| 抄録 | （和） | 言語クラス$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 / / / / | |
| 文献情報 | 信学技報, vol. 122, no. 432, SS2022-62, pp. 91-96, 2023年3月. | |
| 資料番号 | SS2022-62 | |
| 発行日 | 2023-03-07 (SS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | SS2022-62 |
|
| 研究会情報 | |
| 研究会 | SS |
| 開催期間 | 2023-03-14 - 2023-03-15 |
| 開催地（和） | 名護市産業支援センター |
| 開催地（英） | |
| テーマ（和） | ソフトウェアサイエンスおよび一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | SS |
| 会議コード | 2023-03-SS |
| 本文の言語 | 日本語 |
| タイトル（和） | データ木書換え系の正則保存性 |
| サブタイトル（和） | 単項標準形に分解可能なクラス |
| タイトル（英） | Regularity Preservation Property of Data Tree Rewrite Systems |
| サブタイトル（英） | A Subclass Decomposable into Monadic Normal Form |
| キーワード(1)（和/英） | 正則保存性 / regularity preservation property |
| キーワード(2)（和/英） | モデル検査 / model checking |
| キーワード(3)（和/英） | レジスタ木オートマトン / register tree automaton |
| キーワード(4)（和/英） | 単項データ木書換え系 / monadic data tree rewrite system |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 坂尾 優斗 / Yuto Sakao / サカオ ユウト |
| 第1著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 関 浩之 / Hiroyuki Seki / セキ ヒロユキ |
| 第2著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2023-03-15 09:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | SS |
| 資料番号 | SS2022-62 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | no.432 |
| ページ範囲 | pp.91-96 |
| ページ数 | 6 |
| 発行日 | 2023-03-07 (SS) |
[研究会発表申込システムのトップページに戻る]