Balcázar, José L.; Díaz, Josep; Gabarró, Joaquim Uniform characterizations of non-uniform complexity measures. (English) Zbl 0588.68021 Inf. Control 67, 53-69 (1985). Non-uniform complexity measures originated in automata and formal languages theory are characterized in terms of well-known uniform complexity classes. The initial index of languages is introduced by means of several computational models. It is shown to be closely related to context-free cost, boolean circuits, straight line programs, and Turing machines with sparse oracles and time or space bounds. Cited in 4 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68Q45 Formal languages and automata Keywords:complexity of formal languages; initial index of languages PDF BibTeX XML Cite \textit{J. L. Balcázar} et al., Inf. Control 67, 53--69 (1985; Zbl 0588.68021) Full Text: DOI