The interspike interval spike trains of spontaneously active cortical neurons can display nonrandom internal structure. The degree of nonrandom structure can be quantified and was found to decrease during focal epileptic seizures. Greater statistical discrimination between the two physiological conditions (normal vs seizure) was obtained with measurements of context-free grammar complexity than by measures of the distribution of the interspike intervals such as the mean interval, its standard deviation, skewness, or kurtosis. An examination of fixed epoch data sets showed that two factors contribute to the complexity: the firing rate and the internal structure of the spike train. However, calculations with randomly shuffled surrogates of the original data sets showed that the complexity is not completely determined by the firing rate. The sequence-sensitive structure of the spike train is a significant contributor. By combining complexity measurements with statistically related surrogate data sets, it is possible to classify neurons according to the dynamical structure of their spike trains. This classification could not have been made on the basis of conventional distribution-determined measures. Computations with more sophisticated kinds of surrogate data show that the structure observed using complexity measures cannot be attributed to linearly correlated noise or to linearly correlated noise transformed by a static monotonic nonlinearity. The patterns in spike trains appear to reflect genuine nonlinear structure. The limitations of these results are also discussed. The results presented in this article do not, of themselves, establish the presence of a fine-structure encoding of neural information.