Mathematical Foundations of Computer Science 2004

This book constitutes the refereed proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science, MFCS 2004, held in Prague, Czech Republic in August 2004. The 60 revised full papers presented together with full papers or abstracts of 10 invited talks were carefully reviewed and selected from 167 submissions. The papers are organised in topical sections on graph algorithms, approximation, graphs and complexity, circuits, general complexity, automata, parameterized and kolmogrov complexity, semantics, scheduling, algebraic theory of languages, games, languages, geometry, languages and complexity, quantum computing, and XML.