文献

J-GLOBAL ID：201402268205230216   整理番号：14A0161157

交代回数限定の交代性文脈自由文法/言語について

On alternation-bounded alternating context-free grammars and languages

著者 (1件)： MORIYA Etsuro (Waseda Univ., Tokyo, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 371(COMP2013 38-59)  ページ： 107-114  発行年： 2013年12月13日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 交代性文脈自由文法(ACFG)は,非終端記号を存在的非終端記号と全称的非終端記号に分け,存在的非終端記号には従来通り非決定性の生成の役割を与え,全称的非終端記号には並列生成の役割を与えたCFGである。本報告では,存在的文形式(従来型の文形式)と全称的文形式(全称的非終端記号を書き換えるプロダクションを適用する文形式)が交互に繰り返される回数を制限したACFGについて考察し,プロダクションの形に関してある種の標準形を導入し,非終端記号を消去するプロダクションの除去が多項式時間で行なえることを示した上で,ややきつめの制約を加えたACFGの構文解析を行なう多項式時間アルゴリズムを与えている。また,交代回数による無限階層の可能性について考察している。(著者抄録)

シソーラス用語： *文脈自由文法 ,  言語 ,  アルゴリズム ,  *構文分析
準シソーラス用語： 文脈自由言語 ,  多項式時間アルゴリズム

分類 (1件)： 数理言語学  (JB05000V)

タイトルに関連する用語 (3件)： 交代 ,  文脈自由文法 ,  言語