A regularity test for dual bordered OS systems

Summary A dual bordered OS system is a triple (, P, S) where is a finite alphabet, S a finite subset of ^*, the set of axioms, and P a finite set of rules of the form aa × a, where a and x ^*. Using well-quasi-order theory, we show that the regularity problem for such systems is decidable. Whether such a system generates a regular language essentially only depends on the set of rules but not on the axioms.