Languages that we cannot (dis)prove to be Context-Free Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?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 HamDist(w,w')>1 context-free?
Why did Israel vote against lifting the American embargo on Cuba?
What was Apollo 13's "Little Jolt" after MECO?
Is Bran literally the world's memory?
Contradiction:Maximum Power Transfer and High resistance of load
What is a 'Key' in computer science?
My admission is revoked after accepting the admission offer
Are these square matrices always diagonalisable?
How did Elite on the NES work?
Book with legacy programming code on a space ship that the main character hacks to escape
Why doesn't the university give past final exams' answers?
Israeli soda type drink
Has a Nobel Peace laureate ever been accused of war crimes?
What *exactly* is electrical current, voltage, and resistance?
How would it unbalance gameplay to rule that Weapon Master allows for picking a fighting style?
State of Debian Stable (Stretch) Repository between time of two versions (e.g. 9.8 to 9.9)
Voltage output waveform of a differentiating amplifier
What helicopter has the most rotor blades?
Protagonist's race is hidden - should I reveal it?
Where did Arya get these scars?
What to do with someone that cheated their way though university and a PhD program?
Will I lose my paid in full property
Can gravitational waves pass through a black hole?
Why isn't everyone flabbergasted about Bran's "gift"?
Like totally amazing interchangeable sister outfit accessory swapping or whatever
Languages that we cannot (dis)prove to be Context-Free
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?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' context-free?
$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 ($ (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
asked Apr 5 at 10:45
Marzio De BiasiMarzio De Biasi
18.6k243114
$endgroup$
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 ($ (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
asked Apr 5 at 10:45
Marzio De BiasiMarzio De Biasi
18.6k243114
$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
Apr 7 at 16:22
$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
Apr 7 at 16:26
$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
Apr 7 at 17:27
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 ($ (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
asked Apr 5 at 10:45
Marzio De BiasiMarzio De Biasi
18.6k243114
$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 ($ (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
reference-request big-list context-free
asked Apr 5 at 10:45
Marzio De BiasiMarzio De Biasi
18.6k243114
asked Apr 5 at 10:45
Marzio De BiasiMarzio De Biasi
18.6k243114
edited Apr 7 at 17:10
Marzio De Biasi
asked Apr 5 at 10:45
Marzio De BiasiMarzio De Biasi
18.6k243114
asked Apr 5 at 10:45
Marzio De BiasiMarzio De Biasi
18.6k243114
asked Apr 5 at 10:45
Marzio De BiasiMarzio De Biasi
18.6k243114
18.6k243114
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
Apr 7 at 16:22
$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
Apr 7 at 16:26
$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
Apr 7 at 17:27
add a comment |
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
Apr 7 at 16:22
$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
Apr 7 at 16:26
$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
Apr 7 at 17:27
1
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
Apr 7 at 16:22
$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
Apr 7 at 16:22
$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
Apr 7 at 16:26
$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
Apr 7 at 16:26
$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
Apr 7 at 17:27
$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
Apr 7 at 17:27
add a comment |
2 Answers
2
active
oldest
votes
$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.
answered Apr 5 at 17:25
Jeffrey ShallitJeffrey Shallit
6,5742636
$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
Apr 5 at 19:00
add a comment |
$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.
answered Apr 5 at 12:26
AryehAryeh
6,02211841
$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
Apr 5 at 13:54
$begingroup$
If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
$endgroup$
– Aryeh
Apr 5 at 14:04
1
$begingroup$
If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
$endgroup$
– Emil Jeřábek
Apr 5 at 14:48
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
Apr 5 at 15:28
5
$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
Apr 5 at 17:21
|
show 3 more comments
Your Answer
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
);
);
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
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
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered Apr 5 at 17:25
Jeffrey ShallitJeffrey Shallit
6,5742636
$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
Apr 5 at 19:00
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.
answered Apr 5 at 17:25
Jeffrey ShallitJeffrey Shallit
6,5742636
$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
Apr 5 at 19:00
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.
answered Apr 5 at 17:25
Jeffrey ShallitJeffrey Shallit
6,5742636
$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.
answered Apr 5 at 17:25
Jeffrey ShallitJeffrey Shallit
6,5742636
answered Apr 5 at 17:25
Jeffrey ShallitJeffrey Shallit
6,5742636
answered Apr 5 at 17:25
Jeffrey ShallitJeffrey Shallit
6,5742636
answered Apr 5 at 17:25
Jeffrey ShallitJeffrey Shallit
6,5742636
6,5742636
$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
Apr 5 at 19:00
add a comment |
$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
Apr 5 at 19:00
$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
Apr 5 at 19:00
$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
Apr 5 at 19:00
add a comment |
$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.
answered Apr 5 at 12:26
AryehAryeh
6,02211841
$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
Apr 5 at 13:54
$begingroup$
If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
$endgroup$
– Aryeh
Apr 5 at 14:04
1
$begingroup$
If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
$endgroup$
– Emil Jeřábek
Apr 5 at 14:48
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
Apr 5 at 15:28
5
$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
Apr 5 at 17:21
|
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.
answered Apr 5 at 12:26
AryehAryeh
6,02211841
$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
Apr 5 at 13:54
$begingroup$
If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
$endgroup$
– Aryeh
Apr 5 at 14:04
1
$begingroup$
If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
$endgroup$
– Emil Jeřábek
Apr 5 at 14:48
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
Apr 5 at 15:28
5
$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
Apr 5 at 17:21
|
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.
answered Apr 5 at 12:26
AryehAryeh
6,02211841
$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.
answered Apr 5 at 12:26
AryehAryeh
6,02211841
edited Apr 5 at 15:21
answered Apr 5 at 12:26
AryehAryeh
6,02211841
answered Apr 5 at 12:26
AryehAryeh
6,02211841
answered Apr 5 at 12:26
AryehAryeh
6,02211841
6,02211841
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
Apr 5 at 13:54
$begingroup$
If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
$endgroup$
– Aryeh
Apr 5 at 14:04
1
$begingroup$
If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
$endgroup$
– Emil Jeřábek
Apr 5 at 14:48
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
Apr 5 at 15:28
5
$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
Apr 5 at 17:21
|
show 3 more comments
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
Apr 5 at 13:54
$begingroup$
If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
$endgroup$
– Aryeh
Apr 5 at 14:04
1
$begingroup$
If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
$endgroup$
– Emil Jeřábek
Apr 5 at 14:48
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
Apr 5 at 15:28
5
$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
Apr 5 at 17:21
3
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
Apr 5 at 13:54
$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
Apr 5 at 13:54
$begingroup$
If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
$endgroup$
– Aryeh
Apr 5 at 14:04
$begingroup$
If there are infinitely many twin primes, how do you see that $L_TP$ is regular?
$endgroup$
– Aryeh
Apr 5 at 14:04
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
Apr 5 at 14:48
$begingroup$
If there are infinitely many twin primes, how do you show that $L_TP$ is not context-free?
$endgroup$
– Emil Jeřábek
Apr 5 at 14:48
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
Apr 5 at 15:28
$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
Apr 5 at 15:28
5
5
$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
Apr 5 at 17:21
$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
Apr 5 at 17:21
|
show 3 more comments
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.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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
Apr 7 at 16:22
$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
Apr 7 at 16:26
$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
Apr 7 at 17:27