講演抄録/キーワード |
講演名 |
2013-12-21 14:55
交代回数限定の交代性文脈自由文法/言語について ○守屋悦朗(早大) COMP2013-56 |
抄録 |
(和) |
交代性文脈自由文法(ACFG)は,非終端記号を存在的非終端記号と全称的非終端記号に分け,存在的非終端記号には従来通り非決定性の生成の役割を与え,全称的非終端記号には並列生成の役割を与えたCFGである.本報告では,存在的文形式(従来型の文形式)と全称的文形式(全称的非終端記号を書き換えるプロダクションを適用する文形式)が交互に繰り返される回数を制限したACFGについて考察し,プロダクションの形に関してある種の標準形を導入し,非終端記号を消去するプロダクションの除去が多項式時間で行なえることを示した上で,ややきつめの制約を加えたACFGの構文解析を行なう多項式時間アルゴリズムを与えている.
また,交代回数による無限階層の可能性について考察している. |
(英) |
Alternating context-free grammars, in which the number of alternations between existential and universal modes is bounded in the processes of leftmost derivations (BND-ACFG), are considered.
A polynomial time algorithm to remove erasing rules from an arbitrarily given BND-ACFG is given.
Also a polynomial time algorithm is given to obtain a BND-ACFG satisfying some restrictive conditions on the form of productions as well as on a certain classification of nonterminals.
Based on these preliminary results, a polynomial time algorithm for syntax analysis of languages generated by BND-ACFGs satisfying a rather restricted condition is given.
Finally, an infinite hierarchy of languages definable by BND-ACFGs is suggested based on the number of alternations. |
キーワード |
(和) |
文脈自由文法 / 文脈自由言語 / 交代性(限定)文法 / 構文解析 / 非終端記号消去ルール / / / |
(英) |
context-free grammar / alternation / alternation bounded / syntax analysis / erasing rule / / / |
文献情報 |
信学技報, vol. 113, no. 371, COMP2013-56, pp. 107-114, 2013年12月. |
資料番号 |
COMP2013-56 |
発行日 |
2013-12-13 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-56 |