A canonical automaton for one-rule length-preserving string rewrite systems

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

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2015-10, Vol.244 (244), p.203-228
Main Authors: Latteux, Michel, Roos, Yves
Format: Article
Language:English
Subjects:
Computer Science
Formal Languages and Automata Theory
Rational transduction
String rewrite system
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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×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.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2015.07.002