A function f is ISL iff there is some k such that f can be described with a SFST for which This theorem helps make clear how ISL functions are Markovian: the output for input symbol a depends on the last (k − 1) input symbols.
each element of the left projection of S is of length (k + 1) and each element of its right projection is at most of length (k + 1) the size of the characteristic sample is in , which is clearly polynomial in the size of the target transducer.