1
$\begingroup$

This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem?

The setup is as follows: we are given $n$ operator nodes $x\ast_1 x\ast_2\dots\ast_n x$ connecting $n+1$ leaves (whose identity is not important, here denoted by $x$) and the goal is to construct a valid parenthesization of the operators, i.e. a tree with the $\ast_i$ at internal nodes and with $x$ at the leaves. The operators may not be reordered but they can be reassociated. This is subject to two constraints:

  1. Each operator $\ast_i$ has a (left associative) precedence $p_i$, meaning that we prefer $(a\ast_ib)\ast_jc$ over $a\ast_i(b\ast_jc)$ if $p_i\le p_j$.
  2. Each operator $\ast_i$ may require that its left or right argument is or is not a leaf. (That is, there are four combinations of "left leaf, right leaf", "left leaf, right non-leaf" etc and each operator specifies a subset of these four possibilities. I will abbreviate these with $x$ for "leaf" and $T$ for non-leaf subtree, so an operator specification is a subset of $\{xx,xT,Tx,TT\}$.) A valid solution must satisfy the constraints of all operators.

For example: suppose $\ast_1$ has constraint $\{xT\}$ and $\ast_2$ has constraint $\{xx,xT\}$, and they both have precedence $1$. Of the two possible trees $(x\ast_1 x)\ast_2 x$ and $x\ast_1 (x\ast_2 x)$, the precedence prefers the first one, but the first tree violates the conditions on both nodes, as $\ast_1$ sees configuration $xx$ and $\ast_2$ sees $Tx$ and neither of these is allowed. The second tree has $xT$ for $\ast_1$ and $xx$ for $\ast_2$ so this is a valid solution (and the best solution since it is the only one).

With only condition (1), this is a straightforward precedence parsing problem and linear time solutions exist. With condition (2) however, it becomes a constraint satisfaction problem and it would not be surprising to me if linear time solutions no longer exist. A brute force solution would enumerate all trees and hence would be exponential time, but I think it is likely not NP complete because of the locality and linearity of the constraints: some kind of dynamic programming is likely possible.

Note: there is also a question here regarding what condition (1) even means in the presence of constraints. It specifies a preference ordering on individual tree rotations but what if the rotation is not valid? Is there a way to lift (1) to a sensible ordering on entire trees which reduces to standard precedence parsing when the constraints are trivial?

$\endgroup$

1 Answer 1

2
$\begingroup$

Here's a dynamic programming solution to the problem. To address the aside, we score candidate solutions by the number of edges between two internal nodes that represent a violated precedence ordering (so for example if $+$ has lower precedence than $\times$ then $(1+2)+(3\times 4)$ has a cost of 0 and $1+((2+3)\times 4)$ has a cost of 1 because of the $(2+3)\times 4$ subtree which violates precedence). In the absence of constraints, it is always possible to get cost 0 by performing tree rotations on any violated edges, so this reduces to standard precedence parsing in that case. The goal is to return a tree with minimal cost among those that satisfy the constraints.

The subproblem we use in the recursion is to give an optimal tree with designated root $\ast_i$. We evaluate the configuration of $\ast_i$ right away: the left side is a leaf iff $i=1$ and the right side is a leaf iff $i=n$. If this configuration is not legal then there are no solutions with $\ast_i$ at the root.

Otherwise, if the left side is a leaf then it is feasible with cost 0, else we consider each $\ast_j$ for $j<i$ as a possible root for the left subtree, and recursively get an optimal subtree, if one exists, along with its cost. The total cost contribution is then this cost, plus 1 if $p_j>p_i$. Taking the min over these gives us the best left subtree (or fail if no solutions exist).

We can do the same thing for the right subtree: If it is a leaf then we are done, and otherwise we take the min over the cost of all choices of root. The total cost of the tree itself is the sum of left and right costs.

As a mathematical expression, we can say that $\mathsf{cost}(a,b,i)$ calculates the cost of the optimal tree on the substring $x\ast_a x\ast_{a+1} x\dots x \ast_b x$ of the original expression, rooted at $\ast_i$:

$$\begin{align} \mathsf{cost}(a,b,i):={} &\mbox{if }(i=a,i=b)\in\mathsf{config}(\ast_i)\\ &\mbox{then }\\ &\quad\phantom{{}+{}}\left(\mbox{if }i=a\mbox{ then }0\mbox{ else}\min_{a\le j<i}\left(\mathsf{cost}(a,i-1,j)+[p_j>p_i]\right)\right)\\ &\quad{{}+{}}\left(\mbox{if }i=b\mbox{ then }0\mbox{ else}\min_{i<j\le b}\left(\mathsf{cost}(i+1,b,j)+[p_i\le p_j]\right)\right)\\ &\mbox{else }\infty\\ \end{align}$$

The optimal tree is just the min over all possible roots:

$$\mathsf{OPT}:=\mbox{if }n=0\mbox{ then }0\mbox{ else}\min_{1\le i\le n}\mathsf{cost}(1,n,i)$$

The total number of subproblems is $O(n^3)$ since we have one for each triple $1\le a\le i\le b\le n$, and the cost of each subproblem is $O(n)$ since we have to do a min over $a,\dots, b$. So the total cost is $O(n^4)$, which is pretty bad for a parsing algorithm but still polynomial time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.