Abstract
Context-free languages of sub-exponential growth were studied. The growth function was defined as the function whose value at each non-negative integer was the number of words of length n in a fixed formal language. The definition of a bounded language, which is a subset for some words, was also used in the analysis. Results showed that context-free languages of intermediate growth were nonexistent.
| Original language | English |
|---|---|
| Pages (from-to) | 308-310 |
| Number of pages | 3 |
| Journal | Journal of Computer and System Sciences |
| Volume | 64 |
| Issue number | 2 |
| DOIs | |
| State | Published - Mar 2002 |
Keywords
- Context-free languages
- Growth functions
Fingerprint
Dive into the research topics of 'Context-free languages of sub-exponential growth'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver