Mdthbs

Why is an old chain unsafe?

N.B. ligature in Latex

How is the claim "I am in New York only if I am in America" the same as "If I am in New York, then I am in America?

Why has Russell's definition of numbers using equivalence classes been finally abandoned? ( If it has actually been abandoned).

What would the Romans have called "sorcery"?

How can the DM most effectively choose 1 out of an odd number of players to be targeted by an attack or effect?

Why did the Germans forbid the possession of pet pigeons in Rostov-on-Don in 1941?

Can an x86 CPU running in real mode be considered to be basically an 8086 CPU?

Why don't electron-positron collisions release infinite energy?

How does one intimidate enemies without having the capacity for violence?

Why are 150k or 200k jobs considered good when there are 300k+ births a month?

If Manufacturer spice model and Datasheet give different values which should I use?

What is the command to reset a PC without deleting any files

How old can references or sources in a thesis be?

I’m planning on buying a laser printer but concerned about the life cycle of toner in the machine

Japan - Plan around max visa duration

Is it tax fraud for an individual to declare non-taxable revenue as taxable income? (US tax laws)

Why CLRS example on residual networks does not follows its formula?

Could a US political party gain complete control over the government by removing checks & balances?

Can a German sentence have two subjects?

The use of multiple foreign keys on same column in SQL Server

Circuitry of TV splitters

Is it possible to make sharp wind that can cut stuff from afar?

I see my dog run

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

Base-k representations of the co-domain of a polynomial - is it context-free?For a language to be programmable, is it mandatory that it be based on a context free grammarSufficient conditions for the regularity of a context-free languageDoes there exist an extension of regular expressions that captures the context free languages?Are deterministic context-free languages closed under outfix (or other erasing operations)Is SAT a context-free language?Is equivalence of unambiguous context-free languages decidable?Example of context-free tree language which can not be generated by monadic CFTGFor which $R$ is ${0^a10^b10^cmid R(a,b,c)}$ context-free?Continuous mathematics and formal language theoryIs { ww' | HamDist(w,w')>1 } context-free?

19

5

$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, which perhaps has been solved by domotorp, see his preprint)

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

edited 9 hours ago

Marzio De Biasi

asked 2 days ago

Marzio De BiasiMarzio De Biasi

18.5k243114

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  For your second example, I wrote a paper from my answer which is under review (and the first feedback was positive): arxiv.org/abs/1901.03913
  $endgroup$
  – domotorp
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  There are many variants of the first example that are not known to be context-free, I don't know if you want to include them as separate examples; see Chapter 10 of the linked book (Kászonyi-Katsura Theory).
  $endgroup$
  – domotorp
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @domotorp: I just gave it a look (I'm still reading chapter 2) ... they seem to me more technical attempts to attack the main problem.
  $endgroup$
  – Marzio De Biasi
  8 hours ago
  

  
  
  
  

add a comment | 

19

5

$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, which perhaps has been solved by domotorp, see his preprint)

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

edited 9 hours ago

Marzio De Biasi

asked 2 days ago

Marzio De BiasiMarzio De Biasi

18.5k243114

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  For your second example, I wrote a paper from my answer which is under review (and the first feedback was positive): arxiv.org/abs/1901.03913
  $endgroup$
  – domotorp
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  There are many variants of the first example that are not known to be context-free, I don't know if you want to include them as separate examples; see Chapter 10 of the linked book (Kászonyi-Katsura Theory).
  $endgroup$
  – domotorp
  9 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @domotorp: I just gave it a look (I'm still reading chapter 2) ... they seem to me more technical attempts to attack the main problem.
  $endgroup$
  – Marzio De Biasi
  8 hours ago
  

  
  
  
  

add a comment | 

$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, which perhaps has been solved by domotorp, see his preprint)

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

edited 9 hours ago

Marzio De Biasi

asked 2 days ago

Marzio De BiasiMarzio De Biasi

18.5k243114

$endgroup$

share|cite|improve this question

edited 9 hours ago

Marzio De Biasi

asked 2 days ago

Marzio De BiasiMarzio De Biasi

18.5k243114

share|cite|improve this question

edited 9 hours ago

Marzio De Biasi

asked 2 days ago

Marzio De BiasiMarzio De Biasi

18.5k243114

asked 2 days ago

Marzio De BiasiMarzio De Biasi

18.5k243114

asked 2 days ago

Marzio De BiasiMarzio De Biasi

18.5k243114

2 Answers
2

active

oldest

votes

11

$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

edited 2 days ago

answered 2 days ago

AryehAryeh

5,89211841

$endgroup$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $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
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
  $endgroup$
  – Aryeh
  2 days 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
  2 days 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
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  On the contrary, Emil, the "standard" proof that the primes in binary are not context-free easily suffices to prove that every infinite set of primes is not context-free. So if there are infinitely many twin primes, the result is immediate.
  $endgroup$
  – Jeffrey Shallit
  2 days ago
  

  
  
  
  

 | 
show 3 more comments

11

$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

answered 2 days ago

Jeffrey ShallitJeffrey Shallit

6,5332636

$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
  2 days ago
  

  
  
  
  

add a comment | 

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

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

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

Name

Email

Required, but never shown

11

$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

edited 2 days ago

answered 2 days ago

AryehAryeh

5,89211841

$endgroup$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $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
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
  $endgroup$
  – Aryeh
  2 days 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
  2 days 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
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  On the contrary, Emil, the "standard" proof that the primes in binary are not context-free easily suffices to prove that every infinite set of primes is not context-free. So if there are infinitely many twin primes, the result is immediate.
  $endgroup$
  – Jeffrey Shallit
  2 days ago
  

  
  
  
  

 | 
show 3 more comments

11

$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

edited 2 days ago

answered 2 days ago

AryehAryeh

5,89211841

$endgroup$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $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
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  If there are infinitely many twin primes, how do you see that $L_{TP}$ is regular?
  $endgroup$
  – Aryeh
  2 days 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
  2 days 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
  2 days ago
  
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  On the contrary, Emil, the "standard" proof that the primes in binary are not context-free easily suffices to prove that every infinite set of primes is not context-free. So if there are infinitely many twin primes, the result is immediate.
  $endgroup$
  – Jeffrey Shallit
  2 days ago
  

  
  
  
  

 | 
show 3 more comments

$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

edited 2 days ago

answered 2 days ago

AryehAryeh

5,89211841

$endgroup$

share|cite|improve this answer

edited 2 days ago

answered 2 days ago

AryehAryeh

5,89211841

answered 2 days ago

AryehAryeh

5,89211841

answered 2 days ago

AryehAryeh

5,89211841

11

$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

answered 2 days ago

Jeffrey ShallitJeffrey Shallit

6,5332636

$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
  2 days ago
  

  
  
  
  

add a comment | 

11

$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

answered 2 days ago

Jeffrey ShallitJeffrey Shallit

6,5332636

$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
  2 days ago
  

  
  
  
  

add a comment | 

$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

answered 2 days ago

Jeffrey ShallitJeffrey Shallit

6,5332636

$endgroup$

share|cite|improve this answer

answered 2 days ago

Jeffrey ShallitJeffrey Shallit

6,5332636

answered 2 days ago

Jeffrey ShallitJeffrey Shallit

6,5332636

answered 2 days ago

Jeffrey ShallitJeffrey Shallit

6,5332636