15
$\begingroup$

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

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

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\}.$$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @bjornkjoshanssen: Thank you for your example and your answer! $\endgroup$ – user35803 May 3 '19 at 6:40
  • $\begingroup$ @orgesleka You're welcome... I guess concatenation is more like addition than like multiplication $\endgroup$ – Bjørn Kjos-Hanssen May 3 '19 at 6:48
18
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
14
$\begingroup$

Another paper to look at:

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy