Complexity Reference: compref226 (BibTex)

Authors: Makinen,E

Year: 1988

Title: 2 Complexity Measures for Context-free Languages

Journal: International Journal of Computer Mathematics, 1, 29-34

Comments: The strict inclusion between regular and context-free langauges is studied by using two complexity measures based on homomorphisms on context free langauges. The complexity is the minimal number of erased symbols that regulates the language and hence an indication of haow far from being a regular language it is.


| Top | Authors | Journals | Years | Keywords | Search | New | Comments |

Bruce Edmonds, Centre for Policy Modelling, Manchester Metropolitan University