Несводимые языки

Это не обязательно вопрос исследования. Просто вопрос из любопытства:

Я пытаюсь понять, можно ли определить «неприводимые» языки. В качестве первого предположения я называю язык L «сводимым», если он может быть записан как $L = A \cdot B$ с и , в противном случае называю язык «неприводимым». Это правда:$A \cap B = \emptyset$$|A|,|B|>1$

1) Если P неприводимо, A, B, C - языки такие, что , и , то существует язык такой, что ? Это будет соответствовать в целых числах лемме Евклида и будет полезным для доказательства уникальности «факторизации».P ∩ C = ∅ A ⋅ B = C ⋅ P B ′ ∩ P = ∅ B = B ′ ⋅ $A\cap B = \emptyset$$P \cap C = \emptyset$$A\cdot B = C\cdot P$$B' \cap P = \emptyset$$B = B'\cdot P$

2) Правда ли, что каждый язык может быть разложен на конечное число неприводимых языков?

Если у кого-то есть идея о том, как определить «неприводимый» язык, я бы хотел услышать это. (Или, может быть, это уже определено, о чем я не знаю?)

Вот контрпример к этому:

назовем язык L «сводимым», если он может быть записан как $L = A \cdot B$ с $A \cap B = \emptyset$ и $|A|,|B|>1$ , иначе назовите язык "неприводимым". Это правда:

1) Если P неприводимо, A, B, C - языки такие, что $A\cap B = \emptyset$ , $P \cap C = \emptyset$ и $A\cdot B = C\cdot P$ , то существует такой язык $B' \cap P = \emptyset$ , что $B = B'\cdot P$ ?

В унарном алфавите $\{0\}$ определите следующие слова

$$a=0^4,\quad b=0,\qquad c=0^3,\quad p=0^2.$$ Тогда$ab=cp$ и это не тот случай, когда$b=b'p$ для любого$b'$ .

Таким образом, мы получаем контрпример с одноязычными языками

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

Существует понятие первичности языка. Он спрашивает, можно ли записать как L 1 ⋅ L 2, где ни один из факторов не содержит пустое слово. Язык прост, если он не может быть записан в этой форме.$L_1 \cdot L_2$

Для данного регулярного языка, представленного DFA, в [MNS] показано, что он является PSPACE-полным для определения первичности.

[MNS] Вим Мартенс, Матиас Неверт и Томас Швентик, « Разработка схемы для репозиториев XML: сложность и удобство использования », 2010. doi: 10.1145 / 1807085.1807117

Еще одна статья, на которую стоит посмотреть:

• Кай Саломаа, « Языковые разложения, первичность и траекторные операции », 2008.