Presentation | 2022-10-25 Active Learning for Deterministic Bottom-up Nominal Tree Automata Rindo Nakanishi, Yoshiaki Takata, Hiroyuki Seki, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Nominal set plays a central role in a group-theoretic extension of finite automata to those over an infinite set of data values. Moerman et al. proposed an active learning algorithm for nominal word automata with the equality symmetry. In this paper, we introduce deterministic bottom-up nominal tree automata (DBNTA), which operate on trees whose nodes are labelled with elements of an orbit finite nominal set. We then prove a Myhill-Nerode theorem for the class of languages recognized by DBNTA and propose an active learning algorithm for DBNTA. The algorithm can deal with any data symmetry that admits least support, not restricted to the equality symmetry and/or the total order symmetry. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | nominal tree automata / active learning / Myhill-Nerode theorem |
Paper # | SS2022-24,DC2022-30 |
Date of Issue | 2022-10-18 (SS, DC) |
Conference Information | |
Committee | DC / SS |
---|---|
Conference Date | 2022/10/25(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Tatsuhiro Tsuchiya(Osaka Univ.) / Kozo Okano(Shinshu Univ.) |
Vice Chair | Toshinori Hosokawa(Nihon Univ.) / Yoshiki Higo(Osaka Univ.) |
Secretary | Toshinori Hosokawa(Nihon Univ.) / Yoshiki Higo(Chiba Univ.) |
Assistant | / Shinsuke Matsumoto(Osaka Univ.) |
Paper Information | |
Registration To | Technical Committee on Dependable Computing / Technical Committee on Software Science |
---|---|
Language | ENG-JTITLE |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Active Learning for Deterministic Bottom-up Nominal Tree Automata |
Sub Title (in English) | |
Keyword(1) | nominal tree automata |
Keyword(2) | active learning |
Keyword(3) | Myhill-Nerode theorem |
1st Author's Name | Rindo Nakanishi |
1st Author's Affiliation | Nagoya University(Nagoya Univ.) |
2nd Author's Name | Yoshiaki Takata |
2nd Author's Affiliation | Kochi University of Technology(KUT) |
3rd Author's Name | Hiroyuki Seki |
3rd Author's Affiliation | Nagoya University(Nagoya Univ.) |
Date | 2022-10-25 |
Paper # | SS2022-24,DC2022-30 |
Volume (vol) | vol.122 |
Number (no) | SS-225,DC-226 |
Page | pp.pp.16-21(SS), pp.16-21(DC), |
#Pages | 6 |
Date of Issue | 2022-10-18 (SS, DC) |