文献

J-GLOBAL ID：201902284105781525   整理番号：19A1120259

レジスタ文脈自由文法とレジスタ木オートマトンに関する複雑性結果【JST・京大機械翻訳】

Complexity Results on Register Context-Free Grammars and Register Tree Automata

著者 (3件)： Senda Ryoma (Graduate School of Information Science, Nagoya University, Nagoya, Japan) ,  Takata Yoshiaki (Graduate School of Engineering, Kochi University of Technology, Kami City, Kochi, Japan) ,  Seki Hiroyuki (Graduate School of Information Science, Nagoya University, Nagoya, Japan)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11187  ページ： 415-434  発行年： 2018年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： レジスタコンテキストフリー文法(RCFG)とレジスタツリーオートマトン(RTA)は,それぞれ文脈自由文法とツリーオートマトンの拡張であり,制限された方法でデータ値を扱う。データ値を持つXMLのような構造化文書に対する質問言語のモデルとして,RTAは注目されている。本論文は,RCFGとRTAのための基本的決定問題の計算複雑性を調査した。RCFGに対するメンバシップと経験問題はEXPTIME完全であり,RCFGのサブクラスを導入することにより複雑さがどのように減少するかを示した。RTAに対するこれらの問題の複雑さもNP完全でEXPTIME完全であることを示した。Copyright 2018 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *レジスタ ,  問い合わせ言語 ,  木オートマトン ,  船舶 ,  決定問題 ,  文脈自由文法 ,  計算量
準シソーラス用語： NP完全性 ,  *複雑性 , 【Automatic Indexing@JST】

分類 (1件)： 人工知能  (JE08000Z)

タイトルに関連する用語 (4件)： レジスタ ,  文脈自由文法 ,  木オートマトン ,  複雑性