Challenges in Combinatorics on Words (Day 5)

My knees were killing me, but that wouldn’t stop me from going to a talk that relates algebra and automata theory!

  • Kiran Kedlaya gave two talks on Christol’s theorem. Christol’s theorem says that a formal Laurent series is algebraic over the field $\mathbb F_q(t)$, where $q$ is a prime power, if and only if it is automatic. The second of his two talks was about a theorem of his which generalized Christol’s theorem to apply for general power series.
  • Eric Rowland gave a neat talk on characterizing $p$-automatic sequences using 1-dimensional cellular automata. There’s actually a lot more algebra to cellular automata than I would’ve expected was possible (and even some connections to Kedlaya’s talk on Christol’s theorem). Then again, I don’t really know much about cellular automata other than Conway’s Game of Life.

So even though I didn’t really contribute at the workshop and I was kind of wandering around as a lone graduate student, it was a really interesting experience. At the very least, I got to meet some interesting people working on interesting things and I have a pile of interesting things to look up over the summer before I head to Kingston and ramp up into hardcore math research mode.

And now, some miscellany.

  • Lunch notes: tried Mother’s Dumplings again and opted for a double order of dumplings this time around. I went with boiled again, because I couldn’t justify paying a bit more to get a bit less, even if the steamed dumplings were supposed to be amazing. Maybe that’ll happen if I’m there with other people in the future.
  • Commuting notes: I got a ride to and from Fields, since it probably wouldn’t be a good idea to be on the TTC for long periods of time with my knees in their current state. The morning trip involved going across Eglinton, which is an absurdly wide road and I don’t really know why people are mad about LRTs on that road when it’d essentially be replacing a lightly used HOV lane (or maybe even not). Once we hit the DVP, traffic got heavy and Bloor was pretty bad. We went down Sherbourne, where I saw the Minnan-Wong bike lanes and we continued on Carlton and College.
  • The evening commute was also interesting. My dad usually takes Lake Shore through to The Beaches and up Kingston, but apparently, there’s some construction going on there, so we went along Gerrard through the east end of old Toronto instead. We ended up cutting across to Southwest Scarborough on Danforth and back up to STC to pick up a new phone. This was a much better route than the one proposed by my dad, who wanted to go up to the DVP.
  • Replacement phone notes: Got a new phone and restoring service was pretty easy. The tough part was restoring from iCloud backups since, Apple, in their sometimes questionable wisdom, decided that you could only restore iCloud backups when you first set up your phone, which the Koodo lady zipped past while we were at the booth. So I had to reset the iPhone, which was baffling, since it required downloading the latest iOS update, which I’m pretty sure I’d already downloaded. But after all of that, my phone was in pretty much the same state as I had it in yesterday.

Challenges in Combinatorics on Words (Day 4): Bus theft edition

So today was an adventure for reasons unrelated to exciting developments in combinatorics on words.

  • More talks and pretty proof heavy, which I thought I’d enjoy, but for someone who’s not in the field, it was kind of tedious. It was interesting to see that conjectures do get proven, I guess.
  • Theoreticians in CS love complexity measures, so we had two today! Antonio Restivo defined a complexity measure based on periodicity and Jörg Endrullis talked about comparing two different infinite words by using transducers. The transducer thing was pretty interesting because it’s more automata stuff and because there are so many natural questions that arise that haven’t been worked on very much yet.
  • Also, problems were getting solved during the workshop. Steffen Kopecki mentioned that him and others had solved some cases of Thomas Stoll’s problem, which asked if there are infinitely many odd $n$ such that $s_2(n^2) = s_2(n) = k$, where $s_2(n)$ is the sum of binary digits of $n$.
  • I finally got an experience of stereotypical Malvern life, in which my phone got stolen on the bus right as the hooligans were leaving the bus. I chased them down and I guess I was faster than I looked because they looked back and went “oh shit” and one of them decided they needed to stop me so they pushed me.
  • I chased them a bit longer but stopped because I was feeling tired and I realized my knee was actually bleeding really badly, which one guy who was walking home pointed out. That guy was good people and let me into his home to treat my wounds, provided wifi to see if I could track my phone down, and a phone for contacting people.
  • My dad picked me up a bit later and we decided the cut on the knee was pretty nasty so we went over to the hospital, which is my first experience with the Canadian healthcare system after being politically aware. Since my injuries weren’t that bad, I started keeping track of the dreaded wait times. It took about an hour before the doctor saw me and half an hour to treat and get stitches and maybe another half an hour for followup with cleaning and stuff, so it took almost two hours on the dot. That seemed reasonable but maybe I’ve been socially engineered by the communism. Also, didn’t pay anything.

Challenges in Combinatorics on Words (Day 3)

A short day today, with interested persons off to a visit at the ROM.

  • Now that open problem presentations are over, it’s mostly just talks and problem solving time. I don’t know if it was intentional, but today’s talks (other than the plenary talk) dealt mostly with algorithmic aspects of strings, which aren’t really my thing.
  • There was one talk which was particularly interesting, which was Florin Manea’s talk on finding hidden repetitions, which introduced the idea and motivation behind “hidden” repetitions. We want to check for repetitions of a particular factor $x$ or $f(x)$, where $f$ is an involutive (anti-)morphism. This problem actually comes out of the DNA setting, where words are taken over $\{A,C,G,T\}$ and taking the Watson-Crick complement of a word is the involutive antimorphism we’re interested in.
  • Jason Bell gave two plenary talks, one yesterday and one today, on algebraic aspects of $k$-automatic sequences. I’d read about $k$-regular sequences before out of interest but didn’t really retain much of it and I’m glad that I got a chance to have someone actually explain how to derive them from the idea of $k$-automatic sequences and also what the $k$-kernel is.
  • For lunch, it was raining and I didn’t feel like walking all the way down Spadina to King’s Noodle so I decided to try Kom Jug Yuen. It was more expensive and not as great as I was expecting. I’ll just walk to King’s or Gold Stone again next time.
  • The Fields Institute keeps all of its mathematicians and visiting mathematicians very well caffeinated and fed throughout the day. I think they have a scheduled coffee break at 3pm-ish because a bunch of people that I didn’t recognize were always around the coffees and foods and talking about math that I didn’t recognize. For coffee, they’ve usually got some combination of Starbucks and Timothy’s. For food, they have a wide selection of fruits and cakes. For breakfast, they have a platter of baked goods. I have also seen a platter of pita wedges and some kind of nice bread with various delicious dips.

Challenges in Combinatorics on Words (Day 2)

More open problems and talks!

  • There were two talks and a bunch of open problems by Aleksi Saarela and Juhani Karhumäki on $k$-abelian equivalence. So you have your alphabet $\Sigma = \{a_1,…,a_m\}$ and two words $u,v \in \Sigma^*$ and $u = v$ if they’re the same, which is obvious. We have this notion of abelian equivalence, where we have $u \equiv v$ if $|u|_a = |v|_a$ for every $a \in \Sigma$. That is, $u$ and $v$ have the same number of each letter ($aaabba$ and $ababaa$ are abelian equivalent since they both have 4 $a$s and 2 $b$s). We generalize abelian equivalence to $k$-abelian equivalence by saying that $u \equiv_k v$ if $|u|_x = |v|_x$ for every factor $x$ of length up to $k$. A lot of the problems that were posed were questions of how to extend properties that we know for the normal case and the abelian case to this new $k$-abelian setting.
  • The room that we’re in at the Fields Institute has a neat projector setup, where it uses two screens. The right screen displays whatever is currently displayed on the computer, while the left screen displays what was previously the current screen. This is really useful, because speakers tend to go through their slide decks a lot faster than I can write and often refer to definitions and theorems stated on the previous slide. However, the system has an interesting quirk: it somehow detects when the screen changes, which works for most presentations, since they’re static slides, but there was one presentation where the speaker had a slide with an animated gif or something on it and the left screen kept updating.
  • There was a problem from Štepán Starosta that dealt with extending things we know about palindromes to generalizations of palindromes. So instead of considering the mirror or reverse operation, what you’d do is consider a finite group of involutive morphisms and antimorphisms (an involutive function $\Theta$ has the property that $\Theta^2$ is the identity function).
  • I met a prof who happened to do his undergrad at Waterloo and is currently at a university overseas. We had a nice chat about various flavours of CS double majors and students chasing trends to make monies (as it turns out, CS/C&O wasn’t always popular).
  • I think I can articulate now why I feel useless in the problem solving sessions. While I know a bunch of results and definitions, combinatorics on words really is a pretty different field from automata theory or formal languages. So, since the basic “language” of the two fields is the same, if someone walked me through a proof or something, I’d be able to follow it. But when it comes to working on problems, even though the two are related, there’s an intuition to these kinds of problems that I haven’t developed yet nor do I really have a feel for how results are connected or what certain properties might imply.

Challenges in Combinatorics on Words (Day 1)

Workshop blogging! Very exciting, since I’ll try to reconstruct some highlights from my awful note-taking for each day.

  • One of the neat things about this is that unlike a “real” conference, there aren’t many results presented. Instead, the focus is on open problems and working on those problems. Essentially, what you have is very smart people coming up and talking about a problem that they had trouble solving and all of the things they tried before they got frustrated and gave up or something.
  • Luca Zamboni presented an open problem involving factors of an aperiodic infinite word and palindromes. An interesting tidbit was when he described how to use palindromes to describe a word. Basically, you say that certain positions of a word are palindromes and you try and fill in those spots with letters. So the question that comes up is trying to figure out what is the fewest number of palindromes that’s necessary to describe a particular word.
  • Eric Rowland talked about $p$-automatic sequences and deriving an automaton from some polynomial which describes a $p$-automatic sequence. We know how to get the polynomial from an automaton, but coming up with an efficient algorithm for the other direction is tricky.
  • Neil Sloane gave a neat talk about curling numbers. If we have a word $S = XYYYY \cdots Y = XY^k$ with factors $X$ and $Y$ for some finite $k$, then the curling number of $S$ is $k$. We can define a sequence where the $n$th term of the sequence is the curling number of the previous $n-1$ terms. There are a bunch of interesting conjectures that arise from this sort of thing.
  • Also, he really likes sequences, which I guess is what you’d expect from the guy who started the Online Encyclopedia of Integer Sequences. I was in his group for dinner and he spent much of the time introducing various sequences to us and we spent a lot of it playing around with them.
  • I was pretty much useless during open problem solving sessions because of a number of reasons (tiredness, lack of experience in the field and problems, overheating from sitting in the sun). But, I did watch a group work on a problem having to do with unbordered words and factors and it was nice knowing that a bunch of international experts worked on problems in much of the same way I do: by writing stuff on the board and staring at it for a while.

How Toronto’s War on the Church™ ended up going

I should start by noting that I’m by no means an expert on planning or urbanism at all and I’ve only been following this issue whenever it’s popped up. I’ve tried to go through whatever I can of the respective documents and files, but there’s only so much I can understand as an amateur. Basically, the best I can do is read and try to follow what happens at council so that’s what I’ll be focusing on.

So a few months ago, I noticed this thing scary graphic being passed along on Facebook about how Toronto was declaring war on the church or some such thing. Basically the war was conducted on two fronts:

  1. The harmonized zoning bylaw
  2. The Toronto District School Board raising rents on religious groups by some inordinate amount

I’ll be focusing on the harmonized zoning bylaw. First, a bit of history is necessary to put everything in context.

As you may or may not remember, what we now know as the City of Toronto used to be a two-tier municipality consisting of six different cities (Scarborough, North York, East York, York, Etobicoke, and Toronto) and a regional layer of government on top called Metropolitan Toronto. Everyone was happy with this arrangement, so obviously, the provincial government needed to wreck it.

Sometime during the first term of Mike Harris’ Common Sense Revolution™ Progressive Conservative provincial government, it was thought that Toronto (and a few other cities around the province) could run more efficiently as one giant city instead of a bunch of different cities. And so, in 1998, the Government of Ontario decided to smush all of these cities together even though no one wanted it to happen and here we are today, with one giant City of Toronto. Obviously, having to merge six different governments together into one giant government is not a trivial task and even now, 15 years later, we’re still trying to work out the kinks. One of those kinks is planning and zoning regulations.

You see, because Toronto used to be six autonomous cities, this means that all of those cities each had their own sets of planning regulations. This is obviously not ideal. So in order to try and simplify things (or at least make them less unwieldy), the city tried to work on harmonizing the bylaw across the city. This has been a work in progress for many, many years and almost happened in 2010 but it kind of blew up and everyone went back to the drawing board and here we are again.

Now a few months ago, someone found out that the newest version of the proposed draft zoning bylaw turned out to severely restrict the zones where places of worship could be established. Even though the immediate reaction was over the top spiritual war rhetoric, the concerns weren’t unjustified. Essentially, places of worship were limited to select commercial and institutional zones and that was all, no residential or industrial zones. Was it intentional? Was it a mistake? Who knows? But it’s helpful to remember that planning staff was trying to go through an incredibly complex set of regulations and trying to make everything somehow work together.

For those of you who aren’t familiar with how City Council works, essentially, stuff starts out in the various committees before heading out to the council floor. And so, religious leaders and groups went and got in touch with their councillors with their concerns and went and deputed at Planning and Growth Committee meetings and the bylaw was revised into something much more reasonable before being shipped off to council. In other words, there was something that was overlooked by someone, interested and concerned parties gave input and worked with their representatives, changes were made, and civic governance worked as intended.

With that done, we fast forward to the April 3 meeting of Toronto City Council. At this particular council meeting, the mayor made the zoning bylaw and Hero Burger at Nathan Phillips Square his two key items. Most people will remember the second one because councillors basically argued about whether to put a Hero Burger in Nathan Phillips Square for two or three hours and it featured the deputy mayor reading a selection of items from the menu of Hero Burger among other things. But before the Hero Burger shenanigans started, a pretty healthy chunk of time was spent dealing with the zoning bylaw and within that debate, there was a substantial amount of stuff dealing with places of worship.

As was mentioned earlier, initially, places of worship really were significantly impacted negatively by the proposed changes. However, all of that got significantly reworked and when it hit the council floor, it was something much more reasonable. The proposed bylaw now allowed for places of worship in all residential and commercial zones, various institutional zones, and industrial office zones. This was mostly fine, except for some fighting over whether to allow places of worship in light industrial zones.

The context behind this particular scrap is that a common thing for smaller churches to do is to rent or establish their church in areas which are zoned for industrial use because the cost of doing so is a lot cheaper. However, this puts them at odds with the city’s attempts at trying to preserve its industrial lands. What tends to happen is because the land value in these zones tends to be cheaper, condo developers often buy up these lands and try to get zoning changes on the lands. The result is that there are fewer and fewer places in the city where industry can set up operations.

Of course, churches don’t tend to be huge developers or speculators buying up cheap land to flip over to developers, so what’s the problem with letting them on industrial lands? The problem is that places of worship still negatively impact the use of industrial lands for industry. The reason for this is because a place of worship is classified as a sensitive use under provincial regulations and so the surrounding industry has to restrict their industrial activities, even though they’re in an industrial zone.

The particular motion (Motion 3, Part 3) to allow places of worship on light industrial zones was eventually lost and the initial recommendations from Planning and Growth Management were basically passed. Of course, this doesn’t meant that churches are suddenly getting booted from industrial lands. Most churches that are already there legally based on whatever bylaw was in effect before gets grandfathered and gets to stay there. It’s just new churches won’t be able to move into industrial zones.

So tl;dr, everything worked out in the end and it’s going back to staff for one more go-over before being finalized for reals.