<p>here is a similar/ more recent ref (2014) using the technique on probabilistic CFGs. (but they seem to skip over details of the SAT solver...?)</p>

<p><a href="http://jmlr.csail.mit.edu/proceedings/papers/v34/scicluna14a.pdf" rel="nofollow">Grammatical Inference of some Probabilistic Context-Free Grammars from Positive Data using Minimum Satisfiability</a> / Scicluna, Higuera</p>

<blockquote>
  <p>Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning (Clark, 2010b). However, these results are still not extended to probabilistic grammars. In this work, we give a practical algorithm, with some proven properties, that learns a subclass of probabilistic grammars from positive data. A minimum satisfiability solver is used to direct the search towards small grammars. Experiments on typical context-free languages and artificial natural language grammars give positive results.</p>
</blockquote>

CC BY-SA 3.0
2015-03-12T02:18:22.117Z
2015-03-12T02:18:22.117Z
vzn
<p>(I guess the important word in the original question is ``published''.)  There is such an encoding of context-free parsing (more exactly of CYK-style parsing) in  Roland Axelsson, Keijo Heljanko, and Martin Lange, <em>Analyzing Context-Free Grammars Using an Incremental SAT Solver</em>, ICALP 2008, Lecture Notes in Computer Science vol. 5126, pp. 410--422, <a href="http://dx.doi.org/10.1007/978-3-540-70583-3_34">doi:10.1007/978-3-540-70583-3_34</a>.  They use it in particular to detect ambiguity of words $w$ in context-free grammars for growing word lengths.</p>

CC BY-SA 3.0
2015-03-06T10:16:43.203Z
2015-03-06T10:16:43.203Z
Sylvain
<p>Is there a published algorithm for translating a context-free parsing problem into SAT? That is, an algorithm that translates a context-free grammar and an input string into a set clauses that is satisfiable iff the input string is well-formed according to the grammar.</p>

CC BY-SA 3.0
2015-03-06T07:22:08.590Z
I do not know. There is a somewhat related translation of a CFG Ginto a Presburger formula for the Parikh image of L(G) in Theorem 4 o:f Kumar Neeraj Verma, Helmut Seidl, Thomas Schwentick: On the Complexity of Equational Horn Clauses. CADE 2005:337-352 (DOI:10.1007/11532231_25)
Thomas S
<fl.formal-languages><sat>
Translation of context-free parsing into SAT
Atamiri
# Translation of context-free parsing into SAT

(Asked by: username_0 on 2015-03-05)

Is there a published algorithm for translating a context-free parsing problem into SAT? That is, an algorithm that translates a context-free grammar and an input string into a set clauses that is satisfiable iff the input string is well-formed according to the grammar.

**Tags:** fl.formal-languages, sat

> **Comments:**
> **username_1**: I do not know. There is a somewhat related translation of a CFG Ginto a Presburger formula for the Parikh image of L(G) in Theorem 4 o:f Kumar Neeraj Verma, Helmut Seidl, username_1chwentick: On the Complexity of Equational Horn Clauses. CADE 2005:337-352 (DOI:10.1007/11532231_25)  

---

## 2 answers

### Answer by username_3 on 2015-03-06. Score: 13 | Accepted answer

(I guess the important word in the original question is ``published''.) There is such an encoding of context-free parsing (more exactly of CYK-style parsing) in Roland Axelsson, Keijo Heljanko, and Martin Lange, *Analyzing Context-Free Grammars Using an Incremental SAT Solver*, ICALP 2008, Lecture Notes in Computer Science vol. 5126, pp. 410--422, [doi:10.1007/978-3-540-70583-3\_34](http://dx.doi.org/10.1007/978-3-540-70583-3_34). They use it in particular to detect ambiguity of words $w$ in context-free grammars for growing word lengths.


---

### Answer by username_2 on 2015-03-12. Score: 0

here is a similar/ more recent ref (2014) using the technique on probabilistic CFGs. (but they seem to skip over details of the SAT solver...?)

[Grammatical Inference of some Probabilistic Context-Free Grammars from Positive Data using Minimum Satisfiability](http://jmlr.csail.mit.edu/proceedings/papers/v34/scicluna14a.pdf) / Scicluna, Higuera

> Recently, different theoretical learning results have been found for a variety of context-free grammar subclasses through the use of distributional learning (Clark, 2010b). However, these results are still not extended to probabilistic grammars. In this work, we give a practical algorithm, with some proven properties, that learns a subclass of probabilistic grammars from positive data. A minimum satisfiability solver is used to direct the search towards small grammars. Experiments on typical context-free languages and artificial natural language grammars give positive results.


---

