4:59 PM
1

Knuth's original attribute grammar paper (title: Semantics of Context-Free Languages) apparently had a flaw where circularity is always detected but some noncircular AGs may be reported to be circular. Knuth later constructed an exact algorithm which is exponential in time. I am wondering what wa...

1 hour later…
6:15 PM
2

In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\in\{1,\ldots,n\}$ such that, for some assignment, some $k$ clauses \$c_{i1},\ldots,c_{...