Classification of noncounting events

摘要

An event E is a subset of the free monoid A* generated by the finite alphabet A. E is noncounting if and only if there exists an integer k≥0, called the order of E, such that for any x, y, z ∈ A*, xykz ∈ E if and only if xyk+1z ∈ E. From semigroup theory it follows that the number of noncounting events of order ≤1 is finite. Each such event is regular and the finite automata accepting such events over a fixed alphabet are homomorphic images of a universal automaton. Star-free regular expressions for such events are easily obtainable. It is next shown that the number of distinct noncounting events of order ≥2 over any alphabet with two or more letters is infinite. Furthermore, there exist noncounting events which are of any “arbitrary degree of complexity,” e.g. not recursively enumerable.