Learning Subregular Classes of Languages with Factored Deterministic Automata
Jeffrey Heinz, J. H. Rogers · 2013
This paper shows how factored finitestate representations of subregular language classes are identifiable in the limit from positive data by learners which are polytime iterative and optimal. These representations are motivated in two ways. First, the size of this representation for a given regular language can be exponentially smaller than the size of the minimal deterministic acceptor recognizing the language. Second, these representations (including the exponentially smaller ones) describe actual formal languages which successfully model natural language phenomenon, notably in the subfield of phonology. 1