Synopsis:
This volume is dedicated to the 15th Symposium on Fundamentals of Com- tation Theory FCT 2005, held in Lu ¨beck, Germany, on August 17-20, 2005. The FCT symposium was established in 1977 as a biennial event for - searchers interested in all aspects of theoretical computer science, in particular in algorithms, complexity, and formal and logical methods. The previous FCT conferences were held in the following places: 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), Riga (Latvia, 2001) and Malmo ¨ (Sweden, 2003). The FCT conference seriesis coordinatedby a steering comm- tee. Its current members are B. 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 for FCT 2005 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 languages, categorical and topological approaches, circuits, computational and structural complexity, circuit and proof theory, computational biology, com- tational geometry, computer systems theory, concurrency theory, cryptography, domain theory, distributed algorithms and computation, molecular computation, quantumcomputation and information, granular computation, probabilistic c- putation, learning theory, rewriting, semantics, logic in computer science, spe- ?cation, transformation and veri?cation, and algebraic aspects of computer s- ence.
Synopsis:
This book constitutes the refereed proceedings of the 15th International Symposium Fundamentals of Computation Theory, FCT 2005, held in Lubeck, Germany in August 2005. The 46 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 105 submissions. The papers are organized in topical sections on circuits, automata, complexity, approximability, computational and structural complexity, graphs and complexity, computational game theory, visual cryptography and computational geometry, query complexity, distributed systems, automata and formal languages, semantics, approximation algorithms, average case complexity, algorithms, graph algorithms, and pattern matching.
"About this title" may belong to another edition of this title.
