スパースランダム関係構造上の一次文の確率:ランダムCNF公式上の定義可能性への応用【JST・京大機械翻訳】

Larrauri Lazaro Alberto

プレプリント

J-GLOBAL ID：202202203932629715 整理番号：22P0157717

スパースランダム関係構造上の一次文の確率:ランダムCNF公式上の定義可能性への応用【JST・京大機械翻訳】

Probabilities of first order sentences on sparse random relational structures: An application to definability on random CNF formulas

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

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

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

任意の関係言語に対してLynchにより証明されたスパースランダムグラフに対する収束則を拡張した。対称性と反反射原理から成るσに対する有限関係語彙σと一次理論Tを考察した。Tを満足する有限σ構造の二項ランダムモデルを定義し,σにおける各関係を満足するタプルの期待値が線形である場合,一次特性が明確な漸近確率を持つことを示した。また,これらの限界確率は,語彙σにおける各関係Rにおけるタプルの密度を表すいくつかのパラメータに関してよく振舞うことを示した。これらの結果をランダムBoole充足可能性の問題に適用した。n変数に関するランダムk-CNF公式において,各可能なクラスユースが確率Δε_c/n ̄k ̄-1で生じ,非充足可能性を意味するk-CNF公式の1次特性は,nが無限に近づく傾向をほとんど確実にしないことを示した。【JST・京大機械翻訳】

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

システム・制御理論一般 , 計算理論 , 移動通信

, , , , ,

前のページに戻る