6533b827fe1ef96bd128640c
RESEARCH PRODUCT
Two shortest path metrics on well-formed parentheses strings
Jean PalloChristian Germainsubject
CombinatoricsLattice (order)Signal ProcessingMetric (mathematics)Shortest path problemTime complexityComputer Science ApplicationsInformation SystemsTheoretical Computer ScienceMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1996-12-01 | Information Processing Letters |