Espesor finito

En la teoría del lenguaje formal , en particular en la teoría del aprendizaje algorítmico , una clase C de lenguajes tiene grosor finito si cada cadena está contenida en como máximo un número finito de lenguajes en C. Esta condición fue introducida por Dana Angluin como una condición suficiente para que C sea identificable en el límite . ^{[ 1 ]}

Dado un lenguaje L y una clase indexada C = { L ₁ , L ₂ , L ₃ , ... } de lenguajes, un lenguaje miembro L _j ∈ C se denomina concepto mínimo de L dentro de C si L ⊆ L _j , pero no L ⊊ L _i ⊆ L _j para cualquier L _i ∈ C . ^{[ 2 ]} Se dice que la clase C satisface la condición MEF si todo subconjunto finito D de un lenguaje miembro L _i ∈ C tiene un concepto mínimo L _j ⊆ L _i . Simétricamente, se dice que C satisface la condición MFF si todo conjunto finito no vacío D tiene como máximo un número finito de conceptos mínimos en C . Finalmente, se dice que C tiene espesor M-finito si satisface tanto la condición MEF como la condición MFF. ^{[ 3 ]}

El espesor finito implica un espesor M-finito. ^{[ 4 ]} Sin embargo, existen clases que son de espesor M-finito pero no de espesor finito (por ejemplo, cualquier clase de lenguajes C = { L ₁ , L ₂ , L ₃ , ... } tales que L ₁ ⊆ L ₂ ⊆ L ₃ ⊆ ...).