Learning Tier-based Strictly 2-Local Languages Article Swipe

PDF

Related Concepts

Computer science Constant (computer programming) Phonotactics Inference Bounded function Class (philosophy) Artificial intelligence Sample (material) Time complexity Theoretical computer science Programming language Natural language processing Algorithm Linguistics Mathematics Phonology Chemistry Mathematical analysis Chromatography Philosophy

Adam Jardine , Jeffrey Heinz ·

YOU? · · 2016 · Open Access · · DOI: https://doi.org/10.1162/tacl_a_00085 · OA: W2397818378

The Tier-based Strictly 2-Local (TSL 2 ) 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 TSL 2 languages. We prove the 2TSLIA is guaranteed to converge in polynomial time on a data sample whose size is bounded by a constant.