# 22.18 Learning sequences

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)?