Decidable properties of monadic recursive schemas with a depth parameter

Summary Monadic table counter schemas (MTCS) are defined as extensions of recursive monadic schemas by incorporating a depth-of-recursion counter. The family of languages generated by free MTCS under Herbrand interpretation is shown to be the family of ETOL languages. It is proven that the halting and divergence problems are decidable for free MTCS and that the freedom problem is decidable. Most of these results are obtained using results on regular control sequences from L system theory.