Hardprob/Minimum Locally Testable Automaton Order

Материал из DISCOPAL
Версия от 00:17, 14 апреля 2023; StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Локально тестируемый язык <em>L</em>, т.е. некий язык <em>L…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
  • Локально тестируемый язык L, т.е. некий язык L, такой, что положительное целое j,

такое что входит или нет строка x в этот язык зависит от …

    • префикса и суффикса x длины j-1,
    • набора подстрок x длины j.
  • Найти порядок j, т.е. положительное целое j, «свидетель» локальной тестируемости L.
  • Минимизировать значение порядка, т.е. j.

Задача в лаб22 (рид-онли просмотр)


[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.