Extended Abstract
Authors: Huteng Dai (Rutgers University) , Richard Futrell (University of California, Irvine)
Our goal is to link two different formal notions of complexity: the complexity classes defined by Formal Language Theory (FLT)—in particular, the Sub-regular Hierarchy (Rogers et al., 2013; Lai, 2015; Heinz, 2018)—and Statistical Com- plexity Theory (Feldman and Crutchfield, 1998; Crutchfield and Marzen, 2015). The motivation for exploring this connection is that factors involving memory resources have been hypothesized to explain why phonological processes seem to inhabit the Sub-regular Hierarchy, and Statistical Complexity Theory gives an information-theoretic characterization of memory use. It is currently not known whether statistical complexity and FLT define equivalent complexity classes, or whether statistical complexity cross-cuts the usual FLT hierarchies. Our work begins to bridge the gap between FLT and Information Theory by presenting characterizations of certain Sub-regular languages in terms of statistical complexity
Keywords: Formal Language Theory, Information Theory, Subregular Hierarchy, Statistical Complexity, Phonology, Probabilistic Finite-state Automata
How to Cite: Dai, H. & Futrell, R. (2020) “Information-theoretic Characterization of the Sub-regular Hierarchy”, Society for Computation in Linguistics. 3(1). doi: https://doi.org/10.7275/c521-qn83