A Canonical Automaton for One-Rule ...
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
A Canonical Automaton for One-Rule Length-Preserving String Rewrite Systems
Auteur(s) :
Latteux, Michel [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Roos, Yves [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Roos, Yves [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Titre de la revue :
Information and Computation
Pagination :
203--228
Éditeur :
Elsevier
Date de publication :
2015
ISSN :
0890-5401
Mot(s)-clé(s) en anglais :
String rewrite system
rational transduction
automaton.
rational transduction
automaton.
Discipline(s) HAL :
Informatique [cs]/Théorie et langage formel [cs.FL]
Résumé en anglais : [en]
In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a ...
Lire la suite >In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a letter-to-letter transducer that computes the relation induced by a one-rule length-preserving string rewrite system. This transducer can be seen as an automaton over an alphabet A x A. We prove that this automaton is finite if and only if the corresponding relation is rational. We also identify a sufficient condition for the context-freeness of the language L recognized by this automaton and, when this condition is satisfied, we construct a pushdown automaton that recognizes L.Lire moins >
Lire la suite >In this work, we use rearrangements in rewriting positions sequence in order to study precisely the structure of the derivations in one-rule length-preserving string rewrite systems. That yields to the definition of a letter-to-letter transducer that computes the relation induced by a one-rule length-preserving string rewrite system. This transducer can be seen as an automaton over an alphabet A x A. We prove that this automaton is finite if and only if the corresponding relation is rational. We also identify a sufficient condition for the context-freeness of the language L recognized by this automaton and, when this condition is satisfied, we construct a pushdown automaton that recognizes L.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://doi.org/10.1016/j.ic.2015.07.002
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.ic.2015.07.002
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.ic.2015.07.002
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.ic.2015.07.002
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.ic.2015.07.002
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.ic.2015.07.002
- Accès libre
- Accéder au document
- j.ic.2015.07.002
- Accès libre
- Accéder au document