Elementary formal systems, intrinsic complexity, and procrastination

Abstract

The learnability of the subclasses of elementary formal systems (EFS) are analyzed by employing two distinct bodies of abstract studies in the inductive inference literature. The first approach uses constructive ordinals to bound the number of mind changes, while the second adapts reductions for the intrinsic complexity of learnable classes. Results show that ordinal mind change complexity for identification of languages formed by unions of up to n pattern languages is ω+n$/. Results that relate topological properties of learnable classes to that of intrinsic complexity and ordinal mind change complexity are also presented.