Also, I have recently discovered a nice-looking online textbook on 'universal algebra'. I haven't read it yet, though. But, it has some nice applications to computer science (automata theory, rewriting systems, etc.) and model theory. If you are a complexity theorist, a motivation to look at this book may be Straubing's monograph
Finite Automata, Formal Logic, and Circuit Complexity (Progress in Theoretical Computer Science), Springer, 1994.
In this monograph, Straubing demonstrates the possibility of attacking tantalizing open problems in circuit complexity using automata theory, semigroup theory, and finite model theory. In fact, I have heard a rumour that Straubing very recently proved a separation result in complexity theory using this technique ...
5 comments:
Visit? Regularly? That's what RSS aggregators are for.
Awesome! Thanks for letting me know. [I am always behind when it comes to this sort of things :-)]
Thanks for adding me. Also thanks for the pointer to the Straubing article. Reminds me of a post I've had in the back of my head for a while...
Anthony, thanks for the link. This is a great blog you've got. If I had started reading this before beginning my own blog, it would have sped up my learning curve considerably. Somehow this never came up in any of my Google searches--I guess I always forgot to put "descriptive" in front of the word "complexity".
I've had a copy of Neil Immerman's Descriptive Complexity text on my bookshelf for a long time, but haven't had a chance to start digesting it yet. Maybe your blog will help motivate me and get me up to speed on the basics...
Kurt: thanks for your kind words. I certainly hope that my blog will be helpful for people who are interested in logic and complexity, especially those wish to learn finite model theory and descriptive complexity.
Somehow this never came up in any of my Google searches
I don't know. Maybe because I have just recently started this blog ...
Post a Comment