Дана Англюин ( 1987 ; pdf ) определяет модель обучения с помощью запросов на членство и теоретических запросов (контрпримеры к предложенной функции). Она показывает, что регулярный язык, представленный минимальным DFA из состояний, может быть изучен за полиномиальное время (где предложенные функции - DFA) с запросами на членство и не более теоретическими запросами ( размер самого большого контрпримера, предоставленного репетитором). К сожалению, она не обсуждает нижние границы.
Мы можем немного обобщить модель, предполагая магический наставник, который может проверить равенство между произвольными функциями и предоставить контрпримеры, если они различны. Тогда мы можем спросить, насколько сложно выучить классы больше, чем обычные языки. Я заинтересован в этом обобщении и оригинальном ограничении на обычные языки.
Существуют ли какие-либо известные нижние границы для количества запросов в модели членства и контрпримеров?
Меня интересуют нижние оценки количества запросов на членство, теоретических запросов или компромиссов между ними. Меня интересуют нижние оценки для любого класса функций, даже для более сложных классов, чем обычные языки.
Если нижних границ нет: существуют ли известные барьеры для доказательства нижних границ запросов в этой модели?
Смежные вопросы
Есть ли улучшения в алгоритме Даны Англюин для изучения регулярных наборов
источник