International Journal of Foundations of Computer Science

The concepts of alternation and of state alternation are extended from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. For the resulting classes of alternating grammars the expressive power is investigated with respect to the leftmost derivation mode and with respect to the unrestricted derivation mode. In particular new grammatical characterizations for the class of languages that are accepted by alternating pushdown automata are obtained in this way.

We study the problem of scheduling jobs with precedence constraints and present two polynomial time approximation schemes for it. The first one is for the case when the machines are identical and the precedence graph partitions the jobs into groups of fixed size. As an interesting particular case, this yields a polynomial time approximation scheme for scheduling jobs with chain or tree precedence constraints on identical machines, when each chain or tree is of constant size. The second approximation scheme is for scheduling jobs with arbitrarily long chain precedence constraints on uniformly related machines when the number of machines is fixed.

Given two sequences S₁, S₂, and a constrained sequence C, a longest common subsequence of S₁, S₂ with restriction to C is called a constrained longest common subsequence of S₁ and S₂ with C. At the same time, an optimal alignment of S₁, S₂ with restriction to C is called a constrained pairwise sequence alignment of S₁ and S₂ with C. Previous algorithms have shown that the constrained longest common subsequence problem is a special case of the constrained pairwise sequence alignment problem, and that both of them can be solved in O(rnm) time, where r, n, and m represent the lengths of C, S₁, and S₂, respectively. In this paper, we extend the definition of constrained pairwise sequence alignment to a more flexible version, called weighted constrained pairwise sequence alignment, in which some constraints might be ignored. We first give an O(rnm)-time algorithm for solving the weighted constrained pairwise sequence alignment problem, then show that our extension can be adopted to solve some constraint-related problems that cannot be solved by previous algorithms for the constrained longest common subsequence problem or the constrained pairwise sequence alignment problem. Therefore, in contrast to previous results, our extension is a new and suitable model for sequence analysis.

Each day a weather forecaster predicts a probability for each type of weather for the next day. After n days, all the predicted probabilities and the real weather data are sent to a test which decides whether to accept the forecaster as having prior knowledge about the distribution of nature. Consider tests that accept with high probability forecasters who know the distribution of nature. Sandroni shows that any such test can be passed with high probability by a forecaster who has no prior knowledge about the distribution of nature, provided that the duration n is revealed to the forecaster in advance [14]. However, Fortnow and Vohra show that Sandroni's result requires forecasters with high computational complexity [6]. Consider the family of forecasters who select a deterministic Turing-machine forecaster according to an arbitrary distribution and then use that machine for all future forecasts. We show that Sandroni's result requires forecasters even more powerful than those in . We also show that Sandroni's result does not apply when the duration n is not revealed to the forecaster in advance.

A recursive circulant graph G(N,d) has N = cd^m vertices labeled from 0 to N - 1, where d ⩾ 2, m ⩾ 1, and 1 ⩽ c < d, and two vertices x,y ∈ G(N,d) are adjacent if and only if there is an integer k with 0 ⩽ k ⩽ ⌈log_d N⌉ - 1 such that x ± d^k ≡ y (mod N). With the aid of recursive structure, such class of graphs has many attractive features and was considered as a topology of interconnection networks for computing systems. The design of multiple independent spanning trees (ISTs) has many applications in network communication. For instance, it is useful for fault-tolerant broadcasting and secure message distribution. In the previous work of Yang et al. (2009), we provided a constructing scheme to build k ISTs on G(cd^m,d) with d ⩾ 3, where k is the connectivity of G(cd^m,d). However, the proposed constructing rules cannot be applied to the case of d = 2. For the integrity of solving the IST problem on recursive circulant graphs, this paper deals with the case of G(2^m,2) using a set of different constructing rules. Especially, we show that the heights of ISTs for G(2^m,2) are lower than the known optimal construction of hypercubes with the same number of vertices.

We investigate the number of occurrences of a word u as a (scattered) subword of a word w. The notion of a Parikh matrix, recently introduced, is a basic tool in this investigation. In general, several words are associated with a Parikh matrix. The ambiguity can be resolved by associating a unique word called the Lyndon image to each Parikh matrix. In this paper we will investigate properties of Lyndon images and the corresponding questions of ambiguity. We give an exhaustive characterization in the case of a binary alphabet. Our main results in the general case deal with the comparison of unambiguous words and Lyndon images, algorithms for constructing Lyndon images, as well as classes of words with the same Parikh matrix, obtained by circular variance.