Uniform controllable sets of left-invariant vector fields on compact Lie groups

A set of vector fields on a differentiable manifold M is said to be uniformly completely controllable (u.c.c.) if there exists a nonnegative integer N such that evert pair (p, q) of point of M can be joined by a trajectory, or positive orbit, of which involves at most N switches.

In this article we show that if M is a Lie group G and a set of left-invariant vector fields on G, N must be greater than or equal to dim(G)-1. We also construct sets of vector fields which are uniformly completely controllable in dim(G)-1 switches when G is the Lie group of any compact real form of g and g runs over all classical simple Lie algebras over .     

On the number of occurrences of all short factors in almost all words

We previously proved that almost all words of length n over a finite alphabet A with m letters contain as factors all words of length k(n) over A as n→∞, provided limsup_n→∞ k(n)/log n<1/log m.

In this note it is shown that if this condition holds, then the number of occurrences of any word of length k(n) as a factor into almost all words of length n is at least s(n), where lim_n→∞ log s(n)/log n=0. In particular, this number of occurrences is bounded below by C log n as n→∞, for any absolute constant C>0.     

Moments of conjugacy classes of binary words

For each nonempty binary word w=c₁c₂c_q, where c_i{0,1}, the nonnegative integer ∑_i=1^q (q+1−i)c_i is called the moment of w and is denoted by M(w). Let [w] denote the conjugacy class of w. Define M([w])={M(u): u[w]}, N(w)={M(u)−M(w): u[w]} and δ(w)=max{M(u)−M(v): u,v[w]}. Using these objects, we obtain equivalent conditions for a binary word to be an -word (respectively, a power of an -word). For instance, we prove that the following statements are equivalent for any binary word w with |w|2: (a) w is an -word, (b) δ(w)=|w|−1, (c) w is a cyclic balanced primitive word, (d) M([w]) is a set of |w| consecutive positive integers, (e) N(w) is a set of |w| consecutive integers and 0N(w), (f) w is primitive and [w]St.     

Least adaptive optimal search with unreliable tests

We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the (i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let q_e(m) be the smallest integer q satisfying Berlekamp’s bound . Then at least q_e(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly q_e(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly q_e(m) questions—or equivalently, e-error correcting codes with 2^m codewords of length q_e(m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of q_e(m)−m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, q_e(m)−1 questions do not suffice to find the unknown number, and q_e(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.     

Biinfinite words with maximal recurrent unbordered factors

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ^ωuvu^ω, where u and v are finite words, in terms of its unbordered factors.

The main result of the paper states that the words of the form ^ωuvu^ω are precisely the biinfinite words w=a₋₂a₋₁a₀a₁a₂ for which there exists a pair (l₀,r₀) of integers with l₀<r₀ such that, for every integers ll₀ and rr₀, the factor a_la_l0a_r0a_r is a bordered word.

The words of the form ^ωuvu^ω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences “to the left” in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.     

Fast, long-lived renaming improved and simplified

In the long-lived M-renaming problem, N processes repeatedly acquire and release names ranging over {0, …, M − 1}, where M < N. It is assumed that at most k M processes concurrently request or hold names. Efficient solutions to the long-lived renaming problem can be used to improve the performance of applications in which processes repeatedly perform computations whose time complexity depends on the size of the name space containing the processes that participate concurrently. In this paper, we consider wait-free solutions to the long-lived M -renaming problem that use only read and write instructions in an asynchronous, shared-memory multiprocessor. A solution to long-lived renaming is fast if the time complexity of acquiring and releasing a name once is independent of N. We present a new fast, long-lived (k(k + 1)/2)renaming algorithm that significantly improves upon the time and space complexity of similar previous algorithms, while providing a much simpler solution. We also show that fast, long-lived (2k − 1)-renaming can be implemented with reads and writes. This result is optimal with respect to the size of the name space.     

Computing LOGCFL certificates

The complexity class LOGCFL consists of all languages (or decision problems) which are logspace reducible to a context-free language. Since LOGCFL is included in AC¹, the problems in LOGCFL are highly parallelizable.

By results of Ruzzo (JCSS 21 (1980) 218), the complexity class LOGCFL can be characterized as the class of languages accepted by alternating Turing machines (ATMs) which use logarithmic space and have polynomially sized accepting computation trees. We show that for each such ATM M recognizing a language A in LOGCFL, it is possible to construct an L^LOGCFL transducer T_M such that T_M on input w A outputs an accepting tree for M on w. It follows that computing single LOGCFL certificates is feasible in functional AC¹ and is thus highly parallelizable.

Wanke (J. Algorithms 16 (1994) 470) has recently shown that for any fixed k, deciding whether the treewidth of a graph is at most k is in the complexity-class LOGCFL. As an application of our general result, we show that the task of computing a tree-decomposition for a graph of constant treewidth is in functional LOGCFL, and thus in AC¹.

We also show that the following tasks are all highly parallelizable: Computing a solution to an acyclic constraint satisfaction problem; computing an m-coloring for a graph of bounded treewidth; computing the chromatic number and minimal colorings for graphs of bounded tree- width.     

A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=(V,E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(v) of the destination v has at least k parent pointers. A capacity-k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T₁,T₂,…,T_k are pairwise independent, where tree T_i is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-k acorn A, yielding a k-independent sink tree generating scheme.     

New bounds for multi-label interval routing

Interval routing (IR) is a space-efficient routing method for computer networks. For longest routing path analysis, researchers have focused on lower bounds for many years. For any n-node graph G of diameter D, there exists an upper bound of 2D for IR using one or more labels, and an upper bound of for IR using or more labels. We present two upper bounds in the first part of the paper. We show that for every integer i>0, every n-node graph of diameter D has a k-dominating set of size for . This result implies a new upper bound of for IR using or more labels, where i is any positive integer constant. We apply the result by Kutten and Peleg [8] to achieve an upper bound of (1+)D for IR using O(n/D) or more labels, where is any constant in (0,1). The second part of the paper offers some lower bounds for planar graphs. For any M-label interval routing scheme (M-IRS), where , we derive a lower bound of [(2M+1)/(2M)]D−1 on the longest path for , and a lower bound of [(2(1+δ)M+1)/(2(1+δ)M)]D, where δ(0,1], for . The latter result implies a lower bound of on the number of labels needed to achieve optimality.     

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.     

A transformation strategy for implementing distributed, multilayer feedforward neural networks: Backpropagation transformation

Most artificial neural networks (ANNs) have a fixed topology during learning, and often suffer from a number of shortcomings as a result. Variations of ANNs that use dynamic topologies have shown ability to overcome many of these problems. This paper introduces location-independent transformations (LITs) as a general strategy for implementing distributed feed forward networks that use dynamic topologies (dynamic ANNs) efficiently in parallel hardware. A LIT creates a set of location-independent nodes, where each node computes its part of the network output independent of other nodes, using local information. This type of transformation allows efficient support for adding and deleting nodes dynamically during learning. In particular, this paper presents a LIT that supports both the standard (static) multilayer backpropagation network, and backpropagation with dynamic extensions. The complexity of both learning and execution algorithms is O(q(Nlog M)) for a single pattern, where q is the number of weight layers in the original network, N the number of nodes in the widest node layer in the original network, and M is the number of nodes in the transformed network (which is linear in the number hidden nodes in the original network). This paper extends previous work with 2-weight-layer backpropagation networks.     

The p-valued-input, q-valued-output threshold logic and the (p, q)-polypheck-like function

We have previously proposed a concept of p-valued-input, q-valued-output threshold logic, namely (p, q)-threshold logic, where 2 qp, 3p, and suggested that p-valued logical networks with costs as low as those of 2-valued logical networks could be obtained, by using the (p, q)-threshold elements with small values of q. In this paper, we describe (1) the condition under which there is a 2-place (p, q)-adic function such that the output-closed set F, generated only from , is (p, q)-logically complete, and (2) the fact that any n-place(p, q)-adic function can be realized using at most O(n) elements in the above F.     

Efficient algorithms for single- and two-layer linear placement of parallel graphs

This paper outlines an algorithm for optimum linear ordering (OLO) of a weighted parallel graph with O(n log k) worst-case time complexity, and O(n + k log(n/k) log k) expected-case time complexity, where n is the total number of nodes and k is the number of chains in the parallel graph. Next, the two-layer OLO problem is considered, where the goal is to place the nodes linearly in two routing layers minimizing the total wire length. The two-layer problem is shown to subsume the maxcut problem and a befitting heuristic algorithm is proposed. Experimental results on randomly generated samples show that the heuristic algorithm runs very fast and outputs optimum solutions in more than 90% instances.     

A modified and parallelized Viterbi algorithm on hypercube machines

A Viterbi Algorithm is formally modified to select a set of k state sequences with top a posteriori probabilities, where k is a prespecified positive integer. A hypercube parallel algorithm is then developed along with a performance evaluation.     

Classifying molecular sequences using a linkage graph with their pairwise similarities

This paper presents a method for classifying a large and mixed set of uncharacterized sequences provided by genome projects. As the measure of sequence similarity, we use similarity score computed by a method based on the dynamic programming (DP), such as the Smith-Waterman local alignment algorithm. Although comparison by DP based method is very sensitive, when given sequences include a family of sequences that are much diverged in evolutionary process, similarity among some of them may be hidden behind spurious similarity of some unrelated sequences. Also the distance derived from the similarity score may not be metric (i.e., triangle inequality may not hold) when some sequences have multi-domain structure. To cope with these problems, we introduce a new graph structure called p-quasi complete graph for describing a family of sequences with a confidence measure. We prove that a restricted version of the p-quasi complete graph problem (given a positive integer k, whether a graph contains a 0.5-quasi complete subgraph of which size k or not) is NP-complete. Thus we present an approximation algorithm for classifying a set of sequences using p-quasi complete subgraphs. The effectiveness of our method is demonstrated by the result of classifying over 4000 protein sequences on the Escherichia coli genome that was completely determined recently.     

(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.     

基于平行语料和翻译概率的多语种词对齐方法

为了实现多语种词对齐,该文提出一种以点互信息为基础的翻译概率作为改进的多语种单词关联强度度量方法。首先,论证了在服从Zipf定律的普通频级词区域,单词间关联强度的点互信息度量法可简化为翻译概率;其次,对汉语、英语、朝鲜语平行语料进行句子对齐、分词和去停用词等预处理后计算平行语料单词之间的翻译概率,取翻译概率最高的前k个词作为候选翻译词,并通过优化处理提高了词对齐准确率。实验结果表明,该方法可以不完全依赖语料规模,在小规模语料中取得94%以上的准确率,为跨语言小众文献及低资源语言词对齐提供了技术基础。     

On the power of alternation on reversal-bounded alternating Turing machines with a restriction

Whether or not there is a difference of the power among alternating Turing machines with a bounded number of alternations is one of the most important problems in the field of computer science. This paper presents the following result: Let R(n) be a space and reversal constructible function. Then, for any k 1, we obtain that the class of languages accepted by off-line 1-tape rσ_k machines running in reversal O(R(n)) is equal to the class of languages accepted by off-line 1-tape σ₁ machines running in reversal O(R(n)). An off-line 1-tape σ_k machine M is called an off-line 1-tape rσ_k machine if M always limits the non-blank part of the work-tape to at most O(R(n) log n) when making an alternation between universal and existential states during the computation.     

Uniqueness theorems on meromorphic functions sharing one value

In this paper, we study with a weighted sharing method the uniqueness problem of [fⁿ(z)]^(k) and [gⁿ(z)]^(k) sharing one value and obtain some results which extend the theorems given by M. Fang, S. Bhoosnurmath and S. Dyavanal et al.