Глоссарий ИИ
Полный словарь искусственного интеллекта
Система переписывания
Формальный набор правил преобразования, позволяющий изменять символьные выражения по предопределенным схемам. Составляет математическую основу многих механизмов автоматического вычисления и доказательства.
Правило переписывания
Пара (l, r), где l - левая часть, а r - правая часть, определяющая, как заменить один шаблон другим в выражении. Переписывание применяется, когда шаблон l идентифицируется в преобразуемом терме.
Нормальная форма
Выражение, которое больше не может быть переписано ни одним правилом системы. Достижение нормальной формы гарантирует завершение процесса переписывания для данного конкретного терма.
Слияние (конфлюэнтность)
Свойство, гарантирующее, что различные пути переписывания из одного и того же терма сходятся к единственной нормальной форме. Необходимо для обеспечения детерминированности вычислений и согласованности результатов.
Терминация
Свойство системы переписывания, гарантирующее, что невозможна бесконечная последовательность переписываний. Необходимое условие для существования алгоритмов решения и эффективных вычислительных процедур.
Переписывание термов
Парадигма вычислений, в которой преобразования применяются к термам, структурированным в виде деревьев согласно правилам подстановки. Основа многих функциональных языков программирования и систем доказательства.
Система Кнута-Бендикса
Алгоритм пополнения, преобразующий неконфлюэнтную систему переписывания в эквивалентную сходящуюся систему. Используется для решения уравнений и автоматического доказательства теорем.
Критическая пара
Нетривиальное наложение двух правил переписывания, которое может породить неконфлюэнтность. Анализ критических пар позволяет обнаруживать и разрешать конфликты в системах переписывания.
Порядок редукции
Обоснованное отношение порядка на терминах, используемое для доказательства завершаемости системы переписывания. Позволяет гарантировать, что каждое переписывание строго уменьшает термины согласно этому порядку.
Условное переписывание
Расширение систем переписывания, где применение правила зависит от выполнения предварительных условий. Позволяет моделировать более сложные и контекстные преобразования.
Теорема Чёрча-Россера
Фундаментальный результат, устанавливающий эквивалентность между конфлюэнтностью и существованием единственной нормальной формы. Теоретическая основа, гарантирующая согласованность систем вычисления путем переписывания.
Стратегия переписывания
Политика, определяющая порядок и выбор переписываний для применения в термине. Влияет на вычислительную эффективность и может направлять к специфическим результатам.
Переписывание цепочек
Специализация переписывания, где термины являются цепочками символов, а правила - контекстными подстановками. Фундаментальна в компьютерной лингвистике и теории формальных языков.
Критерий Ньюмена
Теорема, устанавливающая, что завершающаяся система переписывания является конфлюэнтной тогда и только тогда, когда все её критические пары сходятся. Упрощает проверку конфлюэнтности в конечных системах.