La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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 Grammaires hors contexte du registre généralisé

Ryoma SENDA, Yoshiaki TAKATA, Hiroyuki SEKI

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.540-548
Date de publication
2020/03/01
Publicisé
2019/11/21
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2019FCP0010
Type de manuscrit
Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Catégories

Auteurs

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

Mots-clés

Table des matières