Necktie knots, formal languages and network security

Wednesday, March 26, 2014 - 1:30pm - 2:30pm
Lind 305
Mikael Vejdemo-Johansson (Royal Institute of Technology (KTH))
A chore for some, space for personal expression for others, the necktie knot used to have very few specific knots in widespread use. In their 1999 paper, Fink & Mao Designing tie knots by random walks. Nature 398, no. 6722 (1999): 31-32) list all possible ways to tie a necktie. They limit their enumeration task by focusing on knots that present a flat front just like all the classical tie knots. This way they established a list of 85 possible tie knots.

Tie knots with intricate patterns of the necktie winding into symmetric but no longer at front displays have emerged in the past decade, introduced by the movie Matrix Reloaded and recreated hobbyists. These tie knots are tied with the narrow end of the tie, wrapping it to create patterns on the surface of the tie knot. As such these knots are not covered by the listing proposed by Fink & Mao.

With a team of collaborators I have extended the listing by Fink and Mao to cover these new tie knots. While doing this we have been able to determine the computational complexity classes of the grammar that describes tie knots.

The formal language techniques that help us analyze the tie knot grammars are used in contemporary security research: a large class of security problems online emerge from different implementations of a communications protocol disagreeing on the actual grammar used. We will talk about the connections between the language techniques for tie knots and those that help us analyze security.