Разработка компиляторов

       

Полурешетки


Полурешеткой называется множество, снабженное идемпотентной, коммутативной и ассоциативной операцией (определение свойств этой операции приведено на слайде). При наличии такой операции естественным образом индуцируется отношение частичного порядка.

Полурешетка L называется ограниченной тогда и только тогда, когда в ней существуют наибольший TL и наименьший элементы.

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



Содержание раздела