TY - JOUR
T1 - Context-free languages of sub-exponential growth
AU - Bridson, Martin R.
AU - Gilman, Robert H.
PY - 2002/3
Y1 - 2002/3
N2 - 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.
AB - 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.
KW - Context-free languages
KW - Growth functions
UR - http://www.scopus.com/inward/record.url?scp=0036507090&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0036507090&partnerID=8YFLogxK
U2 - 10.1006/jcss.2001.1804
DO - 10.1006/jcss.2001.1804
M3 - Article
AN - SCOPUS:0036507090
SN - 0022-0000
VL - 64
SP - 308
EP - 310
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 2
ER -