Langues irréductibles

Ce n'est pas nécessairement une question de recherche. Juste une question par curiosité:

J'essaie de comprendre si l'on peut définir des langues "irréductibles". En premier lieu, j'appelle une langue L "réductible" si elle peut s'écrire $L = A \cdot B$ avec et , sinon appelez la langue "irréductible". Est-ce vrai:| A | , | B | > $A \cap B = \emptyset$$|A|,|B|>1$

1) Si P est irréductible, A, B, C sont des langages tels que , et , alors il existe un langage tel que ? Cela correspondrait en nombres entiers au lemme d'Euklid et serait utile pour prouver l'unicité de la "factorisation".$A\cap B = \emptyset$$P \cap C = \emptyset$$A\cdot B = C\cdot P$$B' \cap P = \emptyset$$B = B'\cdot P$

2) Est-il vrai que chaque langue peut être factorisée en un nombre fini de langues irréductibles?

Si quelqu'un a une meilleure idée de la façon de définir un langage "irréductible", je voudrais l'entendre. (Ou y en a-t-il peut-être déjà une définition, que je ne connais pas?)

Voici un contre-exemple à cela:

appeler une langue L "réductible" si elle peut s'écrire $L = A \cdot B$ avec$A \cap B = \emptyset$ et$|A|,|B|>1$ , sinon appelez le langage "irréductible". Est-ce vrai:

1) Si P est irréductible, A, B, C sont des langages tels que $A\cap B = \emptyset$ , $P \cap C = \emptyset$ et $A\cdot B = C\cdot P$ , alors il existe un langage $B' \cap P = \emptyset$ tel que $B = B'\cdot P$ ?

Dans l'alphabet unaire $\{0\}$ , définissez les mots suivants

$$a=0^4,\quad b=0,\qquad c=0^3,\quad p=0^2.$$ Alors$ab=cp$ et ce n'est pas le cas que$b=b'p$ pour tout$b'$ .

Nous obtenons donc un contre-exemple avec les langues singleton

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

Il y a la notion de primalité d'une langue. Il demande si L peut s'écrire comme où aucun facteur ne contient le mot vide. Une langue est primordiale si elle ne peut pas être écrite sous cette forme.$L_1 \cdot L_2$

Pour un langage régulier donné, représenté par un DFA, il est montré dans [MNS] qu'il est PSPACE-complet de décider de la primalité.

[MNS] Wim Martens, Matthias Niewerth et Thomas Schwentick, « Conception de schéma pour les référentiels XML: complexité et traçabilité », 2010. doi: 10.1145 / 1807085.1807117

Un autre papier à regarder:

• Kai Salomaa, « Décompositions linguistiques, primauté et opérations basées sur la trajectoire », 2008.