Efficient learning of tier-based strictly k-local languages

Adam Jardine, Kevin McMullin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


We introduce an algorithm that learns the class of Tier-based Strictly k-Local (TSLk) formal languages in polynomial time on a sample of positive data whose size is bounded by a constant. The TSLk 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 TSLk grammar and prove several properties about these grammars that aid in their learning.

Original languageEnglish (US)
Title of host publicationLanguage and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings
EditorsFrank Drewes, Carlos Martín-Vide, Bianca Truthe
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319537320
StatePublished - 2017
Event11th International Conference on Language and Automata Theory and Applications, LATA 2017 - Umea, Sweden
Duration: Mar 6 2017Mar 9 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th International Conference on Language and Automata Theory and Applications, LATA 2017
City Umea

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


  • Algorithmic learning
  • Grammatical inference


Dive into the research topics of 'Efficient learning of tier-based strictly k-local languages'. Together they form a unique fingerprint.

Cite this