Irreduzible Sprachen

Dies ist nicht unbedingt eine Forschungsfrage. Nur eine Frage aus Neugier:

Ich versuche zu verstehen, ob man "irreduzible" Sprachen definieren kann. Als erste Vermutung nenne ich eine Sprache L "reduzierbar", wenn sie als mit A ∩ B = ∅ und | geschrieben werden kann A | , | B | > 1 , sonst die Sprache "irreduzibel" nennen. Ist es wahr:$L = A \cdot B$$A \cap B = \emptyset$$|A|,|B|>1$

1) Wenn P irreduzibel ist, A, B, C Sprachen sind, so dass , P ∩ C = ∅ und A ⋅ B = C ⋅ P , dann existiert eine Sprache B ' ∩ P = ∅, so dass B = B ' ⋅ P ? Dies würde in ganzen Zahlen dem Lemma von Euklid entsprechen und wäre nützlich, um die Eindeutigkeit der "Faktorisierung" zu beweisen.$A\cap B = \emptyset$$P \cap C = \emptyset$$A\cdot B = C\cdot P$$B' \cap P = \emptyset$$B = B'\cdot P$

2) Stimmt es, dass jede Sprache in einer endlichen Anzahl von irreduziblen Sprachen berücksichtigt werden kann ?

Wenn jemand eine bessere Idee hat, wie man "irreduzible" Sprache definiert, würde ich es gerne hören. (Oder gibt es vielleicht schon eine Definition davon, von der ich nichts weiß?)

Hier ist ein Gegenbeispiel dazu:

nenne eine Sprache L "reduzierbar", wenn sie geschrieben werden kann als $L = A \cdot B$ mit $A \cap B = \emptyset$ und $|A|,|B|>1$ , sonst die Sprache "irreduzibel" nennen. Ist es wahr:

1) Wenn P irreduzibel ist, A, B, C Sprachen sind, so dass $A\cap B = \emptyset$ , $P \cap C = \emptyset$ und $A\cdot B = C\cdot P$ , dann gibt es eine Sprache $B' \cap P = \emptyset$ so dass $B = B'\cdot P$ ?

Definieren Sie im unären Alphabet $\{0\}$ die folgenden Wörter

$$a=0^4,\quad b=0,\qquad c=0^3,\quad p=0^2.$$ Dann ist$ab=cp$ und es ist nicht der Fall, dass$b=b'p$ für irgendein$b'$ .

Wir erhalten also ein Gegenbeispiel mit den Singleton-Sprachen

$$P=\{p\},\quad A=\{a\},\quad B=\{b\},\quad C=\{c\}.$$

$L_1 \cdot L_2$

Für eine bestimmte reguläre Sprache, die durch einen DFA dargestellt wird, wird in [MNS] gezeigt, dass die Entscheidung über die Primalität PSPACE-vollständig ist.

[MNS] Wim Martens, Matthias Niewerth und Thomas Schwentick, " Schemadesign für XML-Repositorys: Komplexität und Nachvollziehbarkeit ", 2010. doi: 10.1145 / 1807085.1807117

Ein weiteres Papier zum Anschauen:

• Kai Salomaa, " Sprachzerlegungen, Primalität und Flugbahn-basierte Operationen ", 2008.