Verallgemeinerung der Aussage, dass ein Monoid die Sprache erkennt, wenn das syntaktische Monoid das Monoid teilt

9

Sei A ein endliches Alphabet. Für eine gegebene Sprache LA das syntaktische Monoid M(L) ein in der formalen Sprachtheorie bekannter Begriff. Weiterhin erkennt ein Monoid M eine Sprache L wenn ein Morphismus φ:AM so dass L=φ1(φ(L))) .

Dann haben wir das schöne Ergebnis:

Ein Monoid M erkennt LA wenn M(L) ein homomorphes Bild eines Submonoids von M (geschrieben als M(L)M ).

Das Obige ist normalerweise Zustände im Kontext regulärer Sprachen, und dann sind die obigen Monoide alle endlich.

Nehmen wir nun an, wir ersetzen durch ein beliebiges Monoid N und sagen, dass eine Teilmenge L N von M erkannt wird, wenn ein Morphismus φ : N M existiert, so dass L = φ - 1 ( φ ( L ) ) . Dann haben wir immer noch das, wenn M L erkennt , dann ist M ( L ) M (siehe S. Eilenberg, Automaten, Maschinen und Sprachen, Band B), aber gilt das Gegenteil?ANLNMφ:NML=φ1(φ(L))MLM(L)M

Im Beweis für die Umkehrung durch Ausnutzung der Eigenschaft bewiesen, dass, wenn N = φ ( M ) für einen Morphismus φ : M N und ψ : A N auch ein Morphismus ist, wir ρ : A ∗ finden könnenM so, dass φ ( ρ ( u ) ) = ψ ( u ) gilt, einfach durch Auswahl von ρ ( x ) AN=φ(M)φ:MNψ:ANρ:AMφ(ρ(u))=ψ(u) für jedes x A und von diesem auf eine morphism erstreckt A * zu M . Dies funktioniert jedoch nicht für beliebige Monoide N, daher erwarte ich, dass die obige Umkehrung dann falsch ist. Und wenn es falsch ist, für welche Art von Monoid neben A ist es noch wahr, und haben diese Monoide in der Forschungsliteratur Beachtung gefunden?ρ(x)φ1(ψ(x))xAAMNA

StefanH
quelle
Ende des ersten Absatzes: Wäre nicht L statt A?
Mateus de Oliveira Oliveira
@MateusdeOliveiraOliveira Ja, danke, dass du es bemerkt hast!
StefanH

Antworten:

5

Ja, diese Monoide haben in der Forschungsliteratur Beachtung gefunden und führen tatsächlich zu schwierigen Fragen.

Definition . Ein Monoid heißt projektiv, wenn die folgende Eigenschaft gilt: Wenn f : N R ein Monoidmorphismus ist und h : T R ein surjektiver Morphismus ist, dann existiert ein Morphismus g : N T, so dass f = h g .Nf:NRh:TRg:NTf=hg

Eine lange Diskussion über projektive Monoide finden Sie in [1] direkt nach Definition 4.1.33. Es wird insbesondere gezeigt, dass jede projektive endliche Halbgruppe eine Band ist (eine Halbgruppe, in der jedes Element idempotent ist). Aber das Gegenteil ist nicht der Fall und es ist tatsächlich ein offenes Problem zu entscheiden, ob eine endliche Halbgruppe projektiv ist.

q

J.-E. Stift
quelle
Danke für deine Antwort! Aber ist diese Eigenschaft wirklich notwendig, ich meine, sie ist ausreichend, aber versagt die "Divisionseigenschaft" des syntaktischen Monoids im Allgemeinen wirklich, und wenn ja, haben Sie ein Beispiel (oder ein Gegenbeispiel, wenn das syntaktische Monoid ein anderes Monoid teilt , dann erkennt das andere Monoid auch die Teilmenge, aus der das syntaktische Monoid aufgebaut ist)?
StefanH