Questioning to Resolve Transduction Problems
- Eric Meinhardt (UC San Diego)
- Anna Mai (UC San Diego)
- Eric Bakovic (UC San Diego)
- Adam McCollum (Rutgers University)
Abstract
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), 453-454. doi: https://doi.org/10.7275/d6yx-f982
Downloads:
Download PDF