Paper

Tier-Based Strictly Local Stringsets: Perspectives from Model and Automata Theory

Authors: ,

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). doi: https://doi.org/10.7275/2n1j-pj39