Friday, September 12, 2008


“Hamiltonian graphs cannot be expressed in existential monadic second order logic because palindromes are not a regular language.”

Apparently, Keith Ellul immediately realized that without MONADIC the statement is false, because it is “trivial” to see that hamiltonian graphs can be expressed in existential second order logic.

I can't wait to tell the guys at the pub.