0
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ You should probably wait more than two days. $\endgroup$
    – Tyson Williams
    Sep 13, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 15:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.