А́лгебра — раздел математики, который можно нестрого охарактеризовать как обобщение и расширение арифметики; в этом разделе числа и другие математические объекты обозначаются буквами и другими символами, что позволяет записывать и исследовать их свойства в самом общем виде. Слово «алгебра» также употребляется в общей алгебре в названиях различных алгебраических систем. В более широком смысле под «алгеброй» понимают раздел математики, посвящённый изучению операций над элементами множеств произвольной природы, обобщающий обычные операции сложения и умножения чисел.
Вычита́ние (убавление) — одна из вспомогательных бинарных математических операций двух аргументов, результатом которой является новое число (разность), получаемое уменьшением значения первого аргумента на значение второго аргумента. На письме обычно обозначается с помощью знака «минус»: 
. Вычитание — операция обратная сложению.
Умноже́ние — одна из основных математических операций над двумя аргументами, которые называются множителями или сомножителями. Результат умножения называется их произведением.
Суффиксное дерево — бор, содержащий все суффиксы некоторой строки. Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| — длина строки w.
Конкатена́ция — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир».
Регуля́рный язык в теории формальных языков — множество слов, которое распознает некоторый конечный автомат. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
В теории множеств порядковым числом, или ординалом называется порядковый тип вполне упорядоченного множества. Как правило, порядковые числа отождествляются с наследственно транзитивными множествами. Ординалы представляют собой одно из расширений натуральных чисел, отличающееся как от целых, так и от кардинальных чисел. Как и другие разновидности чисел, их можно складывать, перемножать и возводить в степень. Бесконечные порядковые числа называют трансфинитными. Ординалы играют ключевую роль в доказательстве многих теорем теории множеств — в частности, благодаря связанному с ними принципу трансфинитной индукции.
Лексикографический порядок — отношение линейного порядка на множестве слов над некоторым упорядоченным алфавитом 
. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.
Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида — Соломона, работающие с байтами (октетами).
Звезда́ Кли́ни в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях.
- Если V — множество строк
- то V* — минимальное надмножество множества V, которое содержит ε и замкнуто относительно конкатенации. Это также множество всех строк, полученных конкатенацией нуля или более строк из V.
- Если V — множество символов
- то V* — множество всех строк из символов из V с добавлением пустой строки.
В теории кодирования, неравенство Крафта — Макмиллана даёт необходимое и достаточное условие существования разделимых и префиксных кодов, обладающих заданным набором длин кодовых слов.
Су́ффиксный автома́т — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова 
и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова 
существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин.
Ёмкость Шеннона — характеристика неориентированного графа, описывающая предельную плотность кодирования с возможностью гарантированного отслеживания ошибок в канале связи, модель которого представляет данный граф.
Детерминированный конечный автомат, известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году.
