固定性の数値述語を持つ語上の一次論理の存在フラグメントに対する双対性【JST・京大機械翻訳】

Zaiedi Mehdi

プレプリント

J-GLOBAL ID：202202216329024102 整理番号：22P0023109

固定性の数値述語を持つ語上の一次論理の存在フラグメントに対する双対性【JST・京大機械翻訳】

Duality for the existential fragment of first-order logic on words with numerical predicates of a fixed arity

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

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

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

本論文は,理論的コンピュータ科学に現れる問題に対するトポロジー双対性法の適用を調査する研究領域に適合する。このアプローチの最終的な目標の一つは,それらを特徴付ける適切なトポロジーオブジェクトを研究することによって,計算量理論における結果を導くことである。これら2つの一見分離場に関連するリンクは論理であり,単語上の論理として知られる有限モデル理論のサブドメインである。それは,有限アルファベット上で,おそらく非正規の言語のある種のファミリーとしての計算量クラスの記述を可能にする。規則言語の範囲外にある単語に関する一次論理のフラグメントに関連する双対性理論について,非常に少数しか知られていない。本研究の貢献は,そのようなフラグメントの詳細な研究である。整数k≧1を固定し,Boole代数BΣ_1[N ̄u_k]を考察した。それは,ほとんどのk存在性量子化器,文字述語,および希少性l∈{1,k}の均一数値述語のブロックを用いて定義される文章のBoolean組合せから成る単語上の論理の断片に対応する。任意のk≧1に対して,このBoole代数の二重空間の詳細な研究を行い,その点のいくつかの特性化を提供した。k=1の場合,Boole代数BΣ_1[N ̄u_1]を特徴付ける超フィルタ方程式のファミリーを構築することができる。トポロジー法を用いて,これらの方程式が音であり,著者らが言及したBoole代数に関して完全であることを証明した。【JST・京大機械翻訳】

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

論理代数 , 計算理論 , 場の理論一般 , 情報加工一般

, , , , , ,

前のページに戻る