Article ID Journal Published Year Pages File Type
425988 Information and Computation 2015 26 Pages PDF
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
, ,