## Restricted read twice IBDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1]

## Quote:

Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal language L ⊆ Σ∗ , the formal-language-constrained shortest/simple path problem con- sists of finding a shortest (simple) path p in G complying with the additional constraint that l(p) ∈ L. Here l(p) denotes the unique word obtained by concatenating the Σ-labels of the edges along the path p. (1) We show that the formal-language-constrained shortest path problem is solvable efficiently in polynomial time when L is restricted to be a context-free language (CFL).

Can this be used for restricted read twice IBDDs (Indexed Binary Decision Diagram)?

Consider IBBD where every variables occurs twice and the order is restricted to:

1 .. n n .. 1 (this is palindrome)

Treat the BDD as edge labelled digraph where the true edge of variable is labelled as +variable and the false edge as -variable.

Some paths in the digraph are "BDD inconsistent" - if a variable takes both values.

Looks like CFG constraint can help to find "consistent" paths.

It is possible to construct CFG that accepts all palindromes and only palindromes (over the alphabet U {+variable,-variable}.

Finding a path from the root to "true" constrained by the above CFG will give a consistent satisfying assignment - the first half of the path is correct because a variable occurs only once and the second part is the reverse.

Is this correct?

Is this published somewhere?

Thank you.

[1] FORMAL-LANGUAGE-CONSTRAINED PATH PROBLEMS∗ CHRIS BARRETT† , RIKO JACOB‡ , AND MADHAV MARATHE†

-
 Cross-posted on CS-theory: cstheory.stackexchange.com/questions/3940/… – Warren Schudy Dec 23 2010 at 20:41