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

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

Polynomial Time Learnability of Simple Deterministic Languages from MAT and a Representative Sample MAT와 대표 샘플을 통한 단순 결정론적 언어의 다항식 시간 학습 가능성

Yasuhiro TAJIMA, Etsuji TOMITA, Mitsuo WAKATSUKI

  • 조회수

    0

  • 이것을 인용

요약 :

질의어와 선험적 지식을 바탕으로 단순 결정론적 언어에 대한 학습 알고리즘을 제안합니다. 학습자에게는 대표 샘플이라고 불리는 목표 언어의 특수한 유한 하위 집합이 처음에 제공되며, 동등 쿼리와 멤버십 쿼리의 두 가지 유형의 쿼리가 가능합니다. 이 학습 알고리즘은 Ishizaka(1990)의 아이디어를 기반으로 가설 문법의 비단말을 구성합니다. Ishizaka(1990)의 알고리즘에서 학습자는 긍정적인 반례를 통해 가능한 한 많은 규칙을 만들고, 부정적인 반례를 통해 잘못된 규칙을 진단합니다. 이에 비해 우리의 알고리즘은 Angluin(1987)의 알고리즘을 기반으로 간단한 결정론적 문법을 추측하고 이를 긍정 및 부정 반례를 사용하여 진단합니다.

발행
IEICE TRANSACTIONS on Information Vol.E83-D No.4 pp.757-765
발행일
2000/04/25
공개일
온라인 ISSN
DOI
원고의 종류
PAPER
범주
오토마타 이론, 형식언어론

작성자

키워드