The tape-complexity of context-independent developmental languages

摘要

We show that languages in the least full AFL enclosing all E0L-languages are of tape-complexity (log n)3. The proof indicates in what respect context-independent developmental languages are “more complex” than context-free languages, for which a tape-complexity (log n)2 is known.