Nieredukowalne języki

To niekoniecznie jest pytanie badawcze. Tylko pytanie z ciekawości:

Próbuję zrozumieć, czy można zdefiniować języki „nieredukowalne”. Na pierwszy rzut oka nazywam język L „redukowalny”, jeśli można go zapisać jako z i , w przeciwnym razie nazywam język „nieredukowalny” . Czy to prawda:$L = A \cdot B$$A \cap B = \emptyset$$|A|,|B|>1$

1) Jeśli P jest nieredukowalne, A, B, C są takimi językami, że , i , wówczas istnieje język taki, że ? Odpowiadałoby to liczbom całkowitym lematu Euklidesa i byłoby przydatne do wykazania wyjątkowości „faktoryzacji”.$A\cap B = \emptyset$$P \cap C = \emptyset$$A\cdot B = C\cdot P$$B' \cap P = \emptyset$$B = B'\cdot P$

2) Czy to prawda, że ​​każdy język można uwzględnić w skończonej liczbie języków nieredukowalnych?

Jeśli ktoś ma lepszy pomysł na zdefiniowanie „nieredukowalnego” języka, chciałbym go usłyszeć. (A może jest już to określone, czego nie jestem świadomy?)

Oto kontrprzykład na to:

nazwać język L „redukowalny”, jeśli można go zapisać jako $L = A \cdot B$ z $A \cap B = \emptyset$ i $|A|,|B|>1$ , w przeciwnym razie nazwij język „nieredukowalnym”. Czy to prawda:

1) Jeśli P jest nieredukowalne, A, B, C są takimi językami, że $A\cap B = \emptyset$ , $P \cap C = \emptyset$ i $A\cdot B = C\cdot P$ , wówczas istnieje język $B' \cap P = \emptyset$ taki, że $B = B'\cdot P$ ?

W unarnym alfabecie $\{0\}$ zdefiniuj następujące słowa

$$a=0^4,\quad b=0,\qquad c=0^3,\quad p=0^2.$$ Zatem$ab=cp$ i nie jest przypadkiem, że$b=b'p$ dla dowolnego$b'$ .

Otrzymujemy więc kontrprzykład z pojedynczymi językami

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

Istnieje pojęcie pierwotności języka. Pyta, czy L można zapisać jako gdzie żaden czynnik nie zawiera pustego słowa. Język jest najważniejszy, jeśli nie można go napisać w tej formie.$L_1 \cdot L_2$

Dla danego języka regularnego, reprezentowanego przez DFA, w [MNS] pokazano, że decydowanie o pierwszeństwie ma system PSPACE-complete.

[MNS] Wim Martens, Matthias Niewerth i Thomas Schwentick, „ Projektowanie schematu dla repozytoriów XML: złożoność i łatwość obsługi ”, 2010. doi: 10.1145 / 1807085.1807117

Kolejny artykuł do obejrzenia:

• Kai Salomaa, „ Dekompozycje językowe, pierwotność i operacje oparte na trajektorii ”, 2008.