The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Register context-free grammars (RCFG) est une extension des grammaires sans contexte pour gérer les valeurs de données de manière restreinte. Dans RCFG, un certain nombre de valeurs de données dans les registres sont associées à chaque symbole non terminal et une règle de production possède la condition de garde, qui vérifie l'égalité entre le contenu d'un registre et une valeur de données d'entrée. Cet article commence par RCFG et introduit le type de registre, qui est une représentation finie d'une relation entre le contenu des registres. En utilisant le type de registre, l'article fournit une traduction de RCFG en une forme normale et une suppression ϵ d'un RCFG donné. Nous définissons ensuite un RCFG généralisé (GRCFG) où une relation binaire arbitraire peut être spécifiée dans la condition de garde. Puisque les problèmes d'appartenance et de vide s'avèrent indécidables en général, nous étendons le type de registre pour GRCFG et introduisons deux propriétés de GRCFG, la simulation et le progrès, qui garantissent la décidabilité de ces problèmes. En corollaire, ces problèmes se révèlent être EXPTIME-complets pour GRCFG avec un ordre total sur un ensemble dense.
Ryoma SENDA
Nagoya University
Yoshiaki TAKATA
Kochi University of Technology
Hiroyuki SEKI
Nagoya University
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.
Copier
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
Copier
@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},}
Copier
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 -