Syntactic Learning over Tree Tiers

The class of tier-based strictly 2-local (TSL2) languages has been shown to be useful in modeling patterns across different linguistic domains. This paper discusses the learnability of the intersection closure of the TSL2 languages, multi-TSL2 (MTSL2). I present two learning algorithms, one that learns a relevant subclass of MTSL in polynomial time, and one that learns MTSL proper but requires potentially exponential time. Both algorithms generalize across tree-based and string-based data representations. I show that each algorithm correctly learns its target class from a limited sample of positive data, and discuss the tradeoffs between the two. The success of these algorithms delivers a key learning result for subregular linguistics, and demonstrates the utility of subregular language classes in developing a unified learning theory that spans different linguistic domains.