All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2

Displaying 21 – 37 of 37

Showing per page

Forbidden factors and fragment assembly

F. Mignosi, A. Restivo, M. Sciortino (2001)

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

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...

Forbidden Factors and Fragment Assembly

F. Mignosi, A. Restivo, M. Sciortino (2010)

RAIRO - Theoretical Informatics and Applications

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...

Foreword

V. Bruyère, M. Rigo (2010)

RAIRO - Theoretical Informatics and Applications

Formal language properties of hybrid systems with strong resets

Thomas Brihaye, Véronique Bruyère, Elaine Render (2010)

RAIRO - Theoretical Informatics and Applications

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.

Free group languages : rational versus recognizable

Pedro V. Silva (2004)

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

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...

Free group languages: Rational versus recognizable

Pedro V. Silva (2010)

RAIRO - Theoretical Informatics and Applications

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

Previous Page 2