Research Report: Parsing with the Logic FC
Owen M. Bell, Sam M. Thompson, Dominik D. Freydenberger · 2025
FC is a logic on strings that has been primarily studied in database theory for the purpose of information extraction. In this report, we argue that it can be used for more. In particular, we explain how FC and its various extensions can be used as a unifying framework for combining parsers that aligns with the principles of Language-Theoretic Security (LangSec). We first survey the recent literature on FC and its extensions, and explain the different criteria we have for efficiency. We then describe how FC and its extensions can be seen as a replacement for regex, and contextualise FC with Language-Theoretic Security. Finally, we explain how, due to the natural compositionality of the model, we can pull the extensions of FC together into a framework for combining parsers.