Preliminaries to Circuits, II 1
Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, Pauline N. Kawamoto · 1996
This article is the second in a series of four articles (started with [19] and continued in [18], [20]) about modelling circuits by many sorted algebras. First, we introduce some additional terminology for many sorted signatures. The vertices of such signatures are divided into input vertices and inner vertices. A many sorted signature is called circuit like if each sort is a result sort of at most one operation. Next, we introduce some notions for many sorted algebras and many sorted free algebras. Free envelope of an algebra is a free algebra generated by the sorts of the algebra. Evaluation of an algebra is defined as a homomorphism from the free envelope of the algebra into the algebra. We define depth of elements of free many sorted algebras. A many sorted signature is said to be monotonic if every finitely generated algebra over it is locally finite (finite in each sort). Monotonic signatures are used (see [18],[20]) in modelling backbones of circuits without directed cycles.