(p,q)-Logical completeness for output-coherent sets of (p,q)-Logical functions and an application of the set to image processing

We have previously proposed an idea of p-valued input, q-valued output threshold logic to synthesize many-valued, p-valued, logical networks, and derived the condition for (p, q)-logical completeness for the output-closed set of (p, q)-logical functions. In this paper, the condition for (p, q)-logical completeness for the output-coherent set F of (p, q)-logical functions is described, and the proof is given in almost the same way as for the output-closed set. The output-coherent set F is applied to image processing. That is, a restoration scheme is described for images to which normal random noise is added.     

Parallel algorithms for planar dominance counting

Given n points in the plane the planar dominance counting problem is to determine for each point the number of points dominated by it. Point p is said to dominate point q if x(q)x(p) and y(q)y(p), when x(p) and y(p) are the x− and y-coordinate of p, respectively. We present two CREW PRAM parallel algorithms for the problem, one running in O(log n loglog n) time and and the other in O(lognloglogn/logloglogn) time both using O(n) processors. Some applicationsare also given.     

Experimental numerical studies on a supercomputer of natural convection in an enclosure with localized heating

We present particle simulations of natural convection of a symmetrical, nonlinear, three-dimensional cavity flow problem. Qualitative studies are made in an enclosure with localized heating. The assumption is that particles interact locally by means of a compensating Lennard-Jones type force F, whose magnitude is given by −G/r^p + H/r^q.

In this formula, the parameters G, H, p, q depend upon the nature of the interacting particles and r is the distance between two particles. We also consider the system to be under the influence of gravity. Assuming that there are n particles, the equations relating position, velocity and acceleration at time t_k = kΔt, K = 0, 1, 2, …, are solved simultaneously using the “leap-frog” formulas. The basic formulas relating force and acceleration are Newton's dynamical equations F_i,k = m_ia_i,k, I = 1, 2, 3, …, n, where m_i is the mass of the ith particle.

Extensive and varied computations on a CRAY X - MP/24 are described and discussed, and comparisons are made with the results of others.     

Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

An asymptotic theory for recurrence relations based on minimization and maximization

We derive asymptotic approximations for the sequence f(n) defined recursively by f(n)=min_1j<n {f(j)+f(n−j)}+g(n), when the asymptotic behavior of g(n) is known. Our tools are general enough and applicable to another sequence F(n)=max_1j<n {F(j)+F(n−j)+min{g(j),g(n−j)}}, also frequently encountered in divide-and-conquer problems. Applications of our results to algorithms, group testing, dichotomous search, etc. are discussed.     

Learning counting functions with queries

We investigate the problem of learning disjunctions of counting functions, which are general cases of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the domain Z_qⁿ (or Zⁿ) for any given integer q 2 is polynomial time learnable using at most n + 1 equivalence queries, where the hypotheses issued by the learner are disjunctions of at most n counting functions with weights from Z_p. In general, a counting function may have a composite modulus. We prove that, for any given integer q 2, over the domain Z₂ⁿ, the class of read-once disjunctions of Boolean-weighted counting functions with modulus q is polynomial-time learnable with only one equivalence query and O(n^q) membership queries.     

The symmetric all-furthest- neighbor problem

Given a set of n points on the plane, a symmetric furthest-neighbor (SFN) pair of points p, q is one such that both p and q are furthest from each other among the points in . A pair of points is antipodal if it admits parallel lines of support. In this paper it is shown that a SFN pair of is both a set of extreme points of and an antipodal pair of . It is also shown that an asymmetric furthest-neighbor (ASFN) pair is not necessarily antipodal. Furthermore, if is such that no two distances are equal, it is shown that as many as, and no more than, n/2 pairs of points are SFN pairs. A polygon is unimodal if for each vertex p_k, k = 1,…,n the distance function defined by the euclidean distance between p_k and the remaining vertices (traversed in order) contains only one local maximum. The fastest existing algorithms for computing all the ASFN or SFN pairs of either a set of points, a simple polygon, or a convex polygon, require 0(n log n) running time. It is shown that the above results lead to an 0(n) algorithm for computing all the SFN pairs of vertices of a unimodal polygon.     

On the type of a polynomial f, when f(0)f−f(0)f is a monomial

A polynomial is said to be of type (p₁, p₂, p₃) relative to a directed line in the complex plane if, counting multiplicities, it has p₁ zeros to the left of, p₂ zeros on, and p₃ zeros to the right of the line. In this paper we determine explicitly the types of all polynomials belonging to a very restricted (but infinite) family of polynomials. A polynomial ƒ belongs to this family if and only if its coefficients are such that the polynomial ƒ^*(0)ƒ(z)−ƒ(0) ƒ^*(z) is a monomial; here ƒ^* denotes the reflection of ƒ in the directed line.

A special case of the present result appeared in an earlier publication.     

Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”

Rush Hour is a children's game that consists of a grid board, several cars that are restricted to move either vertically or horizontally (but not both), a special target car, and a single exit on the perimeter of the grid. The goal of the game is to find a sequence of legal moves that allows the target car to exit the grid. We consider a slightly generalized version of the game that uses an n×n grid and assume that we can place the single exit and target car at any location we choose on initialization of the game.

In this work, we show that deciding if the target car can legally exit the grid is PSPACE-complete. Our constructive proof uses a lazy form of dual-rail reversible logic such that movement of “output” cars can only occur if logical combinations of “input” cars can also move. Emulating this logic only requires three types of devices (two switches and one crossover); thus, our proof technique can be easily generalized to other games and planning problems in which the same three primitive devices can be constructed.     

ANTS: Agents on Networks, Trees, and Subgraphs

Efficient exploration of large networks is a central issue in data mining and network maintenance applications. In most existing work there is a distinction between the active ‘searcher’ which both executes the algorithm and holds the memory and the passive ‘searched graph’ over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavily-loaded, call for a different paradigm, in which a noncentralized group of one or more lightweight autonomous agents traverse the network in a completely distributed and parallelizable way. Potential advantages of such a paradigm would be fault tolerance against network and agent failures, and reduced load on the busy nodes due to the small amount of memory and computing resources required by the agent in each node. Algorithms for network covering based on this paradigm could be used in today’s Internet as a support for data mining and network control algorithms. Recently, a vertex ant walk ( ) method has been suggested [I.A. Wagner, M. Lindenbaum, A.M. Bruckstein, Ann. Math. Artificial Intelligence 24 (1998) 211–223] for searching an undirected, connected graph by an a(ge)nt that walks along the edges of the graph, occasionally leaving ‘pheromone’ traces at nodes, and using those traces to guide its exploration. It was shown there that the ant can cover a static graph within time nd, where n is the number of vertices and d the diameter of the graph. In this work we further investigate the performance of the method on dynamic graphs, where edges may appear or disappear during the search process. In particular we prove that (a) if a certain spanning subgraph S is stable during the period of covering, then the method is guaranteed to cover the graph within time nd_s, where d_s is the diameter of S, and (b) if a failure occurs on each edge with probability p, then the expected cover time is bounded from above by nd((logΔ/log(1/p))+((1+p)/(1−p))), where Δ is the maximum vertex degree in the graph. We also show that (c) if G is a static tree then it is covered within time 2n.     

Complex random sample scheduling and its application to an N/M/F/Fmax problem

“Complex Random Sample Scheduling(CRSS)” was proposed in this paper as an efficient heuristic method for solving any permutation scheduling problems. To show the effectiveness of the proposed CRSS, it was applied to an N-job, M-machine, permutation flowshop scheduling problem to minimize makespan, N/M/F/F_max. Numerical experiments made it clear that the proposed CRSS provides a schedule very close to the near-optimal schedule obtained by the existing promising heuristic methods such as taboo search and simulated annealing, within less computation time than these heuristic methods.     

Multiple sequence comparison — a peptide matching approach

We present in this paper a peptide matching approach to the multiple comparison of a set of protein sequences. This approach consists in looking for all the words that are common to q of these sequences, where q is a parameter.

The comparison between words is done by using as reference an object called a model. In the case of proteins, a model is a product of subsets of the alphabet Σ of the amino acids. These subsets belong to a cover of Σ, that is, their union covers all of Σ. A word is said to be an instance of a model if it belongs to the model.

A further flexibility is introduced in the comparison by allowing for up to e errors in the comparison between a word and a model. These errors may concern gaps or substitutions not allowed by the cover. A word is said to be this time an occurrence of a model if the Levenshtein distance between it and an instance of the model is inferior or equal to e. This corresponds to what we call a Set-Levenshtein distance between the occurrences and the model itself. Two words are said to be similar if there is at least one model of which both are occurrences. In the special case where e = 0, the occurrences of a model are simply its instances. If a model M has occurrences in at least q of the sequences of the set, M is said to occur in the set.

The algorithm presented here is an efficient and exact way of looking for all the models, of a fixed length k or of the greatest possible length k_max, that occur in a set of sequences. It is linear in the total length n of the sequences and proportional to (e + 2)(2e+ 1)k^e+1p^e+1 g^k where k n is a small value in all practical situations, p is the number of sets in the cover and g is related to the latter's degree of nontransitivity.

Models are closely related to what is called a consensus in the biocomputing area, and covers are a good way of representing complex relationships between the amino acids.     

Optimal and nearly optimal algorithms for approximating polynomial zeros

We substantially improve the known algorithms for approximating all the complex zeros of an n^th degree polynomial p(x). Our new algorithms save both Boolean and arithmetic sequential time, versus the previous best algorithms of Schönhage [1], Pan [2], and Neff and Reif [3]. In parallel (NC) implementation, we dramatically decrease the number of processors, versus the parallel algorithm of Neff [4], which was the only NC algorithm known for this problem so far. Specifically, under the simple normalization assumption that the variable x has been scaled so as to confine the zeros of p(x) to the unit disc x : |x| ≤ 1, our algorithms (which promise to be practically effective) approximate all the zeros of p(x) within the absolute error bound 2^−b, by using order of n arithmetic operations and order of (b + n)n² Boolean (bitwise) operations (in both cases up to within polylogarithmic factors). The algorithms allow their optimal (work preserving) NC parallelization, so that they can be implemented by using polylogarithmic time and the orders of n arithmetic processors or (b + n)n² Boolean processors. All the cited bounds on the computational complexity are within polylogarithmic factors from the optimum (in terms of n and b) under both arithmetic and Boolean models of computation (in the Boolean case, under the additional (realistic) assumption that n = O(b)).     

Deterministic parallel backtrack search

The backtrack search problem involves visiting all the nodes of an arbitrary binary tree given a pointer to its root subject to the constraint that the children of a node are revealed only after their parent is visited. We present a fast, deterministic backtrack search algorithm for a p-processor COMMON CRCW-PRAM, which visits any n-node tree of height h in time O((n/p+h)(logloglogp)²). This upper bound compares favourably with a natural Ω(n/p+h) lower bound for this problem. Our approach embodies novel, efficient techniques for dynamically assigning tree-nodes to processors to ensure that the work is shared equitably among them.     

h- and p-Adaptive boundary element methods

Adaptive boundary element methods and their application to the 2-D potential and elasticity problems are presented in the paper. Based on the theory of approximation, a-posteriori error estimates for the boundary element solution have been developed. Both h-version and p-version are studied. The linear elements are used in the h-version, on the other hand, the hierachical shape functions are employed for the implementation of the p-version. A number of numerical examples are given, demonstrating the success of the techniques developed in this paper.     

Timoshenko beam finite element with four dof and convergence of O(h)

In situations where transverse shear deformations and rotary inertia in beams are important, elements based on the Timoshenko beam theory are useful. Among the two-noded, four DOF elements derived from the minimum total potential energy principle, the HTK. element proposed by Hughes et al. using linear displacement functions for both w and θ and the T1CC4 element proposed by Tessler et al. using quadratic displacement function for w and linear displacement function for θ are well known in the literature. The convergence of the HTK element in the thin beam situation has been too poor due to shear locking but by using selective integration this element can be shown to be equivalent to the T1CC4 element which has a rate of convergence of O(h²). In this paper a five DOF element with w and θ at the end nodes and θ at the middle node and based on the cubic displacement function for w and the quadratic displacement function for θ is first developed. Statically condensing the middle rotational DOF, the well-known (4 × 4) stiffness matrix using the φ-factor defined as φ = 12EI/kGAL² and hitherto obtained only through a flexibility approach or closed-form solution of the governing equations of the Timoshenko beam theory is derived. This element based on cubic displacement function for w has rate of convergence of O(h⁴), is completely free of shear locking and performs equally well in thin as well as thick beam situations.     

Two minimum spanning forest algorithms on fixed-size hypercube computers

Two parallel algorithms for finding minimum spanning forest (MSF) of a weighted undirected graph on hypercube computers, consisting of a fixed number of processors, are presented. One algorithm is suited for sparse graphs, the other for dense graphs. Our design strategy is based on successive elimination of non-MSF edges. The input graph is partitioned equally among different processors, which then repeatedly eliminate non-MSF edges and merge results to gradually construct the desired MSF of the entire graph. Low communication overhead is achieved by restricting the message-flow to between the neighboring processors in the hypercube topology. The correctness of our approach is due to a theorem which states that with total-ordered edges, if an edge of an arbitrary subgraph does not belong to its MSF, then it does not belong to the MSF of the entire graph. For a graph of n vertices and m edges, our first algorithm finds an MSF in O(m log m)/p) time using p processors for p ≤ (mlog m)/n(1+log(m/n)). The second algorithm, efficient for dense graphs, requires O(n²/p) time for p≤n/log n.     

Transient detection with an application to a chemical process

We propose a sequential test procedure for transient detections in a stochastic process which can be expressed as an autoregressive moving average (ARMA) model. Preliminary analysis shows that if an ARMA(p,q) time series exhibits a transient behavior, then its residuals behave as an ARMA(Q,Q) process, where Q ≤ p + q. Based on this fact, we derive a new sequential test to determine when a transient behavior occurs in a given ARMA time series. Simulation experiments conducted in this study show that the proposed test can detect the occurrence of a transient in the ARMA model. We also apply the proposed method to detect transient changes in the pH of an erythromycin salt.