International Journal of Foundations of Computer Science

We have been developing a general theory of information distance and a paradigm of applying this theory to practical problems.[3, 19, 20] There are several problems associated with this theory. On the practical side, among other problems, the strict requirement of triangle inequality is unrealistic in some applications; on the theoretical side, the universality theorems for normalized information distances were only proved in a weak form. In this paper, we will introduce a complementary theory that resolves or avoids these problems.

This article also serves as a brief expository summary for this area. We will tell the stories about how and why some of the concepts were introduced, recent theoretical developments and interesting applications. These applications include whole genome phylogeny, plagiarism detection, document comparison, music classification, language classification, fetal heart rate tracing, question answering, and a wide range of other data mining tasks.

We consider the state complexity of several combined operations. Those results show that the state complexity of a combined operation is in general very different from the composition of the state complexities of the participating individual operations. We also consider general estimation methods for the state complexity of combined operations. In particular, estimation through nondeterministic state complexity is studied. It is shown that the method is very promising for a large class of combined operations.

We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of , where is the maximum rank of any symbol in the input alphabet, m is the total size of the transition table, and n is the number of states.

Simple grammar reduction is an important component in the implementation of Concatenation State Machines (a hardware version of stateless push-down automata designed for wire-speed network packet classification). We present a comparison and experimental analysis of the best-known algorithms for grammar reduction. There are two approaches to this problem: one processing compressed strings without decompression and another one which processes strings explicitly. It turns out that the second approach is more efficient in the considered practical scenario despite having worst-case exponential time complexity (while the first one is polynomial). The study has been conducted in the context of network packet classification, where simple grammars are used for representing the classification policies.

This paper addresses the challenges of symbolic model checking and language emptiness checking where the specification is given as an alternating Büchi automaton.

We introduce a novel version of Miyano and Hayashi's construction that allows us to directly convert an alternating automaton to a polynomially-sized symbolic structure. We thus avoid building an exponentially-sized explicit representation of the corresponding nondeterministic automaton.

For one-weak automata, Gastin and Oddoux' construction produces smaller automata than Miyano and Hayashi's construction. We present a (symbolic) hybrid approach that combines the benefits of both: while retaining full generality, it uses the cheaper construction for those parts of the automaton that are one-weak.

We performed a thorough experimental comparison of the explicit and symbolic approaches and several variants of Miyano and Hayashi's construction, using both BDD-based and SAT-based model checking techniques. The symbolic approaches clearly outperform the explicit one.

Extended finite automata are finite state automata equipped with the additional ability to apply an operation on the currently remaining input word, depending on the current state. Hybrid extended finite automata can choose from a finite set of such operations. In this paper, five word operations are taken into consideration which always yield letter-equivalent results, namely reversal and shift operations. The computational power of those machines is investigated, locating the corresponding families of languages in the Chomsky hierarchy. Furthermore, different types of hybrid extended finite automata, defined by the set of operations they are allowed to apply, are compared with each other, demonstrating that there exist dependencies and independencies between the input manipulating operations.

This paper presents an exhaustive analysis of the problem of computing the L_p distance of two probabilistic automata. It gives efficient exact and approximate algorithms for computing these distances for p even and proves the problem to be NP-hard for all odd values of p, thereby completing previously known hardness results. It further proves the hardness of approximating the L_p distance of two probabilistic automata for odd values of p. Similar techniques to those used for computing the L_p distance also yield efficient algorithms for computing the Hellinger distance of two unambiguous probabilistic automata both exactly and approximately.

A problem closely related to the computation of a distance between probabilistic automata is that of testing their equivalence. This paper also describes an efficient algorithm for testing the equivalence of two arbitrary probabilistic automata A₁ and A₂ in time O(|Σ|(|A₁| + |A₂|)³), a significant improvement over the previously best reported algorithm for this problem.

The factor oracle is a relatively new data structure for the set of factors of a string. It has been introduced by Allauzen, Crochemore, and Raffinot in 1999. It may recognize non-factors (hence the name "oracle") but its implementational simplicity and experimental behaviour are stunning; factor oracle based string matching has been conjectured optimal on average. However, its structure is not well understood. We take important steps in clarifying its structure by explaining how it can be obtained as a quotient of the trie of the set of factors. When seen this way, all known properties of the factor oracle become simple observations. Also, we introduce a framework where various oracles can be compared. The factor oracle is better than several natural ones obtained from the trie of the set of factors, the suffix and the factor automata, respectively.

Weighted finite automata (WFA) are used with FPGA accelerating hardware to scan large genomic banks. Hardwiring such automata raises surface area and clock frequency constraints, requiring efficient ∊-transitions-removal techniques. In this paper, we present bounds on the number of new transitions for the development of acyclic WFA, which is a special case of the ∊-transitions-removal problem. We introduce a new problem, a partial removal of ∊-transitions while accepting short chains of ∊-transitions.

We consider forgetting automata, i.e., linear bounded automata which can only use the operations "move", "erase" (rewrite with a blank symbol) and "delete" (remove completely). A classification of the families of languages corresponding to the possible combinations of operations has been given in [1], here we address some of the problems left open. Furthermore the unary case is being investigated.

The basic properties of distributivity and deletion of pure and o-substitution are investigated. The obtained results are applied to show preservation of recognizability in a number of interesting cases. It is proved that linear and recognizable tree series are closed under o-substitution provided that the underlying semiring is commutative, continuous, and additively idempotent. It is known that, in general, pure substitution does not preserve recognizability (not even for linear target tree series), but it is shown that recognizable linear probability distributions (represented as tree series) are closed under pure substitution.

Rational relations are a powerful model used in many domains such as natural language processing. In this article, we propose a new model of finite state automata: multi-tape automata with symbol classes and identity or non-identity constraints. This model generalizes classical multi-tape automata, as well as automata and transducers with extended alphabet. We define this model in terms of a constraint satisfaction problem and discuss a problem occurring when handling the projection operation. Finally, we describe its implementation and results of a performance test.

A border of a string is a prefix of the string that is simultaneously its suffix. It is one of the basic stringology keystones used as a part of many algorithms in pattern matching, molecular biology, computer-assisted music analysis and others.

The paper offers the automata-theoretical description of Iliopoulos's ALL_BORDERS algorithm. The algorithm finds all borders of a string with don't care symbols. We show that ALL_BORDERS algorithm is an implementation of a finite state transducer of specific form. We describe how such a transducer can be constructed and what should be the input string like. The described transducer finds a set of lengths of all borders.

Last but not least, we define approximate borders and show how to find all approximate borders of a string when we concern Hamming distance definition. Our solution of this problem is based on transducers again. This allows us to use analogy with automata-based pattern matching methods. Finally we discuss conditions under which the same principle can be used for other distance measures.

We investigate the open question asking whether there exist independent systems of three equations over three unknowns admitting non-periodic solutions, formulated in 1983 by Culik II and Karhumäki. In particular, we give a negative answer to this question for a large class of systems. More specifically, the question remains open only for a well specified class of systems. We also investigate systems of two equations over three unknowns for which we give necessary and sufficient conditions for admitting at most quasi-periodic solutions, i.e., solutions where the images of two unknowns are powers of a common word. In doing so, we also give a number of examples showing that these conditions represent a boundary point between systems admitting purely non-periodic solutions and those admitting at most quasi-periodic ones.

Degenerate primers are used to amplify a given set of genomic sequences using a technique called Multiplex Polymerase Chain Reaction (MP-PCR). The problem of minimizing the number of degenerate primers required to amplify a given set of DNA sequences, also known as the Degenerate Primer Design Problem (DPDP), has been extensively studied in the literature and proven to be NP-Complete. In this paper we present efficient algorithms for solving DPDP. For example, one of the algorithms we give in this paper is iterative and has a runtime of O(b|Σ|log_|Σ|dn²mp) to select a set of p degenerate primers, each of given length l and degeneracy at most d, for n sequences each of length m in the input, the number of candidates retained in each iteration being b. Σ is the alphabet of the input strings. This is an improvement over the runtime of the best known prior algorithm, MIPS by Souvenir et al. [15], which has a runtime of O(bn³mp). We provide an experimental comparison of MIPS and our algorithms.