文献

J-GLOBAL ID：202002233389037337   整理番号：20A1203719

分散オートマトンのためのEmptiness問題【JST・京大機械翻訳】

Emptiness problems for distributed automata

著者 (3件)： Kuusisto Antti (Mathematics and Statistics, University of Helsinki, Finland) ,  Kuusisto Antti (Mathematics in the Unit of Computing Sciences, Tampere University, Finland) ,  Reiter Fabian (LIGM, Universite Paris-Est Marne-la-Vallee, France)
資料名： Information and Computation  (Information and Computation)
巻： 272  ページ： Null  発行年： 2020年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 分散オートマトンの3つのクラスに対するエンプティネス問題の決定可能性を調べた。これらのデバイスは,同期ラウンドの無限シーケンスで通信する同一の有限状態機械のネットワークとして作用する有限有向グラフ上で動作する。この問題は,ノードがそれらの近傍から受信されたメッセージを見るが,それら自身の状態を再構成できないような,あるクラスの偽造オートマトンに対するLogSpaceにおいて決定可能であることを示した。グラフの適切なファミリーに制限されると,これらの偽造オートマトンは古典的な有限単語オートマトンと等価であるが,有限ツリーオートマトンよりも厳密に表現性が高い。一方,一般的に,エンプティネス問題は決定できないことを示した。これは,分散オートマトンの2つの厳しく制限されたクラスに対して既に保持されている。それらは,それらがラウンド当たり1つ以上のメッセージを受け取ると直ちに拒否し,その状態図が自己ループを除いて非巡回である必要がある。さらに,計算の異なるモデルのシミュレーションにおける分散オートマトンの柔軟性を実証するために,著者らは正確に同じ計算力を有するオートマトンのクラスを同定することによって制約充足問題の特性化を提供した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 状態図 ,  *オートマトン ,  ネットワーク ,  有向グラフ ,  有限オートマトン ,  有限状態機械 ,  木オートマトン ,  柔軟性 ,  再構成 ,  分散処理 ,  キャラクタリゼーション ,  単語 ,  制約充足問題
準シソーラス用語： 決定可能性 ,  表現力 , 【Automatic Indexing@JST】

著者キーワード (3件)： 有限オートマトン ,  分散コンピューティング ,  Emptiness問題

分類 (1件)： オートマトン理論  (JB04000O)

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