LARA

Lecture 19

(Presented by Ruzica Piskac.)

Push-down automata

Equivalence of push-down automata and context-free grammars.

Intersection of a regular and context-free language.

First-order theorem provers

Completeness of propositional resolution.

Undecidability of first-order logic.

Completeness of first-order resolution.

Slides: