Professor Sleator

5/19/2006 7:49:10 AM

Professor Sleator

I was doing a search on persistent data structures, and came across this paper by CMU Professor Daniel Sleator in the late 1980s. I have encountered his name so often in the course of my work, I wondered if we shared similar interests.

Daniel Sleator coinvented the splay tree data structure, which I have used quite often. He arrived at the startling conclusion that just by rebalancing the most recently accessed node, one can obtain amortized logarithmic behavior for most operations. Sleator also founded the Internet Chess Club, the most popular chess site on the Internet and one which I was once a member of. 

Most importantly, for me, he codeveloped the link grammar parser that I used as the starting point for my own natural language parser. Link grammars are based on semantic relationships between words versus syntactical grouping of phrases. Sleator’s algorithm for parsing English text is very elegant. The open-source wordprocessor, Abiword, reportedly uses the parser for grammar checking.

One of my proudest accomplishments is having noticed an optimization that he missed and coming up with an entirely different simpler, faster, and more general parsing algorithm. I wonder if I should make it public. 

Anyway, great minds think alike…







Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media