A Canonical Automaton for One-Rule Length-Preserving String Rewrite Systems

Latteux, Michel; Roos, Yves

Document type :

Article dans une revue scientifique

DOI :

10.1016/j.ic.2015.07.002

Title :

A Canonical Automaton for One-Rule Length-Preserving String Rewrite Systems

Author(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]

Journal title :

Information and Computation

Pages :

203--228

Publisher :

Elsevier

Publication date :

2015

ISSN :

0890-5401

English keyword(s) :

String rewrite system
rational transduction
automaton.

HAL domain(s) :

Informatique [cs]/Théorie et langage formel [cs.FL]

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

https://doi.org/10.1016/j.ic.2015.07.002
Open access
Access the document

https://doi.org/10.1016/j.ic.2015.07.002
Open access
Access the document

https://doi.org/10.1016/j.ic.2015.07.002
Open access
Access the document

https://doi.org/10.1016/j.ic.2015.07.002
Open access
Access the document

https://doi.org/10.1016/j.ic.2015.07.002
Open access
Access the document

https://doi.org/10.1016/j.ic.2015.07.002
Open access
Access the document

A Canonical Automaton for One-Rule ... BibTeX CSV Excel RIS

Files

A Canonical Automaton for One-Rule ...

BibTeX

CSV

Excel

RIS