×

Uniform characterizations of non-uniform complexity measures. (English) Zbl 0588.68021

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.

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI