Descriptional complexity of lindenmayer systems

Authors

  • Sherzod Turaev Department of Computer Science and Software Engineering College of Information Technology United Arab Emirates University P.O. Box 15551, Al Ain, United Arab Emirates
  • G. Mavlankulov Faculty of Computer Science and Information Technology Universiti Putra Malaysia 43400 UPM Serdang, Selangor, Malaysia
  • M. Othman Faculty of Computer Science and Information Technology Universiti Putra Malaysia 43400 UPM Serdang, Selangor, Malaysia
  • M. H. Selamat Faculty of Computer Science and Information Technology Universiti Putra Malaysia 43400 UPM Serdang, Selangor, Malaysia

Abstract

In this paper we study the nonterminal complexity of Lindenmayer systems with respect to tree controlled grammars. We show that all 0L, D0L and E0L languages can be generated by tree controlled grammars with at most five nonterminals. The results based on
the idea of using a tree controlled grammar in the t-normal form, which has the one active nonterminal, and a coding homomorphism.

Keywords:

Context-free languages, L systems, Tree controlled grammars, Descriptional complexity, Nonterminal complexity

Downloads

Published

2012-12-31

How to Cite

Sherzod Turaev, G. Mavlankulov, M. Othman, & M. H. Selamat. (2012). Descriptional complexity of lindenmayer systems. Applied Mathematics and Computational Intelligence (AMCI), 1(1), 12–23. Retrieved from https://ejournal.unimap.edu.my/index.php/amci/article/view/47

Issue

Vol. 1 No. 1 (2012): December (2012)

Section

Articles