Paper Info
Title
On Word Rewriting Systems Having a Rational Derivation
Abstract
We define four families of word-rewriting systems: the prefix/suffix systems and the left/right systems. The rewriting of prefix systems generalizes the prefix rewriting of systems: a system is prefix (suffix) if a left hand side and a right hand side are overlapping only by prefix (suffix). The rewriting of right systems generalizes the mechanism of transducers: a system is right (left) if a left hand side overlaps a right hand side only on the right (left). We show that these systems have a rational derivation even if they are not only finite but recognizable. Besides these four families, we give simple systems having a non rational derivation.
Year
DOI
Venue
2000
10.1007/3-540-46432-8_4
FoSSaCS
Keywords
Field
DocType
rational derivation,word-rewriting system,non rational derivation,suffix system,right hand side,word rewriting systems,simple system,prefix system,right system,left hand side
Discrete mathematics,Combinatorics,Suffix,Computer science,Cayley graph,Prefix,Regular graph,Rewriting,Transitive closure,Stable system
Conference
Volume
ISSN
ISBN
1784
0302-9743
3-540-67257-5
Citations 
PageRank 
References 
8
0.73
6
Authors
1
Name
Order
Citations
PageRank
Didier Caucal147039.15