Thanks. I would love to chat with you how to factor SP functions!

Thank you for these great questions!

The main goal for this research was not necessarily to beat OSTIA at learning the relevant functions, but to see whether their tiers could be identified efficiently at all. As you rightfully point out, though, the increase from O(n^3) to O(n^5) when compared to OSTIA is disappointingly large. The bulk of the time complexity comes from (1) calculating relevant contributions and (2) extracting information about the prefix function. Kevin and I implement both of these processes by effectively doing nested reads of the sample, but it may be possible to obviate this problematic nesting by using an onward Prefix Tree Transducer (PTT). I suspect that passing the sample once through its onward PTT could (with the right heuristics) extract the contributions necessary to determine the safe/unsafe status of a hypothesized tier element. If this turns out to be the case, the time complexity of tier discovery would reduce to the time complexity of building the onward PTT, which is O(n^2) in the size of the sample.

While I don’t yet know what Lambert’s augmented subsequences would look like in the function case, adapting them to functions is certainly a promising direction. In particular, I think doing so could help with learning the tiers of (M)TSL_k functions for k > 2, which evade the existing algorithms.

Kevin and I are indeed working on SP functions, and the SP_2 functions can handle most of the same patterns as the strongly target-specified MTSL_2 functions, provided there are no “blocking” effects. Learning an SP function requires only the transducer-building step, and modifications of the ISL/OSL algorithms can achieve this while maintaining O(n^2) time complexity, so by virtue of not requiring a tier-discovery step, SP learning is more straightforward than (M)TSL learning. The issue for learning SP functions is that their transducers are exponential in the size of the alphabet, making the amount of necessary data impractical for most cases, since the ISL/OSL algorithms require O(n^2) data in the size of the target transducer. We haven’t yet found a good way of factoring these transducers into a group smaller machines (as is done in some work on SP languages and their acceptors) but finding the right such method could make SP function learning more practical than MTSL function learning when the pattern belongs to both classes.