Обобщение утверждения, что моноид распознает язык, если синтаксический моноид делит моноид

9

Позволять Aбыть конечным алфавитом. Для данного языкаLAсинтаксический Моноид M(L)является известным понятием в теории формального языка. Кроме того, моноидM признает язык L если существует морфизм φ:AM такой, что L=φ1(φ(L))),

Тогда у нас есть хороший результат:

Моноид M признает LA если M(L) является гомоморфным образом подмоноида M (написано как M(L)M).

Вышеуказанное обычно имеет место в контексте обычных языков, и тогда все приведенные выше моноиды конечны.

Теперь предположим, что мы заменим A с произвольным моноидом Nи мы говорим, что подмножество LN признан M если существует морфизм φ:NM такой, что L=φ1(φ(L)), Тогда у нас еще есть, еслиM признает L, тогда M(L)M (см. S. Eilenberg, Автоматы, Машины и Языки, Том B), но верно ли обратное?

В доказательство для A обратное доказывается путем использования свойства, если N=φ(M) для некоторого морфизма φ:MN а также ψ:AN также морфизм, то мы можем найти ρ:AM такой, что φ(ρ(u))=ψ(u) держит, просто выбрав некоторые ρ(Икс)φ-1(ψ(x)) для каждого xA и распространяя это на морфизм из A в M, Но это не работает для произвольных моноидовNпоэтому я ожидаю, что приведенное выше утверждение будет ложным. И если это неверно, то для какого рода моноид уA все еще верно, и эти моноиды получили какое-либо внимание в исследовательской литературе?

StefanH
источник
Конец первого абзаца: не будет L вместо A?
Матеус де Оливейра Оливейра
@MateusdeOliveiraOliveira Да, спасибо, что заметили!
StefanH

Ответы:

5

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

Определение . МоноидNназывается проективным, если выполняется следующее свойство: еслиf:NR является моноидным морфизмом и h:TR является сюръективным морфизмом, то существует морфизм g:NT такой, что f=hg.

Вы можете найти длинное обсуждение проективных моноидов в [1], сразу после определения 4.1.33. В частности, показано, что каждая проективная конечная полугруппа является полосой (полугруппой, в которой каждый элемент идемпотентен). Но обратное неверно, и это действительно открытая проблема, чтобы решить, является ли конечная полугруппа проективной.

[1] Дж. Роудс и Б. Стейнберг, Theqтеория конечных полугрупп . Спрингер Монографии по математике. Springer, New York, 2009. XXII + 666 стр. ISBN: 978-0-387-09780-0

J.-E. Штырь
источник
Спасибо за Ваш ответ! Но действительно ли это свойство необходимо, я имею в виду, что оно достаточно, но действительно ли «свойство деления» синтаксического моноида вообще терпит неудачу, и если да, то есть ли у вас пример (или контрпример, что если синтаксический моноид делит другой моноид тогда другой моноид также распознает подмножество, из которого построен синтаксический моноид)?
StefanH