Pumping Lemmas for Languages Expressed by Computational Models with Registers

Rindo NAKANISHI; Yoshiaki TAKATA; Hiroyuki SEKI

doi:10.1587/transinf.2022FCP0004

Pumping Lemmas for Languages Expressed by Computational Models with Registers

Rindo NAKANISHI, Yoshiaki TAKATA, Hiroyuki SEKI

Full Text Views

0

Cite this

Summary :

Register automaton (RA), register context-free grammar (RCFG) and register tree automaton (RTA) are computational models with registers which deal with data values. This paper shows pumping lemmas for the classes of languages expressed by RA, RCFG and RTA. Among them, the first lemma was already proved in terms of nominal automata, which is an abstraction of RA. We define RTA in a deterministic and bottom-up manner. For these languages, the notion of ‘pumped word’ must be relaxed in such a way that a pumped subword is not always the same as the original subword, but is any word equivalent to the original subword in terms of data type defined in this paper. By using the lemmas, we give examples of languages that do not belong to the above-mentioned classes of languages.

Publication: IEICE TRANSACTIONS on Information Vol.E106-D No.3 pp.284-293

Publication Date: 2023/03/01

Publicized: 2022/10/14

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2022FCP0004

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Foundations of Computer Science Supporting the Information Society —)

Category

Authors

Rindo NAKANISHI
  Nagoya University
Yoshiaki TAKATA
  Kochi University of Technology
Hiroyuki SEKI
  Nagoya University

Keyword

Cite this

Copy

Rindo NAKANISHI, Yoshiaki TAKATA, Hiroyuki SEKI, "Pumping Lemmas for Languages Expressed by Computational Models with Registers" in IEICE TRANSACTIONS on Information, vol. E106-D, no. 3, pp. 284-293, March 2023, doi: 10.1587/transinf.2022FCP0004.
Abstract: Register automaton (RA), register context-free grammar (RCFG) and register tree automaton (RTA) are computational models with registers which deal with data values. This paper shows pumping lemmas for the classes of languages expressed by RA, RCFG and RTA. Among them, the first lemma was already proved in terms of nominal automata, which is an abstraction of RA. We define RTA in a deterministic and bottom-up manner. For these languages, the notion of ‘pumped word’ must be relaxed in such a way that a pumped subword is not always the same as the original subword, but is any word equivalent to the original subword in terms of data type defined in this paper. By using the lemmas, we give examples of languages that do not belong to the above-mentioned classes of languages.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022FCP0004/_p

Copy

@ARTICLE{e106-d_3_284,
author={Rindo NAKANISHI, Yoshiaki TAKATA, Hiroyuki SEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Pumping Lemmas for Languages Expressed by Computational Models with Registers},
year={2023},
volume={E106-D},
number={3},
pages={284-293},
abstract={Register automaton (RA), register context-free grammar (RCFG) and register tree automaton (RTA) are computational models with registers which deal with data values. This paper shows pumping lemmas for the classes of languages expressed by RA, RCFG and RTA. Among them, the first lemma was already proved in terms of nominal automata, which is an abstraction of RA. We define RTA in a deterministic and bottom-up manner. For these languages, the notion of ‘pumped word’ must be relaxed in such a way that a pumped subword is not always the same as the original subword, but is any word equivalent to the original subword in terms of data type defined in this paper. By using the lemmas, we give examples of languages that do not belong to the above-mentioned classes of languages.},
keywords={},
doi={10.1587/transinf.2022FCP0004},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Pumping Lemmas for Languages Expressed by Computational Models with Registers
T2 - IEICE TRANSACTIONS on Information
SP - 284
EP - 293
AU - Rindo NAKANISHI
AU - Yoshiaki TAKATA
AU - Hiroyuki SEKI
PY - 2023
DO - 10.1587/transinf.2022FCP0004
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2023
AB - Register automaton (RA), register context-free grammar (RCFG) and register tree automaton (RTA) are computational models with registers which deal with data values. This paper shows pumping lemmas for the classes of languages expressed by RA, RCFG and RTA. Among them, the first lemma was already proved in terms of nominal automata, which is an abstraction of RA. We define RTA in a deterministic and bottom-up manner. For these languages, the notion of ‘pumped word’ must be relaxed in such a way that a pumped subword is not always the same as the original subword, but is any word equivalent to the original subword in terms of data type defined in this paper. By using the lemmas, we give examples of languages that do not belong to the above-mentioned classes of languages.
ER -