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


The paper is dedicated to generic sets characterization in autonomous terms. In particular, it is shown
that a language $L$ is $t(n)$-generic if and only if there it no nite or innite autonomous automation $A_{L}$
generating the prefix $L|x$ of the characteristic function of the language $L$ in the $(2^n −1)t(2^n −1)$ time. By
using this result it is proved: if the language $L$ is partially recursively enumerable and the time complexity
of enumerating of all words of the language $L$ of length at most of length $|x|$ = $n$ for given word $x$ is
estimated as $n(2^n − 1)t(2^n − 1)$, then the language $L$ is not $t(n)$- random and is not $t(n)$-v random.