DFA Minimization as a Fixed Point

Attention conservation notice: Unless you fit into a very similar academic niche to me this post likely uses techniques you don’t know to solve problems you don’t care about. Even if you are in that niche this is more of a theoretical curiousity than a useful technique at present, but it was useful for me to think through this to see how some stuff connects up.

I’ve been reading a bit about probabilistic bisimilarity distances recently, and I wanted to explore how it relates to things I’ve previously studied about minimizing deterministic finite automata.

The basic trick they use is to realise the object we want (an equivalence relationship or a pseudometric in this case) and consider it as an element of some complete lattice, define a monotonic function on that lattice such that a fixed point of it will have the desired properties, and then use the Knaster-Tarski fixed point theorem to show that the set of such fixed points is no-empty. The desired object is then either the smallest or largest fixed point (both of which the theorem guarantees to exist, and indeed shows us how to construct).

This turns out to work with deterministic finite automata too!

Suppose we have some deterministic finite automaton \(M\) with states \(S = \{s_1, \ldots, s_n\}\), alphabet \(A\), transition function \(\tau : A \times S \to S\) and acceptance function \(\alpha: S \to \{0, 1\}\). We want to construct the minimal deterministic finite automaton which matches the same language by merging equivalent states. This requires us to define an equivalence relationship \(\sim\) on \(M_S\) such that \(s_i \sim s_j\) if and only if the languages starting from \(s_i\) and \(s_j\) are the same. This is called the Myhill-Nerode relationship.

We can realise this equivalence relationship as follows:

We use the observation that the set of equivalence relationships over any set forms a complete lattice (to get the upper bound of a set of equivalence relationships, just take their unions as sets and then take the transitive closure to get back to an equivalence relationship).

What we are looking for is an equivalence relationship with the following two properties:

  1. If \(s_i \sim s_j\) then \(\alpha(s_i) = \alpha(s_j)\).
  2. If \(s_i \sim s_j\) and \(a \in A\) then \(\tau(s_i, a) \sim \tau(s_j, j)\).

i.e. no accepting state is equivalent to a non-accepting state, and the equivalence relationship works with the transition function so that if two states are equivalent they transition to equivalent states given the same character.

Any such equivalence relationship is called a bisimilarity.

We can find such an equivalence relationship as follows:

Let \(E\) be the set of equivalence relations over \(S\) and define \(F: E \to E\) as \(F(R) = \{(s, t) \in S^2: \alpha(s) = \alpha(t) \wedge \forall a \in A, (\tau(a, s), \tau(a, t)) \in R\}\).

(The fact that if \(R\) is an equivalence relationship then so is \(F(R)\) is not immediately obvious, but follows from some fairly straightforward mechanical checking that I will leave as an exercise for the interested reader)

This definition may seem somewhat non-obvious, so lets unpack it:

  1. We require that the resulting equivalence relationship always respects \(\alpha\). i.e. we throw away anything we would otherwise get where it disagrees on whether the state should be accepting.
  2. We take the new relationship to be the set of pairs that the old relationship cannot distinguish any transitions from. So for example if we had states \(s_i, s_j\) such that every transition from them went to an \(R\)-equivalent state, \(F(R)\) would treat them as equivalent. Equally, if you had two R-equivalent states such that \((\tau(a, s_i), \tau(a, s_j)) \not\in R\) (i.e. R distinguishes some transition from them)

So you can think of \(F\) as taking an equivalence relationship and returning something that is in some sense “a bit closer” to being a bisimilarity. If that intuition is correct, then it should be the case that if \(R\) is a fixed point of \(F\) then it is a bisimilarity.

Suppose \(R = F(R)\). Then by construction of \(F\) we have the first property satisfied (that if \(s \sim t\) then \(\alpha(s) = \alpha(t)\).

For the second, suppose that we have \(s, t, a\) with \((\tau(a, s), \tau(a, t)) \not\in R\). Then by definition of \(F\) we musts have that \((s, t) \not\in F(R) = R\). i.e. if \((s, t) \in R\) then \((\tau(a, s), \tau(a, t)) \in R\).

So in order to find a bisimilarity we just need to find fixed points of \(F\), but this is exactly what the Knaster-Tarski fixed point theorem lets us do. \(F\) is montonic, i.e. if \(R \subseteq R’\) then \(F(R) \subseteq F(R’)\) (another “not totally obvious but a mechanical exercise for the interested reader to check” claim), the set of equivalence relationships form a complete lattice, so the set of fixed points of \(F\) also form a complete lattice.

In particular there is a greatest fixed point of \(F\), called the bisimulation relationship. This is exactly the \(\sim\) relationship we were looking for (because if a word causes two states to reach a different language then they could not have been bisimilar, so that relationship is necessarily maximal).

Additionally, the proof of the Knaster-Tarski fixed point theorem shows us how to construct this relationship: We just start with the largest equivalence relationship on \(S\) and repeatedly apply \(F\) to it until we get a fixed point (in general “repeatedly” might require transfinite induction, but because \(S\) is finite so is the set of equivalence relationships over \(F\) and as a result we only have to iterate finitely many times).

But if you squint at it right, this is actually just Hopcroft’s algorithm for DFA minimization! We start with an equivalence relationship which conflates everything, and then we split states apart as we find that they have the wrong label or lead to states that are now known to be equivalent, iterating this until we reach a point where there are no more states to split (i.e. a fixed point of \(F\)). The steps are slightly different in that we actually just split the states by labels once at the beginning and then don’t have to do so again, but because of the way \(F\) behaves in these circumstances the difference is pretty inessential (in particular we always have \(F(R) \subseteq R\) for \(R\) obtained by iterating \(F\) from the largest equivalence relationship, even though this does not hold for arbitrary \(R\)).

Is this observation useful?

Well, not really. It’s useful in the sense that it helped me understand why fixed points on lattices are such a useful technique, and it was nice to relate this back to some things I already understood. So it’s a useful exercise in pedagogy.

Are there any applications of this? Well, maybe. In the context of the probabilistic work the next step here is to look at other interesting lattices which can use similar structure, and that’s pretty interesting, but I’m not sure how useful it is in the language case. Also most of the ways in which it’s useful are likely better served by transforming it into the probabilistic case.

This entry was posted in Automata Theory on by .

Dis-Integrating the (Public) Self

Have you noticed that at some point in the last decade “personal brand” became one of those terms that we pretend we’re using ironically in order to hide the fact that we more or less mean it for real?

Recently I’ve been feeling a bit… the term I’ve been using for this in my head is “global and integrated”. There is one version of me, globally accessible, with all of the parts fitting together as part of a coherent whole.

My personal brand as DRMacIver is a pretty broad one, and deliberately so. I write about tech, cooking, sexuality, stargate, voting systems, fanfic… whatever is on my mind really, but there’s still a certain… gravity well of self-image that things naturally orbit within. Because everything is integrated, it must fit in with everything else. Extremes are damped out, and there’s a constant question of “Should I say this?”.

There isn’t really much that I feel like I can’t say, but there is a difference in how much effort it takes to say them – the recent sexuality post is not something I would normally write, not because I don’t want to talk about it but because I set much higher standards for myself when writing that sort of thing than I do when just bashing out a data structures post or writing some nonsense about Stargate or complaining about how everything is terrible.

Maybe none of that sounds too bad to you, but it’s been feeling pretty constraining to me for a while, and I’ve been thinking of creating a writing pseudonym. The difficult I’ve been having there is essentially how to do opsec and promotion at the same time – it’s easy for me in my public persona to get an audience (and I’m both vain enough to want one and self-aware enough to know that. I do plenty of writing in private, but if I’m going to write in public then I damn well want it to be somewhere that people actually read), so it’s never got off the ground.

The obvious solution to this was to just create writing pseudonyms that aren’t actually a secret but are still lightly separated – I link to them, but they never link back to me. It’s not hard to find out that they are me, but it’s also not immediately apparent and it helps me keep some emotional distance from them.

This solution is so obvious that it took me over a year to notice that it existed.

Anyway, without further ado, I would like you to introduce you to my two new writing personae: This Continuity of Self and Not A Teapot (TC and nat for short).

I originally had a particular theme in mind for TC, but it rapidly went out the window, so instead they have personalities and writing styles and talk about whatever they feel like. TC also acts as a normal-ish tumblr, while the other personae will be closer to straight up blogs.

In one of those things where the joke is much cleverer than I realised at the time, TC wrote the following description of their style:

mebbe that’s because we need to come up with a good creole so we can form a common syncretic framework in which the paradigms of boring nerd-speak and funny shit can socially construct a good shitpost

In fact, a syncretic framework of boring nerd-speak and funny shit-posting is exactly what TC does.

Generally the joke with TC is that it writes simultaneously really well and really badly. It’s happy to use $100 words and it uses them correctly. It could use correct grammar, but it has absolutely no interest in doing so, but if it wants you to understand its point it will write it in a way that is actually much clearer than more coherent attempts would often achieve. Most of the time though, TC is just fucking with you in a way that it hopes will leave you thinking interesting ways. Or just because it’s funny.

(Each of the personae have their own pronouns. TC is either it or they/them pronouns, nat is she/her. There isn’t any particularly good reason for this except “Why should he/him pronouns be the default for fictional characters?”)

In contrast, nat is slightly stuffy and precise, but mostly very earnest. She is routinely exasperated by her sibling, TC, but they actually work quite well together. Where nat takes everything too seriously, TC takes nothing seriously, and the combination of the two perspectives is useful for sandwiching a point. I really enjoyed writing them arguing and will probably do so more.

The joke with nat is that she is constantly on the cusp of degenerating into pure academic-ese, but actually uses fewer big words than TC because she genuinely wants you to understand, while TC just wants you to think. Where nat introduces academic words, she does so in a pedagogical style that is designed to teach you how to use them.

This doesn’t always work, mostly because of the difficulty with roleplaying someone who is smarter than you – where nat fails at pedagogy, it’s because I’m failing at it.

It’s not a deliberate part of the joke that the ridiculous character has a pretentious name and the pretentious character has a ridiculous name, but I like it enough that the next time I create one it probably will be part of the joke.

The advantage of these personae is that they let me change what is difficult for me to write. TC allows me to lift the constraints of dignity and gives me permission to not make sense, while nat allows me to go into full hyper-focused nerd mode and explain some aspect of a problem in extreme detail. Both of these are things that I feel somewhat reluctant to do as DRMacIver (which isn’t to say that I don’t do them, I just feel like I have a budget for how much I allow myself to).

Those are the three personae I have so far, and I think they’re sufficient for the area of persona-space they explore together. Their interests and values are pretty much like the more intellectual side of mine, they just have different focuses and preferences around them. Between the three of us I think we’ve got that covered.

Once they’ve settled own a bit more and I’ve got a better handle on them I’ll likely add some more. I’m idly thinking of some of the following:

  • a persona that is much more embedded in the world and mostly posts detailed descriptions of things that ignore their context and implications
  • a persona explores things from a more mystical perspective (this will be extremely difficult for me)
  • personae to explore more varied writing styles (“writing badly” and “writing more academically” are not exactly stretching my repertoire)

In the meantime though, nat and TC are a lot of fun to write, and I definitely plan to continue doing so.

This entry was posted in Uncategorized on by .

On Not Quite Fitting

Epistemic Status: I believe this to be an accurate description of how I experience the world. I am reasonably confident that it generalises based on what I know about peoples’ experiences, but I may be overstating how widespread it is a bit.

PSA: Please for the love of all the gods do not use this post to pick fights with me about bisexual vs pansexual. Not the time, not the place.

Credit: Thank you to various beta readers for this post. It’s always a bit stressful writing about this sort of thing.

If you talk to be people who fall under the LGBTIAQ* umbrella, one sense you will frequently get is something akin to the idea of “born this way” even if it’s not quite phrased as that – that their gender or sexuality is in some sense a deep seated part of their core identity and that trying to suppress it would be unbearably awful for them.

I have absolutely no doubt that the people saying this are telling the truth, but I think an underappreciated point is that this is still what you would see even if that were not the majority experience.

In particular, my personal experience is quite different.

I am bisexual. I tend not to make a big deal out of this, mostly because I do not date that much, but it turns out that your sexuality doesn’t magically go away just because you’re not doing anything with it.

I chose to be bisexual. At some point I decided that I was bored of describing my sexuality as “It’s complicated and not that interesting but I can give you the decision tree if you really want to spend the next fifteen minutes talking about it…” and that I should just use the commonly accepted word that was least inaccurate for my situation.

In a different life where I had had different experiences I probably would still consider myself to be heterosexual. I mean sure my brain would still occasionally go “hello, boys”, but it’s remarkably easy to ignore what your brain is telling you and just write it off as “brains do weird things sometimes” when it’s something that doesn’t fit your self-image.

Even if I had realised that this was genuinely a thing, there are definitely different circumstances under which I would absolutely not fess up to it in public. I decided to just be out about this in large part because I have social capital to burn and I thought it would be useful to people from a visibility point of view, and because secrets stress me out, but I had less of the former and the costs of my being out were substantially greater then I’d probably shove myself pretty thoroughly into that closet. “Hello fellow hets. Just call me Straightvid McHetero. Yup yup. This here David is all about the ladies” (that’s how straight men talk, right?).

Honestly, that would probably have been OK for me. Especially with how little I date, my sexuality isn’t a huge part of my life. I wouldn’t be happy about it, but I could deal with it.

Before I go any further I want to emphasise that this is not universally true. There are many bisexuals for whom their bisexuality really is a deeply felt part of their identity and for whom passing as straight (or as gay) would be unbearable. The situation is even worse if you are gay and forced to present as heterosexual.

My suspicion is that this, and variations on it, are actually quite a widely shared experience.

The whole reason we have this notion of being in the closet is because society imposes a high cost to breaking its rules. Even the most liberal of societies are still very heteronormative, and even more strongly cisnormative. If you go against these norms, you will be punished. It might be in big ways, it might be in little ways, and it’s certainly better than it was 50 years ago, but there absolutely is going to be a cost.

And what happens as a result is that people do a cost-benefit analysis (usually implicitly. Actually sitting down and going “Is the cost of publicly self-identifying as bisexual worth the benefit to me?” like I did is weird, but I’m like that). The people who are publicly out or otherwise visible as non-conforming are the people for whom the benefit of doing so is greater than the cost.

What this means is that for things where the cost is very high, the overwhelming majority of people you see who do not conform to some norm are people for whom the non-conformance is of sufficient importance to them that it’s worth the cost, or the cost of conformance is too high.

You can see this as more and more people feel comfortable coming out of the closet as things get gradually better – as the level of policing of people’s sexuality gradually goes down, the number of people for whom it is worth it to explore their sexuality goes up. This isn’t what a binary “you’re either LGBT or you’re not” split looks like, it’s exactly what happens when you have a continuous spectrum and everyone below some threshold is quietly pretending that there’s nothing to see here.

Centering gender and sexual politics and discussion on the people most strongly affected is absolutely the right thing to do, but I think it’s still useful to be aware that this spectrum exists and literally everybody is somewhere on it (that’s why it’s a spectrum).

This is important for a number of different reasons.

The first is simply that I’m pretty sure that it’s true. It’s good to believe true things. The world makes more sense that way. This model of how people are behaving is (as far as I can tell) extremely consistent with both the data and many many quiet conversations I’ve had with friends about their experiences.

The second is that I think it is extremely helpful to people to understand this about themselves, especially if they are in a  boundary area. Stressing about the question “Am I bisexual or am I just faking it?” seems to be an almost universal bisexual experience, and that’s not surprising given this dynamic! When most of what you hear is from people whose sexual identity is burned into their very soul, “I don’t know what’s going on but sometimes I feel like it might be nice to be able to kiss boys??” feels fake in comparison.

It’s also useful from a political point of view. There is strength in numbers, and understanding that the range of experiences includes a much more broad base of people who would experiment if given the option significantly increases our numbers. I’d much rather describe my sexuality as “Look over there!” followed by dropping a smoke bomb and escaping in the confusion, and my decision to identify as bisexual instead is in no small part a political one. I suspect there are quite a lot of others out there who could usefully do the same.

(Please note: If you actually feel you’re genuinely 100% straight don’t just call yourself bisexual for political reasons. I think the label becomes significantly less personally and politically useful if people start doing that).

Finally, the biggest reason I think that this is important to talk about is because that’s how we beat pluralistic ignorance – the phenomenon that people can widely share an experience without knowing that the experience is widely shared.

Imagine an extremely oppressive society in which presenting as anything but straight is completely not an option (sadly this probably does not require much imagination). Now wave a magic wand and everyone wakes up one morning as a 50/50 split bisexual. What happens?

Well, almost nothing. Possibly enforcement of the rules gets even stricter, because now people are terrified of being found out as bisexual themselves. Although everyone is bisexual, but thinks everyone else is straight.

I think it is extremely likely that we are in a less extreme version of this scenario, with almost everyone failing to quite fit the mould that society wants them to but still being complicit in enforcing the accompanying social rules on others.

(Some people benefit enormously from the current state of society, but both things can be true at the same time).

I really do mean almost everyone, because this isn’t a problem confined to sexuality (although I do think that for a sufficiently broad definition of bisexual there are a hell of a lot more of us out there than is commonly supposed, so maybe it’s even a majority if you just stick to sexuality). The human experience is full of spectra – gender is probably one or more spectra, there are a whole variety of neurodivergences which certainly are, and a whole variety of less obvious preferences and traits that society forces us to fit into.

As a result, I believe most people are spending their lives being made vaguely miserable by an attempt to conform to rules that describe an ideal that almost nobody conforms or wants to conform to. If we could all take a step back and just decide not to enforce some of those rules, almost everybody would be more able to express themselves in some way that they were more comfortable with.

Talking about this problem won’t make it go away on its own – some of these rules are due to genuine value differences, and some of the people being made miserable would actively choose to enforce the rules even if given the option not to – but I think it’s a good first step.

By acknowledging that we all experience these degrees of variation, and that nobody quite fits in, maybe we can start to broaden the range of behaviours that society accepts and make it easier for people to experiment and find out what actually works for them.

If you would like to read and learn more about this, I can highly recommend “Queer: A Graphic History” by  Meg-John Barker and Julia Scheele. Foolish I read it right after rather than right before writing this post, so it did not directly inform it, but I think there’s a lot of overlap nevertheless.

This entry was posted in Feminism, Performing philosophy without a license on by .

Doing the Two-Step for Efficient Reversible Deletes

Attention conservation notice: I’m back to blogging about tech again. Sorry.

Credit: Thanks to Suzy Hamilton for useful information about dance types.

I recently read Donald Knuth’s dancing links paper. It was sent to me as an example of good writing, which I don’t entirely agree with (it’s locally good writing, but I didn’t really understand it until I rewrote the first couple of pages in my own words and notation and then it was fine), but regardless of whether it’s good writing it’s definitely an interesting technique that I was previously vaguely aware of but didn’t appreciate.

Roughly the idea of dancing links is this:

  1. For efficiently implementing depth first search for solving some hard combinatorial problem (e.g. SAT solving, but also others. The main example of the paper is the exact cover problem) it is very useful to be able to have mutable data structures with undoable operations. In your recursive call you make a bunch of changes, and you undo them all before returning.
  2. A particularly useful category of undoable change is to be able to maintain a list of elements that you can delete individual elements from, then undo those deletes.
  3. A doubly-linked list allows you to efficiently implement that by removing a node from the list and just keeping it around (with its pointers still intact) and then just reinserting it when you undo. Apparently this is like the links in the doubly-linked list “dancing”, hence the name.

1 and 2 are interesting points that I think will have a significant impact on how I design things. I am very glad to have read the paper for that.

Point 3, eh. No thanks.

There are two problems with it:

  1. Doubly-linked lists are a bullshit data structure
  2. Point 1 of this list is in large part responsible for one of my main problems with wrapping my head around the paper: If you give me an interesting algorithmic approach then I’m going to want to wrap it up as an ADT so I can treat it in terms of an abstract set of operations it implements and reason about that separately from the algorithm. Doing this as a doubly linked list makes that hard because of what the deletion operation ends up looking like.

It turns out that it’s actually really easy to fix both these problems if you are willing to relax one of the constraints very slightly: The desire to keep all of the elements in a particular order.

There is a data structure that supports the following operations:

  • Initialise with N elements in O(N).
  • Get the current number of elements in O(1)
  • Get the element at index i in O(1)
  • Delete the element at index i, putting the element that was previously at index length – 1 in its place (or just delete it if i = length – 1) in O(1).
  • Undo a single delete O(1)

So if you perform k deletes and then call undo k times, the list is back in the state it was before the deletes.

Moreover there is very little indirection involved (everything is just stored in an array) so algorithms using this involve almost no pointer-chasing, unlike a doubly linked list, and is likely substantially more efficient as a result (but I have done literally zero benchmarking to demonstrate this). It also uses less memory per item.

One important thing to note is that although the order of the elements changes, it does so in a sufficiently predictable way that forward iteration over the list is easy: You just iterate as normal, and if you want to delete the current element you just skip incrementing the loop index.

How does this data structure work?

  1. Put all the desired elements in an array of length N. Store a length field and an undo stack. The length field keeps track of the end of the currently present elements – everything that has been deleted is kept in the array but stored starting from index length.
  2. When you delete the element at index i, push i onto the undo stack, decrement the length by 1, and swap the elements at position i and position length.
  3. When you undo, pop i from the undo stack, swap positions i and length, and then increment length.

That’s it. We’re done.

This is probably a known technique – it only took me about an hour of thinking about the problem to come up with it, so it would be frankly bizarre if nobody had noticed this since the dancing links technique was invented in 1979 – but some cursory googling didn’t find anything, so if nothing else this post will hopefully make the idea more visible and maybe someone who knows of it can send me a link (dancing or otherwise).

In general this technique of “You can remove an element from an array in O(1) if you don’t mind losing the order” is surprisingly powerful and I think underappreciated. It’s pretty straightforward once you see it, but allows for some pleasingly elegant data structure designs.

This entry was posted in programming on by .

Cooking on Easy Mode

Attention conservation notice: this is a food post. If you’re not here for the food posts, maybe go reread Stargate Physics 101 instead or something.

Content note: Aggressively non-vegan food.

The other evening I had zero energy but felt like I should at least make some token effort at real cooking so I just flipped all the dials to easy mode:

  • lots of salt
  • more butter than you are willing to admit to
  • caramelised onions
  • a single strong spice or herb (e.g. chilli, black pepper, rosemary)
  • meat
  • a pressure cooker

Pretty much all of these dial up the tasty to effort ratio of everything you cook. None of them are essential (I want to emphasise that it is possible to make extremely tasty vegan food. Meat and butter are just easy mode).

Here’s the specific combination I deployed:

  1. Slice a lot of red onions. Put them in the pressure cooker with lots of butter, lots of salt, and a dollop of smoked chilli paste.
  2. Cook on high heat until the pressure cooker whistles, then low heat for another 20 minutes. The onions should be slightly caramelised and very juicy when you take the lid off.
  3. Add shredded chicken (about 3 times by volume of what I used for the red onions. I had a bunch in the freezer that I’d made previously).
  4. Stir it all up until well mixed. Same drill as before with the pressure cooker.
  5. Serve on corn talcos

I don’t know if I get to count this as properly Mexican food. I tend to get in trouble with my sister-in-law when I do that. But it was tasty and definitely in that direction.

The result was frankly almost offensively tasty. I had a sore throat which made eating painful and I still ate way too much of this.

This entry was posted in Food on by .