An application of Cohen's result on star height to the theory of control structures

摘要

A result/concept on star height is applied to two problems in the theory of control structures. First, Kosaraju's systems REn of control structures are generalized and it is shown by using Cohen's result on star height that the generalized systems constitute a pathwise hierarchy with respect to their expressive powers. Second, by using a concept on star height, a result of Peterson et al. (Comm. ACM 16 (1973), 503–512) that RE∞ is pathwise complete is sharpened.