縮約フリー部分構造論理におけるタワー完全問題【JST・京大機械翻訳】

Tanaka Hiromi

プレプリント

J-GLOBAL ID：202202207970005666 整理番号：22P0024733

縮約フリー部分構造論理におけるタワー完全問題【JST・京大機械翻訳】

Tower-Complete Problems in Contraction-Free Substructural Logics

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

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

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

収縮のない部分構造論理の族の非要素計算複雑性を調べた。Lazi’cとSchmitz(2015)が先駆する技術の助けにより,交換と弱体化(FL_ew)による完全Lambek計算のための脱誘導問題は,要素的ではない(即ち,基本再帰関数によって有界で決定できる決定問題のクラス)が,PR(即ち,初期再帰的関数によって有界で決定できる決定問題のクラス)にあることを示した。より正確には,この問題がTowerに対して完全であり,Schmitz(2016)により導入された高速成長複雑性階層の一部を形成する非要素複雑性クラスであることを示した。同じ複雑性結果は,BCK-論理,すなわちFL_ewの含意フラグメントにおける脱誘導性に対してさえある。さらに,Dal LagoとMartini(2004)により決定可能な,基本アフィン論理に対する確率問題のTower-完全性を示した。【JST・京大機械翻訳】

, , , , , , ,
, , 【Automatic Indexing@JST】

計算理論 , グラフ理論基礎

, ,

前のページに戻る