Generalized Register Context-Free Grammars

Ryoma SENDA  Yoshiaki TAKATA  Hiroyuki SEKI  

IEICE TRANSACTIONS on Information and Systems   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 —)
register context-free grammar,  register type,  computational complexity,  data word,  data language,  

Full Text: PDF(343.5KB)>>
Buy this Article

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.