Конечная толщина
В теории языка , в частности в теории алгоритмического обучения , класс C языков формальной имеет конечную толщину если каждая строка содержится не более чем в конечном числе языков C. , Это условие было введено Даной Англуином как достаточное условие для того, чтобы C было идентифицируемо в пределе . [1]
Соответствующее понятие M-конечной толщины
[ редактировать ]Учитывая язык L и индексированный класс C = { L 1 , L 2 , L 3 , ... } языков, язык-член L j ∈ C называется минимальным понятием L внутри если C, L ⊆ L j , но не L ⊊ L i ⊆ L j для любого L i ∈ C . [2] Говорят, что класс C удовлетворяет MEF-условию , если каждое конечное подмножество D языка-члена L i ∈ C имеет минимальное понятие L j ⊆ L i . Симметрично говорят, что C удовлетворяет условию MFF , если каждое непустое конечное множество D имеет не более чем конечное число минимальных понятий в C . Наконец, C говорят, что имеет M-конечную толщину, если он удовлетворяет как MEF-, так и MFF-условию. [3]
Конечная толщина подразумевает М-конечную толщину. [4] Однако существуют классы M-конечной толщины, но не конечной толщины (например, любой класс языков C = { L 1 , L 2 , L 3 , ... } такой, что L 1 ⊆ L 2 ⊆ L 3 ⊆ ...).
Ссылки
[ редактировать ]- ^ Дана Англуин (1980). «Индуктивный вывод формальных языков на основе положительных данных» (PDF) . Информация и контроль . 45 (2): 117–135. дои : 10.1016/s0019-9958(80)90285-5 . ( citeseer.ist.psu.edu ); здесь: Условие 3, стр.123 середина. Исходное требование Англуина (каждый непустой набор строк должен содержаться не более чем в конечном числе языков) эквивалентно.
- ^ Андрис Амбайнис; Санджай Джайн; Арун Шарма (1997). «Обычное изменение сознания, сложность языковой идентификации». Вычислительная теория обучения (PDF) . ЛНКС. Том. 1208. Спрингер. стр. 301–315. ; здесь: Определение 25
- ^ Амбайнис и др. 1997, Определение 26
- ^ Амбайнис и др. 1997, Следствие 29