Classifying regular events in symbolic logic

摘要

Regular events have been classified by star-height, star-free events by the “dot-depth hierarchy,” and events of dot-depth one by the so-called β-hierarchy. It is shown here that the latter two hierarchies have appealing characterizations in symbolic logic: Referring to a first-order language L in which star-free events are described, an event is shown to be of dot-depth n iff it is defined by a Boolean combination of L-sentences in prenex normal form with a Σn-prefix. The β-hierarchy is characterized by the quantifier-rank of L-sentences with Σ1-prefix. A similar characterization of star-height would require the inclusion of weak monadic second-order quantifiers; it is shown that the natural classification of events depending on these quantifiers will not yield on infinite hierarchy.