# Our paper with Neerja Mhaskar on logic of stringology appeard in Discrete Applied Math

In this paper, A new formal framework for Stringology is proposed, which consists of a three-sorted logical theory $S$ designed to capture the combinatorial reasoning about finite strings. We propose a language $L_S$ for expressing assertions about strings, and study in detail two sets of formulas $\Sigma_0^B$, a set of formulas decidable in polytime, and $\Sigma_1^B$, a set of formulas with the property that those provable in $S$ yield polytime algorithms.