| 講演名 | 1998/3/24 LOGCFLのある部分クラスについて 大木 由起子, 守屋 悦郎, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 1-turn PDAでは受理できない言語でもLOG-space transducerによって変換してやると、1-turn PDAで受理できるようになるものが存在する。そのような言語のクラスをLOGLCFLと定義し、ここでは次の3つのことについて証明する: (1)metalinear CFLのクラス⊆LOGLCFL (2)DPDA(f(n))(f(n)-turn DPDAによって受理される言語のクラス)⊆DSPACE(f(n)log(n)) (3)finite-turn DPDAによって受理される言語のクラス⊆LOGLCFL.これらの結果はlog-spaceで決定性のTM上でのスタックの中身の扱い方を考えることによって求められる。 |
| 抄録(英) | Let LOGCFL denote the family of languages which are log(n)-space reducible to languages accepted by 1-turn PDA's. The results given in this paper are the following :(1)the class of metalinear CFL's⊆LOGLCFL, (2)DPDA(f(n))(the class of the languages accepted by f(n)-turn-bounded DPDA's)⊆DSPACE(f(n)log(n)), (3)the class of languages accepted by finite-turn DPDA's⊆LOGLCFL. These results are obtained by guessing or by directly simulating the stack changes of the PDA, by a log-space transducer. |
| キーワード(和) | LOGCFL / 1-turn PDA / metalinear CFL / auxiliary PDA |
| キーワード(英) | LOGCFL / 1-turn PDA / metalinear CFL / auxiliary PDA |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/3/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | LOGCFLのある部分クラスについて |
| サブタイトル（和） | |
| タイトル（英） | On a subclass of LOGCFL |
| サブタイトル（和） | |
| キーワード(1)（和/英） | LOGCFL / LOGCFL |
| キーワード(2)（和/英） | 1-turn PDA / 1-turn PDA |
| キーワード(3)（和/英） | metalinear CFL / metalinear CFL |
| キーワード(4)（和/英） | auxiliary PDA / auxiliary PDA |
| 第 1 著者 氏名（和/英） | 大木 由起子 / Yukiko OHKI |
| 第 1 著者 所属（和/英） | 早稲田大学理工学研究科数理科学専攻 Department of Mathematics, Graduate School of Science and Engineering, Waseda University |
| 第 2 著者 氏名（和/英） | 守屋 悦郎 / Etsuro MORIYA |
| 第 2 著者 所属（和/英） | 早稲田大学教育学部数学教室 Department of Mathematics, School of Education, Waseda University |
| 発表年月日 | 1998/3/24 |
| 資料番号 | |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 628 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |