UncombedCoconut
commented
1 year ago I'm fine with preferring {0,1} for just the set/alphabet. Most of these changes look good! I'm inclined to just merge, though it may be better to see what cosmo thinks first. (Also I'll punt on any question about a "\mathcal{A}" -- I believe such phrasing would have been added by cosmo in pursuit of clarity.)
\todo{Shawn's Comment: Does this just mean for any $B_0 \preceq R_0$ and $B_1 \preceq R_1$?} -- Yes.
\todo{Shawn: What is $Q_{cf}$? I guess it's $Q$ in canonical form -- yes -- ... but that's the same set as $Q$, right? This is just a permutation of $[n]$?} -- not necessarily, as this definition works on DFAs in general (which have $Q$ an arbitrary finite set).
\todo{Shawn: What do you mean by not standard? Like there is a more common way to refer to canonical forms, but this one differs?} - I mean that "the canonical form of a DFA" is a definition I created for present purposes; if the reader uses this term in other context, probably no one will know what they're talking about.
todo{Shawn: Shouldn't this be to $m_\ell$? As in there should be something that transitions to the highest defined state (State $\ell$)?} - I'm pretty sure you're right; this may have been fallout from me improving the index conventions after I started writing.
I think writing the one element set $s=\{\begin{bmatrix}0 & e_\bot\end{bmatrix}\}$ actually doesn't make sense -- it was already a vector (representing a set of classical NFA states).
sligocki
tcosmo
Really interesting write-up! I added comments (as \todo{}s) and tried to fix a few things (but y'all should check that my "fixes" are actually correct or if I'm misunderstanding).
One notable change that I made that may be controversial is: I switched all references to tape symbols from \mathbb{2} to {0, 1} (maybe you want to use [2] instead? I'm happy with that). My reasoning here is that \mathbb{2} had been defined as the boolean semiring and previously only used roughly as a True/False to indicate if a given state was present in a row vector or if a transition matrix transitioned from one state to another or not. I think of tape symbols as a different type of thing, they are not booleans, you can't add them, they just happen to have the same number of elements labeled the same way. But, for example, this analysis could be expanded to multi-symbol TMs in which case the \mathbb{2} and [n] would not coincide any more.
Anyway, I leave it to y'all to decide if you want to accept my suggestion here, but I think at least some explanation is necessary. When I first saw \mathbb{2} used for the symbols I really didn't understand what you were talking about at first.