IEICE TRANSACTIONS on Information
Generalized Register Context-Free Grammars
Summary :
Register context-free grammars (RCFG) is an extension of context-free grammars to handle data values in a restricted way. In RCFG, a certain number of data values in registers are associated with each nonterminal symbol and a production rule has the guard condition, which checks the equality between the content of a register and an input data value. This paper starts with RCFG and introduces register type, which is a finite representation of a relation among the contents of registers. By using register type, the paper provides a translation of RCFG to a normal form and ϵ-removal from a given RCFG. We then define a generalized RCFG (GRCFG) where an arbitrary binary relation can be specified in the guard condition. Since the membership and emptiness problems are shown to be undecidable in general, we extend register type for GRCFG and introduce two properties of GRCFG, simulation and progress, which guarantee the decidability of these problems. As a corollary, these problems are shown to be EXPTIME-complete for GRCFG with a total order over a dense set.
- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.540-548
- Publication Date
- 2020/03/01
- Publicized
- 2019/11/21
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2019FCP0010
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
- Category
Authors
Ryoma SENDA
Nagoya University
Yoshiaki TAKATA
Kochi University of Technology
Hiroyuki SEKI
Nagoya University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ryoma SENDA, Yoshiaki TAKATA, Hiroyuki SEKI, "Generalized Register Context-Free Grammars" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 3, pp. 540-548, March 2020, doi: 10.1587/transinf.2019FCP0010.
Abstract: Register context-free grammars (RCFG) is an extension of context-free grammars to handle data values in a restricted way. In RCFG, a certain number of data values in registers are associated with each nonterminal symbol and a production rule has the guard condition, which checks the equality between the content of a register and an input data value. This paper starts with RCFG and introduces register type, which is a finite representation of a relation among the contents of registers. By using register type, the paper provides a translation of RCFG to a normal form and ϵ-removal from a given RCFG. We then define a generalized RCFG (GRCFG) where an arbitrary binary relation can be specified in the guard condition. Since the membership and emptiness problems are shown to be undecidable in general, we extend register type for GRCFG and introduce two properties of GRCFG, simulation and progress, which guarantee the decidability of these problems. As a corollary, these problems are shown to be EXPTIME-complete for GRCFG with a total order over a dense set.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019FCP0010/_p
Copy
@ARTICLE{e103-d_3_540,
author={Ryoma SENDA, Yoshiaki TAKATA, Hiroyuki SEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Generalized Register Context-Free Grammars},
year={2020},
volume={E103-D},
number={3},
pages={540-548},
abstract={Register context-free grammars (RCFG) is an extension of context-free grammars to handle data values in a restricted way. In RCFG, a certain number of data values in registers are associated with each nonterminal symbol and a production rule has the guard condition, which checks the equality between the content of a register and an input data value. This paper starts with RCFG and introduces register type, which is a finite representation of a relation among the contents of registers. By using register type, the paper provides a translation of RCFG to a normal form and ϵ-removal from a given RCFG. We then define a generalized RCFG (GRCFG) where an arbitrary binary relation can be specified in the guard condition. Since the membership and emptiness problems are shown to be undecidable in general, we extend register type for GRCFG and introduce two properties of GRCFG, simulation and progress, which guarantee the decidability of these problems. As a corollary, these problems are shown to be EXPTIME-complete for GRCFG with a total order over a dense set.},
keywords={},
doi={10.1587/transinf.2019FCP0010},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Generalized Register Context-Free Grammars
T2 - IEICE TRANSACTIONS on Information
SP - 540
EP - 548
AU - Ryoma SENDA
AU - Yoshiaki TAKATA
AU - Hiroyuki SEKI
PY - 2020
DO - 10.1587/transinf.2019FCP0010
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2020
AB - Register context-free grammars (RCFG) is an extension of context-free grammars to handle data values in a restricted way. In RCFG, a certain number of data values in registers are associated with each nonterminal symbol and a production rule has the guard condition, which checks the equality between the content of a register and an input data value. This paper starts with RCFG and introduces register type, which is a finite representation of a relation among the contents of registers. By using register type, the paper provides a translation of RCFG to a normal form and ϵ-removal from a given RCFG. We then define a generalized RCFG (GRCFG) where an arbitrary binary relation can be specified in the guard condition. Since the membership and emptiness problems are shown to be undecidable in general, we extend register type for GRCFG and introduce two properties of GRCFG, simulation and progress, which guarantee the decidability of these problems. As a corollary, these problems are shown to be EXPTIME-complete for GRCFG with a total order over a dense set.
ER -
English
