Stability in L systems |
| |
Authors: | John J Grefenstette |
| |
Affiliation: | Computer Science Department, Vanderbilt University, Nashville, TN 37235, U.S.A. |
| |
Abstract: | Given an L System G, a word w is said to be k-stable in G if, once w occurs in a derivation, the derivation can proceed no more than k steps before the next occurence of w. The set of k-stable words in an L System is called the k-stable language of the system. The k-stable languages of the main classes of L Systems are characterized by the Adult languages of the corresponding classes. This work provides a new characterization of the Chomsky hierarchy in terms of totally parallel grammars, and some consequences of this characterization are explored. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|