Hello @DanielFischer!!!
I want to explain why the execution time of partition at an array of length n is $\Theta(n)$. That is the function partition:
partition(A,p,r){
x<-A[r]
i<-p-1
for j<-p to r-1
if A[j]<=x then
i<-i+1
swap(A[i],A[j])
swap(A[i+1],A[r])
return i+1
See here for an intro.
So there is not really a lot of research into the problem (say as much as research into FLT) at the moment. I thought we could come up with the obvious properties that smallest grammars must have. Here are some:
Prop. 0.0 There exist no unused rules in a smallest gramma...
I have this condition:
$$ \forall v\in \ker(-\Delta_p-\lambda)\setminus\{0\}:\\(p-1)\int_0^{\pi} h(x) v(x)
dx< \underline{F(+\infty)}\int_0^{\pi} v^+(x) dx+\overline{
F(-\infty)}\int_0^{\pi} v^-(x) dx$$ where $h\in L^{p'}(0,\pi),
p'=\frac{p}{p-1}, p>1$ and $$F(x)=\begin{cases}\frac{p}{x}\...
