4
$\begingroup$

Boolean algebra is well-studied and you could easily find a lot of introductory materials on different operators, properties, how eveything is nicely related to the algebra of sets, and so on.
Coming from the EE background, I also know that you can construct any circuit using NAND/NOR gates, because of their nice functional completeness properties. The same goes for stateful circuits, as you could build a simple stateful RS-Latch with 2 NAND/NOR gates, by applying them to each other.
This is where it gets interesting - does that mean that the state arises from the recursion? i.e. 

 q = nand(r, nand(s, q))

Unfortunately, I couldn't find anything like "algebra of sequential logic" or any notion on how mathematics seems to deal with state (or, better say: time?!). Most likely, my search keywords are compeltely off.
Could you help me out? I would like to know how mathematicians deal with sequential circuits - any introductory book would be great.

$\endgroup$
6
  • $\begingroup$ My recommended search terms are Moore Mealy FSM. $\endgroup$
    – Axel Kemper
    Aug 8, 2017 at 9:06
  • $\begingroup$ algebraic automaton theory $\endgroup$
    – AlvinL
    Aug 8, 2017 at 9:07
  • 1
    $\begingroup$ @AxelKemper not the state machines, but the state itself. $\endgroup$
    – artemonster
    Aug 8, 2017 at 9:33
  • $\begingroup$ The computers in the world run on the sequential switching theory. Montgomery intuited it, Caldwell and his PhD student Huffman developed. That put Americans on the Moon, because Apollo navigation computer used that very logic in its ICs. $\endgroup$
    – Brian Cannard
    Sep 26, 2020 at 5:58
  • $\begingroup$ And you're asking right questions. I want to work with you. Please, find me, and get connected. $\endgroup$
    – Brian Cannard
    Sep 26, 2020 at 6:02

2 Answers 2

Reset to default
3
$\begingroup$

The math involved is that of Semigroups and its application to "sequential circuits" is named "algebraic theory of machines".

Read just to start:

Krohn, Rhodes, Arbib - Algebraic Theory of Machines, Languages and Semigroups

$\endgroup$
6
  • $\begingroup$ And what about temporal logic? Is it related somehow? $\endgroup$
    – artemonster
    Aug 8, 2017 at 9:34
  • $\begingroup$ Also, found this: Asynchronous Operators of Sequential Logic: Venjunction & Sequention. Do you know anything about this, by chance? $\endgroup$
    – artemonster
    Aug 8, 2017 at 18:15
  • $\begingroup$ @artemonster It depends on what you need. This last book is not a mathematical book. If you want to learn the mathematics behind Mealy machines, Semigroups is the way to go and the book I suggested has been written by people with engineer-oriented minds that possibly inadvertently working on sequential circuits have discovered important results in the theory of the Semigroups. Following this approach you have the chance to start studing mathematical arguments that are difficult when approached abstractly (as most mathematicians inevitably do, not knowing sequential circuits). $\endgroup$
    – trying
    Aug 8, 2017 at 18:55
  • $\begingroup$ Thank you, again. It's just that I was very dissatisfied with the basic definition of state machines (a tuple of a transition function, state set and output function) and wanted to know where the "state" comes from and if there is another meaning to the state, beyond just being a "symbol" :) $\endgroup$
    – artemonster
    Aug 8, 2017 at 19:38
  • $\begingroup$ I've started the Krohn text and it seems to be exactly what I'm looking for. Are there any more modern texts with similar coverage you might recommend? $\endgroup$
    – Dragonsheep
    Oct 21, 2017 at 19:43
1
$\begingroup$

I don't know the answer, but I'd like to register a little bit of doubt regarding the position that semigroups/automata provide the most direct account of such phenomena. I'm not saying they aren't related, but I don't think knowing the basic definitions of that branch of knowledge directly answers your question. Anyway, I recommend reading up about traced monoidal categories, which are places where this kind of feedback is allowable. Specifically, you should probably read up on traced cartesian monoidal categories. You may also be interested in this old question of mine at MathOverflow.

$\endgroup$
2
  • 1
    $\begingroup$ I've found a lot of papers lately that state that the "mainstream" semigroup theory "is not enough" to describe stateful functions well. Maybe "Primitive Recursion and state machines" would be of interest to you. Thank you for links. $\endgroup$
    – artemonster
    Aug 16, 2017 at 7:48
  • $\begingroup$ Also, this quite blew my mind : "the existence of a trace operator is equivalent to the existence of a “parameterized” fixed point operator satisfying certain properties". Soooo, basically, state arises from a fixed point, i.e. q = not not q? $\endgroup$
    – artemonster
    Aug 16, 2017 at 8:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .