Personal tools

Necktie knots, formal languages and network security

Speaker: Mikael Vejdemo-Johansson Affiliations: Jozef Stefan Institute (JSI), Royal Institute of Technology (KTH), and the IMA (at University of Minnesota)

  • Computer Science Seminar
  • Geometry/ Topology Seminar
When Fri, Feb 28, 2014
from 11:00 AM to 12:00 PM
Where TBD
Contact Name
Contact Phone 3149777002
Add event to calendar vCal

A chore for some, space for personal expression for others, the necktie knot used to have very few speci c 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.


For recent news coverage on this result, see the following:

« September 2017 »