文档介绍:JOURNAL OF COMBINATORIAL THEORY 8, 115-133 (1970)
Heterogeneous Algebras*
GARRETT BIRKHOFF AND JOHN D. LIPSON t
Department of Mathematics, Havard University,
Cambridge, Massachusetts 02138
Received December 3, 1968
ABSTRACT
Many of the basic theorems about general "algebras" derived in [1, Ch. 6]
are extended to a class of heterogeneous algebras which includes automata, state
machines, and monoids acting on sets. It is shown that some algebras can be
fruitfully studied, using different interpretations, both as (homogeneous) algebras
and as heterogeneous algebras, and a non-trivial "free machine" is constructed
as an application. The extent of the overlap with previous work of Higgins [9]
is specified.
1. INTRODUCTION
We generalize in this paper the usual [1, p. 132] notion of an "algebra",
so as to include as special cases the notions of a monoid acting on a set,
"automaton" (sequential machine) and "state machine" (semi-automaton).
We show that most of the general theory of algebraic systems of [1, Ch. 6]
applies with undiminished force. Our basic definition is the following;
it is essentially equivalent to that of an "algebra with a scheme of opera-
tors" (or "Z-algebras") of Higgins [9]; see also [14].
DEFINITION. An algebra is a system A ---- [5a, F] in which:
1. 5 P =- {S~} is a family of non-void sets S~ of different types of elements,
each called a phylum of the algebra A. The phyla S~ are indexed by some
set I; ., Si ~ 5# for i ~ I (or are called by appropriate names).
2. F ---- {f~) is a set of finitary operations, where eachf~ is a mapping
f~ : Si(1.~) • S~(~.~) • ". • S~(n<~),~) --~ S~(~) (1)
* Presented at the Yale University Conference on