This book constitutes the refereed proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, MFCS 2006, held in Star? Lesn?, Slovakia in August/September 2006.

The 62 revised full papers presented together with the full papers or abstracts of 7 invited talks were carefully reviewed and selected from 174 submissions. All current aspects in theoretical computer science and its mathematical foundations are addressed, ranging from algorithms and data structures, to complexity, automata, semantics, logic, formal specifications, models of computation, concurrency theory, computational geometry, parallel and distributed computing, networks, bioinformatics, quantum computing, cryptography, knowledge-based systems, and artificial intelligence.