Reference A method for synthesizing sequential circuits [mealy-circuits]

Abstract

  • September , 1955
  • George H. Mealy

The theoretical basis of sequential circuit synthesis is developed, with particular reference to the work of D. A. Huffman and E. F. Moore. A new method of synthesis is developed which emphasizes formal procedures rather than the more familiar intuitive ones. Familiarity is assumed with the use of switching algebra in the synthesis of combinational circuits. 

 @article
{mealy-circuits, title={A method for synthesizing sequential circuits}, volume={34}, ISSN={0005-8580}, DOI={10.1002/j.1538-7305.1955.tb03788.x}, abstractNote={The theoretical basis of sequential circuit synthesis is developed, with particular reference to the work of D. A. Huffman and E. F. Moore. A new method of synthesis is developed which emphasizes formal procedures rather than the more familiar intuitive ones. Familiarity is assumed with the use of switching algebra in the synthesis of combinational circuits.}, number={5}, journal={The Bell System Technical Journal}, author={Mealy, George H.}, year={1955}, month={Sep}, pages={1045–1079} }

Backlinks

Categories of stochastic dynamical systems › Introduction [efr-5QC5]

Given a set of inputs A and a set of outputs B, there are essentially two make sense of the informal description "finite-state automaton which reads inputs from A and produces outputs in B". These are the notions of Mealy machine and Moore machine. Simply put, if the set of states is S, a mealy machine is a function A \times S \to B \times S, whereas a Moore machine is a pair A \times S \to S, S \to B. In other words, in a Moore machine the output does not depend on the current input, but only on previous inputs (through their effect on the state), but in a Mealy machine, the input can be passed through directly.

Using the language of categorical systems theory, we can make the following definitions:

Definition Moore Machine [efr-0006]

In a dynamical systems theory, a Moore machine with state space S and interface A is a lens TS \leftrightarrows A. The category of Moore machines with interface A is the slice category of the functor T over A---that is, a morphism of Moore machines is a morphism S \to S' so that the obvious triangle commutes.

Definition Mealy Machine [efr-0005]

In a dynamical systems theory, a Mealy machine with state space S and interface A consists of a costate lens TS \otimes A \leftrightarrows I. The category of Mealy machines with interface A is the comma category of the functor T(-) \otimes A over I---that is, a morphism of Mealy machines is S \to S' so that the obvious triangle commutes.

A Moore machine in the sense of Definition [efr-0006] is what Myers calls a (open) dynamical system, and they are the central object of study in Reference [myers-cst]. Arguably, both Moore machines and Mealy machines deserve the name of "open dynamical system"---the difference is how they interact with the external world.

Observe in particular that, if A=I, the categories of Mealy and Moore machines agree, both being equal to the slice of T over the unit I. In other words, the two notions of closed dynamical system coincide.

It is clear that both Mealy and Moore machines, in this sense, are special kinds of parametrized morphism in lenses, namely those parametrized by an object of the form TS. This leads naturally to the idea that there should be a triple category of morphisms of this type, charts, and lenses.

We call the parametrized lenses TS \otimes \bar {A} \leftrightarrows \bar {B} bisystems since they generalize the two types of machine, Moore and Mealy (but we choose to stick with "system" rather than "machine").

Example Machine Learning as a bisystem [efr-000E]

It is an observation which goes back at least to Reference [backprop-as-functor], and was more thoroughly developed in Reference [bruno-etal-categorical-learning-2021], that the process of training a machine learning algorithm by gradient descent can be abstracted in the following way:

  • Wanting to learn a function X \to Y, we choose a parametrized function f: X \times P \to Y, where all these are, in the simplest case, Euclidean spaces \mathbb {R}^k
  • We take the backwards derivative of f, obtaining a lens: (f,Df): {TX \choose X} \otimes {TP \choose P} \leftrightarrows {TY \choose Y}
  • For each datum (x_n,y_n), we compute the loss gradient \nabla L(-,y_n) : Y \to TY, and combining this with x_n \in X and the current parameter p, we get a gradient on the parameter space which we can use to update

Thus a machine learning algorithm is a sort of bisystem. Indeed our bisystems are essentially an abstracted version of the learners of Fong--Spivak--Tuyeras. The functoriality of this assignment is the main point of the above-mentioned papers.

In this chapter, we will put together the ingredients we have assembled so far and construct a triple category of stochastic dynamical systems. We will also give the construction of triple categories of systems in the ordinary case.

Note that the theory of Markov fibrations does not quite generalize the ordinary theory of fibrations---only fibrations with a Cartesian base (Example [efr-CJTH] and Proposition [efr-Z75A]). Since the pullbacks in \mathcal {C}_\mathrm {det} play such a key role in the theory, it is not clear that this can be dispensed with. Although Cartesian bases certainly cover the vast majority of examples from the literature on categorical systems, it is of course worth noting that they are not a requirement. Moreover, we will see that the construction of the double category of lenses and charts encounters certain problems for a general Markov fibration not seen for ordinary fibrations. Hence we will give a separate description of the triple categories in each of the two cases.

The notions of Mealy and Moore machine are both quite old, going back to Reference [mealy-circuits], Reference [moore-gedanken-sequential]. While we do obtain finite-state automata of these types as special cases, our interest is primarily in the analysis of dynamical systems, which tends to ask rather different questions than automata theory. Thus, despite using the terminology, we will not be particularly interested in the actual theory of Mealy and Moore machines. We do mention one recent paper, Reference [semibicategory-of-moore-automata], which has a category-theoretic approach similar in spirit to our own. Their category of Mealy machines can be obtained, not as our category of Mealy machines above, but by considering maps TS \otimes A \to B in the case where A = {* \choose A}, B = {* \choose B} are trivial in the secondary component. In the discrete case, such a map is given by A \times S \to B \times S.

It should also be noted that the idea of embedding Mealy machines as the morphisms TS \otimes A \to I is not original, but was communicated to the author by Matteo Capucci. It seems not to have appeared in the literature so far. The idea that there "should" be a triple category of systems, like the one we will construct, has also circulated as folklore, although again an explicit construction has yet to appear. Very similar ideas appear in the work of Shapiro and Spivak, see for example Reference [shapiro-spivak-dynamic-operads].

We begin this chapter with a treatment of double categories of charts and lenses in the context of Markov fibrations (and stochastic modules). The construction does not work quite as well as in the classical case---the difficulty is essentially that the equivalence relation which defines stochastic charts has a directed nature, and given a 2-cell defined in an obvious way \phi \to \psi , and an equation \psi \xleftarrow {\sim } \psi ', there is not (apparently) in general a way to lift this to an arrow \phi ' \to \psi ' (with \phi ' \simeq \phi ). However, we can construct a double category whose globular horizontal 2-category have connected components given by the stochastic charts (or lenses).

We proceed to give an account of categorical systems theory for these double categories. The chief problem posed by the above is that we may not have any good clock systems (Example [efr-9WQU]). Two equivalent charts should represent the same system, but they may receive different sets of maps from the supposed clock system (and thus have different sets of trajectories). We resolve this by proving that, for lenses with a deterministic base, every equivalence class of lenses has an initial representative. Moreover, mapping out of this initial representative to a representative of some other lens, a 2-cell exists filling a given square if and only if it commutes as a map of lenses and charts in the classical case (recall that over deterministic bases, Markov fibrations become ordinary fibrations). In particular the trajectories of a system with respect to such a clock system depend only on their equivalence class.

We follow this up by constructing the above discussed triple categories of "bimachines", that is systems which combine Mealy and Moore machines. We do this both for stochastic and the ordinary case---the procedure is exactly the same, but of course they are different objects, neither generalizing the other.

We end by constructing a stochastic dynamical systems theory for smooth dynamical systems---requiring a brief detour to construct a suitable Markov category of smooth kernels.