Polynomial Functors Constrained by Regular Expressions

I’ve now finished revising the paper that Dan Piponi and I had accepted to MPC 2015; you can find a PDF here:

Polynomial Functors Constrained by Regular Expressions

Here’s the 2-minute version: certain operations or restrictions on functors can be described by regular expressions, where the elements of the alphabet correspond to type arguments. The idea is to restrict to only those structures for which an inorder traversal yields a sequence of types matching the regular expression. For example, (aa)^* gives you even-size things; a^*ha^* gives you the derivative (the structure has a bunch of values of type a, a single hole of type h, and then more values of type a), and b^*ha^* the dissection.

dissected-tree

The punchline is that we show how to use the machinery of semirings, finite automata, and some basic matrix algebra to automatically derive an algebraic description of any functor constrained by any regular expression. This gives a nice unified way to view differentiation and dissection; we also draw some connections to the theory of divided differences.

I’m still open to discussion, suggestions, typo fixes, etc., though at this point they won’t make it into the proceedings. There’s certainly a lot more that could be said or ways this could be extended further.

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in math, writing and tagged , , , , , , . Bookmark the permalink.

6 Responses to Polynomial Functors Constrained by Regular Expressions

  1. mimblewabe says:

    Beautiful!

    Don’t have many suggestions yet since I only skimmed it quickly. The one I have: on the dissection of 1 + XL you should add the proof that L a \times L b indeed satisfies the same equation as the disection. It’s not at all clear at first and I’d argue that it’s certainly more non-trivial than the other steps of the derivation (which are after all just mechanical applications of the dissection rules).

  2. First glance I had flashbacks to the transfer matrix method that Stanley talks about in volume I of his enumerative combinatorics books to crank generating functions (species).

    • Brent says:

      Thanks for this reference! The movers finally delivered our belongings (3.5 weeks late) including my copy of Stanley, so I was finally able to look this up. And you’re absolutely right, there is a strong connection there.

  3. Pingback: The blog lives! and Secrets of Creation Trilogy | The Math Less Traveled

  4. Pingback: Rethinking Inheritance with Algebraic Ornaments | Categorical Imperative

  5. Pingback: The divided difference track | blog :: Brent -> [String]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s