Learning Tier-based Strictly 2-Local Languages

Adam Jardine, Jeffrey Heinz


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
Bibkey:
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)
Copy Citation:
PDF:
https://aclanthology.org/Q16-1007.pdf