Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2 ^m l ^O(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2 ⁿ n ^O(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732 ⁿ ) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.     

喇叭增益的精确设计和精确计算

本文综述了作者和他人有关喇叭增益的精确设计与精确计算的理论结果,并且得出结论,举出实例。     

Coinduction for preordered algebra

We develop a combination, called hidden preordered algebra, between preordered algebra, which is an algebraic framework supporting specification and reasoning about transitions, and hidden algebra, which is the algebraic framework for behavioural specification. This combination arises naturally within the heterogeneous framework of the modern formal specification language CafeOBJ. The novel specification concept arising from this combination, and which constitutes its single unique feature, is that of behavioural transition. We extend the coinduction proof method for behavioural equivalence to coinduction for proving behavioural transitions.     

Hypergeometric Functions in Exact Geometric Computation

Most problems in computational geometry are algebraic. A general approach to address nonrobustness in such problems is Exact Geometric Computation (EGC). There are now general libraries that support EGC for the general programmer (e.g., Core Library, LEDA Real). Many applications require non-algebraic functions as well. In this paper, we describe how to provide non-algebraic functions in the context of other EGC capabilities. We implemented a multiprecision hypergeometric series package which can be used to evaluate common elementary math functions to an arbitrary precision. This can be achieved relatively easily using the Core Library which supports a guaranteed precision level of accuracy. We address several issues of efficiency in such a hypergeometric package: automatic error analysis, argument reduction, preprocessing of hypergeometric parameters, and precomputed constants. Some preliminary experimental results are reported.     

Generalised Coinduction

We introduce the λ-coiteration schema for a distributive law λ of a functor T over a functor F. Under certain conditions it can be shown to uniquely characterise functions into the carrier of a final F-coalgebra, generalising the basic coiteration schema as given by finality. The duals of primitive recursion and course-of-value iteration, which are known extensions of coiteration, arise as instances of our framework. One can furthermore obtain schemata justifying recursive specifications that involve operators such as addition of power series, regular operators on languages, or parallel and sequential composition of processes.Next, the same type of distributive law λ is used to generalise coinductive proof techniques. To this end, we introduce the notion of a λ-bisimulation relation. It specialises to what could be called bisimulation up-to-equality or bisimulation up-to-context for contexts built from operators of the type mentioned above. We state that every such relation is contained in some larger conventional bisimulation and demonstrate that this principle leads to simpler bisimilarity proofs using less complex relations.     

Exact Computation of Delaunay and Power Triangulations

In this paper we present a topologically correct and efficient version of the algorithm by Guibas and Stolfi (Algorithmica 7 (1992), pp. 381-413) for the exact computation of Delaunay and power triangulations in two dimensions. The algorithm avoids numerical errors and degeneracies caused by the accumulation of rounding errors in fixed length floating point arithmetic when constructing these triangulations.Most methods for computing Delaunay and power triangulations involve the calculation of two basic primitives: the INCIRCLE test and the CCW orientation test. Both primitives require the computation of the sign of a determinant. The key to our method is the exact computation of this sign and is based on an algorithm for determining the sign of the sum of a finite set of normalized floating point numbers of fixed mantissa length (machine numbers) exactly. The exact computation of the primitives allows the construction of the correct Delaunay and power triangulations. The method has been implemented and tested for the incremental construction of Delaunay and power triangulations. Tests have been conducted for different distributions of points for which non-exact algorithms may encounter difficulties, for example, slightly perturbed points on a grid or on a circle. Experimental results show that the performance of our implementation is comparable with that of a simple implementation of the incremental algorithm in single precision floating point arithmetic. For random distribution of points the exact algorithm is only 4 times slower than the inexact implementation. The algorithm is easy to implement, robust and portable as long as the input data to the algorithm remains exact.     

求图符号控制数的完全算法研究

确定图的符号控制数是NP-难度的问题。针对求解该问题的完全算法即能求得精确最优解的算法进行了研究,提出了几个启发式的限界策略,给出了两个完全算法:回溯算法和A算法。计算实验表明,针对随机产生的问题实例,用这两个算法求解时所生成的结点数目还不到其状态空间树中结点总数目的千分之五。对这两个算法也进行了比较。     

Exact Computation of Polynomial Zeros Expressible by Square Roots

In this paper we give an efficient algorithm to find symbolically correct zeros of a polynomial f ∈ R[X] which can be represented by square roots. R can be any domain if a factorization algorithm over R[X] is given, including finite rings or fields, integers, rational numbers, and finite algebraic or transcendental extensions of those. Asymptotically, the algorithm needs O(T_f(d²)) operations in R, where T_f(d) are the operations for the factorization algorithm over R[X] for a polynomial of degree d. Thus, the algorithm has polynomial running time for instance for polynomials over finite fields or the rationals. We also present a quick test for deciding whether a given polynomial has zeros expressible by square roots and describe some additional methods for special cases.     

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number of disjoint dominating sets. This number is called the domatic number of the graph. We prove that the problem of determining whether or not the domatic number of a given graph is exactly one of k given values is complete for BH_2k(NP), the 2kth level of the boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not the domatic number of a given graph equals exactly a given integer. Note that DP = BH₂(NP). We obtain similar results for the exact versions of generalized dominating set problems and of the conveyor flow shop problem. Our reductions apply Wagner's conditions sufficient to prove hardness for the levels of the boolean hierarchy over NP.     

Coinductive Field of Exact Real Numbers and General Corecursion

In this article we present a method to define algebraic structure (field operations) on a representation of real numbers by coinductive streams. The field operations will be given in two algorithms (homographic and quadratic algorithm) that operate on streams of Möbius maps. The algorithms can be seen as coalgebra maps on the coalgebra of streams and hence they will be formalised as general corecursive functions. We use the machinery of Coq proof assistant for coinductive types to present the formalisation.     

A Coinduction Principle for Recursive Data Types Based on Bisimulation

The concept of bisimulation from concurrency theory is used to reason about recursively defined data types. From two strong-extensionality theorems stating that the equality (resp. inequality) relation is maximal among all bisimulations, a proof principle for the final coalgebra of an endofunctor on a category of data types (resp. domains) is obtained. As an application of the theory developed, an internal full abstraction result (in the sense of S. Abramsky and C.-H. L. Ong [Inform. and Comput.105, 159–267 (1993)] for the canonical model of the untyped call-by-valueλ-calculus is proved. Also, the operational notion of bisimulation and the denotational notion of final semantics are related by means of conditions under which both coincide.     

Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram

We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT) . Constructing CVT requires to repeatedly compute Restricted Voronoi Diagram (RVD) , defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd -tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O ( m log n ), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd's iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than with the state-of-art approaches.     

一种改进的实数编码遗传算法

遗传算法的一个显著特点是它交替在编码空间和解空间中工作,它在编码空间对染色体进行遗传运算,而在解空间对解进行评估和选择。因此,如何将问题的解转换为编码表达的染色体是遗传算法的关键问题。近十年来,针对特殊问题,提出了各种非0-1串的编码方法。实数编码方法是用于解决复杂的约束优化问题的首选方法。     

进化计算的二进制与浮点数自适应混合编码方法

提出了一种新的基于二进制码串和浮点数码串的混合编码方法,将遗传个体的每一变量编码为二进制和浮点数的混合码串,使得进化计算能结合二进制编码方法全局探索能力强的特点和浮点数编码方法局部寻优能力强的特点,在这种混合编码方法中,根据进化过程中遗传群体平均适应度的变化,自适应地改变二进制码串和浮点数码串所占比例,使得进化计算的全局探索能力和局部寻优能力得到了较好的平衡,提高了进化计算的收敛速度和全局优化收敛率,文章对一系列典型函数的优化计算实验验证了基于二进制码串和浮点数码串的混合编码的特点。     

Coinduction in Control of Partially Observed Discrete-Event Systems

Coalgebra and coinduction provide new results and insights for the supervisory control of discrete-event systems (DES) with partial observations. In the case of full observations, coinduction has been used to define a new operation on languages called supervised product, which represents the tuple of languages of the supervised system. The first language acts as a supervisor and the second as an open-loop system (plant). We show first that the supervised product is equal to the infimal controllable superlanguage of the supervisor's (specification) language with respect to the plant language. This can be generalized to the partial observation case, where the supervised product is shown to be equal to the infimal controllable and observable superlanguage. A modification on the supervised product is presented, which corresponds to the control policy for with the issue of observability is separated from the issue of controllability. The operation defined by coinduction is shown to be equal to the infimal observable superlanguage.