Here’s a blog of things I’ve found interesting in computer science. I’ve tried to write this blog as if it were for my younger undergraduate self, perhaps some time between first arriving at university and the end of second year. That’s just a rough guide, though! Hopefully some of it is interesting.
Posts
Here’s what I've been up to. Click the titles of the posts to go to their respective pages.
It's a standard result that all Büchi automata recognise precisely finite unions of languages of the form $U \cdot V^\omega$, where $U$ and $V$ are both regular languages; we call such recognised languages /$\omega$-regular expressions/. Büchi himself proved the result in \cite{Buchi-1960b}, Lemma 10. It's a nice result to have, particularly because of its simplicitly, as well as how well it captures the intuition of what a run on a Büchi automaton looks like.
In computer science, we like to show that things are decidable, and indeed the method to show that a problem is decidable is easy enough; simply give an algorithm that decides your problem. But we would also like to show that some things are undecidable (generally so we can stop trying to find algorithms for them).
I've been reading up around Büchi automata (BAs) recently, as well as their cousins (Muller, Rabin, Streett and parity automata, amongst others), and have been wondering what similar automata exist that may or may not be equivalent to Büchi automata. So here's a catalogue of some automata I've thought up as of late.
When doing mathematics, you might wonder what it is that makes mathematical statements true. It's true that $2 + 2 = 4$, sure, but what makes it true is unclear. Ask a mathematician, and they may heartily tell you that it follows from the axioms. But, if that's the case, what is it that makes the axioms true?