| Presentation | 2023-03-15 Regularity Preservation Property of Data Tree Rewrite Systems Yuto Sakao, Hiroyuki Seki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | regularity preservation property / model checking / register tree automaton / monadic data tree rewrite system |
| Paper # | SS2022-62 |
| Date of Issue | 2023-03-07 (SS) |
| Conference Information | |
| Committee | SS |
|---|---|
| Conference Date | 2023/3/14(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Kozo Okano(Shinshu Univ.) |
| Vice Chair | Yoshiki Higo(Osaka Univ.) |
| Secretary | Yoshiki Higo(Shinshu Univ.) |
| Assistant | Shinsuke Matsumoto(Osaka Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Software Science |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Regularity Preservation Property of Data Tree Rewrite Systems |
| Sub Title (in English) | A Subclass Decomposable into Linear Monadic Normal Form |
| Keyword(1) | regularity preservation property |
| Keyword(2) | model checking |
| Keyword(3) | register tree automaton |
| Keyword(4) | monadic data tree rewrite system |
| 1st Author's Name | Yuto Sakao |
| 1st Author's Affiliation | Nagoya University(Nagoya Univ.) |
| 2nd Author's Name | Hiroyuki Seki |
| 2nd Author's Affiliation | Nagoya University(Nagoya Univ.) |
| Date | 2023-03-15 |
| Paper # | SS2022-62 |
| Volume (vol) | vol.122 |
| Number (no) | SS-432 |
| Page | pp.pp.91-96(SS), |
| #Pages | 6 |
| Date of Issue | 2023-03-07 (SS) |