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)