On Complexity Classes and Algorithmically Random Languages (Extended Abstract).

Ronald V. Book Jack H. Lutz Klaus W. Wagner

Published in: STACS (1992)

Keyphrases

extended abstract
tractable cases
intrinsic complexity
expressive power
complexity measures
databases
computational complexity
worst case
language independent
lower bound
cross lingual
space complexity
grammatical inference