On prefixal one-rule string rewrite systems

Prefixal one-rule string rewrite systems are one-rule string rewrite systems for which the left-hand side of the rule is a prefix of the right-hand side of the rule. String rewrite systems induce a transformation over languages: from a starting word, one can associate all its descendants. We prove,...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-11, Vol.795, p.240-256
Main Authors: Latteux, Michel, Roos, Yves
Format: Article
Language:English
Subjects:
Computation and Language
Computer Science
Context free language
One-rule 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:Prefixal one-rule string rewrite systems are one-rule string rewrite systems for which the left-hand side of the rule is a prefix of the right-hand side of the rule. String rewrite systems induce a transformation over languages: from a starting word, one can associate all its descendants. We prove, in this work, that the transformation induced by a prefixal one-rule rewrite system always transforms a finite language into a context-free language, a property that is surprisingly not satisfied by arbitrary one-rule rewrite systems. We also give here a decidable characterization of the prefixal one-rule rewrite systems whose induced transformation is a rational transduction.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.07.004