MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(I'm not entirely sure what to tag this; feel free to retag.)

While thinking about automata (specifics below), I ran into the following phenomenon:

A cofunction system is a pair of sets $X, A$, together with a pair of maps $ar\colon X\rightarrow\mathbb{N}$ (arity) and $in\colon\subseteq X\times A^{<\mathbb{N}}\rightarrow X$ (input; a partial map), where the domain of $in$ is precisely the set of tuples with the "right" number of inputs from $A$: $$dom(in)=\{(x, a_1, . . . , a_n): n=ar(x)\}.$$

This is just a dual setup to an abstract picture of a set of finite-arity functions on a set; in that case, we would of course have $coim(in)=A$ instead of $X$.

Anyways, I would like to know:

what are "cofunction systems" actually called?

The specific thing I was looking at which led me to this question was the following: say that a labelled automaton on $\{0, 1\}$ is a finite-state automaton with alphabet $\{0, 1\}$, together with a map from the set of states to $\{0, 1\}$. So, for example, $$A=(\{a, b\}, \{(a, 0: a), (b, 0: b), (a, 1: b), (b, 1: a)\}, \{(a: 1), (b: 0)\})$$ is a labelled automaton, which switches states only on input 1, and with state $a$ labelled 1 and state $b$ labelled 0. Say that a finite dynamical system is a digraph - possibly with loops - in which each node has out-degree 1. (Thinking of each node and arrow of a finite dynamical system being labelled with "0," labelled automata are generalizations of finite dynamical systems to larger alphabets.)

Now, I can combine two labelled automata and get a finite dynamical system on the Cartesian product of their state sets - by feeding their labels to each other as inputs. So, for example, feeding $A$ to itself in this manner gives the following four-state finite dynamical system (which I can't seem to actually draw here): $(a, b)$ goes to $(a, a)$, $(b, a)$ goes to $(a, a)$, and $(a, a)$ goes to $(b, b)$, which loops to itself.

Of course, that's not the only way to combine automata. I could feed a single automaton to itself, or combine three automata in a circle with each feeding off the one counterclockwise before it, or in general in any way where each input automaton was being fed the state label of exactly one (not necessarily other) input automaton.

So, for each finite dynamical system $F$, there is a map $LA^{\vert F\vert}\rightarrow FDS$ from labelled automata to finite dynamical systems; the example above of combining two labelled automata corresponds to the dynamical system consisting of a single 2-cycle. Playing around with this situation led me to this question.

I suppose a second, softer question is:

Has this particular setup with labelled automata and dynamical systems been studied before; conversely is it known to be silly?

I have figured out a couple small things about this, but nothing particularly interesting; on the other hand, it is fun to play around with.

share|cite|improve this question
You might want to look at – Benjamin Steinberg Sep 29 '13 at 2:19
That's certainly an interesting article, but I don't see that it is directly related to what I'm asking (although it may be, and I might not be seeing the connection). Could you elaborate? – Noah Schweber Sep 29 '13 at 21:19
It's about dynamical systems from composing automata. It seemed like what you are getting at. – Benjamin Steinberg Sep 29 '13 at 21:35
@Noah, I think your presentation of the question is not the best possible. I spent almost a dozen of minutes trying to understand what your very sad crying face $\colon \subseteq$ actually means. Finally I figured it out, but got tired and switched my attention to something happier. – Michal R. Przybylek Oct 11 '13 at 22:17
It's sad because it's not defined everywhere! :P That's the notation I learned for partial functions - is there one which is preferable? (I like this one, because it uses only pre-existing symbols, but I'm open to suggestions.) – Noah Schweber Oct 12 '13 at 19:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.