文献

J-GLOBAL ID：201702228898930778   整理番号：17A1497786

一定高のプッシュダウンを用いた非決定論的オートマトン上でのブール言語操作【Powered by NICT】

Boolean language operations on nondeterministic automata with a pushdown of constant height

著者 (4件)： Bednarova Zuzana (Department of Computer Science, P. J. Safarik University, Jesenna 5, 04154 Kosice, Slovakia) ,  Geffert Viliam (Department of Computer Science, P. J. Safarik University, Jesenna 5, 04154 Kosice, Slovakia) ,  Mereghetti Carlo (Dipartimento di Informatica, Universita degli Studi di Milano, via Comelico 39, 20135 Milano, Italy) ,  Palano Beatrice (Dipartimento di Informatica, Universita degli Studi di Milano, via Comelico 39, 20135 Milano, Italy)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 90  ページ： 99-114  発行年： 2017年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： プッシュダウンの大きさに限界を持つ通常のプッシュダウンオートマトン,すなわち,一定高さ非決定性プッシュダウンオートマトン上でのBoole演算のコストを調べた。交差では,指数関数的シミュレーションを示し,指数関数的爆発は,最悪ケースが必要であることを証明した。組合では,代わりに,補体のために,二重指数関数シミュレーションを示し,単一指数関数的下限を証明し,線形トレードオフを提供する。正規言語のBoole演算のための同じギャップは非制限プッシュダウンと伝統的な非決定性オートマトンのためのが示されている。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： プッシュダウンオートマトン ,  シミュレーション ,  非決定性オートマトン ,  非決定性 ,  補体 ,  *オートマトン ,  演算 ,  線形性 ,  *言語 ,  指数関数
準シソーラス用語： 正規言語 , 【Automatic Indexing@JST】

著者キーワード (4件)： 記述複雑性 ,  有限状態オートマトン ,  正規言語 ,  非決定性プッシュダウンオートマトン

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (2件)： オートマトン ,  言語