Терм

Материал из WikiGrapp
Версия от 10:45, 20 сентября 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

Терм (Term) — правильно построенная формула над некоторым алфавитом \,\Sigma, образованным из множества символов переменных \,V и символов r-арных функций \,\Sigma_r, где \,r\geq 0 — арность функций (количество ее "аргументов").

Если терм \,t имеет вид

f(t_1, t_2, \ldots, t_r),

где \,f \in \Sigma_r, \,r>0, то \,f называется внешним (корневым) символом терма \,t, а термы \,t_1, \,t_2, \ldots, t_r и их подтермы — подтермами терма \,t. Терм \,tзамкнутый, если в нем нет переменных, и линейный, если он не содержит двух вхождений одной и той же переменной.

Терм \,t называется редуцируемым (относительно некоторой системы переписывания термов \,R), если существует такой терм \,s, отличный от \,t, что t \longrightarrow_R s, и нередуцируемым (или тупиковым) в противном случае. Термы \,t и \,s эквивалентны, если t \longrightarrow_R s или s \longrightarrow_R t.

Если t \longrightarrow_R s и \,s нередуцируемый, то \,s называется нормальной формой терма \,t. Термы конвергентны, если их нормальные формы совпадают.

В качестве графововых представлений терма используются дерево выражения и дэг выражения.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.