Presentation | 2018-01-18 Computational Complexity of Membership and Emptiness Problems for Register Context-Free Grammars Ryoma Senda, Hiroyuki Seki, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Register context-free grammar (RCFG) is an extension of context-free grammar to handle data values. RCFGs can be applied to designing query languages for structured documents with data values. This paper investigates the computational complexity of the membership and emptiness problems for RCFGs, and shows that the both problems for RCFGs are EXPTIME-complete and the membership problem for RCFGs without ε-rules is PSPACE-complete. We also show the complexity of those problems for some other subclasses of RCFGs. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Context-free Grammar / Register Context-Free Grammar / Computational Complexity |
Paper # | MSS2017-54,SS2017-41 |
Date of Issue | 2018-01-11 (MSS, SS) |
Conference Information | |
Committee | SS / MSS |
---|---|
Conference Date | 2018/1/18(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Kazuhiro Ogata(JAIST) / Morikazu Nakamura(Univ. of Ryukyus) |
Vice Chair | Akio Nakata(Hiroshima City Univ.) / Shigemasa Takai(Osaka Univ.) |
Secretary | Akio Nakata(Tokyo Inst. of Tech.) / Shigemasa Takai(Osaka Univ.) |
Assistant | Kazuyuki Shima(Hiroshima City Univ.) / Hideki Kinjo(Okinawa Univ.) |
Paper Information | |
Registration To | Technical Committee on Software Science / Technical Committee on Mathematical Systems Science and its applications |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Computational Complexity of Membership and Emptiness Problems for Register Context-Free Grammars |
Sub Title (in English) | |
Keyword(1) | Context-free Grammar |
Keyword(2) | Register Context-Free Grammar |
Keyword(3) | Computational Complexity |
1st Author's Name | Ryoma Senda |
1st Author's Affiliation | Nagoya University(Nagoya Univ.) |
2nd Author's Name | Hiroyuki Seki |
2nd Author's Affiliation | Nagoya University(Nagoya Univ.) |
Date | 2018-01-18 |
Paper # | MSS2017-54,SS2017-41 |
Volume (vol) | vol.117 |
Number (no) | MSS-380,SS-381 |
Page | pp.pp.41-46(MSS), pp.41-46(SS), |
#Pages | 6 |
Date of Issue | 2018-01-11 (MSS, SS) |