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 Σ 0 B , a set of formulas decidable in polytime, and Σ 1 B , a set of formulas with the property that those provable in S yield polytime algorithms.
Authors
Soltys M; Mhaskar N
Journal
Discrete Applied Mathematics, Vol. 274, , pp. 141–151