In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word from a given set of substrings (fragments) of a word . We introduce an hypothesis involving the set of fragments and the maximal length of the minimal forbidden factors of . Such hypothesis allows us to reconstruct uniquely the word from the set in linear...
Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have...
Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages.
Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have...
In this paper methods and results related to the notion of minimal
forbidden words are applied to the fragment assembly problem. The
fragment assembly problem can be formulated, in its simplest form,
as follows: reconstruct a word from a given set of
substrings () of a word . We introduce an
hypothesis involving the set of fragments and the maximal
length of the minimal forbidden factors of . Such
hypothesis allows us to reconstruct uniquely the word from the
set in linear time. We prove...
Download Results (CSV)