Barriere, E.; Flocchini, P.; Fomin, F.; Fraigniaud, P.; Nisse, N.; Santoro, N.; Thilikos, D. Information and computation Vol. 219, p. 1-16 DOI: 10.1016/j.ic.2012.08.004 Data de publicació: 2012-10 Article en revista
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.