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
레지스터 오토마톤(RA), 레지스터 컨텍스트 자유 문법(RCFG) 및 레지스터 트리 오토마톤(RTA)은 데이터 값을 처리하는 레지스터를 갖춘 계산 모델입니다. 이 논문은 RA, RCFG, RTA로 표현된 언어 클래스에 대한 펌핑 기본형을 보여줍니다. 그 중 첫 번째 보조정리는 RA를 추상화한 명목형 오토마타(Nominal Automata) 측면에서 이미 증명되었다. 우리는 결정론적이고 상향식 방식으로 RTA를 정의합니다. 이러한 언어의 경우 펌핑된 하위 단어가 항상 원래 하위 단어와 동일하지는 않지만 본 논문에 정의된 데이터 유형 측면에서 원래 하위 단어와 동등한 모든 단어가 되도록 '펌프된 단어' 개념을 완화해야 합니다. . 기본형을 사용하여 위에서 언급한 언어 클래스에 속하지 않는 언어의 예를 제공합니다.
Rindo NAKANISHI
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.
부
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
부
@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},}
부
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 -