# How math deals with state or “algebra of sequential logic”

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.

• My recommended search terms are Moore Mealy FSM. – Axel Kemper Aug 8 '17 at 9:06
• algebraic automaton theory – Alvin Lepik Aug 8 '17 at 9:07
• @AxelKemper not the state machines, but the state itself. – artemonster Aug 8 '17 at 9:33

## 2 Answers

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

• And what about temporal logic? Is it related somehow? – artemonster Aug 8 '17 at 9:34
• Also, found this: Asynchronous Operators of Sequential Logic: Venjunction & Sequention. Do you know anything about this, by chance? – artemonster Aug 8 '17 at 18:15
• @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). – trying Aug 8 '17 at 18:55
• 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" :) – artemonster Aug 8 '17 at 19:38
• 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? – Dragonsheep Oct 21 '17 at 19:43

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.

• 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. – artemonster Aug 16 '17 at 7:48
• 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? – artemonster Aug 16 '17 at 8:06