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

$\endgroup$
  • 1
    $\begingroup$ @bjornkjoshanssen: Thank you for your example and your answer! $\endgroup$ – orgesleka May 3 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 at 6:48
19
$\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

$\endgroup$
15
$\begingroup$

Another paper to look at:

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.