A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

Generalized Register Context-Free Grammars Gramáticas livres de contexto de registro generalizado

Ryoma SENDA, Yoshiaki TAKATA, Hiroyuki SEKI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.540-548
Data de publicação
2020/03/01
Publicitada
2019/11/21
ISSN online
1745-1361
DOI
10.1587/transinf.2019FCP0010
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Categoria

autores

Ryoma SENDA
  Nagoya University
Yoshiaki TAKATA
  Kochi University of Technology
Hiroyuki SEKI
  Nagoya University

Palavra-chave