You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Ryan Schwiebert (Nov 15 2025 at 03:18):Sorry to cram that all in the title. I am very interested in getting into what I can learn about these topics through the lens of monoidal categories and/or toposes. We have many finite state machines at work, but my colleagues are not familiar with Behavior Trees per se. Both FSMs and BT's seem amenable to applied category theory, maybe even BT's moreso.
I am slowly reading the relevant parts of Seven Sketches on toposes, and the relation of logic, behavior and syntax seems very relevant. It's just all so much to take in. I was hoping someone here might have tidbits to share to speed me along my learning path here.
Jonty Male (Nov 15 2025 at 09:15):https://autcat.github.io/ was a good branching point during my undergraduate thesis - but obviously more on the FSM side
John Baez (Nov 15 2025 at 10:43):A more specific question could elicit lots of replies here. Just asking for "tidbits" probably won't get folks excited, but there are people here who know lots about some of these topics.
Ryan Schwiebert (Nov 15 2025 at 14:04):It's really a case of not knowing enough to have a specific question. This is about as specific as I can get:
Ryan Schwiebert (Nov 15 2025 at 14:07):Really the first exposure i had to FSM (are they different from finite state automata?) was in algebraic coding theory, because you can use a FSM to encode a stream of bits, and it turns out that has a polynomial representation, and algebraic properties, IIRC. Now the FSMs I work with are in software, and I wonder how I can understand and improve them.
John Baez (Nov 15 2025 at 20:42):"the first exposure i had to FSM (are they different from finite state automata?)"
That's the kind of question mathematicians love most: a precise question that has a yes-or-no answer! There's no waffling around with these questions. And if you pose them correctly, you get precious bits of information.
I looked up finite state machine and in the first line it said
A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition.[1] An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition.
So apparently the answer to your question is yes.
Eilenberg, one of the founding fathers of category theory, wrote two books on category theory and finite state machines. Apparently all his friends in algebraic topology thought he was wasting his time. You can get them on LibGen. They're fairly interesting. I think there are some newer papers that discuss some results in these books, but I can't remember what they are.
What's a 'behavior tree'?
Ryan Schwiebert (Nov 16 2025 at 03:34):@John Baez So, Automata, Language and Machines volumes A and B? It's a very trippy journey even through the table of contents!
Ryan Schwiebert (Nov 16 2025 at 03:46):John Baez said:
What's a 'behavior tree'?
When I first heard about them I couldn't tell what would make them different from FSMs, except for maybe the layout. The idea is to lay out a pattern of behavior that's executed according to certain primitives. The nodes have access to a pool of state, and the tree keeps being executed from root to some leaf where an action happens, potentially many times a second.
Learning about the primitives helps with seeing how one might work. The execution of a node results in either "success, running, or failure" A running node will eventually become "success/failure." There are nodes that act like conditionals, and nodes that execute a sequence of children, waiting for one to succeed, or maybe waiting for one to fail ,nodes that enable looping, and so on. And it sure sounds like you could potentially dynamically graft subtrees into the tree depending on conditionals.
I'm not good at explaining it because so far I've only read a couple websites and chatted with AI a bit to learn what to search for, but it does seem different in character from a finite state machine.
I hear they use them for NPC player behavior in the gaming industry...
Ryan Schwiebert (Nov 16 2025 at 14:23):@John Baez This looks like a current and relevant extension to what Eilenberg was working on: Mathematical Foundations of Automata Theory
John Baez (Nov 16 2025 at 22:17):Ryan Schwiebert said:
John Baez So, Automata, Language and Machines volumes A and B?
Yes, those are the ones.
John Baez This looks like a current and relevant extension to what Eilenberg was working on: Mathematical Foundations of Automata Theory
This looks like a nice modern treatment!
(It should be "Automaton Theory", but that's a very minor complaint. Saying "Automata Theory" is like saying "Categories Theory".)
Ryan Schwiebert (Nov 17 2025 at 02:44):@John Baez Oo, i just ran across this survey Behavior Trees in Robotics and AI. Section 2 appears to be a very helpful and careful comparison of BTs to FSMs, decision trees, and a few other notions I did not know about.
John Baez (Nov 17 2025 at 09:12):Do you think behavior trees are widely used in robotics? @Joe Moeller - maybe Aaron Ames will know.
There are a million notions in computer science, and in some sense only the most elegant and the most widely used are worth learning for a nonexpert such as me.
Joe Moeller (Nov 17 2025 at 16:05):I guess what I can say at the moment is:
Ryan Schwiebert (Nov 17 2025 at 21:08):Based on the pages I've found, and conversations with roboticists at work, they all know about BTs, but it is not yet something they've done. Perhaps it's just catching on. Maybe the AI people are ahead of the roboticists at the moment.
Ryan Schwiebert (Nov 17 2025 at 21:15):Two of the types of "composite" nodes are called "sequence" and "selector". The first one works like a universal quantifier (succeeding iff its children do) and the second like an existential quantifier (succeeding iff any of its children do.) This tutorial I read today has a separate name for "decorator nodes" that only have one children, and they describe "invert", "always succeed" and "always fail" as cases of those nodes. The final type of node is "leaf" which can do anything basically. It might trigger the agent to do an action, or else do some sort of check against state, and then report success or failure up the chain.
At this point it looks kind of like the non-leaf nodes are largely control structures, and the leaves are where you can access and change state. (Possibly it's interesting that's where the side-effects are.)
Maybe it's just because I"m reading these at the same time, but it sounds like these trees have their own internal logic, possibly like a topos? I'll have to keep my eye out to see if other such features appear.
Alex Kreitzberg (Nov 18 2025 at 22:25):Here's some context that might be helpful.
Behavior Trees were popularized by the following GDC talk on the AI in the video game Halo 2: https://www.youtube.com/watch?v=m9W-hpxuApk
Here's a transcription of the talk: https://www.gamedeveloper.com/programming/gdc-2005-proceeding-handling-complexity-in-the-i-halo-2-i-ai
Behavior trees were seen as a way to increase modularity over Finite state machines.
In the talk there were suggestive tree diagrams:
My understanding is this talk was reverse engineered into other tools in game development, like the behavior tree editor in the unreal engine:
Unreal example of behavior tree
The tree is somewhat deceptive, because implicit in the diagram is some means of sampling the world and player state to update the tree.
After this popularization, I think the definitions you see on wikipedia were a consolidated. Whatever the history, these definitions were then carried over into fields like robotics.
The name "behavior tree" is still a game developer term of art, it doesn't necessarily match the wikipedia definition. For example, in the original Halo 2 talk, "impluses" were "added" (really they were removed from the definition) to make small changes on the tree when unusual play states happened.
With that context, I agree monoidal categories may be usefully applied here, BTs feel like a sort of multi-category to me. My sense is much of applied category theory amounts to making diagrams like the above rigorous. You've already identified a notion of "And" and "Or" in behavior trees, if you want it to be a topos you'd also need a sort of "object classifier" or "boolean" concept.
Finite state machines, by contrast, have widely recognized careful definitions, or close analogs in category theory with careful definitions. And they are applied much more broadly than just game AI. The intro text on category theory "Conceptual Mathematics" spends quite a bit of space on discrete dynamical systems, graphs, etc.
Basic concepts in category theory remind me of finite state machines. For example, if you imagine a category with a single object , and say three distinct generating arrows from the object to itself, . That gives you a simple syntax, with an example of a morphism in that category. Then finding a functor from this category into , would give the previous "program" an interpretation as a composition of endofunctions.
These functions can be thought of as the arrows which transition the states of the associated set. Of course the entire state space is the object of this category, whereas finite state machine diagrams have arrows between states. You can define such a category with the states as objects by forming the category of elements of the specified functor interpreting into Set.
Individual automata aren't toposes by themselves, but all the possible interpretations collectively form a topos, by inheriting the topos structure from , just like how functions into a vector space, themselves form a vector space.
I find these bundles of connections interesting to think about. I don't know much about how category theory might apply to AI specifically, but if you're interested I bet there's somebody here with some thoughts on how that works.
Ryan Schwiebert (Nov 18 2025 at 22:30):@Alex Kreitzberg The other thing that struck me as topos like (based on my limited understanding so far, from Seven Sketches) is that the tree evolves over time. Nodes convert to Success/Failure while going through Running. The description in seven sketches is "things happening over time over a site."
Do these boolean-like evaluations of nodes convert into something globally boolean-like for a potential subobject classifier? (Sorry my knowledge of toposes is still so sketchy. i cannot even bring the details of subobject classifiers to mind, and I recall not quite getting the glueing concepts for sheafs.)
Alex Kreitzberg (Nov 18 2025 at 23:20):Essentially by definition, Toposes are certain well behaved categories of presheaves (The presheaves and category are so well behaved they're called "sheaves" and a "site" respectively). What you're noticing is can look "temporal".
So has a boolean set. Functions into that boolean set are the predicates. When you bake in an implicit time dependence by introducing a domain category, what happens to predicates? That would be how object classifiers are introduced via Sheafs. That's my understanding of how sheafs build toposes (but I confess, I'm an enthusiast so I don't have clever ideas here for your example).
In my explanations, I've been leaning on the more general definition of elementary topos as a crutch. It simply requires our category:
has finite limits, ("And")
is cartesian closed, and ("Implies")
has a subobject classifier. ("Notion of truth")
So you've already mentioned "sequencing" as a notion of "and" - for fun lets see if that satisfies point 1 (maybe this isn't what you were trying to do). Requirement 2, that it be cartesian closed, would mean our diagramatic language would need some notion of anonymous function defined nicey in terms of sequencing, since we're calling it "and". This would be analogous to currying in a functional language.
You need these "higher order functions" to define predicates into the "classifying space" the analog of booleans.
I don't have good ideas for how to do this, because I haven't thought about behavior trees for very long. I should say, I have a friend who worked on Halo who is familiar with the "in the trenches" definition, so you've inspired me to talk with them a bit about the definition. So maybe I'll have something more clever to add later.
Kevin Carlson (Nov 19 2025 at 11:43):Just a drive-by comment that you have the implication backwards: all categories of presheaves are toposes, but most toposes are not full categories of presheaves. Most toposes are certain particularly nice reflective subcategories of presheaf categories, namely those for which the reflector (called "sheafification" in this context) preserves finite limits.
John Baez (Nov 19 2025 at 14:41):I don't think what Alex said was actually wrong if he was talking about Grothendieck topoi here:
Essentially by definition, Toposes are certain well behaved categories of presheaves (The presheaves and category are so well behaved they're called "sheaves" and a "site" respectively).
I think some people say "topos" and mean "Grothendieck topos", so maybe Alex is working within this tradition. But if I were trying to explain toposes to someone (Ryan) I would have said something like "The nicest toposes, called Grothendieck toposes, are categories of specially nice presheaves called sheaves".
Kevin Carlson (Nov 19 2025 at 16:30):Yes, I was responding as if Alex meant to say "certain well-behaved categories of the form ", which isn't quite right, whereas "certain well-behaved categories whose objects are objects of categories of the form " does work, maybe that's what he meant.
fosco (Nov 19 2025 at 16:36):Alex Kreitzberg said:
- has finite limits, ("And")
Finite limits give you the ability to say "and", plus the ability to say "the biggest subobject where f=g"; the latter is impossible with conjunctions only, no?
Alex Kreitzberg (Nov 19 2025 at 17:04):I'm happy people are calling me out XD
I tried to reverse engineer how the terminology is used on the nlab, but I wouldn't be surprised if my usage, or understanding, are confused.
The sense I got from the nlab is you might have any of
And all of these would be called "A Topos" and it was up to the reader to establish from context whether it was a grothendieck topos or an elementary topos. (I found this odd, because it felt like calling a square a rectangle and expecting the reader to know we'll use square properties)
Even with that, badly self imposed, rule I appreciate folks pointing out there are still mistakes.
Additionally, the definition used in seven sketches (page 242) defined a topos to be a category of sheaves. So I was trying to walk backwards from that definition.
The point is (which was subtly emphasized by fosco's comment), when talking about toposes - the subobject classifier, a generalization of "boolean" used for finding subsets, is the star of the show:
After sleeping on the problem, it occured to me they actually did define an operation that looks very much like finding sub trees for Halo 2:
bitmasking trees in behavior trees
For example, If you're in a vehicle you only have access to some of your "behaviors". Given this "subsetting" via "bit masks", maybe something like intersections and unions becomes meaningful.
Kevin Carlson (Nov 19 2025 at 17:23):A category of presheaves is a category of sheaves (ie Grothendieck topos), which is an elementary topos, which is category with a subobject classifier. But all these implications are irreversible. Most category theorists saying "topos" mean "elementary topos", but for historical reasons and the fact that Grothendieck toposes are pretty great, it's far from unheard of to use "topos" to mean "Grothendieck topos."
Ryan Schwiebert (Nov 19 2025 at 20:46):One thing that hasn't been clear to me so far in the discussion of behavior tree is the scope of "blackboard" which is shared. It seems like if all nodes have access to global state, it might cause problems with composition. If, say, two subtrees had actions competing over the same piece of shared state, it sounds like it could lead to deadlock or some runaway cycle.
Maybe some scoping better than "everything global" would help. Maybe, for example, a node knows all its children's scopes. Or, potentially, all sibling nodes share a scope, slightly smaller than the parent node.
Another question I have somewhat related to this is about whether or not it's expected you can dynamically modify the tree. If you can add siblings to a sequence node, for example, that seems to get us back into the same state-sharing danger I was worried about.
Perhaps programmers have thought it through already. One person I talked to suggested that dynamically adding to trees is "not the way to go." It would certainly simplify things if the tree were locked in before execution. We would still have the option to make some subtrees function conditionally, which is kind of a proxy for dynamically inserting nodes.
Ryan Schwiebert (Nov 19 2025 at 20:47):Anyhow, thanks for all your insights into toposes. I never imagined I'd be at the stage where learning such things seemed within reach...
Alex Kreitzberg (Nov 19 2025 at 21:30):When being scared of mutability, be careful to avoid throwing the baby out with the bath water.
If I have a variable that allows "mutating" a 2 into a 3, that doesn't mean "2 + 1" is bad.
Similarly, whether or not you decide it's a good idea to allow mutability for a tree, I very much think it's a good idea to understand what "adding a sibling to a sequence" means.
These behavior trees might be the objects of some category. In which case figuring out the arrows between them, perhaps adding one tree to another tree, is key to understanding them.