Hardprob/Minimum Locally Testable Automaton Order — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Локально тестируемый язык <em>L</em>, т.е. некий язык <em>L…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Локально тестируемый язык <em>L</em>, т.е. некий язык <em>L</em>, такой, что положительное целое <em>j</em>, | + | * Локально тестируемый язык <em>L</em>, т.е. некий язык <em>L</em>, такой, что положительное целое <em>j</em>, такое что входит или нет строка <em>x</em> в этот язык зависит от … |
| − | такое что входит или нет строка <em>x</em> в этот язык зависит от … | + | |
** префикса и суффикса <em>x</em> длины <em>j-1</em>, | ** префикса и суффикса <em>x</em> длины <em>j-1</em>, | ||
** набора подстрок <em>x</em> длины <em>j</em>. | ** набора подстрок <em>x</em> длины <em>j</em>. | ||
Текущая версия на 00:18, 14 апреля 2023
- Локально тестируемый язык L, т.е. некий язык L, такой, что положительное целое j, такое что входит или нет строка x в этот язык зависит от …
- префикса и суффикса x длины j-1,
- набора подстрок x длины j.
- Найти порядок j, т.е. положительное целое j, «свидетель» локальной тестируемости L.
- Минимизировать значение порядка, т.е. j.
Задача в лаб22 (рид-онли просмотр)