Ограниченная монотонная рекурсия и МГ-автоматыстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
Аннотация:На основе ограниченной монотонной рекурсии определен класс BMR словарных функций над алфавитом {1,2}. Введен новый тип вычислительного устройства - многоголовочный нестирающий автомат с выходом (МГ-автомат). Доказано, что класс BMR совпадает с классом MHA словарных функций, вычислимых на МГ-автоматах за полиномиальное время. Приведены многочисленные примеры словарных функций из класса BMR.