Inequalities for Stationary Poisson Cuboid Processes

A cuboid is a rectangular parallelepipedon. By the notion “stationary Poisson cuboid process” we understand a stationary Poisson hyperplane process which divides the Euclidean space ?^d into cuboids. It is equivalent to speak of a stationary Poisson cuboid tessellation. The distributions of volume and total edge length of the typical cuboid and the origin-cuboid of a stationary Poisson cuboid process are considered. It is shown that these distributions become minimal, in the sense of a specific order relation, in the case of quasi-isotropy. A possible connection to a more general problem, treated in [6], is also discussed.     

Detecting evolving patterns of self‐organizing networks by flow hierarchy measurement

Hierarchies occur widely in evolving self‐organizing ecological, biological, technological, and social networks, but detecting and comparing hierarchies is difficult. Here we present a metric and technique to quantitatively assess the extent to which self‐organizing directed networks exhibit a flow hierarchy. Flow hierarchy is a commonly observed but theoretically overlooked form of hierarchy in networks. We show that the ecological, neurobiological, economic, and information processing networks are generally more hierarchical than their comparable random networks. We further discovered that hierarchy degree has increased over the course of the evolution of Linux kernels. Taken together, our results suggest that hierarchy is a central organizing feature of real‐world evolving networks, and the measurement of hierarchy opens the way to understand the structural regimes and evolutionary patterns of self‐organizing networks. Our measurement technique makes it possible to objectively compare hierarchies of different networks and of different evolutionary stages of a single network, and compare evolving patterns of different networks. It can be applied to various complex systems, which can be represented as directed networks. © 2011 Wiley Periodicals, Inc. Complexity, 2011     

发展方程族Lax表示的广义结构*

本文给出非线性发展方程族的一个生成格式(该格式包含了保谱族与非保谱族作为其两个特殊情况),并提供该格式下发展方程族Lax表示的广义结构.最后,作为应用,我们讨论了Levi族发展方程.     

Power contexts and their concept lattices

We introduce a framework for the study of formal contexts and their lattices induced by the additional structure of self-relations on top of the traditional incidence relation. The induced contexts use subsets as objects and attributes, hence the name power context and power concept. Six types of new incidence relations are introduced by taking into account all possible combinations of universal and existential quantifiers as well as the order of the quantifications in constructing the lifted power contexts. The structure of the power concept lattice is investigated through projection mappings from the baseline objects and attributes to those of the power context, respectively. We introduce the notions of extensional consistency and intensional consistency, corresponding to the topological notions of continuity in the analogous setting when concepts are viewed as closed sets. We establish Galois connections for these notions of consistency. We further introduce the notion of faithfulness for the first type of lifted incidence relation based on the fact that it can be equivalently characterized by a concept-faithful morphism. We also present conditions under which the power concept lattice serves as a factor lattice of the base concept lattice.     

Methods for derivation of the stochastic Boltzmann hierarchy

We consider different methods for the derivation of the stochastic Boltzmann hierarchy corresponding to the stochastic dynamics that is the Boltzmann-Grad limit of the Hamiltonian dynamics of hard spheres. Solutions of the stochastic Boltzmann hierarchy are the Boltzmann-Grad limit of solutions of the BBGKY hierarchy of hard spheres in the entire phase space. A new concept of reduced distribution functions corresponding to the stochastic dynamics are introduced. They take into account the contribution of the hyperplanes of lower dimension where stochastic point particles interact with one another. The solutions of the Boltzmann equation coincide with one-particle distribution functions of the stochastic Boltzmann hierarchy and are represented by integrals over the hyperplanes where the stochastic point particles interact with one another.     

Study of a universal formal context

Studying a universal formal context, we obtain a number of properties of the context itself, its concepts, and the lattice formed by the set of these concepts. The most significant of these properties is represented by a theorem showing that there exists an embedding of the concept lattice of an arbitrary at most countable universal context into the concept lattice of a universal context under which the image of the embedding is an initial segment of the concept set of a universal formal context with infinite volumes, and the validity of the dual result. It is shown that the theorem also holds in the computable case. This theorem demonstrates the complexity of the structure of a universal formal context.     

Boolean Hierarchies of Partitions over a Reducible Base

The Boolean hierarchy of partitions was introduced and studied by Kosub and Wagner, primarily over the lattice of NP-sets. Here, this hierarchy is treated over lattices with the reduction property, showing that it has a much simpler structure in this instance. A complete characterization is given for the hierarchy over some important lattices, in particular, over the lattices of recursively enumerable sets and of open sets in the Baire space.     

层次系统DEA模型的研究

经典的DEA模型视决策单元为黑匣子,不考虑内部结构.实际上,决策单元DMU可能具有各种各样的结构.对DMU进行效率评价时,尽管最初的输入和最终的输出相同,但考虑DMU结构与忽视DMU结构得到的效率不同.基于这样一种思想,提出了一种基于层次系统的DEA模型.     

On a Mathematical Comparison between Hierarchy and Network with a Classification of Coordination Structures

This paper proposes a mathematical model to compare a network organization with a hierarchical organization. In order to formulate the model, we define a three-dimensional framework of the coordination structure of a network and of other typical coordination structures. In the framework, we can define a network structure by contrasting it with a hierarchy, in terms of the distribution of decision making, which is one of the main features of information processing. Based on this definition, we have developed a mathematical model for evaluating coordination structures. Using this model, we can derive two boundary conditions among the coordination structures with respect to the optimal coordination structure. The boundary conditions help us to understand why an organization changes its coordination structure from a hierarchy to a network and what factors cause this change. They enable us, for example, to find points of structural change where the optimal coordination structure shifts from a hierarchy to a hierarchy with delegation or from a hierarchy with delegation to a network, when the nature of the task changes from routine to non-routine. In conclusion, our framework and model may provide a basis for discussing the processes that occur when coordination structures change between a hierarchy and a network.     

两台带服务等级的可拒绝同型机排序问题的在线算法

两台同型机M_1,M_2, 加工速度一致, 但拥有不同的加工能力,用其服务等级表示, M_1的服务等级为1, M_2的服务等级为2. 工件j按列表在线到达,每个工件带有三个参数: 长度t_j,等级g_j=1或2, 罚值p_j. 当j到达时, 可以被拒绝, 但要付出相应的罚值p_j, 也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M_1加工, 等级为2的工件可以分给M_1或M_2加工, 加工不允许中断. 目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和. 对于该问题给出了一个在线算法, 其竞争比为11/6, 以及问题一个下界5/3.     

On R-trees with low query complexity

The R-tree is a well-known bounding-volume hierarchy that is suitable for storing geometric data on secondary memory. Unfortunately, no good analysis of its query time exists. We describe a new algorithm to construct an R-tree for a set of planar objects that has provably good query complexity for point location queries and range queries with ranges of small width. For certain important special cases, our bounds are optimal. We also show how to update the structure dynamically, and we generalize our results to higher-dimensional spaces.     

The applications of the gauge transformation for the BKP hierarchy

In this paper, we investigated four applications of the gauge transformation for the BKP hierarchy. Firstly, it is found that the orbit of the gauge transformation for the constrained BKP hierarchy defines a special (2+1)$(2+1)$-dimensional Toda lattice equation structure. Then the tau function of the BKP hierarchy generated by the gauge transformation is shown to be the Pfaffian. And the higher Fay-like identities for the BKP hierarchy is also obtained through the gauge transformation. At last, the compatibility between the additional symmetry and the gauge transformation of the BKP hierarchy is proven.     

Generalized domination in closure systems

In the context of extracting maximal item sets and association rules from a binary data base, the graph-theoretic notion of domination was recently used to characterize the neighborhood of a concept in the corresponding lattice.In this paper, we show that the notion of domination can in fact be extended to any closure operator on a finite universe and be efficiently encoded into propositional Horn functions. This generalization enables us to endow notions and algorithms related to Formal Concept Analysis with Horn minimization and minimal covers of functional dependencies in Relational Databases.     

An integrable lattice hierarchy, associated integrable coupling, Darboux transformation and conservation laws

A new integrable lattice hierarchy is constructed from a discrete matrix spectral problem, some related properties of the new hierarchy are discussed. The Hamiltonian structures and Liouville integrability of the new hierarchy are established by using the discrete trace identity. A kind of integrable coupling for the new hierarchy is constructed through enlarging spectral problems. A Darboux transformation (DT) with two variable parameters and the infinitely many conservation laws for a typical lattice equation in the new hierarchy are constructed based on its Lax representation, the explicit solutions are obtained via the DT, the structures for those solutions are graphically investigated. All these properties might be helpful to understanding some physical phenomena.     

A locality-preserving cache-oblivious dynamic dictionary

This paper presents a simple dictionary structure designed for a hierarchical memory. The proposed data structure is cache-oblivious and locality-preserving. A cache-oblivious data structure has memory performance optimized for all levels of the memory hierarchy even though it has no memory-hierarchy-specific parameterization. A locality-preserving dictionary maintains elements of similar key values stored close together for fast access to ranges of data with consecutive keys.The data structure presented here is a simplification of the cache-oblivious B-tree of Bender, Demaine, and Farach-Colton. The structure supports search operations on N data items using O(log_BN+1) block transfers at a level of the memory hierarchy with block size B. Insertion and deletion operations use O(log_BN+log²N/B+1) amortized block transfers. Finally, the data structure returns all k data items in a given search range using O(log_BN+k/B+1) block transfers.This data structure was implemented and its performance was evaluated on a simulated memory hierarchy. This paper presents the results of this simulation for various combinations of block and memory sizes.     

Hyperspheric Integer Programming

This paper develops an efficient method for finding the optimal solution to linear mathematical programs on 0–1 variables. It is shown that the lattice (0–1) points satisfying some linear constraint of dimension n can equally be represented by those lying in a hypersphere of the same dimension. The lattice points satisfying two linear constraints can be represented by a hypersphere which contains the intersection of the hyperspheres of the two constraints. The method for finding the optimal solution consists of enumerating lattice points which are close to the center of the hypersphere corresponding to the constraints. As soon as a better value of the objective function has been found, than some lower bound, we find a new hypersphere which contains the lattice points of the constraints at which the objective function remains higher than the best known value. We continue in this manner until we have at some stage enumerated all lattice points within a given hypersphere and found none which give a better value.     

Rational points of lattice ideals on a toric variety and toric codes

We show that the number of rational points of a subgroup inside a toric variety over a finite field defined by a homogeneous lattice ideal can be computed via Smith normal form of the matrix whose columns constitute a basis of the lattice. This generalizes and yields a concise toric geometric proof of the same fact proven purely algebraically by Lopez and Villarreal for the case of a projective space and a standard homogeneous lattice ideal of dimension one. We also prove a Nullstellensatz type theorem over a finite field establishing a one to one correspondence between subgroups of the dense split torus and certain homogeneous lattice ideals. As application, we compute the main parameters of generalized toric codes on subgroups of the torus of Hirzebruch surfaces, generalizing the existing literature.     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

基本概念格的数据扩展及相容性判定问题

数据分析在计算机数据处理中占有重要地位.概念格理论是数据分析有力工具,本文以概念格为工具,讨论数据扩展而引起的相容性问题.主要是将数据作为概念格中的对象,在给定数据基本集并假设数据特征一定的条件下,考虑数据扩展相容性问题,解决了数据扩展的相容性判定问题并给出了相应的判定定理.目的是使在特征一定的情况下,数据对象达到最大化.     

约束KP系列的广义Wronskian解

Kadomstev-Petviashvili(KP)系列的r-函数能够表示成生成函数的广义Wronskian行列式,这里的生成函数满足一组线性偏微分方程.本文引入一种新的方法把由规范变换Tn+k生成的KP系列约化到M(相似文献