A regularity test for dual bordered OS systems (Q1060851)

A dual bordered OS system is a triple (\(\Sigma\),P,S) where \(\Sigma\) is a finite alphabet, S a finite subset of \(\Sigma^*\), the set of axioms, and P a finite set of rules of the form \(a\to axa\), where \(a\in \Sigma\) and \(x\in \Sigma^*\). 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.