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†
