Abstract
The Tier-based Strictly 2-Local (TSL2) languages are a class of formal languages which have been shown to model long-distance phonotactic generalizations in natural language (Heinz et al., 2011). This paper introduces the Tier-based Strictly 2-Local Inference Algorithm (2TSLIA), the first nonenumerative learner for the TSL2 languages. We prove the 2TSLIA is guaranteed to converge in polynomial time on a data sample whose size is bounded by a constant.- Anthology ID:
- Q16-1007
- Volume:
- Transactions of the Association for Computational Linguistics, Volume 4
- Month:
- Year:
- 2016
- Address:
- Cambridge, MA
- Editors:
- Lillian Lee, Mark Johnson, Kristina Toutanova
- Venue:
- TACL
- SIG:
- Publisher:
- MIT Press
- Note:
- Pages:
- 87–98
- Language:
- URL:
- https://aclanthology.org/Q16-1007
- DOI:
- 10.1162/tacl_a_00085
- Cite (ACL):
- Adam Jardine and Jeffrey Heinz. 2016. Learning Tier-based Strictly 2-Local Languages. Transactions of the Association for Computational Linguistics, 4:87–98.
- Cite (Informal):
- Learning Tier-based Strictly 2-Local Languages (Jardine & Heinz, TACL 2016)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-4/Q16-1007.pdf