List partitions

By definition, apartition of a list is a division of that list into nonempty contiguous segments. Many programming and operations research problems can be specified in terms of list partitions, and we present a hierarchy of theorems for deriving programs from such specifications. Throughout, reasoning is conducted in an equational style using the calculus for program synthesis developed by Bird and Meertens.Supported by a BP research studentship.     

Bernoulli functions and periodic B-splines

Bernoulli polynomials and the related Bernoulli functions are of basic importance in theoretical numerical analysis. It was shown by Golomb and others that the periodic Bernoulli functions serve to construct periodic polynomial splines on uniform meshes. In an unknown paper Wegener investigated remainder formulas for polynomial Lagrange interpolation via Bernoulli functions. We will use Wegener's kernel function to construct periodicB-splines. For uniform meshes we will show that Locher's method of interpolation by translation is applicable to periodicB-splines. This yields an easy and stable algorithm for computing periodic polynomial interpolating splines of arbitrary degree on uniform meshes via discrete Fourier transform.     

A partition on a Bernoulli shift which is not weakly Bernoulli

In an attempt to further classifyK-automorphism D. Ornstein suggested (orally) a stronger mixing property calledweak Bernoulli (together with N. Friedman he proved that if a generator has this property then the transformation is isomorphic to a Bernoulli shift). I show that in a Bernoulli shift there is a partition which is not weak Bernoulli. I use the following theorem: The shift on a regular stationary Gaussian process is isomorphic to a Bernoulli shift.Research sponsored by the Air Force Office of Scientific Research, Office of Aerospace Research, United States Air Force, under Grant AF-AROSR-1312-67. Present address: Mathematics Institute, University of Warwick, Coventry CV4 7AL, England.     

Nonboolean partitions and their logic

 Working in the framework of the infinite-valued propositional calculus of Łukasiewicz we develop a generalization of the notion of boolean partition. Applications are given to handle the dependent and the independent variable in approximate definitions by cases—as softly, tractably and robustly as possible.     

Integer partitions and the Sperner property

The objectives of this paper are three-fold. First, we would like to call attention to a very attractive problem, the question of whether or not the poset of integer partitions ordered by refinement has the Sperner property. We provide all necessary definitions, and enough bibliography to interest a newcomer in the problem. Second, we prove four new theorems, two by exhaustive computation and two in the more traditional manner. Finally, we highlight the central role played by Larry Harper in the literature of this subject.     

Path partitions of hypercubes

A path partition of a graph G is a set of vertex-disjoint paths that cover all vertices of G. Given a set of pairs of distinct vertices of the n-dimensional hypercube Qn, is there a path partition of Qn such that ai and bi are endvertices of Pi? Caha and Koubek showed that for 6m?n, such a path partition exists if and only if the set P is balanced in the sense that it contains the same number of vertices from both classes of bipartition of Qn.In this paper we show that this result holds even for 2m−e<n, where e is the number of pairs of P that form edges of Qn. Moreover, our bound is optimal in the sense that for every n?3, there is a balanced set P in Qn such that 2m−e=n, but no path partition with endvertices prescribed by P exists.     

Vague相似关系与Vague划分

通过对单位区间[0,1]的闭子区间集中的元素——Vague值的定义,引入二元Vague关系、关系运算、逆关系、关系的合成、λ-截关系等新的定义。从基于可能度的区间数序关系的概念以及Vague集投票模型的实际意义两个方面,引入闭子区间集中Vague值的偏序关系的定义,并利用偏序关系证明了Vague关系的一些主要性质。给出了满足sup-min传递性的Vague相似关系以及Vague划分的定义,建立了Vague相似关系与Vague划分一一对应性,进而以[0,1]上连续t模作为广义的“与”逻辑算子,引入Vague相似关系的特例——满足T-传递性的Vague T-相似关系与Vague T-划分新的定义。     

On partitions and presortedness of sequences

To take advantage of existing order in a sequence when sorting, we evaluate the quantity of this information by the minimal size of decomposition of the input sequence, particularly the minimal size of chain and of monotonic partitions. Some sorting strategies that are optimal with respect to these measures of presortedness are presented. The relationships between these new measures of presortedness and other known measures have also been explored. As an application, we carry out the optimality of an adaptive sorting algorithm Skiena'sMelsort. For some special partitioning strategies, we present two sorting algorithms based on Dijkstra'sSmoothsort. Moreover, the optimalities of these two algorithms are demonstrated. By examining the optimalities of sorting algorithms with respect to certain measures of presortedness, we also propose some optimal sorting strategies for one class of measures. Finally, we discuss other types of sorting problems, such as sorting multisets and topological sorting. In particular, we derive an optimal algorithm for sorting multisets and for finding the multiset sizes as well.A preliminary version of this paper was presented at the Second Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA (January 28–30, 1991).The main part of the work was conducted while the author was with Lund University.     

Indexing dataspaces with partitions

Dataspaces are recently proposed to manage heterogeneous data, with features like partially unstructured, high dimension and extremely sparse. The inverted index has been previously extended to retrieve dataspaces. In order to achieve more efficient access to dataspaces, in this paper, we first introduce our survey of data features in the real dataspaces. Based on the features observed in our study, several partitioning based index approaches are proposed to accelerate the query processing in dataspaces. Specifically, the vertical partitioning index utilizes the partitions on tokens to merge and compress data. We can both reduce the number of I/O reads and avoid aggregation of data inside a compressed list. The horizontal partitioning index supports pruning partitions of tuples in the top-k query. Thus, we can reduce the computation overhead of irrelevant candidate tuples to the query. Finally, we also propose a hybrid index with both vertical and horizontal partitioning. The extensive experiment results in real data sets demonstrate that our approaches outperform the previous techniques and scale well with the large data size.     

基于之型分量码的系统非规则GLDPC码

首先提出了一种新型的编码结构—基于之型分量码的系统非规则GLDPC码;其次在加性高斯白噪声信 道下利用基于高斯近似的密度进化理论设计G}ICI工DPC码的度分布序列;最后对G}IGI_DPC码进行了性能分析。 仿真结果表明,中等码长的ZS-IGLDPC码在误码率性能方面有一定的优势。     

Optimal Prefix Codes And Huffman Codes

Existence of the optimal prefix codes is shown in this paper. Relationship between the optimal prefix code and the Huffman code is also discussed. We prove that all Huffman codes are optimal prefix codes and conversely optimal prefix codes need not be Huffman codes. Especially, the problem of whether the optimal prefix code has to be maximal is presented. Although for information source alphabets of being not greater than four letters we show that an optimal prefix code must be maximal, it remains to be an open problem in general. As seen from Huffman codes, optimal prefix codes are used not only for statistical modeling but also for dictionary methods. Moreover, it is obtained that the complexity of breaking an optimal prefix code is NP-complete from the viewpoint of computational difficulty.     

Many-valued equalities, singletons and fuzzy partitions

 This paper deals with interrelations between many-valued equalities, singletons and many-valued partitions. Applications to the principle of sliding transition and to fuzzy control theory are given.     

Protocol analysis and synthesis by structured partitions

Protocols can be viewed as predefined sequences of message exchanges between machines for performing network control functions and for providing network services. One way of modeling protocols is by using communicating finite state machines. The interaction between finite state machines can be very involved, even for machines with few states. To counteract the complexity for protocol analysis and synthesis, we propose a partitioning method based on protocol subgraphs. We found that if there are ‘cross interactions’ involving the entire protocol graph, then the protocol is not decomposable by our technique and must be analyzed or synthesized as a whole. However, if there are subunits of message exchanges within the protocol graph that are self-contained, in other words, if there are no ‘cross interactions’ between protocol subgraphs, then the protocol is decomposable. For protocols that are decomposable, we show that it is only necessary to examine a subspace of the entire reachability space to understand the behavior of the protocol and to guarantee its progress properties. This allows us to analyze and synthesize protocols based on these subgraphs.     

Graph matching and clustering using spectral partitions

Although inexact graph-matching is a problem of potentially exponential complexity, the problem may be simplified by decomposing the graphs to be matched into smaller subgraphs. If this is done, then the process may cast into a hierarchical framework and hence rendered suitable for parallel computation. In this paper we describe a spectral method which can be used to partition graphs into non-overlapping subgraphs. In particular, we demonstrate how the Fiedler-vector of the Laplacian matrix can be used to decompose graphs into non-overlapping neighbourhoods that can be used for the purposes of both matching and clustering.     

Codes Derived from Binary Goppa Codes

We present a new family of binary codes derived from the family of classical Goppa codes. We generalize properties of Goppa codes to this family, including bounds on the dimension and minimum distance and construction of a polynomial-time algorithm of decoding up to the designed distance. Asymptotically, these codes have the same parameters as Goppa codes.     

A definition for I-fuzzy partitions

In this paper, we define I-fuzzy partitions (or intuitionistic fuzzy partitions as called by Atanassov or interval-valued fuzzy partitions). As our ultimate goal is to compare the results of standard fuzzy clustering algorithms (e.g. fuzzy c-means), we define a method to construct them from a set of fuzzy clusters obtained from several executions of fuzzy c-means. From a practical point of view, the approach presented here tries to solve the difficulty of comparing the results of fuzzy clustering methods and, in particular, the difficulty of finding the global optimal.     

Blurred partitions but thicker walls

In this paper, we explore public administration as a site of use for Computer Supported Cooperative Work (CSCW) applications, and outline the particular opportunities and challenges that CSCW and public administration pose for each other. We argue that public administrations in modern democratic societies are in both their organizational structures and their activities subservient to legal and political norms in a way that is different from private organizations; therefore, public administration cannot slavishly emulate CSCW applications that have proven themselves in a private context. Public administrations have to assess forms of CSCW in the light of the normative structure that is specific for them.We argue that the introduction of CSCW will further the tendencies to bureaucratisation and skew power biases towards public administration and away from the citizen. We give evidence for this contention on the basis of a comparison of different national attempts to introduce CSCW in Social Security offices in the Netherlands, the United Kingdom and Sweden. Although each of these countries is inspired by different ideals about the relationship between state and citizen in the social security sector, the influence of CSCW in all three cases goes in the same direction.