Недавно наткнулся на моноид
и в общем случае моноиды
для некоторого множества
. Эти моноиды связаны с правильными скобочными последовательностями (
— множество видов скобок, строка равна
ровно в случае своей сбалансированности), хотя изначально я их получил, описывая типы команд в конкатенативном языке, работающем со стеком, и
означают
push и
pop значений типа
(и подтипирования в таком языке конечно тоже не должно быть, а то определяющие соотношения усложнятся). (Можно также говорить о языке, работающем с деком, заменив любое
на
: концы независимы, если запретить командам знать о точной длине дека, а потому и их типам зависеть от неё.)
Простейший случай —
— напоминает мне что-то на полпути между
и
(немудрено: первый — подмоноид, а второй — фактор-моноид), и у его элементов есть простая нормальная форма
.
Если кто-то встречал называние этого какими-нибудь именами, поделитесь!