Natural state transformations

摘要

The concept of generalized3 sequential machines in arbitrary categories is developed in the paper. The change in viewpoint from the previous studies comes from the appropriate choice of a monoidal category. Thus a monad, rather than a monoid in the category of sets, becomes the crucial notion of this development. By reexpressing the old notion of a generalized sequential machine, a concise framework is developed that easily yields results on, for example, bottom-up and top-down tree transformations. Transformations, i.e., maps that change the underlying structure, rather than sequential machines, are emphasized and natural state transformations are defined as certain generalized morphisms of monads. On this basis, a duality theory for direct and inverse state transformations is developed, which lays bare the relationship between the two models of finite state (tree) transformations mentioned above.