Restriction of active symbols in k-limited etol systems and a normal form theorem

Abstract

For every positive integer k, fc-limited ETOL systems provide a limitation of the parallel rewriting of ETOL systems. In such systems, at each step of the rewriting process exactly min {k,∗,w}{∗,w being the number of occurrences of the symbol a in w) occurrences of any symbol a of the word w considered have to be rewritten. A symbol is called active in respect to a table if it is rewritten by a word different from itself by at least one production of this table. We investigate the influence of restricting the number of active symbols in a system. It is shown that each klETOL language is generated by a klETOL system with no more than 3 active symbols in each of its tables.

Keywords:

• Formal languages
• limited TOL systems

C.R. Categories:

• F.4.2