| Presentation | 2016-01-25 A method for making proof graph finite on disjunctive parameterised Boolean equation systems Yutaro Nagae, Masahiko Sakai, Hiroyuki Seki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A parameterised Boolean equation system (PBES) is a set of equations that defines sets as the least and/or greatest fixed-points that satisfy the equations. This paper studies a technique to solve the membership problem of PBESs, which is undecidable, by extending the notion of proof graphs. A vertex $X(v)$ in a proof graph represents that the data $v$ is in the set $X$, if the graph satisfies conditions induced from a given PBES. However, proof graphs are infinite in general, thus we introduce verticies each of which stands for a set of verticies of the original ones. For a subclass of disjunctive PBESs, we clarify conditions for the extended proof graphs. We also show that examples having no finite proof graph except for extended one. We further propose a method to construct a graph, called a dependency space, that contains an extended proof graph in its sub-graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | parameterised Boolean equation systemsmembership problemproof graph |
| Paper # | MSS2015-49,SS2015-58 |
| Date of Issue | 2016-01-18 (MSS, SS) |
| Conference Information | |
| Committee | SS / MSS |
|---|---|
| Conference Date | 2016/1/25(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Shiinoki-Geihin-Kan |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Shoji Yuen(Nagoya Univ.) / Satoshi Yamane(Kanazawa Univ.) |
| Vice Chair | Kazuhiro Ogata(JAIST) / Morikazu Nakamura(Univ. of Ryukyus) |
| Secretary | Kazuhiro Ogata(Tokyo Inst. of Tech.) / Morikazu Nakamura(Waseda Univ.) |
| Assistant | Yoshiki Higo(Osaka Univ.) / Hideki Kinjo(Okinawa Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Software Science / Technical Committee on Mathematical Systems Science and its applications |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A method for making proof graph finite on disjunctive parameterised Boolean equation systems |
| Sub Title (in English) | |
| Keyword(1) | parameterised Boolean equation systemsmembership problemproof graph |
| 1st Author's Name | Yutaro Nagae |
| 1st Author's Affiliation | Nagoya University(Nagoya Univ.) |
| 2nd Author's Name | Masahiko Sakai |
| 2nd Author's Affiliation | Nagoya University(Nagoya Univ.) |
| 3rd Author's Name | Hiroyuki Seki |
| 3rd Author's Affiliation | Nagoya University(Nagoya Univ.) |
| Date | 2016-01-25 |
| Paper # | MSS2015-49,SS2015-58 |
| Volume (vol) | vol.115 |
| Number (no) | MSS-419,SS-420 |
| Page | pp.pp.81-85(MSS), pp.81-85(SS), |
| #Pages | 5 |
| Date of Issue | 2016-01-18 (MSS, SS) |