Consider sequences of well-formed parentheses (or up/down sequences) of the type counted by the Catalan numbers. See http://www-math.mit.edu/~rstan/ec/catalan.pdf These are sometimes called Dyck words or Tamari sequences. The first several are (), (()), ()(), ((())), (()()), (())(), ()(()), and ()()().
For fixed length, these words can be placed in binary trees or associohedra, and there are distance measurements based on polyhedral geometry and rotation in binary trees: See https://dx.doi.org/10.1090%2FS0894-0347-1988-0928904-4 and http://arxiv.org/abs/1207.6296 and http://link.springer.com/book/10.1007/978-3-0348-0405-9
Question: Is there a well-defined distance between words of different length?
E.g., I'd like a distance measurement for which () is closer to (()()) than to ()()() because the missing pieces are deeper. In my context, deeper means smaller. The distance measurement should reproduce those cited above when the word-lengths match. I hope that this is possible with discretized hyperbolic geometry or just binary rotations combined with an appropriately weighted Hamming distance.
I'm not terribly familiar with this field and my basic lit search has come up dry. Has this been studied?
