Languages that we cannot (dis)prove to be Context-Free












11












$begingroup$


I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.




Is there a recent survey on the subject or an open problem section from a recent conference ?



Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.




The examples I found are:




  • the well known language of Primitive words $Q = { w mid w neq u^i (|u| > 1) }$ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)

  • the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory)


Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_{Goldbach} = { 1^{2n} mid 2n$ cannot be expressed as a sum of two primes$}$). I'm not quite interested in such examples.










share|cite|improve this question











$endgroup$

















    11












    $begingroup$


    I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.




    Is there a recent survey on the subject or an open problem section from a recent conference ?



    Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.




    The examples I found are:




    • the well known language of Primitive words $Q = { w mid w neq u^i (|u| > 1) }$ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)

    • the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory)


    Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_{Goldbach} = { 1^{2n} mid 2n$ cannot be expressed as a sum of two primes$}$). I'm not quite interested in such examples.










    share|cite|improve this question











    $endgroup$















      11












      11








      11


      4



      $begingroup$


      I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.




      Is there a recent survey on the subject or an open problem section from a recent conference ?



      Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.




      The examples I found are:




      • the well known language of Primitive words $Q = { w mid w neq u^i (|u| > 1) }$ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)

      • the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory)


      Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_{Goldbach} = { 1^{2n} mid 2n$ cannot be expressed as a sum of two primes$}$). I'm not quite interested in such examples.










      share|cite|improve this question











      $endgroup$




      I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.




      Is there a recent survey on the subject or an open problem section from a recent conference ?



      Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.




      The examples I found are:




      • the well known language of Primitive words $Q = { w mid w neq u^i (|u| > 1) }$ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)

      • the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory)


      Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_{Goldbach} = { 1^{2n} mid 2n$ cannot be expressed as a sum of two primes$}$). I'm not quite interested in such examples.







      reference-request big-list context-free






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 14 hours ago







      Marzio De Biasi

















      asked 17 hours ago









      Marzio De BiasiMarzio De Biasi

      18.5k243113




      18.5k243113






















          2 Answers
          2






          active

          oldest

          votes


















          7












          $begingroup$

          How about the language $L_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_{TP}$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_{TP}$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_{n+1}-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.






          share|cite|improve this answer











          $endgroup$









          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            14 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
            $endgroup$
            – Aryeh
            14 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            13 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            13 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            12 hours ago





















          6












          $begingroup$

          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${bf t} = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            9 hours ago












          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "114"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f42658%2flanguages-that-we-cannot-disprove-to-be-context-free%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          7












          $begingroup$

          How about the language $L_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_{TP}$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_{TP}$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_{n+1}-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.






          share|cite|improve this answer











          $endgroup$









          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            14 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
            $endgroup$
            – Aryeh
            14 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            13 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            13 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            12 hours ago


















          7












          $begingroup$

          How about the language $L_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_{TP}$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_{TP}$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_{n+1}-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.






          share|cite|improve this answer











          $endgroup$









          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            14 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
            $endgroup$
            – Aryeh
            14 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            13 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            13 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            12 hours ago
















          7












          7








          7





          $begingroup$

          How about the language $L_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_{TP}$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_{TP}$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_{n+1}-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.






          share|cite|improve this answer











          $endgroup$



          How about the language $L_{TP}$ of twin primes? I.e., all pairs of natural numbers $(p,p')$ (represented, say, in unary), such that $p,p'$ are both prime and $p'=p+2$? If twin primes conjecture is true, then $L_{TP}$ is not context-free; otherwise, it's finite.



          Edit: Let me give a quick proof sketch that the twin primes conjecture implies that $L_{TP}$ is not context-free. Associate to any language $L$ its length sequence $0le a_1le a_2leldots$, where the integer $ell$ appears in the sequence iff there is a word of length $ell$ in $L$. It is a consequence of the pumping lemma(s) that for $L$ that are regular or CFL, the length sequence satisfies the bounded differences property: there is an $R>0$ such that $a_{n+1}-a_nle R$ for all $n$. It is an easy and well-known fact in number theory that the primes do not have bounded differences. Finally, any infinite subsequence of a sequence violating the bounded differences property itself must violate it.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 13 hours ago

























          answered 15 hours ago









          AryehAryeh

          5,84411840




          5,84411840








          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            14 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
            $endgroup$
            – Aryeh
            14 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            13 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            13 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            12 hours ago
















          • 2




            $begingroup$
            Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
            $endgroup$
            – Marzio De Biasi
            14 hours ago










          • $begingroup$
            If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
            $endgroup$
            – Aryeh
            14 hours ago










          • $begingroup$
            I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
            $endgroup$
            – Marzio De Biasi
            13 hours ago






          • 1




            $begingroup$
            If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?
            $endgroup$
            – Emil Jeřábek
            13 hours ago






          • 1




            $begingroup$
            Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
            $endgroup$
            – Emil Jeřábek
            12 hours ago










          2




          2




          $begingroup$
          Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
          $endgroup$
          – Marzio De Biasi
          14 hours ago




          $begingroup$
          Nice, thanks! But I'm not quite interested in languages that are linked to unknown conjectures about the (non)finiteness of some sets. BTW if those conjectures are true the resulting language is also regular :-)
          $endgroup$
          – Marzio De Biasi
          14 hours ago












          $begingroup$
          If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
          $endgroup$
          – Aryeh
          14 hours ago




          $begingroup$
          If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
          $endgroup$
          – Aryeh
          14 hours ago












          $begingroup$
          I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
          $endgroup$
          – Marzio De Biasi
          13 hours ago




          $begingroup$
          I mean if (dis)proving a conjecture, results in a finite set. In your case - twin primes - if the conjecture is false.
          $endgroup$
          – Marzio De Biasi
          13 hours ago




          1




          1




          $begingroup$
          If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?
          $endgroup$
          – Emil Jeřábek
          13 hours ago




          $begingroup$
          If there are infinitely many twin primes, how do you show that $L_{TP}$ is not context-free?
          $endgroup$
          – Emil Jeřábek
          13 hours ago




          1




          1




          $begingroup$
          Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
          $endgroup$
          – Emil Jeřábek
          12 hours ago






          $begingroup$
          Oh, sorry, I didn’t notice you represent the numbers in unary. Then it is clear. (I believe that proving this for binary representation would require a considerable progress on the twin primes conjecture.)
          $endgroup$
          – Emil Jeřábek
          12 hours ago













          6












          $begingroup$

          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${bf t} = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            9 hours ago
















          6












          $begingroup$

          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${bf t} = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            9 hours ago














          6












          6








          6





          $begingroup$

          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${bf t} = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.






          share|cite|improve this answer









          $endgroup$



          Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${bf t} = 0110100110010110 cdots $. To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that). But the corresponding result for subwords is still open.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 10 hours ago









          Jeffrey ShallitJeffrey Shallit

          6,4832635




          6,4832635












          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            9 hours ago


















          • $begingroup$
            Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
            $endgroup$
            – Marzio De Biasi
            9 hours ago
















          $begingroup$
          Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
          $endgroup$
          – Marzio De Biasi
          9 hours ago




          $begingroup$
          Great, thanks! If you saw it stated somewhere (perhaps in one of your many papers on the Thue-Morse sequence? ;-) you can add the reference (even if stated in the iterated morphism form).
          $endgroup$
          – Marzio De Biasi
          9 hours ago


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Theoretical Computer Science Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f42658%2flanguages-that-we-cannot-disprove-to-be-context-free%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Statuo de Libereco

          Tanganjiko

          Liste der Baudenkmäler in Enneberg