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

<h2>Quote:</h2>

<p>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).</p>

<hr>

<p>Can this be used for restricted read twice BDDs (Binary Decision Diagram)?</p>

<p>Consider BDD where every variables occurs twice and the order of all paths root->T is restricted to:</p>

<p>1 .. n n .. 1 (this is palindrome)</p>

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

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

<p>Looks like CFG constraint can help to find "consistent" paths.</p>

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

<p>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.</p>

<p>Is this correct (computer experiments suggest it is)?</p>

<p>A different grammar may give different restriction.</p>

<p>Is this published somewhere?</p>

<p>To my humble knowledge this is one of the very few examples of read twice BDD supporting poly-time SAT query.</p>

<p>EDIT: The problem I am trying to solve is to find types of read twice BDDs which allow polytime SAT query with the help of CFGs. The above construction gives example for the case when the order of the variables is restricted to a palindrome, hence the (possibly incorrect)  description "restricted" (because of the restriction of the order). I am not familiar with CFGs.</p>

<p>Discussion about an extension (almost sure impossible) of this <a href="https://math.stackexchange.com/questions/14311/can-a-polynomial-size-cfg-over-large-alphabet-describe-a-language-where-each-ter">at math.SE</a></p>

<p>Example: Simple read twice BDD on x,y. The concatenation of edge labels give the palindrome word: "+x -y -y +x"</p>

<p><img src="https://ll0x.wdfiles.com/local--files/admin%3Amanage/aa.png" alt="bdd"></p>

<p>Thank you.</p>

<p>[1]
<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.446&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">FORMAL-LANGUAGE-CONSTRAINED PATH PROBLEMS∗ CHRIS BARRETT† , RIKO JACOB‡ , AND MADHAV MARATHE†</a></p>

CC BY-SA 2.5
2010-12-23T08:19:06.833Z
Also [cross-posted](http://math.stackexchange.com/questions/14506/restricted-read-twice-bdds-and-context-free-grammars) on Math.SE. Please add a link to the other copies when cross-posting.
Kaveh
CC BY-SA 2.5
2010-12-23T20:25:09.333Z
Please define the problem you are trying to solve. For example what is a "restricted read twice BDD"?
Warren Schudy
CC BY-SA 2.5
2010-12-23T20:40:31.327Z
Also cross-posted on mathoverflow: http://mathoverflow.net/questions/48568/restricted-read-twice-ibdds-and-context-free-grammars
Warren Schudy
CC BY-SA 2.5
2010-12-28T12:47:25.027Z
EDIT: The problem I am trying to solve is to find types of read twice BDDs which allow polytime SAT query with the help of CFGs. The above construction gives example for the case when the order of the variables is restricted to a palindrome, hence the (possibly incorrect) description "restricted" (because of the restriction of the order). I am not familiar with CFGs.
Leon Leon
CC BY-SA 2.5
2010-12-28T16:37:02.463Z
By the, I will prefer the discussion to be on MATH.SE. The moderators there **practice the art of moderation better...**
Leon Leon
CC BY-SA 2.5
2010-12-29T04:43:19.060Z
Leon, the target communities on Math.SE and this site are quite different and therefore the expectations from OP are also different. This site's current policy discourages simultaneous cross-posting. It is expected that OP include links to the other copies when cross-posting and also define the terms used in the question or provide links to such definitions, and we have kindly asked you to do this. You can start a meta-discussion if there have a specific point about the policies or moderation. Note that no one is forcing you to post your questions here and we are not moderators but just users.
Kaveh
CC BY-SA 2.5
2010-12-29T11:17:35.527Z
Thank you. Have I missed other definitions? I don't feel like commenting on meta.
Leon Leon
CC BY-SA 2.5
2010-12-29T12:50:58.103Z
Can't give example via editing because of spam prevention. Example: Simple read twice BDD on x,y. The concatenation of edge labels give the palindrome word: "+x -y -y +x" The graph is at: http://imagebin.org/index.php?mode=image&id=130052
Leon Leon
CC BY-SA 2.5
2010-12-29T12:52:20.507Z
For reasons beyond my understanding, the imagebin.org link needs copy/paste to see the graph.
Leon Leon
<graph-theory><reference-request><graph-algorithms><fl.formal-languages><grammars>
Restricted read twice BDDs and context free grammars
Leon Leon
# Restricted read twice BDDs and context free grammars

(Asked by: username_0 on 2010-12-22)

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 BDDs (Binary Decision Diagram)?

Consider BDD where every variables occurs twice and the order of all paths root->T 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 (computer experiments suggest it is)?

A different grammar may give different restriction.

Is this published somewhere?

To my humble knowledge this is one of the very few examples of read twice BDD supporting poly-time SAT query.

EDIT: The problem I am trying to solve is to find types of read twice BDDs which allow polytime SAT query with the help of CFGs. The above construction gives example for the case when the order of the variables is restricted to a palindrome, hence the (possibly incorrect) description "restricted" (because of the restriction of the order). I am not familiar with CFGs.

Discussion about an extension (almost sure impossible) of this [at math.SE](https://math.stackexchange.com/questions/14311/can-a-polynomial-size-cfg-over-large-alphabet-describe-a-language-where-each-ter)

Example: Simple read twice BDD on x,y. The concatenation of edge labels give the palindrome word: "+x -y -y +x"

![bdd](https://ll0x.wdfiles.com/local--files/admin%3Amanage/aa.png)

Thank you.

[1]
[FORMAL-LANGUAGE-CONSTRAINED PATH PROBLEMS∗ CHRIS BARRETT† , RIKO JACOB‡ , AND MADHAV MARATHE†](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.446&rep=rep1&type=pdf)

**Tags:** graph-theory, reference-request, graph-algorithms, fl.formal-languages, grammars
> **Comments:**
> **username_1**: Also [cross-posted](http://math.stackexchange.com/questions/14506/restricted-read-twice-bdds-and-context-free-grammars) on Math.SE. Please add a link to the other copies when cross-posting.  
> **username_2**: Please define the problem you are trying to solve. For example what is a "restricted read twice BDD"?  
> **username_2**: Also cross-posted on mathoverflow: http://mathoverflow.net/questions/48568/restricted-read-twice-ibdds-and-context-free-grammars  
> **username_0**: EDIT: The problem I am trying to solve is to find types of read twice BDDs which allow polytime SAT query with the help of CFGs. The above construction gives example for the case when the order of the variables is restricted to a palindrome, hence the (possibly incorrect) description "restricted" (because of the restriction of the order). I am not familiar with CFGs.  
> **username_0**: By the, I will prefer the discussion to be on MATH.SE. The moderators there **practice the art of moderation better...**  
> **username_1**: Leon, the target communities on Math.SE and this site are quite different and therefore the expectations from OP are also different. This site's current policy discourages simultaneous cross-posting. It is expected that OP include links to the other copies when cross-posting and also define the terms used in the question or provide links to such definitions, and we have kindly asked you to do this. You can start a meta-discussion if there have a specific point about the policies or moderation. Note that no one is forcing you to post your questions here and we are not moderators but just users.  
> **username_0**: Thank you. Have I missed other definitions? I don't feel like commenting on meta.  
> **username_0**: Can't give example via editing because of spam prevention. Example: Simple read twice BDD on x,y. The concatenation of edge labels give the palindrome word: "+x -y -y +x" The graph is at: http://imagebin.org/index.php?mode=image&id=130052  
> **username_0**: For reasons beyond my understanding, the imagebin.org link needs copy/paste to see the graph.  

---

## 0 answers

