論文の概要: Parameterized Complexity Of Representing Models Of MSO Formulas
- arxiv url: http://arxiv.org/abs/2604.08707v1
- Date: Thu, 09 Apr 2026 18:56:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-13 17:57:53.544793
- Title: Parameterized Complexity Of Representing Models Of MSO Formulas
- Title（参考訳）: MSO式表現モデルのパラメータ化複雑性
- Authors: Petr Kučera, Petr Martinek,
- Abstract要約: モナディック二階述語論理(MSO2)は、クールセルの定理によるパラメータ化複雑性において重要な役割を果たす。
自由変数を持つ MSO2 公式のモデルは、上記のパラメータでパラメータ化線形である決定図で表せることを示す。
特に,木幅を考慮した場合の逐次決定図(SDD)サイズに対するパラメータ化線形上界と,パラメータのパス幅を考慮した場合の順序付き二分決定図(OBDD)サイズに対するパラメータ化線形上界を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Monadic second order logic (MSO2) plays an important role in parameterized complexity due to the Courcelle's theorem. This theorem states that the problem of checking if a given graph has a property specified by a given MSO2 formula can be solved by a parameterized linear time algorithm with respect to the treewidth of the graph and the size of the formula. We extend this result by showing that models of MSO2 formula with free variables can be represented with a decision diagram whose size is parameterized linear in the above mentioned parameter. In particular, we show a parameterized linear upper bound on the size of a sentential decision diagram (SDD) when treewidth is considered and a parameterized linear upper bound on the size of an ordered binary decision diagram (OBDD) when considering the pathwidth in the parameter. In addition, building on a lower bound on the size of OBDD by Razgon (2014), we show that there is an MSO2 formula and a class of graphs with bounded treewidth which do not admit an OBDD with the size parameterized by the treewidth. Our result offers a new perspective on the Courcelle's theorem and connects it to the area of knowledge representation.
- Abstract（参考訳）: モナディック二階述語論理(MSO2)は、クールセルの定理によるパラメータ化複雑性において重要な役割を果たす。
この定理は、与えられたグラフが与えられた MSO2 式で指定された性質を持つかどうかを確認する問題は、グラフのツリー幅と公式のサイズに関してパラメータ化された線形時間アルゴリズムによって解決できる、というものである。
この結果は、自由変数を持つ MSO2 公式のモデルが、上記のパラメータでパラメータ化線形である決定図で表現できることを示して拡張する。
特に,木幅を考慮した場合の逐次決定図(SDD)サイズに対するパラメータ化線形上界と,パラメータのパス幅を考慮した場合の順序付き二分決定図(OBDD)サイズに対するパラメータ化線形上界を示す。
さらに、Razgon (2014) による OBDD のサイズに基づく下界上に構築すると、MSO2 式と、木幅でパラメータ化されたサイズを持つ OBDD を含まない有界木幅グラフのクラスが存在することが分かる。
この結果はクールセルの定理に新たな視点を与え、それを知識表現の領域に結びつける。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Joint Bayesian Inference of Graphical Structure and Parameters with a
Single Generative Flow Network [59.79008107609297]
本稿では,ベイジアンネットワークの構造上の結合後部を近似する手法を提案する。
サンプリングポリシが2フェーズプロセスに従う単一のGFlowNetを使用します。
パラメータは後部分布に含まれるため、これは局所確率モデルに対してより柔軟である。
論文 参考訳（メタデータ） (2023-05-30T19:16:44Z) - Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。
いわゆる「ツリー幅」が最も顕著な構造パラメータの1つであるという観測から着想を得て,本アルゴリズムは入力インスタンスの一次グラフの小さなツリー幅を利用する。
論文 参考訳（メタデータ） (2023-05-30T17:02:07Z) - Gaussian process regression and conditional Karhunen-Lo\'{e}ve models
for data assimilation in inverse problems [68.8204255655161]
偏微分方程式モデルにおけるデータ同化とパラメータ推定のためのモデル逆アルゴリズムCKLEMAPを提案する。
CKLEMAP法は標準的なMAP法に比べてスケーラビリティがよい。
論文 参考訳（メタデータ） (2023-01-26T18:14:12Z) - Identification in Tree-shaped Linear Structural Causal Models [4.751074059099236]
そこで本研究では,有向成分が木を形成するモデルについて検討し,二方向エッジの欠落サイクルがモデル同定に有効であることを示す。
複数の欠落したサイクルが組み合わさってユニークな解が得られることを示す。
論文 参考訳（メタデータ） (2022-03-03T16:59:49Z) - Generalising Recursive Neural Models by Tensor Decomposition [12.069862650316262]
テンソル型定式化を利用した構造文脈のモデルアグリゲーションに対する一般的なアプローチを提案する。
パラメータ空間の大きさの指数関数的成長は、タッカー分解に基づく近似によって制御できることを示す。
これにより、隠れたサイズ、計算複雑性、モデル一般化によって制御される符号化の表現性の間のトレードオフを効果的に制御できる。
論文 参考訳（メタデータ） (2020-06-17T17:28:19Z) - Semiparametric Nonlinear Bipartite Graph Representation Learning with
Provable Guarantees [106.91654068632882]
半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。
提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。
我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
論文 参考訳（メタデータ） (2020-03-02T16:40:36Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。