We introduce CPDL+, a family of expressive logics rooted in Propositional
Dynamic Logic (PDL). In terms of expressive power, CPDL+ strictly contains PDL
extended with intersection and converse (a.k.a. ICPDL) as well as Conjunctive
Queries (CQ), Conjunctive Regular Path Queries (CRPQ), or some known extensions
thereof (Regular Queries and CQPDL). We investigate the expressive power,
characterization of bisimulation, satisfiability, and model checking for CPDL+.
We argue that natural subclasses of CPDL+ can be defined in terms of the
tree-width of the underlying graphs of the formulas. We show that the class of
CPDL+ formulas of tree-width 2 is equivalent to ICPDL, and that it also
coincides with CPDL+ formulas of tree-width 1. However, beyond tree-width 2,
incrementing the tree-width strictly increases the expressive power. We
characterize the expressive power for every class of fixed tree-width formulas
in terms of a bisimulation game with pebbles. Based on this characterization,
we show that CPDL+ has a tree-like model property. We prove that the
satisfiability problem is decidable in 2ExpTime on fixed tree-width formulas,
coinciding with the complexity of ICPDL. We also exhibit classes for which
satisfiability is reduced to ExpTime. Finally, we establish that the model
checking problem for fixed tree-width formulas is in \ptime, contrary to the
full class CPDL+.

介绍了一种基于 PDL 的表达力丰富的逻辑家族 CPDL+，研究了其最小模型检查问题和可满足性问题，将 CPDL + 的表达能力与树宽相关联，并通过基于树宽的逐步升级证明了其表达能力的严格上升。

PDL on Steroids：关于具有交集和转置的 PDL 表达式的扩展性探讨

PDL on Steroids: on Expressive Extensions of PDL with Intersection and  Converse

Chow and Liu (1968) studied the problem of learning a maximumlikelihood
Markov tree. We generalize their work to more complexMarkov networks by
considering the problem of learning a maximumlikelihood Markov network of
bounded complexity. We discuss howtree-width is in many ways the appropriate
measure of complexity andthus analyze the problem of learning a maximum
likelihood Markovnetwork of bounded tree-width.Similar to the work of Chow and
Liu, we are able to formalize thelearning problem as a combinatorial
optimization problem on graphs. Weshow that learning a maximum likelihood
Markov network of boundedtree-width is equivalent to finding a maximum weight
hypertree. Thisequivalence gives rise to global, integer-programming
based,approximation algorithms with provable performance guarantees, for
thelearning problem. This contrasts with heuristic local-searchalgorithms which
were previously suggested (e.g. by Malvestuto 1991).The equivalence also allows
us to study the computational hardness ofthe learning problem. We show that
learning a maximum likelihoodMarkov network of bounded tree-width is NP-hard,
and discuss thehardness of approximation.

通过将 Chow 和 Liu 在最大似然马尔科夫树方面的工作推广到更复杂的马尔科夫网络，我们研究了高度限制下最大似然马尔科夫网络学习问题，结果表明其复杂度是 NP 难问题。

最大似然界树宽马尔可夫网络

Maximum Likelihood Bounded Tree-Width Markov Networks

This paper presents a new anytime algorithm for the marginal MAP problem in
graphical models. The algorithm is described in detail, its complexity and
convergence rate are studied, and relations to previous theoretical results for
the problem are discussed. It is shown that the algorithm runs in
polynomial-time if the underlying graph of the model has bounded tree-width,
and that it provides guarantees to the lower and upper bounds obtained within a
fixed amount of computational resources. Experiments with both real and
synthetic generated models highlight its main characteristics and show that it
compares favorably against Park and Darwiche's systematic search, particularly
in the case of problems with many MAP variables and moderate tree-width.

提出了一种新的任何时间算法解决图模型中的边际 MAP 问题，该算法可以在多项式时间内运行且当模型的图具有有限的树宽时，可以提供下限和上限保证。实验表明它可以在具有多个 MAP 变量和中等树宽的问题中表现得很好，并且相比 Park 和 Darwiche 的系统搜索而言有更好的表现。