Irreducible languages

Question

This is not necessarily a research question. Just a question out of curiosity:

I am trying to understand if one can define "irreducible" languages. As a first guess I call a language L "reducible" if it can be written as $L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$, otherwise call the language "irreducible". Is it true:

1) If P is irreducible, A,B, C are languages such that $A\cap B = \emptyset$, $P \cap C = \emptyset$ and $A\cdot B = C\cdot P$, then there exists a language $B' \cap P = \emptyset$ such that $B = B'\cdot P$? This would correspond in integers to the lemma of Euklid and would be usefull to prove uniqueness of "factorization".

2) Is it true that every language can be factored in a finite number of irreducible languages?

If someone has a better idea on how to define "irreducible" language, I would like to hear it. (Or is there maybe already a definiton of this, which I am unaware of?)

Answer 1

Here's a counterexample to this:

call a language L "reducible" if it can be written as $L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$, otherwise call the language "irreducible". Is it true:

1) If P is irreducible, A,B, C are languages such that $A\cap B = \emptyset$, $P \cap C = \emptyset$ and $A\cdot B = C\cdot P$, then there exists a language $B' \cap P = \emptyset$ such that $B = B'\cdot P$?

In the unary alphabet $\{0\}$, define the following words $$a=0^4,\quad b=0,\qquad c=0^3,\quad p=0^2.$$ Then $ab=cp$ and it is not the case that $b=b'p$ for any $b'$.

So we get a counterexample with the singleton languages $$P=\{p\},\quad A=\{a\},\quad B=\{b\},\quad C=\{c\}.$$

Answer 2

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

Answer 3

Another paper to look at:

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