Information-theoretic Characterization of the Sub-regular Hierarchy
- Huteng Dai (Rutgers University)
- Richard Futrell (University of California, Irvine)
Abstract
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), 445-448. doi: https://doi.org/10.7275/c521-qn83
Downloads:
Download PDF