グラフと線形順序づけにおける符号化【JST・京大機械翻訳】

Knight Julia; Soskova Alexandra; Vatev Stefan

プレプリント

J-GLOBAL ID：202202203336741320 整理番号：22P0058087

グラフと線形順序づけにおける符号化【JST・京大機械翻訳】

Coding in graphs and linear orderings

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2019年03月16日プレプリントサーバーでの情報更新日： 2020年01月20日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

無向グラフにおける有向グラフAのTuring計算可能埋込みΦがある。さらに,均一解釈を与える公式の固定タプルがある。すなわち,すべての有向グラフAに対して,これらの式はΦ(G)におけるAを解釈する。それは,Aが,Φ(A)に均一に還元されるMedvedevであった。すなわち,すべてのAに働く固定Turing演算子がある。任意の線形秩序に対してMedvedevが縮小しないグラフGが存在することを観測した。したがって,Gはいかなる線形秩序においても効果的に解釈されない。同様に,計算可能なΣ_2式を用いて線形秩序で解釈されないグラフが存在する。任意のグラフは計算可能なΣ_3式を用いて線形秩序化で解釈できる。FriedmanとStanleyは線形順序付けにおいて有向グラフのTuring計算可能埋込みLを与えた。L_ω_1,ω公式の固定タプルがなく,全てのGに対して,出力線形秩序化L(G)における入力グラフGを解釈することを示した。また,Harrison-TrainorとMontalb’anは,全く異なる証明によって,これも示した。【JST・京大機械翻訳】

, , , ,
, 【Automatic Indexing@JST】

一般相対論及び重力理論 , オートマトン理論 , その他のシステム・制御理論 , 液体クロマトグラフィー , 計算理論

, , ,

前のページに戻る