This book constitutes the refereed proceedings of the Fourth International Computer Science Symposium in Russia, CSR 2009, held in Novosibirsk, Russia, August 18-23, 2009. The 29 revised papers presented together with 4 invited papers were carefully reviewed and selected from 66 submissions. All major areas in computer science are addressed. The theory track deals with algorithms, protocols, and data structures; complexity and cryptography; formal languages, automata and their applications to computer science; computational models and concepts; proof theory and applications of logic to computer science.