Sequence analysis is an important research method in bioinformatics. Constant time solutions on BSR can be found in the literature to many applications. In this paper, some problems of sequence analysis are involved, and the constant time solutions on BSR to them are proposed, which is the first constant time solutions to the problems on any model of computation

Constant time solutions on BSR can be found in the literature to many applications, such as parenthesis matching, tree decoding, tree reconstruction, and etc. However, the problem of encoding a tree in constant time on BSR is still open. In this paper, some properties will be discussed on binary search trees and the i-p sequence, and based on the properties, a constant time algorithm on BSR is proposed for encoding a binary search tree into its i-p sequence, which is the first constant time solution to the problem on any model of computation.

Takaoka has recently proposed two loopless algorithms for generating well formed parenthesis strings with length $2n$ and combinations $\mathcal{C}(r,n)$ of $n$ elements out of $r$ elements, respectively. O(1) time algorithms for generating $\mathcal{C}(r,n)$ in canonical representation that were found in the literature cannot list combinations with the Strong Minimal Change Property (SMCP), Eades and McKay's algorithm can generate $\mathcal{C}(r,n)$ in canonical representation with SMCP, but needs O$(n)$ worst-case time per combination. In this paper, we mainly discuss some orders with SMCP for $\mathcal{C}(r,n)$ in canonical representation, and give a loopless algorithm to generate $\mathcal{C}(r,n)$ in canonical representation with SMCP. We also give a loopless algorithm to list well formed parenthesis strings with length $2n$. Our two algorithms are more efficient in both space and time than Takaoka's two algorithms, respectively. In addition, our algorithms can be modified easily to generate objects in some different orders.

Constant time solutions for many applications have been obtained on BSR, but some theoretical problems on BSR (broadcasting with selective reduction) that raised when BSR was proposed have not been solved. Three of them are: 1) No lower bound for any problem on BSR is known except trivial constant time, 2) is there any improvement with nonconstant BSR time but still better than the lower bound for CRCW?, and 3) how to characterize problems for which BSR achieves constant time performance. In this paper, we have solved these three problems. For Problem 1, a lower bound on BSR is shown for any computational problem with an optimal sequential solution. An efficient sorting algorithm answers the second problem. A necessary condition is given for the third problem. The work-time (WT) scheduling principle and optimality for BSR are also introduced for investigating the BSR performance when the number of processors available, p, is different from the input size, n, of problems.

A recursive algorithm GenWordsR and a non-recursive algorithm GenWordsNR are presented in this paper to generate sequences for regular k-ary trees efficiently. They are compared with some of the previous recursive and non-recursive algorithms for this problem that were found in the literature. When the average number of recursive calls is used as a measure of the time complexity of recursive algorithms for generating k-ary trees, O(k) calls for a k-ary tree is the bestresult in the previous recursive algorithms, while O(1/k) calls for a k-ary tree is needed by GenWordsR. When the average number of comparisons is used as a measure of the time complexity of non-recursive algorithms for generating k-ary trees, GenWordsNR outperforms the previous non-recursive algorithms. As k increases, the number (and the average number) of comparisons performed by GenWordsNR tends to 66% that of the best previous non-recursive algorithms.

BSR (Broadcasting with Selective Reduction) is a PRAM more powerful than any CRCW PRAM. In order to extend the Broadcast Instruction of BSR and make it more useful for a large class of applications, this article permits it to use a general form of selection, specifically, an arbitrary relational expression. BSR with general selection is denoted by BSR/sup +/. Thus, BSR or BSR with k criteria (k>1) is BSR/sup +/ in a special case. An efficient implementation for the Broadcast Instruction of BSR/sup +/ is proposed, requiring (1/k)th of the circuits used by the best previous implementation of BSR with k criteria. Of all PRAMs, BSR/sup +/ is the most powerful in computation.

In contrast to traditional integer sequences for the representation of binary trees, a kind of character sequence (words) is presented for binary trees based on a grammar GBT and for full binary trees based on a grammar GFBT. The properties of words derived from GBT (GFBT) are discussed in depth, including necessary and sufficient conditions for a word, prefix and suffix of Ł(GBT) (Ł(GFBT)) and algorithms are given and analysed for the enumeration of words of Ł(GBT) (Ł(GFBT)) lexicographically and in other ways. By modifying an algorithm for the enumeration of words in Ł(GBT), an algorithm is obtained to enumerate binary trees with a computer representation in an average time of O(1) per tree. The problem with non-isomorphic series of binary trees is also discussed within the category of a grammar.