Forbidden factors and fragment assembly

F. Mignosi; A. Restivo; M. Sciortino

Displaying similar documents to “Forbidden factors and fragment assembly”

Efficient validation and construction of border arrays and validation of string matching automata

Jean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We present an on-line linear time and space algorithm to check if an integer array $f$ is the border array of at least one string $w$ built on a bounded or unbounded size alphabet $Σ$ . First of all, we show a bijection between the border array of a string $w$ and the skeleton of the DFA recognizing $Σ^{*} w$ , called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a skeleton...

Correcting spelling errors by modelling their causes

Sebastian Deorowicz, Marcin Ciura (2005)

International Journal of Applied Mathematics and Computer Science

Similarity:

This paper accounts for a new technique of correcting isolated words in typed texts. A language-dependent set of string substitutions reflects the surface form of errors that result from vocabulary incompetence, misspellings, or mistypings. Candidate corrections are formed by applying the substitutions to text words absent from the computer lexicon. A minimal acyclic deterministic finite automaton storing the lexicon allows quick rejection of nonsense corrections, while costs associated...

Computing the prefix of an automaton

Marie-Pierre Béal, Olivier Carton (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

On a certain event recognizable in real time

Miloslav Nekvinda (1972)

Kybernetika

Similarity:

Drunken man infinite words complexity

Marion Le Gonidec (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this article, we study the complexity of drunken man infinite words. We show that these infinite words, generated by a deterministic and complete countable automaton, or equivalently generated by a substitution over a countable alphabet of constant length, have complexity functions equivalent to (log ) when goes to infinity. 

On low-complexity bi-infinite words and their factors

Alex Heinis (2001)

Journal de théorie des nombres de Bordeaux

Similarity:

In this paper we study bi-infinite words on two letters. We say that such a word has stiffness $k$ if the number of different subwords of length $n$ equals $n + k$ for all $n$ sufficiently large. The word is called $k$ -balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most $k$ . In the present paper we give a complete description of the class of bi-infinite words of stiffness $k$ and show that the number of subwords of length $n$ from this class has...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study the complexity of the infinite word $u_{β}$ associated with the Rényi expansion of $1$ in an irrational base $β > 1$ . When $β$ is the golden ratio, this is the well known Fibonacci word, which is sturmian, and of complexity $ℂ (n) = n + 1$ . For $β$ such that $d_{β} (1) = t_{1} t_{2} \dots t_{m}$ is finite we provide a simple description of the structure of special factors of the word $u_{β}$ . When $t_{m} = 1$ we show that $ℂ (n) = (m - 1) n + 1$ . In the cases when $t_{1} = t_{2} = \dots = t_{m - 1}$ or $t_{1} > max {t_{2}, \dots, t_{m - 1}}$ we show that the first difference of the complexity function $ℂ (n + 1) - ℂ (n)$ takes value in ${m - 1, m}$ for every $n$ , and consequently...