Espessura finita
Na teoria de linguagens formais, particularmente na teoria da aprendizagem algorítmica, uma classe C de linguagens tem espessura finita se toda cadeira de caracteres é contada em, no máximo, um número finito de linguagens em C. Essa condição foi introduzida por Dana Angluin como uma condição suficiente para C sendo identificável no limite.[1]
A noção relacionada de espessura M-finita[editar | editar código-fonte]
Tome a linguagem L e uma classe indexada C = { L1, L2, L3, ... } de linguagens, uma linguagem membro Lj ∈ C é dita conceito mínimo de L dentro de C se L ⊆ Lj, mas não L ⊊ Li ⊆ Lj para qualquer Li ∈ C.[2]
A classe C satisfaz a condição-MEF se todo subconjunto finito D de uma linguagem membro Li ∈ C tem um conceito mínimo Lj ⊆ Li. Simetricamente, C satisfaz a condição-MFF se todo conjunto finito não-vazio D tem no máximo um número finito de conceitos mínimos em C. Finalmente, C é dito ter espessura M-finita se esta satisfaz ambas condição-MEF e condição-MFF. [3]
Espessura finita implica finita-M espessura.[4] Contudo, existem classes que são de finita-M espessura mas não de espessura finita (por exemplo, qualquer classe de linguagens C = { L1, L2, L3, ... } tal que L1 ⊆ L2 ⊆ L3 ⊆ ...).
Referências
- ↑ Dana Angluin (1980). «Inferência indutiva de linguagens formais de dados positivos» (PDF). Information and Control. 45: 117–135. doi:10.1016/s0019-9958(80)90285-5; here: Condição 3, p.123 mid. Exigência original de Angluin (todo conjunto de cadeias de caracteres (palavras) não-vazias estão contidas em, no máximo, um número finito de linguagens) é equivalente.
- ↑ Andris Ambainis, Sanjay Jain, Arun Sharma (1997). «Ordinal mind change complexity of language identification». Teoria de aprendizado computacional (PDF). Col: LNCS. 1208. [S.l.]: Springer. pp. 301–315; here: Definição 25
- ↑ Ambainis et al. 1997, Definição 26
- ↑ Ambainis et al. 1997, Corolário 29
