0xDE (11011110) wrote,

A partial order on strings of parentheses

Any string of properly nested parentheses represents a tree, with a node for each matching pair of parents and the parent of a node being the next outer pair of parens. So by Kruskal's tree theorem, parenthesis strings are well-quasi-ordered by a partial order in which s ≤ t whenever s can be reached from t by the removal of matched parens. But this sort of parenthesis removal is a very nonlocal operation: the match of a paren can be very far in the string from it.

Here's another pair of operations for modifying parenthesis strings that are somewhat more local. Remove a pair of matched parentheses only if there is nothing between them. Or, if it would preserve the proper nesting of the parens, replace a consecutive pair "()" by its swap ")(". So for instance we could turn "((()))" into "(()())" by swapping the innermost pair of parens. The reachability relation for these operations also turns out to be a well-quasi-order!

Read more...Collapse )
Tags: chord diagrams, combinatorics
  • Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded