文献

J-GLOBAL ID：202002225944411193   整理番号：20A1034599

トランスデューサによって定義されたデータ語関数の計算可能性について【JST・京大機械翻訳】

On Computability of Data Word Functions Defined by Transducers

著者 (4件)： Exibard Leo (Universite Libre de Bruxelles, Brussels, Belgium) ,  Exibard Leo (Aix Marseille Univ, Universite de Toulon, CNRS, LIS, Marseille, France) ,  Filiot Emmanuel (Universite Libre de Bruxelles, Brussels, Belgium) ,  Reynier Pierre-Alain (Aix Marseille Univ, Universite de Toulon, CNRS, LIS, Marseille, France)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12077  ページ： 217-236  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 本論文では,無限アルファベット(データ[数式:原文を参照]単語)上の無限単語の計算可能関数を合成する問題を検討した。計算可能性の概念は,限界において対応する無限出力を作り出すことができる無限の入力を有するTuring機械を通して定義される。レジスタを備えた非決定的変換器を用い,レジスタオートマトンを出力で拡張し,機能を特定した。このような変換器は,機能を定義しない可能性があるが,データ[数式:原文を参照]単語の一般的関係をより一般的に示し,与えられた変換器が関数を定義するかどうかを試験することがPSpace完全であることを示した。次に,いくつかのレジスタ変換器によって定義された関数を与えて,そのような関数が計算可能であるかどうかについて,それが決定可能であることを示した。既知の有限アルファベットの場合について,計算可能性と連続性がレジスタ変換器により定義された関数に対して一致することを示し,連続性を決定する方法を示した。また,それらの問題がPTimeであるサブクラスを定義した。Copyright The Author(s) 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 変換器 ,  オートマトン ,  Turing機械 ,  レジスタ ,  *計算可能性 ,  連続性 ,  単語

著者キーワード (6件)： データ語 ,  レジスタオートマトン ,  レジスタ変換器 ,  機能性 ,  連続性 ,  計算可能性

分類 (2件)： オートマトン理論  (JB04000O) ,  データベースシステム  (JD03030U)

タイトルに関連する用語 (4件)： トランスデューサ ,  定義 ,  関数 ,  計算可能性