## Mathematical Foundations of Computer Science 2004: 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, ProceedingsThis 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Invited Lectures | 1 |

Problems and Techniques | 25 |

Polynomial Time Approximation Schemes | 28 |

Copyright | |

46 other sections not shown

### Other editions - View all

### Common terms and phrases

1-random Abelian group algebraic ambient approximation algorithm assignment automaton boolean boolean circuit c.e. reals cell cellular automata circuit clauses coloring Computer Science configuration consider constant constraint construction Corollary corresponding defined definition denote disk graphs dominating set Downey edges enumerable equivalent exists finite fixed-parameter fixed-parameter tractable formula function gadget gate given graph G Hence Hirschfeldt independent set infinite input integer isomorphic Kolmogorov complexity labeled languages Lemma LNCS logic lower bounds mapping monoid nodes notion NP-complete NP-hard obtain operations optimal oracle output parameter parameterized complexity path planar graphs polynomial polynomial-time port precolored problem Proc proof of Theorem prove PSPACE PSPACE-complete recognizable reduction restricted robot satisfying Schnorr sequence Solovay Springer Springer-Verlag standard verifier string structure subcircuit subgraph subset systems of equations theory tree treewidth Turing unit disk graphs upper bound variables vertex cover vertices zero-knowledge zero-knowledge proof