It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the "core" of the gate, and the output) and adjacency matrix

$\begin{pmatrix}0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$.

Gluing these together gives a bijective correspondence between a certain class of digraphs and circuits built from wires and NAND gates. With this in mind,

is there a standard terminology for this correspondence/construction? Are there common references where it is discussed?

I am particularly interested in the extent to which topological features of the digraph (e.g., the non-trivial homotopy induced by flip-flops) can be or have been related to the computational features of the corresponding circuit.

NB. This was cross posted from MSE after two days.

  • $\begingroup$ You should probably wait more than two days. $\endgroup$ – Tyson Williams Sep 13 '12 at 12:45
  • 1
    $\begingroup$ I'm unclear as to how the digraph is representing the NAND gate. It doesn't seem to be a digraph representing the NAND function, e.g. as $(x,y) \mapsto (0,\;\mathrm{NAND}(x,y))$. Could you elaborate? $\endgroup$ – Niel de Beaudrap Sep 13 '12 at 16:50
  • $\begingroup$ @Niel- Assume that wires are undirected edges. After gluing wires and graphs of the form in the question (and removing trivial wires, consecutive directed edges, etc.), we obtain a graph with some inputs (vertices with only one outbound edge and no undirected ones) and outputs (vertices with only one inbound edge and no undirected ones). Every vertex with two inbound directed edges and one outbound directed edge corresponds to a NAND in the following way: order the N input vertices and take a bitstring of length N: the kth bit goes to the kth input vector and is "propagated" along the... $\endgroup$ – S Huntsman Sep 13 '12 at 17:19
  • 1
    $\begingroup$ @Niel de Beaudrap: I cannot follow the asker’s argument in the comments, but I think that it is just the underlying DAG of the circuit made of two input gates, one NAND gate, and one output gate. $\endgroup$ – Tsuyoshi Ito Sep 13 '12 at 22:47
  • 1
    $\begingroup$ @kristoffer, thx yeah exactly. note there are some deep thms on decomposition of FSMs. so one could convert the time/history-dependent "cyclic circuit" (which seems to be studied more in EE than CS?) to a FSM and apply eg the krohn-rhodes decomposition to reveal "deep structure". SH you mentioned you are interested in flip-flop structure which the K-R thm reveals a fundamental structure/decomposition. K-R called it decomposition into "primes" but as the wikipedia article notes, there is some nuance there. $\endgroup$ – vzn Sep 14 '12 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.