Abstract
We introduce an algorithm that learns the class of Tier-based Strictly k-Local (TSL\(_k\)) formal languages in polynomial time on a sample of positive data whose size is bounded by a constant. The TSL\(_k\) languages are useful in modeling the cognition of sound patterns in natural language [6, 11], and it is known that they can be efficiently learned from positive data in the case that \(k=2\) [9]. We extend this result to any k and improve on its time efficiency. We also refine the definition of a canonical TSL\(_k\) grammar and prove several properties about these grammars that aid in their learning.
We thank Jane Chandlee, Gunnar Hansson, Jeff Heinz, and three reviewers.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsReferences
García, P., Vidal, E., Oncina, J.: Learning locally testable languages in the strict sense. In: Proceedings of Workshop on Algorithmic Learning Theory, pp. 325–338 (1990)
Gold, M.E.: Language identification in the limit. Inf. Control 10, 447–474 (1967)
Heinz, J.: The inductive learning of phonotactic patterns. Ph.D. thesis, University of California, Los Angeles (2007)
Heinz, J.: Learning long-distance phonotactics. Linguist. Inq. 41, 623–661 (2010)
Heinz, J.: Computational phonology part I: foundations. Lang. Linguist. Compass 5(4), 140–152 (2011)
Heinz, J., Rawal, C., Tanner, H.G.: Tier-based strictly local constraints for phonology. In: Proceedings of 49th Annual Meeting of the Association for Computational Linguistics, pp. 58–64. Association for Computational Linguistics, Portland, June 2011
de la Higuera, C.: Characteristic sets for polynomial grammatical inference. Mach. Learn. 27(2), 125–138 (1997)
Jardine, A.: Learning tiers for long-distance phonotactics. In: Proceedings of 6th Conference on Generative Approaches to Language Acquisition North America (GALANA 2015), pp. 60–72 (2016)
Jardine, A., Heinz, J.: Learning tier-based strictly 2-local languages. Trans. Assoc. Comput. Linguist. 4, 87–98 (2016)
Jurafsky, D., Martin, J.H.: Speech and Language Processing, 2nd edn. Pearson Prentice Hall, Upper Saddle River (2009)
McMullin, K.: Tier-based locality in long-distance phonotactics: learnability and typology. Ph.D. thesis, University of British Columbia (2016)
McMullin, K., Hansson, G.Ó: Long-distance phonotactics as tier-based strictly 2-local languages. In: Proceedings of 2014 Annual Meeting on Phonology. Linguistic Society of America, Washington, DC (2016)
McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)
Nevins, A.: Locality in Vowel Harmony. No. 55 in Linguistic Inquiry Monographs. MIT Press, Cambridge (2010)
Odden, D.: Adjacency parameters in phonology. Language 70(2), 289–330 (1994)
Rogers, J., Heinz, J., Fero, M., Hurst, J., Lambert, D., Wibel, S.: Cognitive and sub-regular complexity. In: Morrill, G., Nederhof, M.-J. (eds.) FG 2012-2013. LNCS, vol. 8036, pp. 90–108. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39998-5_6
Rogers, J., Pullum, G.: Aural pattern recognition experiments and the subregular hierarchy. J. Log. Lang. Inf. 20, 329–342 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Jardine, A., McMullin, K. (2017). Efficient Learning of Tier-Based Strictly k-Local Languages. In: Drewes, F., Martín-Vide, C., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2017. Lecture Notes in Computer Science(), vol 10168. Springer, Cham. https://doi.org/10.1007/978-3-319-53733-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-53733-7_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53732-0
Online ISBN: 978-3-319-53733-7
eBook Packages: Computer ScienceComputer Science (R0)