Fundamentals of Computation Theory

The papers in this volume were presented at the 14th Symposium on Fun- mentals of Computation Theory. The symposium was established in 1977 as a biennial event for researchers interested in all aspects of theoretical computer science, in particular in al- rithms, complexity, and formal and logical methods. The previous FCT con- rences were held in the following cities: Poznan ' (Poland, 1977), Wendisch-Rietz (Germany, 1979), Szeged (Hungary, 1981), Borgholm (Sweden, 1983), Cottbus (Germany, 1985), Kazan (Russia, 1987), Szeged (Hungary, 1989), Gosen-Berlin (Germany, 1991), Szeged (Hungary, 1993), Dresden (Germany, 1995), Krak' ow (Poland, 1997), Iasi (Romania, 1999), and Riga (Latvia, 2001). The FCT conferences are coordinated by the FCT steering committee, which consistsofB.Chlebus(Denver/Warsaw),Z.Esik(Szeged),M.Karpinski(Bonn), A. Lingas (Lund), M. Santha (Paris), E. Upfal (Providence), and I. Wegener (Dortmund).The call for papers sought contributions on original research in all aspects of theoretical computer science including design and analysis of algorithms, abstract data types, approximation algorithms, automata and formal lang- ges, categorical and topological approaches, circuits, computational and str- turalcomplexity,circuitandprooftheory,computationalbiology,computational geometry, computer systems theory, concurrency theory, cryptography, domain theory, distributed algorithms and computation, molecular computation, qu- tum computation and information, granular computation, probabilistic com- tation, learning theory, rewriting, semantics, logicin computer science, speci?- tion, transformation and veri?cation, and algebraic aspects of computer science. There were 73 papers submitted, of which the majority were very good.