“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.
No comments:
Post a Comment