Ранговый алфавит

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

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

$f(a,g(a),f(a,b,c))$,

a,b,c — константы, g — унарный, а f — троичный.

Напротив,

$f(a,f(a))$

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

Ссылки

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