Exact maximum likelihood estimation for non-stationary periodic time series models

Time series models with parameter values that depend on the seasonal index are commonly referred to as periodic models. Periodic formulations for two classes of time series models are considered: seasonal autoregressive integrated moving average and unobserved components models. Convenient state space representations of the periodic models are proposed to facilitate model identification, specification and exact maximum likelihood estimation of the periodic parameters. These formulations do not require a priori (seasonal) differencing of the time series. The time-varying state space representation is an attractive alternative to the time-invariant vector representation of periodic models which typically leads to a high dimensional state vector in monthly periodic time series models. A key development is our method for computing the variance-covariance matrix of the initial set of observations which is required for exact maximum likelihood estimation. The two classes of periodic models are illustrated for a monthly postwar US unemployment time series.     

The complexity of the satisfiability problem for Krom formulas

We study the computational complexity of the satisfiability problem for Krom (CNF-2) formulas. Upper and lower bounds are obtained for several decidable classes of formulas determined by quantifier prefix and degree of predicate letters. For example, we show that determining satisfiability of Krom formulas with quantifier prefix of the form ……… is complete for deterministic exponential time, but that if the number of universal quantifiers is bounded then polynomial time suffices.     

A decomposition based algorithm for maximal contractions

This paper proposes a decomposition based algorithm for revision problems in classical propositional logic. A set of decomposing rules are presented to analyze the satisfiability of formulas. The satisfiability of a formula is equivalent to the satisfiability of a set of literal sets. A decomposing function is constructed to calculate all satisfiable literal sets of a given formula. When expressing the satisfiability of a formula, these literal sets are equivalent to all satisfied models of such formula. A revision algorithm based on this decomposing function is proposed, which can calculate maximal contractions of a given problem. In order to reduce the memory requirement, a filter function is introduced. The improved algorithm has a good performance in both time and space perspectives.     

Hardness and approximation of minimum maximal matchings

In this paper, we consider the minimum maximal matching problem in some classes of graphs such as regular graphs. We show that the minimum maximal matching problem is NP-hard even in regular bipartite graphs, and a polynomial time exact algorithm is given for almost complete regular bipartite graphs. From the approximation point of view, it is well known that any maximal matching guarantees the approximation ratio of 2 but surprisingly very few improvements have been obtained. In this paper we give improved approximation ratios for several classes of graphs. For example any algorithm is shown to guarantee an approximation ratio of (2-o(1)) in graphs with high average degree. We also propose an algorithm guaranteeing for any graph of maximum degree Δ an approximation ratio of (2?1/Δ), which slightly improves the best known results. In addition, we analyse a natural linear-time greedy algorithm guaranteeing a ratio of (2?23/18k) in k-regular graphs admitting a perfect matching.     

Generalized modal satisfiability

It is well known that modal satisfiability is PSPACE-complete (Ladner (1977) [21]). However, the complexity may decrease if we restrict the set of propositional operators used. Note that there exist an infinite number of propositional operators, since a propositional operator is simply a Boolean function. We completely classify the complexity of modal satisfiability for every finite set of propositional operators, i.e., in contrast to previous work, we classify an infinite number of problems. We show that, depending on the set of propositional operators, modal satisfiability is PSPACE-complete, coNP-complete, or in P. We obtain this trichotomy not only for modal formulas, but also for their more succinct representation using modal circuits. We consider both the uni-modal and the multi-modal cases, and study the dual problem of validity as well.     

Model checking for action-based logics

A model checker is described that supports proving logical properties of concurrent systems. The logical properties can be described in different action-based logics (variants of Hennessy-Milner logic). The tools is based on the EMC model checker for the logic CTL. It therefore employs a set of translation functions from the considered logics to CTL, as well as a model translation function from labeled transition systems (models of the action-based logics) to Kripke structures (models for CTL). The obtained tool performs model checking in linear time complexity, and its correctness is guaranteed by the proof that the set of translation functions, coupled with the model translation function, preserves satisfiability of logical formulae.     

可满足实例的归结复杂度

GRB模型是一种随机约束满足问题模型,此模型具有精确的可满足相变现象。针对实验中出现的GRB模型在相变区域产生的可满足实例都是难解的现象,利用子句宽度和归结复杂度的关系证明了GRB模型在相变点附近产生的可满足实例对于树型归结证明具有指数下界。因此从理论上证明了在相变区域产生的可满足实例对基于归结的算法是难解的。     

Generalized Definite Set Constraints

Set constraints (SC) are logical formulae in which atoms are inclusions between set expressions. Those set expressions are built over a signature , variables and various set operators. On a semantical point of view, the set constraints are interpreted over sets of trees built from and the inclusion symbol is interpreted as the subset relation over those sets. By restricting the syntax of those formulae and/or the set of operators that can occur in set expressions, different classes of set constraints are obtained. Several classes have been proposed and studied for some problems such as satisfiability and entailment. Among those classes, we focus in this article on the class of definite SC's introduced by Heintze and Jaffar, and the class of co-definite SC's studied by Charatonik and Podelski. In spite of their name, those two classes are not dual from each other, neither through inclusion inversion nor through complementation. In this article, we propose an extension for each of those two classes by means of an intentional set construction, so called membership expression. A membership expression is an expression {x| (x)}. The formula (x) is a positive first-order formula built from membership atomst in S in which S is a set expression. We name those two classes respectively generalized definite and generalized co-definite set constraints. One of the main point concerning those so-extended classes is that the two generalized classes turn out to be dual through complementation. First, we prove in this article that generalized definite set constraints is a proper extension of the definite class, as it is more expressive in terms of sets of solutions. But we show also that those extensions preserve some main properties of the definite and co-definite class. Hence for instance, as definite set constraints, generalized definite SC's have a least solution whereas the generalized co-definite SC's have a greatest solution, just as co-definite ones. Furthermore, we devise an algorithm based on tree automata that solves the satisfiability problem for generalized definite set constraints. Due to the dualization, the algorithm solves the satisfiability problem for generalized co-definite set constraints as well. This algorithm proves first that for those generalized classes, the satisfiability problem remains DEXPTIME-complete. It provides also a proof for regularity of the least solution of generalized definite constraints and so, by dualization for the greatest solution for the generalized co-definite SC's.     

A polynomial space construction of tree-like models for logics with local chains of modal connectives

The LA-logics (“logics with Local Agreement”) are polymodal logics defined semantically such that at any world of a model, the sets of successors for the different accessibility relations can be linearly ordered and the accessibility relations are equivalence relations. In a previous work, we have shown that every LA-logic defined with a finite set of modal indices has an NP-complete satisfiability problem. In this paper, we introduce a class of LA-logics with a countably infinite set of modal indices and we show that the satisfiability problem is PSPACE-complete for every logic of such a class. The upper bound is shown by exhibiting a tree structure of the models. This allows us to establish a surprising correspondence between the modal depth of formulae and the number of occurrences of distinct modal connectives. More importantly, as a consequence, we can show the PSPACE-completeness of Gargov's logic DALLA and Nakamura's logic LGM restricted to modal indices that are rational numbers, for which the computational complexity characterization has been open until now. These logics are known to belong to the class of information logics and fuzzy modal logics, respectively.     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

SLS算法求解平衡正则(k,2r)-CNF公式

可满足性问题的求解算法和结构性质研究是计算机科学中重要问题之一，为寻求某些CNF公式子类问题有效算法或算法改进途径，对公式的结构加以某些限制，其中限定子句长度为恒定常数和变元出现次数是常见的处理方式。研究具有正则结构且每个变元正负出现均衡的结构化公式的可满足性问题求解，其随机生成模型的构建及随机实验测试有助于观察解分布状况。并且，随机局部搜索算法在求解具有一定规则结构CNF公式实例中具有良好效率。本文集中研究平衡正则(k, 2r)-CNF公式的求解问题，即限制每个子句的长度为k，每个变元出现的次数为偶数2r,并且每个变元正负出现的次数在相等情况下的可满足性问题求解。给出BR(n,  k, 2r)模型，以此模型来生成具有特殊结构的平衡正则(k, 2r)-CNF公式实例，利用随机局部搜索算法求解问题。通过限制初始指派的0文字和1文字各占一半且均匀生成，以WalkSAT算法和NSAT算法做实验对比，发现对于平衡正则(k, 2r)-CNF公式，实例具有明显效率。     

基于消息传递关系网络的布尔可满足性预测

布尔可满足性求解能够验证的问题规模通常受限, 因此, 如何高精度地预测布尔可满足性问题的可满足性是一个重要研究问题, 也是一项具有挑战性的工作.相关研究工作一般使用由文字节点和子句节点组成的图来表示布尔可满足性问题的结构, 但是这种表征方法缺少了变量、子句之间的重要关系信息.在我们的方法中, 通过将原始布尔可满足性问题实例表征为多关系异构图的方式来表达变量和句子之间的关系, 并设计使用消息传递关系网络模型来捕获实例的关系信息, 提取了更多的结构特征.结果表明, 该模型在预测精度、泛化能力和资源需求等方面均优于现有模型, 对所选数据集的平均预测精度为81%.该模型在小规模问题(变量数为100)上训练, 在大规模数据集上预测的平均预测精度达到了80.8%.同时, 该模型对随机生成的非均匀随机问题的预测精度达到99%, 这意味着它学习了预测可满足性的重要特征.此外, 模型预测所花费的时间随着问题规模的增大也只是呈线性增长. 总结而言, 本文基于关系消息传递网络提出了一个预测精度更高, 泛化能力更好的布尔可满足性预测方法.     

可满足问题中的模型计数

模型计数问题是指计算给定问题的解的个数,这是一类比决策更困难的问题,也是人工智能领域研究的一个热点问题.对模型计数问题的研究不仅可以提高算法的求解效率,更能促进对问题困难本质的了解.以可满足问题（命题可满足（SAT）和约束可满足问题（CSP））为例,从精确算法和近似求解两方面综述了模型计数问题的研究现状,重点介绍了相关概念以及各个算法之间的优缺点,并提出了有待解决的开放性问题,对模型计数问题的研究予以了总结和展望.     

一种基于变量熵求解约束满足问题的置信传播算法

在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.     

Point algebras for temporal reasoning: Algorithms and complexity

We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.     

Formal Verification Techniques Based on Boolean Satisfiability Problem

This paper exploits Boolean satisfiability problem in equivalence checking and model checking respectively. A combinational equivalence checking method based on incremental satisfiability is presented. This method chooses the candidate equivalent pairs with some new techniques, and uses incremental satisfiability algorithm to improve its performance.By substituting the internal equivalent pairs and converting the equivalence relations into conjunctive normal form (CNF)formulas, this approach can avoid the false negatives, and reduce the search space of SAT procedure. Experimental results on ISCAS‘85 benchmark circuits show that, the presented approach is faster and more robust than those existed in literature.This paper also presents an algorithm for extracting of unsatisfiable core, which has an important application in abstraction and refinement for model checking to alleviate the state space explosion bottleneck. The error of approximate extraction is analyzed by means of simulation. An analysis reveals that an interesting phenomenon occurs, with the increasing density of the formula, the average error of the extraction is decreasing. An exact extraction approach for MU subformula, referred to as pre-assignment algorithm, is proposed. Both theoretical analysis and experimental results show that it is more efficient.     

Deciding a class of path formulas for conflict-free petri nets

The aim of this paper is to develop a unified approach for deriving complexity results for problems concerning conflict-free Petri nets. To do so, we first define a class of formulas for paths in Petri nets. We then show that answering the satisfiability problem for conflict-free Petri nets is tantamount to solving a system of linear inequalities (which is known to be in P). Since a wide spectrum of Petri net problems (including various fairness-related problems) can be reduced to the satisfiability problem in a straightforward manner, our approach offers an umbrella under which many Petri net problems for conflict-free Petri nets can be shown to be solvable in polynomial time. As a side-product, our analysis provides evidence as to why detecting unboundedness for conflict-free Petri nets is easier (provided P ≠ NP) than for normal and sinkless Petri nets (which are two classes that properly contain conflict-free Petri nets). A preliminary version was presented at the 14th International Conference on Application and Theory of Petri Nets, Chicago, IL, USA, June 1993.     

Resolution-based decision procedures for the universal theory of some classes of distributive lattices with operators

We establish a link between the satisfiability of universal sentences with respect to classes of distributive lattices with operators and their satisfiability with respect to certain classes of relational structures. This justifies a method for structure-preserving translation to clause form of universal sentences in such classes of algebras. We show that refinements of resolution yield decision procedures for the universal theory of some such classes. In particular, we obtain exponential space and time decision procedures for the universal clause theory of (i) the class of all bounded distributive lattices with operators satisfying a set of (generalized) residuation conditions, and (ii) the class of all bounded distributive lattices with operators, and a doubly-exponential time decision procedure for the universal clause theory of the class of all Heyting algebras.     

A propositional theorem prover to solve planning and other problems

Classical STRIPS-style planning problems are formulated as theorems to be proven from a new point of view: that the problem is not solvable. The result for a refutation-based theorem prover may be a propositional formula that is to be proven unsatisfiable. This formula is identical to the formula that may be derived directly by various “SAT compilers”, but the theorem-proving view provides valuable additional information not in the formula, namely, the theorem to be proven. Traditional satisfiability methods, most of which are based on model search, are unable to exploit this additional information. However, a new algorithm called “Modoc” is able to exploit this information and has achieved performance comparable to the fastest known satisfiability methods, including stochastic search methods, on planning problems that have been reported by other researchers, as well as formulas derived from other applications. Unlike most theorem provers, Modoc performs well on both satisfiable and unsatisfiable formulas. Modoc works by a combination of back-chaining from the theorem clauses and forward-chaining on tractable subformulas. In some cases, Modoc is able to solve a planning problem without finding a complete assignment because the back-chaining methodology is able to ignore irrelevant clauses. Although back-chaining is well known in the literature, a high level of search redundancy existed in previous methods; Modoc incorporates a new technique called “autarky pruning”, which reduces search redundancy to manageable levels, permitting the benefits of back-chaining to emerge, for certain problem classes. Experimental results are presented for planning problems and formulas derived from other applications. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Decision Procedure for a Sublanguage of Set Theory Involving Monotone, Additive, and Multiplicative Functions

MLSS is a decidable sublanguage of set theory involving the predicates membership, set equality, set inclusion, and the operators union, intersection, set difference, and singleton.In this paper we extend MLSS with constructs for expressing monotonicity, additivity, and multiplicativity properties of set-to-set functions. We prove that the resulting language is decidable by reducing the problem of determining the satisfiability of its sentences to the problem of determining the satisfiability of sentences of MLSS.