On renaming a set of clauses as a Horn set

Let S = {C₁, …, C_m} be a set of clauses in the propositional calculus and let n denote the number of variables appearing these clauses. We present and O(mn) time algorithm to test whether S can be renamed as a Horn set.     

A method of inexact steepest descent for systems of linear equations

Our approach combines the method of inexact steepest descent with the method of contractor directions to obtain an algorithm for solving systems of linear equations. In order to enhance the scope of applicability, we consider an iterative method with variable step-size iterations. We prove the convergence and given an error estimate for our method.

The algorithm is well-suited for parallel computation. In fact, for systems with m equations and n unknowns, each iteration may be computed in parallel time O(log m + log n), on an EREW PRAM with O(mn) processors.     

On the k-path partition of graphs

The k-path partition problem is to partition a graph into the minimum number of paths, so that none of them has length more than k, for a given positive integer k. The problem is a generalization of the Hamiltonian path problem and the problem of partitioning a graph into the minimum number of paths. The k-path partition problem remains NP-complete on the class of chordal bipartite graphs if k is part of the input, and we show that it is NP-complete on the class of comparability graphs even for k=3. On the positive side, we present a polynomial-time solution for the problem, with any k, on bipartite permutation graphs, which form a subclass of chordal bipartite graphs.     

A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs

Many robust control problems can be formulated in abstract form as convex feasibility programs, where one seeks a solution x that satisfies a set of inequalities of the form . This set typically contains an infinite and uncountable number of inequalities, and it has been proved that the related robust feasibility problem is numerically hard to solve in general.

In this paper, we discuss a family of cutting plane methods that solve efficiently a probabilistically relaxed version of the problem. Specifically, under suitable hypotheses, we show that an Analytic Center Cutting Plane scheme based on a probabilistic oracle returns in a finite and pre-specified number of iterations a solution x which is feasible for most of the members of , except possibly for a subset having arbitrarily small probability measure.     

基于序贯线性贝叶斯的RFID标签数量估计算法

为解决现有标签数量估计算法中估计精度与复杂度之间的矛盾,在分析比较现有算法的基础上,提出一种基于序贯线性贝叶斯的射频识别（RFID）标签数量估计算法。首先,基于线性贝叶斯理论,充分利用空闲、成功和碰撞时隙数量观测值及相关性,建立了标签数量估计问题的线性模型;然后,推导了标签数量估计值的闭式表达式,给出了表达式各阶统计量的序贯式求解方法;最后,对序贯式贝叶斯算法的计算复杂度进行了分析和对比。仿真结果表明,所提算法通过序贯贝叶斯方法提高了估计精度和识别效率,当观测时隙数为帧长一半时估计误差仅为4%。该算法以线性解析式形式更新标签数量估计值,避免了穷举搜索,与高精度的最大后验概率和马氏距离算法相比,计算复杂度由O（n²）和O（n）下降为O（1）。经理论分析和仿真验证,基于序贯线性贝叶斯的RFID标签数量估计算法兼具高精度和低复杂度的特性,能很好地满足硬件资源受限应用场景下对标签数量的估计需求。     

Similarity solutions for surface-tension driven flows in a slot with an insulated bottom

We study a two-point boundary values problem (TPBVP) T + Q(Aƒƒ″−(ƒ′)²)=β, ƒ(0)=ƒ(1)=ƒ′(1)=ƒPrime;(0)+1=0, 1A<∞ which arises from a study of similarity transformation for surface-tension drive flows of low Prandtl number fluids in a slot with an insulated bottom. Numerical solutions of the (TPBVP) are found for cases of assumed linear (A = 2) and quadratic (A = 1) radiation of temperature along the free surface. The corresponding bifurcation diagrams in terms of Q and β indicate that multiple solutions occur at some Q when A = 1 and unique solution exists for each Q when A = 2. Some existing properties of the TPBVP when A = 1 and 2, are also verified mathematically.     

Sojourn time distribution in the M/M/1 queue with discriminatory processor-sharing

In this paper, we consider a queue with multiple K job classes, Poisson arrivals, exponentially distributed required service times in which a single processor serves according to the DPS discipline. More precisely, if there are n_i class i jobs in the system, i=1,…,K, each class j job receives a fraction _j/∑_i=1^K_in_i of the processor capacity. For this queue, we obtain a system of equations for joint transforms of the sojourn time and the number of jobs. Using this system of equations we find the moments of the sojourn time as a solution of linear simultaneous equations, which solves an open problem.     

Contrast-optimal k out of n secret sharing schemes in visual cryptography

Visual cryptography and (k,n)-visual secret sharing schemes were introduced by Naor and Shamir (Advances in Cryptology — Eurocrypt 94, Springer, Berlin, 1995, pp. 1–12). A sender wishing to transmit a secret message distributes n transparencies amongst n recipients, where the transparencies contain seemingly random pictures. A (k,n)-scheme achieves the following situation: If any k recipients stack their transparencies together, then a secret message is revealed visually. On the other hand, if only k−1 recipients stack their transparencies, or analyze them by any other means, they are not able to obtain any information about the secret message. The important parameters of a scheme are its contrast, i.e., the clarity with which the message becomes visible, and the number of subpixels needed to encode one pixel of the original picture. Naor and Shamir constructed (k,k)-schemes with contrast 2^−(k−1). By an intricate result from Linial (Combinatorica 10 (1990) 349–365), they were also able to prove the optimality of these schemes. They also proved that for all fixed kn, there are (k,n)-schemes with contrast . For k=2,3,4 the contrast is approximately and . In this paper, we show that by solving a simple linear program, one is able to compute exactly the best contrast achievable in any (k,n)-scheme. The solution of the linear program also provides a representation of a corresponding scheme. For small k as well as for k=n, we are able to analytically solve the linear program. For k=2,3,4, we obtain that the optimal contrast is at least and . For k=n, we obtain a very simple proof of the optimality of Naor's and Shamir's (k,k)-schemes. In the case k=2, we are able to use a different approach via coding theory which allows us to prove an optimal tradeoff between the contrast and the number of subpixels.     

A robustness measure for hypercube networks

Hypercube networks offer a feasible cost-effective solution to parallel computing. Here, a large number of low-cost processors with their own local memories are connected to form an n-cube (B_n) or one of its variants; and the inter-processor communication takes place by message passing instead of shared variables. This paper addresses a constrained two-terminal reliability measure referred to as distance reliability (DR) as it considers the probability that a message can be delivered in optimal time from a given node s to a node t. The problem is equivalent to that of having an operational optimal path (not just any path) between the two nodes. In B_n, the Hamming distance between labels of s and t or H(s, t) determines the length of the optimal path between the two nodes. The shortest distance restriction guarantees optimal communication delay between processors and high link/node utilization across the network. Moreover, it provides a measure for the robustness of symmetric networks. In particular, when H(s, t) = n in B_n, DR will yield the probability of degradation in the diameter, a concept which directly relates to fault-diameter. The paper proposes two schemes to evaluate DR in B_n. The first scheme uses a combinatorial approach by limiting the number of faulty components to (2H(s, t) − 2), while the second outlines paths of length H(s, t) and, then generates a recursive closed-form solution to compute DR. The theoretical results have been verified by simulation. The discrepancy between the theoretical and simulation results is in most cases below 1% and in the worst case 4.6%.     

An Accurate Tag Estimate Method for Improving the Performance of an RFID Anticollision Algorithm Based on Dynamic Frame Length ALOHA

In a radio-frequency identification (RFID) system, the dynamic frame length ALOHA protocol is widely adopted to solve the anticollision problem. Analysis for the anticollision problem can be divided into two primary parts. The concern of the first part is how to precisely estimate the number of tags. The other part involves determination of dynamic frame length to achieve maximum throughput or channel usage efficiency. In this paper, we present an accurate method for estimating tag quantity. This method is based on the maximum a posteriori probability decision. We also derive the optimal frame length using radio channel efficiency. Simulation results indicate the tag estimate error of the proposed method is less than 4%. Use of our proposed tag estimate method together with optimal frame length can achieve close to the theoretical maximum throughput of the framed ALOHA algorithm.     

Modified region decomposition method and optimal depth decision tree in the recognition of non-uniform sized characters – An experimentation with Kannada characters

In contrast to English alphabets, some characters in Indian languages such as Kannada, Hindi, Telugu may have either horizontal or vertical or both the extensions making it difficult to enclose every such character in a standard rectangular grid as done quite often in character recognition research. In this work, an improved method is proposed for the recognition of such characters (especially Kannada characters), which can have spread in vertical and horizontal directions. The method uses a standard sized rectangle which can circumscribe standard sized characters. This rectangle can be interpreted as a two-dimensional, 3×3 structure of nine parts which we define as bricks. This structure is also interpreted as consecutively placed three row structures of three bricks each or adjacently placed three column structures of three bricks each.

It is obvious that non-uniform sized characters cannot be contained within the standard rectangle of nine bricks. The work presented here proposes to take up such cases. If the character has horizontal extension, then the rectangle is extended horizontally by adding one column structure of three bricks at a time, until the character is encapsulated. Likewise, for vertically extended characters, one row structure is added at a time. For the characters which are smaller than the standard rectangle, one column structure is removed at a time till the character fits in the shrunk rectangle. Thus, the character is enclosed in a rectangular structure of m×n bricks where m3 and n1. The recognition is carried out intelligently by examining certain selected bricks only instead of all mn bricks. The recognition is done based on an optimal depth logical decision tree developed during the Learning phase and does not require any mathematical computation.     

Comparing parallel Newton''s method with parallel Laguerre''s method

Newton's and Laguerre's methods can be used to concurrently refine all separated zeros of a polynomial P(z). This paper analyses the rate convergence of both procedures, and its implication on the attainable number n of correct figures. In two special cases the number m of iterations required to reach an accuracy η = 10⁻ⁿ is shown to grow as log_λ n, where λ = 3 for Newton's and λ = 4 for Laguerre's. In the general case m is shown to grow linearly with n for both procedures. An assessment of the efficiency of the two methods is also given, by evaluating the computational complexity of operations in circular arithmetic, and the efficiency indices of the two iterative schemes.     

Parallel clustering algorithms

Clustering techniques play an important role in exploratory pattern analysis, unsupervised learning and image segmentation applications. Many clustering algorithms, both partitional clustering and hierarchical clustering, require intensive computation, even for a modest number of patterns. This paper presents two parallel clustering algorithms. For a clustering problem with N = 2ⁿ patterns and M = 2^m features, the time complexity of the traditional partitional clustering algorithm on a single processor computer is O(MNK), where K is the number of clusters. The proposed algorithm on anSIMD computer with MN processors has a time complexity O(K(n + m)). The time complexity of the proposed single-link hierarchical clustering algorithm is reduced from O(MN²) of the uniprocessor algorithm to O(nN) with MN processors.     

An efficient evolutionary algorithm for accurate polygonal approximation

An optimization problem for polygonal approximation of 2-D shapes is investigated in this paper. The optimization problem for a digital contour of N points with the approximating polygon of K vertices has a search space of C(N, K) instances, i.e., the number of ways of choosing K vertices out of N points. A genetic-algorithm-based method has been proposed for determining the optimal polygons of digital curves, and its performance is better than that of several existing methods for the polygonal approximation problems. This paper proposes an efficient evolutionary algorithm (EEA) with a novel orthogonal array crossover for obtaining the optimal solution to the polygonal approximation problem. It is shown empirically that the proposed EEA outperforms the existing genetic-algorithm-based method under the same cost conditions in terms of the quality of the best solution, average solution, variance of solutions, and the convergence speed, especially in solving large polygonal approximation problems.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Parallel merging: algorithm and implementation results

An efficient parallel algorithm for merging two sorted lists is presented. The algorithm is based on a novel partitioning algorithm that splits the two lists among the processors, in a way that ensures load balance during the merge. The partitioning algorithm can itself be efficiently parallelized, allowing the solution to scale with increased numbers of processors. A shared memory multiprocessor is assumed. The time complexity for partitioning and merging is O(N/p + log N), where p is the number of processors and N is the total number of elements in the two lists. Implementation results on a twenty node Sequent Symmetry multiprocessor are also presented.     

Heaps and heapsort on secondary storage

A heap structure designed for secondary storage is suggested that tries to make the best use of the available buffer space in primary memory. The heap is a complete multi-way tree, with multi-page blocks of records as nodes, satisfying a generalized heap property. A special feature of the tree is that the nodes may be partially filled, as in B-trees. The structure is complemented with priority-queue operations insert and delete-max. When handling a sequence of S operations, the number of page transfers performed is shown to be O(∑_{i = 1}^S(1/P) log_(M/P)(N_i/P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and N_i, the number of records in the heap prior to the ith operation (assuming P 1 and S> M c · P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑_{i = 1}^S log₂ N_i). Using the suggested data structure we obtain an optimal external heapsort that performs O((N/P) log_(M/P)(N/P)) page transfers and O(N log₂ N) comparisons in the worst case when sorting N records.     

Identifying a control function in parabolic partial differential equations from overspecified boundary data

Determination of an unknown time-dependent function in parabolic partial differential equations, plays a very important role in many branches of science and engineering. In the current investigation, the Adomian decomposition method is used for finding a control parameter p(t) in the quasilinear parabolic equation u_t=u_xx+p(t)u+, in [0,1]×(0,T] with known initial and boundary conditions and subject to an additional condition in the form of which is called the boundary integral overspecification. The main approach is to change this inverse problem to a direct problem and then solve the resulting equation using the well known Adomian decomposition method. The decomposition procedure of Adomian provides the solution in a rapidly convergent series where the series may lead to the solution in a closed form. Furthermore due to the rapid convergence of Adomian’s method, a truncation of the series solution with sufficiently large number of implemented components can be considered as an accurate approximation of the exact solution. This method provides a reliable algorithm that requires less work if compared with the traditional techniques. Some illustrative examples are presented to show the efficiency of the presented method.     

Analytical modeling and performance of dual-bus high-speed networks under the Adaptive Cycle Cell Insertion (ACCI) protocol

Adaptive Cycle Cell Insertion (ACCI) is a MAC protocol which has been introduced by Baiocchi et al. in 1990. It was designed for use in high-speed (broadband) MANs utilizing a dual-bus topology and to be compatible for operation in an ATM environment. The performance evaluation of ACCI has been provided in terms of simulations; in addition, the mean access delay was evaluated only for the case of single cells. We present in this paper an analytical model to estimate the average frame delays in a dual-bus network operating under the ACCI protocol. Moreover, the model incorporates the case where the number of cells in a frame is given by a general, positive integer, random variable. Results for several different traffic patterns are presented and the accuracy of the analytical estimates for frame delays at arbitrary stations is compared with simulations.     

Formal energy of symplectic scheme for Hamiltonian systems and its applications (II)

In this paper, for 4-fold and 8-fold compositions of symplectic schemes, the authors obtain the formulae for calculation of the first three terms of the power series in stepsize of their formal energies. Utilizing the special properties of revertible schemes, the authors construct higher order revertible symplectic schemes for general Hamiltonian systems only through formal energies. From any order s (even) to order s + 2, a determining conclusion is obtained. And from any order s (even) to order s + 4, an algebraic equation system, when s is evaluated whose solution gives a rise by 4 in order, is about to be set up. As examples, for the cases of s = 2 and s = 4, the numerical results are to be gained.