文献

J-GLOBAL ID：201802214732121235   整理番号：18A2060426

無限語,多項式および原子の次数【JST・京大機械翻訳】

Degrees of Infinite Words, Polynomials and Atoms

著者 (5件)： Endrullis Jorg (Department of Computer Science, Vrije Universiteit Amsterdam, Amsterdam, the Netherlands) ,  Karhumaeki Juhani (Department of Mathematics and Statistics & FUNDIM, University of Turku, Turku, Finland) ,  Klop Jan Willem (Department of Computer Science, Vrije Universiteit Amsterdam, Amsterdam, the Netherlands) ,  Klop Jan Willem (Centrum Wiskunde & Informatica (CWI), Amsterdam, the Netherlands) ,  Saarela Aleksi (Department of Mathematics and Statistics & FUNDIM, University of Turku, Turku, Finland)
資料名： International Journal of Foundations of Computer Science  (International Journal of Foundations of Computer Science)
巻： 29  号： 5  ページ： 825-843  発行年： 2018年 
JST資料番号： W0409A  ISSN： 0129-0541  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 無限単語を変換するための有限状態変換器とそれらのパワーを研究した。記号の無限シーケンスは,形式言語から純粋な数学と物理への広範囲の分野で最も重要である。認識と変換言語のための有限オートマトンはよく理解されているが,無限語を変換するためのオートマトンのパワーについてはほとんど知られていない。有限状態変換器により実現された単語変換は,単語の複雑性比較をもたらし,それにより,(変換器)度と呼ばれる等価クラス,およびこれらの程度に対する部分次数を誘導する。次のような程度の階層は,非可解性の再帰理論的程度に類似しており,また,変換装置がTuring機械であるTuring度として知られている。しかしながら,複雑さ測度として,チューリング機械はあまりにも強い。それらはすべての計算可能な単語を同定することによって分類問題を三倍化する。有限状態変換器により,より細粒化された階層を識別することができる。Turing度とは対照的に,それらの自然性にもかかわらず,変換器の程度についてはほとんど知られていない。線形代数と解析からの方法を用いて,変換器の程度に無限に多くの原子が存在することを示した。Copyright 2018 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 線形代数 ,  変換器 ,  オートマトン ,  有限オートマトン ,  単語 ,  計算 ,  形式言語 ,  *多項式 ,  有限状態機械 ,  言語 ,  Turing機械 ,  測度
準シソーラス用語： 自然性 ,  複雑性 ,  *次数 , 【Automatic Indexing@JST】

著者キーワード (3件)： 無限語 ,  有限状態変換器 ,  無限語の次数

分類 (2件)： オートマトン理論  (JB04000O) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 無限 ,  多項式 ,  原子 ,  次数