On the complexity of learning a language: An improvement of Block's
  algorithm
  Language learning is thought to be a highly complex process. One of the
hurdles in learning a language is to learn the rules of syntax of the language.
Rules of syntax are often ordered in that before one rule can applied one must
apply another. It has been thought that to learn the order of n rules one must
go through all n! permutations. Thus to learn the order of 27 rules would
require 27! steps or 1.08889x10^{28} steps. This number is much greater than
the number of seconds since the beginning of the universe! In an insightful
analysis the linguist Block ([Block 86], pp. 62-63, p.238) showed that with the
assumption of transitivity this vast number of learning steps reduces to a mere
377 steps. We present a mathematical analysis of the complexity of Block's
algorithm. The algorithm has a complexity of order n^2 given n rules. In
addition, we improve Block's results exponentially, by introducing an algorithm
that has complexity of order less than n log n.
