Loading [MathJax]/extensions/MathZoom.js
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...
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 w from a given set I of
substrings (fragments) of a word w. We introduce an
hypothesis involving the set of fragments I and the maximal
length m(w) of the minimal forbidden factors of w. Such
hypothesis allows us to reconstruct uniquely the word w from the
set I in linear...
We study hybrid systems with strong resets from the perspective of
formal language theory. We define a notion of hybrid regular
expression and prove a Kleene-like theorem for hybrid systems. We
also prove the closure of these systems under determinisation and
complementation. Finally, we prove that the reachability problem is
undecidable for synchronized products of hybrid systems.
We provide alternative proofs and algorithms for results proved by Sénizergues on rational and recognizable free group languages. We consider two different approaches to the basic problem of deciding recognizability for rational free group languages following two fully independent paths: the symmetrification method (using techniques inspired by the study of inverse automata and inverse monoids) and the right stabilizer method (a general approach generalizable to other classes of groups). Several...
We provide alternative proofs and algorithms for results
proved by Sénizergues on rational and recognizable free
group languages. We consider two different approaches to the basic
problem of deciding recognizability for rational free group languages
following two fully independent paths: the symmetrification
method (using techniques inspired by the study of
inverse automata and inverse monoids) and
the right stabilizer method (a general approach generalizable to other
classes of
groups). Several...
Currently displaying 21 –
37 of
37