Yes, that matches my memory from Hillis's book based on his thesis (iirc it came out a few years before that paper).

I imagine you could also do this for NFAs -- composing them is just a little extra work.