International Journal of Foundations of Computer Science

Algorithmic combinatorics on partial words, or sequences of symbols over a finite alphabet that may have some do-not-know symbols or holes, has been developing in the past few years. Applications can be found, for instance, in molecular biology for the sequencing and analysis of DNA, in bio-inspired computing where partial words have been considered for identifying good encodings for DNA computations, and in data compression. In this paper, we focus on two areas of algorithmic combinatorics on partial words, namely, pattern avoidance and subword complexity. We discuss recent contributions as well as a number of open problems. In relation to pattern avoidance, we classify all binary patterns with respect to partial word avoidability, we classify all unary patterns with respect to hole sparsity, and we discuss avoiding abelian powers in partial words. In relation to subword complexity, we generate and count minimal Sturmian partial words, we construct de Bruijn partial words, and we construct partial words with subword complexities not achievable by full words (those without holes).

Hyper-minimization of deterministic finite automata (DFA) is a recently introduced state reduction technique that allows a finite change in the recognized language. A generalization of this lossy compression method to the weighted setting over semifields is presented, which allows the recognized weighted language to differ for finitely many input strings. First, the structure of hyper-minimal deterministic weighted finite automata is characterized in a similar way as in classical weighted minimization and unweighted hyper-minimization. Second, an efficient hyper-minimization algorithm, which runs in time , is derived from this characterization. Third, the closure properties of canonical regular languages, which are languages recognized by hyper-minimal DFA, are investigated. Finally, some recent results in the area of hyper-minimization are recalled.

This paper is a survey on the equational descriptions of languages. The first part is devoted to Birkhoff's and Reiterman's theorems on equational descriptions of varieties. Eilenberg's variety theorem and its successive generalizations form the second part. The more recent results on equational descriptions of lattices of languages are presented in the third part of the paper.

We investigate how two agents can communicate through a noisy medium modeled as a finite non deterministic transducer. The sender and the receiver are also described by finite transducers which can respectively encode and decode binary messages. When the communication is reliable, we call the encoder/decoder pair a channel.

We study the channel synthesis problem which, given a transducer, asks whether or not such sender and receiver exist and builds them if the answer is positive. To that effect we introduce the structural notion of encoding state in a transducer which is a necessary condition for the existence of a channel. It is not, however, a sufficient condition. In fact, we prove that the problem is undecidable. Nonetheless, we obtain a synthesis procedure when the transducer is functional. We discuss these results in relation to security properties.

The quotient complexity, also known as state complexity, of a regular language is the number of distinct left quotients of the language. The quotient complexity of an operation is the maximal quotient complexity of the language resulting from the operation, as a function of the quotient complexities of the operands. The class of star-free languages is the smallest class containing the finite languages and closed under boolean operations and concatenation. We prove that the tight bounds on the quotient complexities of union, intersection, difference, symmetric difference, concatenation and star for star-free languages are the same as those for regular languages, with some small exceptions, whereas 2ⁿ-1 is a lower bound for reversal.

This work continues investigations on avoidability of languages. We show that the language of primitive non-palindromes is strongly unavoidable for context-free languages that are not linear. This means that every language from this class contains infinitely many primitive non-palindromes.

In the second part, we extend the defintion of palindromes. In the center of a word we admit a bounded factor that is not palindromic. For k-palindromes, the length of this factor can be up to k. For non-primitive words, k-palindromicity implies conventional palindromicity if these words are long enough. Therefore we can extend the unavoidability result to k-palindromes.

A bounded language (for some k ≥ 1 and not-necessarily distinct nonempty words x₁, …, x_k) is bounded semilinear if the set is semilinear. We give characterizations of bounded semilinear languages in terms of one-way and two-way deterministic counter machines.

A (non-circular) de Bruijn sequence w of order n is a word such that every word of length n appears exactly once in w as a factor. In this paper, we generalize the concept to different settings: the multi-shift de Bruijn sequence and the pseudo de Bruijn sequence. An m-shift de Bruijn sequence of order n is a word such that every word of length n appears exactly once in w as a factor that starts at a position im + 1 for some integer i ≥ 0. A pseudo de Bruijn sequence of order n with respect to an antimorphic involution θ is a word such that for every word u of length n the total number of appearances of u and θ(u) as a factor is one. We show that the number of m-shift de Bruijn sequences of order n is aⁿ!a^(m-n)(an-1) for 1 ≤ n ≤ m and is (a^m!)^an-m for 1 ≤ m ≤ n, where a is the size of the alphabet. We provide two algorithms for generating a multi-shift de Bruijn sequence. The multi-shift de Bruijn sequence is important for solving the Frobenius problem in a free monoid. We show that the existence of pseudo de Bruijn sequences depends on the given alphabet and antimorphic involution, and obtain formulas for the number of such sequences in some particular settings.

The dot-depth hierarchy is a classification of star-free languages. It is related to the quantifier alternation hierarchy of first-order logic over finite words. We consider subclasses of languages with dot-depth 1/2 and dot-depth 1 obtained by prohibiting the specification of prefixes or suffixes. As it turns out, these language classes are in one-to-one correspondence with fragments of alternation-free first-order logic without min- or max-predicate, respectively. For all fragments, we obtain effective algebraic characterizations. Moreover, we give new proofs for the decidability of the membership problem for dot-depth 1/2 and dot-depth 1.

The main problem for an individual user peer in a peer-to-peer network with heterogeneous source peers is the peer selection problem, namely, switching among source peers and finally settling on one, while keeping the total time of probing and downloading to a minimum. There has been little investigation on selecting source peers with stochastic service capacities. The main contribution of this paper is to address the problem of reducing download times in peer-to-peer file sharing systems with stochastic service capacities. A precise analysis of the expected download time is given when the service capacity of a source peer is a random variable. A chunk-based switching and peer selection algorithm using the method of probing high-capacity peers is proposed and the expected download time of the algorithm is analyzed. Two subproblems of the optimal choice of the threshold of high-capacity source peers and the optimal order of probing are also solved. The performance of the algorithm is compared with the random chunk-based switching method. It is shown that noticeable performance improvement can be obtained.

Abelian periodicity of strings has been studied extensively over the last years. In 2006 Constantinescu and Ilie defined the abelian period of a string and several algorithms for the computation of all abelian periods of a string were given. In contrast to the classical period of a word, its abelian version is more flexible, factors of the word are considered the same under any internal permutation of their letters. We show two O(|y|²) algorithms for the computation of all abelian periods of a string y. The first one maps each letter to a suitable number such that each factor of the string can be identified by the unique sum of the numbers corresponding to its letters and hence abelian periods can be identified easily. The other one maps each letter to a prime number such that each factor of the string can be identified by the unique product of the numbers corresponding to its letters and so abelian periods can be identified easily. We also define weak abelian periods on strings and give an O(|y|log(|y|)) algorithm for their computation, together with some other algorithms for more basic problems.

Let two nonperiodic binary morphisms g,h: {a,b}* → Δ* be given. A word w is called a solution of g and h if g(w)=h(w). We say that a solution w is simple if whenever w₁, w₁u, w₂ and w₂u' are prefixes of w^ω such that

We initiate the study of testing for general forbidden posets in a colored ordered rooted forest whose structure is fixed. First, we consider the case where the forbidden set consists of (ancestral) chains, and second, we consider the case in which it consists of one general ordered rooted forest. For both cases, we provide 1-sided error, non-adaptive tests, whose query complexity is polynomial in ∊^-1 and is independent of the input size and the number of colors. Both tests do not require additional time complexity beyond the complexity of making the queries, except an O(n) time preprocessing stage in the test for a set of chains.