文献

J-GLOBAL ID：202202273649682869   整理番号：22A0903649

NFAsの構造特性と非決定性測度の成長速度【JST・京大機械翻訳】

Structural properties of NFAs and growth rates of nondeterminism measures

著者 (2件)： Keeler Chris (School of Computing, Queen’s University, Kingston, Ontario K7L 2N8, Canada) ,  Salomaa Kai (School of Computing, Queen’s University, Kingston, Ontario K7L 2N8, Canada)
資料名： Information and Computation  (Information and Computation)
巻： 284  ページ： Null  発行年： 2022年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ツリー幅(それぞれ,ストリング経路幅)は,与えられた入力における非決定論的有限オートマトン(NFA)の部分(それぞれ,完全)計算の数を測定する。NFAsの構造特性により,木幅とストリング経路幅の多項式と指数成長速度を特性化した。多項式成長速度は,大まかに言いており,サイクルをラベル付けする文字列が一定の要求条件を満たす,有界数のサイクルを通す計算が存在する。主な結果として,著者らは,NFAの木幅とストリング経路幅を結合する多項式の度合が,互いに異なることを示した。より一般的に,NFAは,もし計算が大部分のK明確なサイクルで訪問できるならば,サイクル高さKを持つと言われている。著者らは,NFAが有限サイクル高さを持ち,その最適サイクル高さを計算するために,NFAが有限サイクル高さを持つかどうかを決定する多項式時間アルゴリズムを与えた。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *測度 ,  多項式 ,  有限オートマトン ,  経路 ,  キャラクタリゼーション ,  *構造特性 ,  *成長速度 ,  文字列 ,  非決定性
準シソーラス用語： 木幅 ,  多項式時間アルゴリズム ,  有界 , 【Automatic Indexing@JST】

著者キーワード (6件)： 有限オートマトン ,  非決定性 ,  ツリー幅 ,  ストリング経路幅 ,  成長速度 ,  状態の複雑さ

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 構造特性 ,  非決定性 ,  測度 ,  成長速度