2012/12/11 by Eric Werner, Werner, Eric
Computer Science · #Computability, Logic, AI Algorithms #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #cs.CL #cs.LG #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1212.2390
7 pages. Key Words: Language learning, rules of language, complexity, learning algorithms, evolution of language
arxiv created 2012/12/11 · openalex publication_date 2012/12/11 · arxiv updated 2012/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.08889x1028 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 n2 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.