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\le 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!

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 "\( (\,)\,(\,(\,)\,) \)" can be formed in this way from the sequence of substrings "", "\( (\,) \)". Most of the time, applying either of the two modification operations to the level-\( k \) string leads to a similar operation on one of the substrings in this sequence, and if that were all that could happen then we could apply Higman's lemma together with the induction hypothesis for \( k-1 \)  to show that the sequences of substrings are well-quasi-ordered and therefore that the induction hypothesis holds for \( k \). There is a complication: swapping a pair of parentheses that are nested within exactly one other pair (in the level-\( k \) string) leads to an operation in the sequence of substrings that splits one substring into two. But these extra ways of reaching one sequence of subtrings from another only make it harder to find an infinite antichain, so the argument using Higman's lemma remains valid.

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.