Idiomas irredutíveis

Esta não é necessariamente uma questão de pesquisa. Apenas uma pergunta por curiosidade:

Estou tentando entender se é possível definir linguagens "irredutíveis". Como primeira hipótese, chamo uma linguagem L de "redutível" se puder ser escrita como com A ∩ B = ∅ e | Um | , | B | > 1 , caso contrário, chame o idioma de "irredutível". É verdade:$L = A \cdot B$$A \cap B = \emptyset$$|A|,|B|>1$

1) Se P é irredutível, A, B, C são idiomas tais que , P ∩ C = ∅ e A ⋅ B = C ⋅ P , então existe um idioma B ′ ∩ P = ∅ tal que B = B ′ ⋅ P ? Isso corresponderia em números inteiros ao lema de Euklid e seria útil para provar a singularidade da "fatoração".$A\cap B = \emptyset$$P \cap C = \emptyset$$A\cdot B = C\cdot P$$B' \cap P = \emptyset$$B = B'\cdot P$

2) É verdade que toda língua pode ser fatorada em um número finito de línguas irredutíveis?

Se alguém tiver uma idéia melhor sobre como definir linguagem "irredutível", eu gostaria de ouvi-la. (Ou talvez já exista uma definição disso, da qual desconheço?)

Aqui está um contra-exemplo para isso:

chame um idioma L de "redutível" se puder ser escrito como $L = A \cdot B$ com $A \cap B = \emptyset$ e $|A|,|B|>1$ , caso contrário, chame o idioma de "irredutível". É verdade:

1) Se P é irredutível, A, B, C são idiomas tais que $A\cap B = \emptyset$ , $P \cap C = \emptyset$ e $A\cdot B = C\cdot P$ , então existe um idioma $B' \cap P = \emptyset$ tal que $B = B'\cdot P$ ?

No alfabeto unário $\{0\}$ , defina as seguintes palavras

There is the notion of primality of a language. It asks whether L can be written as $L_1 \cdot L_2$ where neither factor contains the empty word. A language is prime if it cannot be written in this form.

For a given regular language, represented by a DFA, it is shown in [MNS] that it is PSPACE-complete to decide primality.

[MNS] Wim Martens, Matthias Niewerth and Thomas Schwentick, "Schema design for XML repositories: complexity and tractability", 2010. doi:10.1145/1807085.1807117

Another paper to look at:

• Kai Salomaa, "Language Decompositions, Primality, and Trajectory-Based Operations", 2008.