First-order spectra with one binary predicate

The spectrum, Sp(), of a sentence is the set of cardinalities of finite structures which satisfy . We prove that any set of integers which is in Func₁^∞, i.e. in the class of spectra of first-order sentences of type containing only unary function symbols, is also in BIN¹, i.e. in the class of spectra of first-order sentences of type involving only a single binary relation.

We give similar results for generalized spectra and some corollaries: in particular, from the fact that the large complexity class _cNTIME_RAM(cn) is included in Func₁^∞ for unary languages (n denotes the input integer), we deduce that the set of primes and many “natural” sets belong to BIN¹.

We also give some consequences for the image of spectra under polynomials of .     

Séparateurs dans les mots infinis engendrés par morphismes

Let x be an infinite word on a finite alphabet A. For each position n, the separator of x at n is the smallest factor of x which begins at index n and that does not appear before in x. Let S_x be the function such that S_x(n) is the length of the separator of x at index n if it exists and otherwise 0.

We consider the problem of computing S_x in the case where x is generated by iterating a morphism σ : A* → A*. We prove the following theorem:     

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.     

On symmetric differences of NP-hard sets with weakly P-selective sets

The symmetric differences of NP-hard sets with weakly-P-selective sets are investigated. We show that if there exist a weakly-P-selective set A and an NP-^P_m-hard set H such that H - AεP_btt(sparse) and A — HεP_m(sparse) then P = NP. So no NP-^P_m-hard set has sparse symmetric difference with any weakly-P-selective set unless P = NP. The proof of our main result is an interesting application of the tree prunning techniques (Fortune 1979; Mahaney 1982). In addition, we show that there exists a P-selective set which has exponentially dense symmetric difference with every set in P_btt(sparse).     

A complete algebraic solvability test for the nonstrict Lyapunov inequality

For arbitrary equally sized square complex matrices A and Q (Q Hermitian), the paper provides a complete algebraic test for verifying the existence of a Hermitian solution X of the nonstrict Lyapunov inequality A^*X + XA + Q 0. If existing, we exhibit how to construct a solution. Our approach involves the validation problem for the linear matrix inequality Σ_j=1^k (A_j^*X_jB_j + B_j^*X_j^*A_j) + Q> 0 in X_j, for which we provide an algebraic solvability test and a construct solutions if the kernels of A_j or, dually, those of B_j form an isotonic sequence.     

Solvable black-box group problems are low for PP

Let B = B_mm>0 be a countable family of finite groups whose elements are uniquely encoded as strings of uniform length, and group operations are computable in time bounded by a polynomial in m. A black-box group over a group family B is a subgroup of some member of B and is presented by a generator set. In this paper we study the complexity of several algorithmic problems for abelian black-box groups and solvable black-box groups.

We design a suitable oracle algorithm that computes an independent set of generators for a given abelian black-box group. Using this we show that the problems of Membership Testing, Group Intersection, Order Verification, and Group Isomorphism over abelian black-box groups are in SPP. We also show that Group Factorization, Coset Intersection, and Double Coset Membership problems over abelian black-box groups are in LWPP. As a consequence, all these problems are low for PP and C=P.

We define the notion of canonical generator sets for classes of groups and show that solvable black-box groups have canonical generator sets. We design a suitable randomized oracle algorithm that computes a canonical generator set for a given solvable black-box group. Using this algorithm we show that Membership Testing, Order Verification, and Group Isomorphism for solvable groups are in ZPP^SPP and hence low for PP. We also show that Group Intersection, Group Factorization, Coset Intersection, and Double Coset Membership for solvable groups are low for PP.     

Thermodynamics and phase diagram of the binary system Bi2O3-B2O3

We analyzed the thermodynamic data of the binary system Bi₂O₃-B₂O₃. The phase diagram contains five compounds, of which four melt congruently, and a miscibility gap, close to pure B₂O₃. The three sets of transformation data of Bi₂O₃, the enthalpy of mixing data in the liquid, and the critical point of the miscibility gap gave five equations for the excess Gibbs energy of mixing and five sets of values for the enthalpies of formation of the binary compounds. The critical point data yielded another set of transformation data for Bi₂O₃. Using the monotectic composition and the enthalpy of mixing data also yielded a set of transformation data for Bi₂O₃. The values obtained using the enthalpy of mixing data are the most reliable values.     

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.     

Human Action Recognition by Semilatent Topic Models

We propose two new models for human action recognition from video sequences using topic models. Video sequences are represented by a novel “bag-of-words” representation, where each frame corresponds to a “word.” Our models differ from previous latent topic models for visual recognition in two major aspects: first of all, the latent topics in our models directly correspond to class labels; second, some of the latent variables in previous topic models become observed in our case. Our models have several advantages over other latent topic models used in visual recognition. First of all, the training is much easier due to the decoupling of the model parameters. Second, it alleviates the issue of how to choose the appropriate number of latent topics. Third, it achieves much better performance by utilizing the information provided by the class labels in the training set. We present action classification results on five different data sets. Our results are either comparable to, or significantly better than previously published results on these data sets.     

用广义选择性神经网络集成预测MHC-II分子结合肽

MHC II类分子结合肽的预测对于免疫研究和疫苗设计非常重要,然而其结合肽长度的可变性等原因使其预测变得极为困难,提出了一种基于广义选择性神经网络集成的MHC II分子结合肽预测算法,该算法是一种双层集成模型。第一层是用微分进化算法去生成初始神经网络集成池,第二层是从初始神经网络集成池中选择部分组成最终的神经网络集成。实验结果表明广义选择性神经网络集成比传统的选择性神经网络有更好的泛化性能。     

Computation of generalised inverse of a special class of matrices

The computation of the generalised Inverse A⁺ of matrix A depends critically of the rank of A and involves several matrix multiplications. It is shown here that if A is of the form where A_i are now vectors, then A⁺ can be computed efficiently and accurately by a simple algebraic method.     

Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

An approximate A algorithm and its application to the SCS problem

In this paper we deal with algorithm A^* and its application to the problem of finding the shortest common supersequence of a set of sequences. A^* is a powerful search algorithm which may be used to carry out concurrently the construction of a network and the solution of a shortest path problem on it. We prove a general approximation property of A^* which, by building a smaller network, allows us to find a solution with a given approximation ratio. This is particularly useful when dealing with large instances of some problem. We apply this approach to the solution of the shortest common supersequence problem and show its effectiveness.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.