검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

Pumping Lemmas for Languages Expressed by Computational Models with Registers 레지스터를 사용하여 계산 모델로 표현된 언어에 대한 기본 정리 펌핑

Rindo NAKANISHI, Yoshiaki TAKATA, Hiroyuki SEKI

  • 조회수

    0

  • 이것을 인용

요약 :

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

발행
IEICE TRANSACTIONS on Information Vol.E106-D No.3 pp.284-293
발행일
2023/03/01
공개일
2022/10/14
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2022FCP0004
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science — Foundations of Computer Science Supporting the Information Society —)
범주

작성자

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

키워드