The piecewise testable index of a word u, denoted h(u), is the
least integer n such that u is completely defined by listing its (scattered) subwords of length at most n. Here a subword is a subsequence of u, not a factor. Equivalently, h(u) is the least n such that u can be defined in the n-variable BΣ₁ fragment of the first-order logic over words. It was recently shown in [1] that being able to bound or estimate the index of words is an invaluable tool for measuring the complexity of piecewise-testable language.
During his internship, Ritam Raha worked on the problem of efficiently computing h(u). Polynomial-time (cubic) methods were already described in [1] but we managed to propose new algorithms running in O(|A|.|u|), where |A| is the size of the underlying alphabet. We also found unexpected connections between h(u) and m(u), a measure introduced by I. Simon in [2] and mostly forgotten since: m(u) is the least m such that u is m-reduced, i.e., such that removing any letter from u yields a word u’ that has less subwords of length at most m. Since m(u) is easier to compute than h(u), the connections have algorithmic implications. An outcome of this research is that we could characterize the longest words on a 2-letter alphabet with given index, yielding exact bounds for h(u) as a function of the length of u. We could also improve the known bounds (from [1]) on larger alphabets. These results will eventually find their place in a paper.
BIBLIOGRAPHY:
[1] P. Karandikar and Ph. Schnoebelen. The height of piecewise-testable languages with applications in logical complexity. In Proc. 25th EACSL Conf. Computer Science Logic (CSL 2016), Marseille, France, 2016.
[2] I. Simon. Hierarchies of Event with Dot-Depth One. PhD thesis, University of Waterloo, Dept. Applied Analysis and Computer Science, Waterloo, ON, Canada, 1972.