New architectures for constructed complex systems

This paper is an overview of our research program in intelligent systems. Our object of study is constructed complex systems, which are software and hardware systems mediated or managed by computers. We describe how biological systems provide stiff competition for constructed complex systems in the areas of autonomy and intelligence, robustness, adaptability, and communication. We describe our computationally reflective integration infrastructure, called ‘wrappings', and show how it can provide many of the necessary flexibilities. We also describe two directions of research in computational semiotics, which for us means the study of the use of symbols by computing systems. We describe our ‘conceptual categories', which are a method of knowledge representation that supports these flexibilities, and some new results on symbol systems, which leads to some new mathematical questions about what can be represented in formal systems and how they can be extended automatically. These are then combined to describe our architecture, which we are currently in the process of implementing.     

Densities for random balanced sampling

A random balanced sample (RBS) is a multivariate distribution with n components X_k, each uniformly distributed on [-1,1], such that the sum of these components is precisely 0. The corresponding vectors lie in an (n-1)-dimensional polytope M(n). We present new methods for the construction of such RBS via densities over M(n) and these apply for arbitrary n. While simple densities had been known previously for small values of n (namely 2,3, and 4), for larger n the known distributions with large support were fractal distributions (with fractal dimension asymptotic to n as n→∞). Applications of RBS distributions include sampling with antithetic coupling to reduce variance, and the isolation of nonlinearities. We also show that the previously known densities (for n?4) are in fact the only solutions in a natural and very large class of potential RBS densities. This finding clarifies the need for new methods, such as those presented here.     

Probability models for access security system architectures

This paper presents probability models of access control security system architectures. Access control is the process of screening objects; for example people, baggage, entering a secured area in order to detect and prevent entry by threats such as unauthorized personnel, firearms, explosives. A security system architecture consists of device technologies, as well as operational policies and procedures for utilizing the technologies. The probability models are developed based on Type I (a false alarm is given) and Type II (a threat is not detected) errors. The concept of controlled sampling, in which objects may take different paths through the system, is introduced. New architectures consisting of multiple devices and controlled sampling are proposed and analyzed. The results presented indicate that for specific threat levels, multiple-device systems can be identified which outperform single-device systems for certain error probability measures.     

A fast algorithm for balanced sampling

Summary  The cube method (Deville & Tillé 2004) is a large family of algorithms that allows selecting balanced samples with equal or unequal inclusion probabilities. In this paper, we propose a very fast implementation of the cube method. The execution time does not depend on the square of the population size anymore, but only on the population size. Balanced samples can thus be selected in very large populations of several hundreds of thousands of units.     

New constructions for balanced Howell rotations

Howell rotations have been used in bridge tournaments for a long time. But it was not until 1955 that Parker and Mood first gave a rigorous definition of a balanced Howell rotation and began a systematic study of its mathematical properties. Later, Berlekamp and Hwang extended this work to the study of complete balanced Howell rotations (which are special cases of balanced Howell rotations). Surprisingly, even though the concept of balanced Howell rotations precedes that of complete balanced Howell rotations, systematic construction methods have been studied only for the latter. Most of these construction methods use the properties of a Galois field GF(p^γ) where p^γ is a prime power. In this paper, we use the properties of a Galois domain GD(p^γq^s) to construct balanced Howell rotations for n partnerships where n ? 1 is the product of two prime powers satisfying certain conditions. In particular, we construct a balanced Howell rotation for 36 partnerships, this being the smallest number for which the existence of a balanced Howell rotation was not previously known. We also give two composition methods for the constructions of balanced Howell rotations.     

Optimal balanced control for call centers

In this paper we study the optimal assignment of tasks to agents in a call center. For this type of problem, typically, no single deterministic and stationary (i.e., state independent and easily implementable) policy yields the optimal control, and mixed strategies are used. Other than finding the optimal mixed strategy, we propose to optimize the performance over the set of ??balanced?? deterministic periodic non-stationary policies. We provide a stochastic approximation algorithm that allows to find the optimal balanced policy by means of Monte Carlo simulation. As illustrated by numerical examples, the optimal balanced policy outperforms the optimal mixed strategy.     

Bounds for the number of common symbols in balanced and certain partially balanced designs

We secure inequalities on submatrices of N′N, where N is the incidence matrix of certain designs. These inequalities are then compared with other results previously known.     

Improved inequalities for balanced incomplete block designs

It is known that there are some lower bounds for the number of blocks in a balanced incomplete block design (BIBD). Especially, Fisher's inequality b?v is well-known for a BIBD with parameters v, b, r, k and λ. Fisher's inequality can be improved upon if one puts additional restrictions on a BIBD. Artificial restrictions are infinite in number so is the number of new bounds. The condition of non-symmetry on the design discussed here is a very simple restriction. The main purpose of this paper is to give improvements of inequalities for BIBDs with the only condition of non-symmetry. Improved inequalities appear to be the best for any non-symmetrical BIBD.     

Some bounds for partially balanced block designs

Bounds on eigenvalues of theC-matrix for a partially balanced block (PBB) design are given together with some bounds on the number of blocks. Furthermore, a certain equiblock-sized PBB design is characterized. These results contain, as special cases, the known results for variance-balanced block designs and so on.     

A multiplication theorem for balanced howell rotations

The concept of partitionable starters is introduced and it is shown how to construct: a balanced Howell rotation on mn players from a balanced Howell rotation on n players, a balanced Howell rotation on m players, and a partitionable starter on m players. Two results concerning the existence of partitionable starters are proved     

Empirical likelihood for balanced ranked-set sampled data

Ranked-set sampling (RSS) often provides more efficient inference than simple random sampling (SRS). In this article, we propose a systematic nonparametric technique, RSS-EL, for hypothesis testing and interval estimation with balanced RSS data using empirical likelihood (EL). We detail the approach for interval estimation and hypothesis testing in one-sample and two-sample problems and general estimating equations. In all three cases, RSS is shown to provide more efficient inference than SRS of the same size. Moreover, the RSS-EL method does not require any easily violated assumptions needed by existing rank-based nonparametric methods for RSS data, such as perfect ranking, identical ranking scheme in two groups, and location shift between two population distributions. The merit of the RSS-EL method is also demonstrated through simulation studies. This work was supported by National Natural Science Foundation of China (Grant No. 10871037)     

Perspectives of data-flow architectures

For about forty years now, computer architecture design has followed the Von Neumann principles. By added features, e.g. pipelined processor organisation, vector/array-processing, multiprocessing and today's technology we are looking at supercomputer designs, which may have scalar performance of several hundred Mflops and vector performance of thousands of Mflops but the design space of Von Neumann-type computers seems to be exploited and hardware technology is assumed to reach a point at which physical constraints limit further performance improvements.Therefore, it is growingly accepted that non-Von Neumann models of computation are necessary to exploit program concurrency. A highly promising part of current research on concurrent computer organisation is focused on two principles, which are distinguished by the way computations manipulate their arguments and by the way the execution of computations is initiated: Pure data-driven schemes and schemes which combine data-driven and demand-driven computation.Both schemes seem suited to support a project Guiding Land Vehicles along Roadways by Computer Vision.     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

On balanced bases

It is proved that either a given balanced basis of the algebra (n + 1)M₁ M_n or the corresponding complementary basis is of rank n + 1. This result enables us to claim that the algebra (n + 1)M₁ M_n is balanced if and only if the matrix algebra M_n admits a WP-decomposition, i.e., a family of n + 1 subalgebras conjugate to the diagonal algebra and such that any two algebras in this family intersect orthogonally (with respect to the form tr XY) and their intersection is the trivial subalgebra. Thus, the problem of whether or not the algebra (n + 1)M₁ M_n is balanced is equivalent to the well-known Winnie-the-Pooh problem on the existence of an orthogonal decomposition of a simple Lie algebra of type A_n–1 into the sum of Cartan subalgebras.