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.