Abstract
Authors: Eric Meinhardt (UC San Diego) , Anna Mai (UC San Diego) , Eric Bakovic (UC San Diego) , Adam McCollum (Rutgers University)
Elgot & Mezei (1965) show that non-deterministic regular functions (NDRFs) 𝚽 are compositions ρ ⚬ λ of two contradirectional subsequential functions (SSQs), where λ is unbounded lookahead for ρ. Such decompositions facilitate the identification of processes that require supra-SSQ expressivity. We use concepts adapted from decision theory to outline a set of necessary and sufficient properties for a composition ρ ⚬ λ to define a non-SSQ NDRF 𝚽. These conditions define a set of functions between the IF-WDRFs (McCollum et al. 2018, Hao & Andersson 2019) and proper NDRFs, organized in terms of a precise notion of the degree of lookahead that λ provides for ρ.
Keywords: computational phonology, descriptive complexity, formal language theory
How to Cite: Meinhardt, E. , Mai, A. , Bakovic, E. & McCollum, A. (2020) “Questioning to Resolve Transduction Problems”, Society for Computation in Linguistics. 3(1). doi: https://doi.org/10.7275/d6yx-f982