Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
425988 | Information and Computation | 2015 | 26 Pages |
Abstract
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×AA×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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michel Latteux, Yves Roos,