✦ LIBER ✦

Two shortest path metrics on well-formed parentheses strings

✍ Scribed by Christian Germain; Jean Pallo

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 416 KB
Volume: 60
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(96)00180-9

No coin nor oath required. For personal study only.

✦ Synopsis

We present an analysis of two transformations on well-formed parentheses strings. Using a lattice approach, the corresponding least-move distances are computable, the first in linear time and the second in quadratic time.