Espessura finita

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 LjC é dita conceito mínimo de L dentro de C se LLj, mas não LLiLj para qualquer LiC.[2]

A classe C satisfaz a condição-MEF se todo subconjunto finito D de uma linguagem membro LiC tem um conceito mínimo LjLi. 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 L1L2L3 ⊆ ...).

Referências

  1. 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.
  2. 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
  3. Ambainis et al. 1997, Definição 26
  4. Ambainis et al. 1997, Corolário 29
Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.