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
Registrar gramáticas livres de contexto (RCFG) é uma extensão de gramáticas livres de contexto para lidar com valores de dados de forma restrita. No RCFG, um certo número de valores de dados em registradores está associado a cada símbolo não terminal e uma regra de produção possui a condição de guarda, que verifica a igualdade entre o conteúdo de um registrador e um valor de dados de entrada. Este artigo começa com RCFG e introduz o tipo de registro, que é uma representação finita de uma relação entre o conteúdo dos registros. Ao usar o tipo de registro, o artigo fornece uma tradução de RCFG para uma forma normal e remoção de ϵ de um determinado RCFG. Definimos então um RCFG generalizado (GRCFG) onde uma relação binária arbitrária pode ser especificada na condição de guarda. Como os problemas de pertinência e de vazio se mostram indecidíveis em geral, estendemos o tipo de registro para GRCFG e introduzimos duas propriedades de GRCFG, simulação e progresso, que garantem a decidibilidade desses problemas. Como corolário, mostra-se que esses problemas são EXPTIME-completos para GRCFG com uma ordem total sobre um conjunto denso.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -