Неизбежный шаблон

В математике и теоретической информатике шаблон является неизбежным шаблоном, если он неизбежен в любом конечном алфавите.

Минимальная кратность шаблона равна где - число вхождений символа в шаблон . Другими словами, это количество вхождений наименее часто встречающегося символа в . ${\ Displaystyle р}$ ${\ Displaystyle м (р) = \ мин (\ mathrm {count_ {р}} (х): х \ в р)}$ ${\ Displaystyle \ mathrm {count_ {р}} (х)}$ ${\ Displaystyle х}$ ${\ Displaystyle р}$ ${\ Displaystyle р}$ ${\ Displaystyle р}$

Учитывая конечные алфавиты и , слово является экземпляром шаблона, если существует нестирающий полугрупповой морфизм такой, что , где обозначает звезду Клини из . Нестирание означает, что для всех , где обозначает пустую строку . ${\ Displaystyle \ сигма}$ ${\ Displaystyle \ Дельта}$ ${\ Displaystyle х \ в \ сигма ^ {*}}$ ${\ displaystyle p \ in \ Delta ^ {*}}$ ${\ Displaystyle е: \ Дельта ^ {*} \ стрелка вправо \ Сигма ^ {*}}$ ${\ Displaystyle е (р) = х}$ ${\ Displaystyle \ сигма ^ {*}}$ ${\ Displaystyle \ сигма}$ ${\ Displaystyle е (а) \ neq \ varepsilon}$ ${\ Displaystyle а \ в \ дельта}$ ${\ Displaystyle \ varepsilon}$

Говорят , что слово соответствует или встречается с шаблоном, если фактор (также называемый подсловом или подстрокой ) является экземпляром шаблона . В противном случае говорят, что он избегает или является -свободным. Это определение можно обобщить на случай бесконечного на основе обобщенного определения «подстроки». ${\ Displaystyle ш}$ ${\ Displaystyle р}$ ${\ Displaystyle ш}$ ${\ Displaystyle р}$ ${\ Displaystyle ш}$ ${\ Displaystyle р}$ ${\ Displaystyle р}$ ${\ Displaystyle ш}$