Tier-Based Strictly Local Stringsets: Perspectives from Model and Automata Theory
- Dakotah Lambert (Stony Brook University)
- James Rogers (Earlham College)
Abstract
Defined by Heinz et al. (2011) the Tier-Based Strictly Local (TSL) class of stringsets has not previously been characterized by an abstract property that allows one to prove a stringset\'s membership or lack thereof. We provide here two such characterizations: a generalization of suffix substitution closure and an algorithm based on deterministic finite-state automata (DFAs). We use the former to prove closure properties of the class. Additionally, we extend the approximation and constraint-extraction algorithms of Rogers and Lambert (2019a) to account for TSL constraints, allowing for free conversion between TSL logical formulae and DFAs.
Keywords: locality, formal language theory, model theory, automata theory
How to Cite:
Lambert, D. & Rogers, J., (2020) “Tier-Based Strictly Local Stringsets: Perspectives from Model and Automata Theory”, Society for Computation in Linguistics 3(1), 330-337. doi: https://doi.org/10.7275/2n1j-pj39
Downloads:
Download PDF