The Sequence Equivalence Problem Is Decidable for OS Systems ; CU-CS-137-78
Andrzej Ehrenfeucht, Grzegorz Rozenberg · CU Scholar (University of Colorado Boulder) · 1978
OS systems generalize context-free grammars without non-terminals. It is shown that it is decidable whether or not two arbitrary OS systems generate the same set of (derivation) sequences. As a corollary we get that it is decidable whether or not two arbitrary context-free grammars have the same sets of derivation sequences.