Journal article
A formal framework for Stringology
Abstract
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
Publisher
Elsevier
Publication Date
March 2020
DOI
10.1016/j.dam.2018.03.010
ISSN
0166-218X