Regularity and context-freeness over word rewriting systems

Didier Caucal and Dinh Trong Hieu

Abstract. We describe a general decomposition mechanism to express the derivation relation of a word rewriting system R as the composition of a (regular) substitution followed by the derivation relation of a system R0 ∪ D, where R0 is a strict sub-system of R and D is the Dyck rewriting system. From this decomposition, we deduce that the system R (resp. R-1) preserves regular (resp. context-free) languages whenever R0 ∪ D does. From this we can deduce regularity and context-freeness preservation properties for a generalization of tagged bifix systems