Department of Mathematics

Indian Institute Of Technology Madras , Chennai
  • Mathematics Department Shifted to NAC Office of the Department of Mathematics is moved from HSB to New Academic Complex (NAC) 5th and 6th Floor

Greene's Theorem for Timed Words

Speaker : Prof. Amritanshu Prasad (The Institute of Mathematical Sciences, Chennai)

30-08-2018

Abstract :

A timed word in an alphabet A is a word where the letters of the alphabet occur with timestamps. Words of this type arose in the theory of timed automata developed by Alur and Dill to perform the formal verification of real-time systems. For a timed word in a finite ordered alphabet, we consider the algorithmic problem of determining the longest weakly increasing subword in one pass over the word. We generalize Schensted's classical algorithm for ordinary words to the setting of timed words. We also extend the interpretation due to Curtis Greene of the shape of the tableau resulting from Schensted's algorithm to the setting of timed words. These timed versions are then used to give piecewise linear interpolations of classical bijections between words and tableaux.

Key Speaker Prof. Amritanshu Prasad (The Institute of Mathematical Sciences, Chennai)
Place NAC 522
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None