Algorithmic and resource-bounded Baire category and corresponding generictiy concepts introduced in computability theory and computational complexity theory, respectively, have become elegant and powerful tools in these settings. Here we introduce some new generictiy notions based on extension functions computable by finite automata which are tailored for capturing diagonalizations over regular sets and functions. We show that the generic sets obtained either by the partial regular extension functions of any fixed constant length or by all total regular extension of constant length are just the sets with saturated (also called disjunctive) characteristic sequence α as a substring. We also show that these automatic generic sets are not regular but may be context free. Furthermore, we introduce stronger automatic generictiy notions based on regular extension functions of nonconstant length and we show that the corresponding generic sets are bi-immune for the class or regular and context free languages.
展开▼
