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.

Leave a Reply

Your email address will not be published. Required fields are marked *