15

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?)

Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • "if it can be written as $L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$," where ​ $\cdot$ ​ is ... ​ ​ ​ ​ –  Jul 27 '16 at 18:00
  • 1
    $\cdot$ is concatenation –  Jul 27 '16 at 18:06
  • 4
    You may be interested in the paper "Prime Languages", although it is a different notion: http://www.cs.huji.ac.il/~ornak/publications/mfcs13.pdf – Denis Jul 28 '16 at 10:46

3 Answers3

18

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Thomas S
  • 1,417
  • 11
  • 14
14

Another paper to look at:

Glorfindel
  • 359
  • 1
  • 4
  • 10
Jeffrey Shallit
  • 6,986
  • 33
  • 38
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\}.$$

Bjørn Kjos-Hanssen
  • 4,485
  • 2
  • 25
  • 40