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
The proof is not difficult, as these things go. It's clearly a partial order and has no infinite descending chains (each step decreases the sum of the levels of the matched pairs of parens) so the main thing that needs to be shown is that there are no infinite antichains. If an infinite set of strings of matched parens contains parens that are nested arbitrarily deep, it can't be an antichain, because a set of parens nested k levels deep can reach any other set of k parens (this is easiest to see in terms of the representation of parenthesis strings as monotonic paths in a grid, where the parenthesis swapping operation is the removal of a grid square from the region below the path). So, we can assume that any candidate set for being an infinite antichain only has a finite level k of nesting, and then apply induction on k.
A string of nesting level k can be formed in a unique way from a sequence of substrings of nesting level k − 1 by wrapping a pair of parens around each substring in the sequence and then concatenating them together. For instance, the string
The reason I started thinking about this is because a very similar sequence of operations (swapping a nested pair of top half-symbols or bottom half-symbols, or removing a slash or backslash) generates a well-quasi-order on my notation for 321-avoiding permutations, with almost the same proof. Sadly, though, these operations don't seem to preserve a lot of useful properties of the corresponding bipartite permutation graphs (or other structures associated with the permutation), so I'm not sure what these orders are good for.