Automata: Some resources

[turion]

I really liked reading through your blog post about automata. There is some related reading that you might enjoy (or already be aware of):

• Your Context class looks a lot like "predicate transformers", see https://webspace.science.uu.nl/~swier004/publications/2019-icfp-submission-a.pdf
  • I also think that your Context class related to modalities of containers/strictly positive types/polynomial functors (e.g. https://www.cs.nott.ac.uk/~psztxa/publ/cont-tcs.pdf). For example, there is a function box :: Finite r => Reader r Bool -> Bool that takes the and over all possible values of the environment r.
• Without the accepting functions, automata in a monad have been studied. They've been called "transducers" and some other name. There is e.g. a category-theoretic work by Bart Jacobs, "A Bialgebraic Review of Deterministic Automata".
• Automata in a monad have been implemented in Haskell a few times, e.g. hackage.haskell.org/package/dunai (using a final encoding) or in my hackage.haskell.org/package/essence-of-live-coding (initial encoding) looking a lot like your definition. Applying this to nondeterminism (I used monad-bayes) really gives rise to some great applications, e.g. https://hackage.haskell.org/package/rhine-bayes

[iagoleal]

Hi Manuel! I'm glad you liked the post and thanks for the suggestions.

I wasn't aware of most of these points, so I will reply to them separately.

• While writing I had an itch that the Context class should have some well-known name but couldn't find anything. The best I got was Foldable but it starts to get off for the probabilistic monads. Well, Foldable models some logic of a container, so it may be a better way to think of it.
• Hmm I knew the name transducers for automata with outputs. The categorical point of view is nice to know, nevertheless.
• These are some nice and useful libraries! I have been thinking about how to use that Haskell definition of probabilistic automata to do reinforcement learning. After all, they are essentially the same as Markov decision processes! Did you apply rhine-bayes to any reinforcement problem?