Автономные автоматы и t(n)-генерические языки

Cтатья посвящена характеризации генерических множеств в терминах автономных автоматов. В частности, установлено, что язык L является t(n) -генерическим тогда и только тогда, когда не существует конечный или бесконечный автономный автомат AL, порождающий префикс L | x  характеристической функции языка L за время (2n-1)t(2n-1). На основе этого результата доказано, что если язык L частично-рекурсивно перечислим и временная сложность перечисления всех слов языка L, не превышающих заданное слово Χ длины | x |=n, оценивается как n(2n-1)t(2n-1), то язык L не является t(n)-v - случайным.