« first day (2474 days earlier)   

4:59 PM
1
Q: Flaw with Knuth original attribute grammar paper

Node.JSKnuth'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
Q: Maximum-minimum-satisfiability

Erel Segal-HaleviIn 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_{...

 

« first day (2474 days earlier)