International Journal of Foundations of Computer Science

Given a string s on an alphabet Σ, a word-length k and a budget D, we want to determine the smallest number of distinct k-mers that can be left in s, if we are allowed to replace up to D letters of s. This problem has several parameters, and we discuss its complexity under all sorts of restrictions on the parameters values. We prove that some versions of the problem are polynomial, while others are NP-hard. We also introduce some Integer Programming formulations to model the NP-hard cases.

Hidden Markov models (HMMs) are effective tools to detect series of statistically homogeneous structures, but they are not well suited to analyse complex structures. Numerous methodological difficulties are encountered when using HMMs to segregate genes from transposons or retroviruses, or to determine the isochore classes of genes. The aim of this paper is to analyse these methodological difficulties, and to suggest new tools for the exploration of genome data. We show that HMMs can be used to analyse complex genes structures with bell-shaped distributed lengths, modelling them by macro-states. Our data processing method, based on discrimination between macro-states, allows to reveal several specific characteristics of intronless genes, and a break in the homogeneity of the initial coding exons. This potential use of markovian models to help in data exploration seems to have been underestimated until now, and one aim of our paper is to promote this use of Markov modelling.

A fundamental problem in music is to classify songs according to their rhythm. A rhythm is represented by a sequence of “Quick” (Q) and “Slow” (S) symbols, which correspond to the (relative) duration of notes, such that S = 2Q. In this paper, we present an efficient algorithm for locating the maximum-length substring of a music text t that can be covered by a given rhythm r.

Table-driven (TD) DFA-based string processing algorithms are examined from a number of vantage points. Firstly, various strategies for implementing such algorithms in a cache-efficient manner are identified. The denotational semantics of such algorithms is encapsulated in a function whose various arguments are associated with each implementation strategy. This formal view of the implementation strategies suggests twelve different algorithms, each blending together the implementation strategies in a particular way. The performance of these algorithms is examined in against a set of artificially generated data. Results indicate a number of cases where the new algorithms outperform the traditional TD algorithm.

We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the indexation. The data structure presented is based on the suffix tree and indexes all the gapped-factors of a text with a fixed size of gap, and only those. The construction of this data structure is done online in linear time and space. Such a data structure may play an important role in various pattern matching and motif inference problems, for instance in text filtration.

Multilingual text compression exploits the existence of the same text in several languages to compress the second and subsequent copies by reference to the first. We explore the details of this framework and present experimental results for parallel English and French texts.

We present some combinatorial problems which arise in the fields of music representation and music processing, in particular in the context of analysis of the harmonic structure of chord sequences. We are mainly concerned with problems related to chord sequences which exhibit a certain kind of regular harmonic structure, and provide also algorithms to solve some of them. In particular, we present an -time algorithm, based on bit-parallelism, to check whether a given chord progression of length n is regular, where m is the size of the chords in the progression.

In this paper two concurrent versions of Brzozowski's deterministic finite automaton (DFA) construction algorithm are developed from first principles, the one being a slight refinement of the other. We rely on Hoare's CSP as our notation.

The specifications that are proposed of the Brzozowski algorithm are in terms of the concurrent composition of a number of top-level processes, each participating process itself composed of several other concurrent processes. After considering a number of alternatives, this particular overall architectural structure seemed like a natural and elegant mapping from the sequential algorithm's structure.

While we have carefully argued the reasons for constructing the concurrent versions as proposed in the paper, there are of course, a large range of alternative design choices that could be made. There might also be scope for a more fine-grained approach to updating sets or checking for similarity of regular expressions. At this stage, we have chosen to abstract away from these considerations, and leave their exploration for a subsequent step in our research.

The Compressed Delta Encoding paradigm is introduced, i.e., delta encoding directly in two given compressed files without decompressing. Here we explore the case where the two given files are compressed using LZW, and devise the theoretical framework for modeling delta encoding of compressed files. In practice, although working on the compressed versions in processing time proportional to the compressed files, our target file may be considerably smaller than the corresponding LZW form.

We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachability labeling algorithm presented by Agrawal et al. (1989), we show that for a random string of length n, its ST-graph can be preprocessed in O(n log n) expected time and space to answer reachability queries in O(log n) time. Furthermore, we present a series of strings that require time and space to answer reachability queries in O(log n) time for the same algorithm. Exhaustive computational calculations for strings of length n ≤ 33 have revealed that the same strings are also the worst case instances of the algorithm. We therefore conjecture that reachability queries can be answered in O(log n) time with a worst case time and space preprocessing complexity of .

We propose new algorithms for (δ,γ,α)-matching. In this string matching problem we are given a pattern P = p₀p₁ … p_m−1 and a text T = t₀t₁ … t_n−1 over some integer alphabet Σ = {0…σ − 1}. The pattern symbol p_i δ-matches the text symbol t_j iff |p_i − t_j| ≤ δ. The pattern P (δ,γ)-matches some text substring t_j … t_j+m−1 iff for all i it holds that |p_i − t_j+i| ≤ δ and Σ |p_i − t_j+i| ≤ γ. Finally, in (δ,γ,α)-matching we also permit at most α-symbol gaps between each matching text symbol. The only known previous algorithm runs in O(nm) time. We give several algorithms that improve the average case up to O(n) for small α, and the worst case to or O(nm log(γ)/w), where and w is the number of bits in a machine word. The proposed algorithms can be easily modified to solve several other related problems, we explicitly consider e.g. character classes (instead of δ-matching), (Δ-limited) k-mismatches (instead of γ-matching) and more general gaps, including negative ones. These find important applications in computational biology. We conclude with experimental results showing that the algorithms are very efficient in practice.

In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at leastL. Such automata can be used in a variety of practical applications, including network security pattern matching, in which false-matches are only a performance nuisance. The construction algorithm is particularly efficient, and is tunable to yield more or less exact automata.

An asymptotic lower bound for the maxrun function ρ(n) = max {number of runs in string x | all strings x of length n} is presented. More precisely, it is shown that for any ε > 0, (α−ε)n is an asymptotic lower bound, where . A recent construction of an increasing sequence of binary strings “rich in runs” is modified and extended to prove the result.

We use singulary vocabularies to analyze first-order definability over doubly-linked data structures. Singulary vocabularies contain only monadic predicate and monadic function symbols. A class of mathematical structures in any vocabulary can be elementarily interpreted in a singulary vocabulary, while preserving notions of total size and degree. Doubly-linked data structures are a special case of bounded-degree finite structures in which there are reciprocal connections between elements, corresponding closely with physically feasible models of information storage. They can be associated with logical models involving unary relations and bijective functions in what we call an invertible singulary vocabulary. Over classes of these models, there is a normal form for first-order logic which eliminates all quantification of dependent variables. The paper provides a syntactically based proof using counting quantifiers. It also makes precise the notion of implicit calculability for arbitrary arity first-order formulas. Linear-time evaluation of first-order logic over doubly-linked data structures becomes a direct corollary. Included is a discussion of why these special data structures are appropriate for physically realizable models of information.

We present an exhaustive analysis of the problem of computing the relative entropy of two probabilistic automata. We show that the problem of computing the relative entropy of unambiguous probabilistic automata can be formulated as a shortest-distance problem over an appropriate semiring, give efficient exact and approximate algorithms for its computation in that case, and report the results of experiments demonstrating the practicality of our algorithms for very large weighted automata. We also prove that the computation of the relative entropy of arbitrary probabilistic automata is PSPACE-complete.

The relative entropy is used in a variety of machine learning algorithms and applications to measure the discrepancy of two distributions. We examine the use of the symmetrized relative entropy in machine learning algorithms and show that, contrarily to what is suggested by a number of publications in that domain, the symmetrized relative entropy is neither positive definite symmetric nor negative definite symmetric, which limits its use and application in kernel methods. In particular, the convergence of training for learning algorithms is not guaranteed when the symmetrized relative entropy is used directly as a kernel, or as the operand of an exponential as in the case of Gaussian Kernels.

Finally, we show that our algorithm for the computation of the entropy of an unambiguous probabilistic automaton can be generalized to the computation of the norm of an unambiguous probabilistic automaton by using a monoid morphism. In particular, this yields efficient algorithms for the computation of the L_p-norm of a probabilistic automaton.

We call a word L-symmetric with respect to a finite language L if it contains the same number of scattered subwords u as of u^R for every word u from L. We show that increasing the size of the language L may lead to an unlimited refinement of the language of L-symmetric words. Further we prove that if a long enough initial segment of a D0L-sequence consists entirely of L-symmetric words, then all words in the sequence are L-symmetric.