4 ms·

I feel like if you want a good introductory theory text you need to focus less on everything up to (and including) decidability and get as quickly as you can to

by j2kun 13y ago

I feel like if you want a good introductory theory text you need to focus less on everything up to (and including) decidability and get as quickly as you can to complexity theory. There are certainly a few central milestones, but to spend 200 pages and only get to P/NP seems like a crime. There are so many other topics to whet one's appetite for theoretical computer science! Then again, this text appears to have been written for the kind of readers who have never written a proof before. So I expect this would fill a semester of puzzling over the minute details of the pumping lemma and various closure properties (but again, to what end?).

csense 13y ago
I disagree. Automata theory has important practical applications -- most string processing turns out to be finite automata (hence regular expressions), and push-down automata are very important to understand if you're writing a compiler.
- j2kun 13y ago
  You disagree with what? I never said anything about practical applications. And you'd better bet that complexity theory (and the world of topics that basic familiarity with complexity theory opens) has more important applications. Cryptography, combinatorial optimization, approximation algorithms, communication complexity, machine learning theory, need I go on? All I'm saying is that automata theory doesn't give the glimpse into theoretical computer science that every "introductory theory" textbook ought to.
mindcrime 13y ago
but again, to what end? Not everybody is coming from the same place. I was just looking for a freely available text that covered automata stuff, so I could brush up on a few things that I ran across reading an AI book. This one caught my eye as being both very recent and licensed under a CC license, which is a sweet spot to me. Is it the best possible book for some particular class, or for any particular student? Who's to say? But I reckon a few HN users might find this useful.
gone35 13y ago
I see your point but, from my limited experience, I've found the material on decidability crucial to get a good working grasp of many of the core abstractions central to both complexity theory and theory of computation in general such as languages, non-constructive proofs, reductions, etc. I feel that without such exposure, it would be hard for a newcomer to appreciate the subtleties of the discipline... Big fan of your math \cap programming series, by the way. Keep it up.
3rd3 13y ago
There are quite a few important insights along the way: http://cstheory.stackexchange.com/questions/14811/what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata http://cstheory.stackexchange.com/questions/14811/what-is-th...
- j2kun 13y ago
  I think very few of these are actually revealed in such an introductory course, and you can gain the same insights from other topics in complexity theory (for example PSPACE = NPSPACE).
mabbo 13y ago
The authors are two of my favorite profs from undergrad. The curriculum at the time had some problems. This book is written for a course that helps fix some of those problems. So yes, this is written for people who have never written a proof before-undergrads in first or second year.

by j2kun 13y ago

csense 13y ago

I disagree. Automata theory has important practical applications -- most string processing turns out to be finite automata (hence regular expressions), and push-down automata are very important to understand if you're writing a compiler.

j2kun 13y ago
You disagree with what? I never said anything about practical applications. And you'd better bet that complexity theory (and the world of topics that basic familiarity with complexity theory opens) has more important applications. Cryptography, combinatorial optimization, approximation algorithms, communication complexity, machine learning theory, need I go on? All I'm saying is that automata theory doesn't give the glimpse into theoretical computer science that every "introductory theory" textbook ought to.

mindcrime 13y ago

but again, to what end? Not everybody is coming from the same place. I was just looking for a freely available text that covered automata stuff, so I could brush up on a few things that I ran across reading an AI book. This one caught my eye as being both very recent and licensed under a CC license, which is a sweet spot to me. Is it the best possible book for some particular class, or for any particular student? Who's to say? But I reckon a few HN users might find this useful.

gone35 13y ago

I see your point but, from my limited experience, I've found the material on decidability crucial to get a good working grasp of many of the core abstractions central to both complexity theory and theory of computation in general such as languages, non-constructive proofs, reductions, etc. I feel that without such exposure, it would be hard for a newcomer to appreciate the subtleties of the discipline... Big fan of your math \cap programming series, by the way. Keep it up.

3rd3 13y ago

There are quite a few important insights along the way: http://cstheory.stackexchange.com/questions/14811/what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata http://cstheory.stackexchange.com/questions/14811/what-is-th...

j2kun 13y ago
I think very few of these are actually revealed in such an introductory course, and you can gain the same insights from other topics in complexity theory (for example PSPACE = NPSPACE).

mabbo 13y ago

The authors are two of my favorite profs from undergrad. The curriculum at the time had some problems. This book is written for a course that helps fix some of those problems. So yes, this is written for people who have never written a proof before-undergrads in first or second year.