Ранжированный алфавит - Ranked alphabet - Wikipedia

В теоретическая информатика и формальная теория языка, а ранжированный алфавит пара обычный алфавит F и функция Arity: F→ ℕ. Каждая буква в F имеет свой арность так что его можно использовать для создания термины. Нулевые элементы (нулевой арности) также называют константы. Термины, построенные с помощью унарных символов и констант, можно рассматривать как струны. Более высокие артерии приводят к правильному деревья.

Например, в термине

${\displaystyle f(a,g(a),f(a,b,c))}$,

а, б, в константы, грамм унарный, и ж является троичным.

Наоборот,

${\displaystyle f(a,f(a))}$

не может быть допустимым термином, так как символ ж появляется один раз как двоичный, а один раз как унарный, что является незаконным, как Arity должна быть функцией.

Рекомендации

• Комон, Юбер; Дауше, Макс; Гиллерон, Реми; Жакемар, Флоран; Лужие, Денис; Лёдинг, Кристоф; Тисон, Софи; Томмази, Марк (ноябрь 2008 г.). «Отборочные». Методы и приложения древовидных автоматов (PDF). Получено 11 февраля 2014.