## A Class of Graph Properties Computable in Linear Time

A cool theorem.

Ron Fagin is a great theorist who has made many important contributions to diverse aspects of computing. He is perhaps most famous for his brilliant categorization of polynomial time by second order logic—Fagin’s Theorem.

Today I plan on talking about a related theorem—Courcelle’s—proved in 1990. Yet the theorem is not, in my opinion, as well known as it should be. The truth is I did not know this pretty theorem until I ran across it the other day. So perhaps everyone else knows Courcelle’s result except for me. Oh well.

View original post 940 more words

Advertisements

## Leave a Reply