The following is a problem inspired from quantitative program verification. It is more vague than ``Prove or disprove whether XYZ holds'', but in turn has real applications in probabilistic verification. I posed this problem several times to several different machine learning experts and none of them were able (or interested) to help me with this problem. I now hope that the automata (learning) experts can help me out.
We would like to learn / guess the limit of the sequence \[ 1, \quad \frac{3}{2}, \quad \frac{7}{4}, \quad \frac{15}{8}, \quad {\dots} \quad {}\longrightarrow{} \quad 2 \] In order to approach this problem more systematically, we do have – in practice – access to a more symbolic representation of this sequence, namely \[ 1, \quad 1 + q, \quad 1 + q + q^2, \quad 1 + q + q^2 + q^3, \quad {\dots} \quad {}\longrightarrow{} \quad \frac{1}{1 - q}~.\] The limit $\frac{1}{1-q}$ has Taylor expansion \[ 1 + q + q^2 + q^3 + q^4 + q^5 + \cdots \] So learning the limit of this sequence appears like wanting to learn the ``regular language''~$q^*$ but only from positive examples: First we get $1 ({=} \varepsilon)$, then $q$, then $q^2$, and so on. So the problem is: How can we learn / guess regular languages from positive examples (reasonably well)?
Going one step further, we would also like to learn the following sequence (which did not occur to me in practice, but I made up): \[ q, \quad q + 2q^2, \quad q + 2q^2 + 3q^3, \quad q + 2q^2 + 3q^3 + 4q^4, \quad {\dots} \quad {}\longrightarrow{} \quad \frac{1}{(1 - q)^2}\] The limit $\frac{1}{(1-q)^2}$ has Taylor expansion $q + 2q^2 + 3q^3 + 4q^4 + 5q^5 + \cdots$
So learning the limit of this sequence appears like wanting to learn a weighted ``regular language'' (are there regular expressions for weighted languages?) but only from positive examples. So: How can we learn / guess weighted regular languages from positive examples (reasonably well)?
Another example – this one again does actually occur in practice – is learning the limit of the (more complicated) sequence \[ 1, \quad 2, \quad 2 + 2q - q^2, \quad 2 + 2q + 2q^2 - 2q^3, \quad {\dots} \quad {}\longrightarrow{} \quad \textnormal{???} \] Notice that, for $q^2$, the weight changed from ${-}1$ to $2$ from iteration 3 to 4. The same can be observed for the $q^0$ weight from iteration 1 to 2. I hence suspect that this is not ``learning from positive examples'' anymore, but something slightly more general. In particular, I do believe that the weights for each $q^n$ stabilize at some iteration and never again change. So our problem is: From what kind of examples are we even trying to learn here? Can such learning be done (reasonably well)?