Fundamentals of Computation Theory

ThesymposiaonFundamentalsofComputationTheoryareheldeverytwoyears. Following the tradition established at the ?rst FCT 1977, the conference brings together specialists in theoretical ?elds of Computer Science from various co- tries and stimulates mathematical research in theoretical computer science. - pics of interest for the satellite workshop onE?cientAlgorithms WEA2001 are: computational complexity, graph and network algorithms, ?ow and routing - gorithms,coloringandpartitioning,cutsandconnectivity,packingandcovering, scheduling algorithms, approximation algorithms, inapproximability results, - line problems, randomized algorithms, integer programming, semide?nite p- gramming, algorithmic geometry, polyhedral combinatorics, branch and bound algorithms, cutting plane algorithms, and various applications. The 13th FCT was held in Riga-Lielupe, August 22-24, 2001 with an - ditional day (August 25) for the satellite workshop WEA2001. The previous meetings were held in the following cities: Poznan-K ornik, Poland, 1977 Wendish-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 Thisyearthenumberofsubmittedpaperswashigh.TheProgramCommittee decided to accept 28 submissions as regular papers and 15 submissions as short papers. Additionally, the Program Committee of WEA2001 accepted 8 papers.

Includes supplementary material: sn.pub/extras

Inhalt
Invited Papers.- Towards Axiomatic Basis of Inductive Inference.- Approximation Algorithms for Fractional Covering and Packing Problems, and Applications.- Challenges of Commutation.- Approximating Bounded Degree Instances of NP-Hard Problems.- Universal Algebra and Computer Science.- Quantum Algorithms.- Regular Papers.- A Discrete Approximation and Communication Complexity Approach to the Superposition Problem.- On Computational Power of Quantum Branching Programs.- Efficient Computation of Singular Moduli with Application in Cryptography.- Ambainis-Freivalds' Algorithm for Measure-Once Automata.- Are There Essentially Incomplete Knowledge Representation Systems?.- Best Increments for the Average Case of Shellsort.- Approximating Minimum Cocolourings.- Curved Edge Routing.- Time/Space Efficient Compressed Pattern Matching.- Modelling Change with the Aid of Knowledge and Time.- If P ? NP then Some Strongly Noninvertible Functions Are Invertible.- Prediction-Preserving Reducibility with Membership Queries on Formal Languages.- Dense Families and Key Functions of Database Relation Instances.- On the Complexity of Decidable Cases of Commutation Problem for Languages.- Cones, Semi-AFPs, and AFPs of Algebraic Power Series.- New Small Universal Circular Post Machines.- Divisibility Monoids: Presentation, Word Problem, and Rational Languages.- Concurrency in Timed Automata.- How Powerful Are Infinite Time Machines?.- Equivalence Problem of Composite Class Diagrams.- Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2.- On the Category of Event Structures with Dense Time.- Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions.- Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case.-Relating Automata-Theoretic Hierarchies to Complexity-Theoretic Hierarchies.- Polynomial Time Algorithms for Finding Unordered Tree Patterns with Internal Variables.- Piecewise and Local Threshold Testability of DFA.- Compositional Homomorphisms of Relational Structures.- Short Papers.- Representation of Autonomous Automata.- Quantum Reversibility and a New Model of Quantum Automaton.- Space-Efficient 1.5-Way Quantum Turing Machine.- A Combinatorial Aggregation Algorithm for Stationary Distribution of a Large Markov Chain.- A Primitive for Proving the Security of Every Bit and about Universal Hash Functions & Hard Core Bits.- Pythagorean Triples in Unification Theory of Nilpotent Rings.- Two-States Bilinear Intrinsically Universal Cellular Automata.- Linear Time Recognizer for Subsets of ?2.- Fuzzy Sets and Algorithms of Distributed Task Allocation for Cooperative Agents.- On Recursively Enumerable Subsets of N and Rees Matrix Semigroups over (Z3 ; + ).- Quantum Real - Time Turing Machine.- Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control.- Linear Automata and Recognizable Subsets in Free Semirings.- On Logical Method for Counting Dedekind Numbers.- A General Method for Graph Isomorphism.- WEA Invited Papers.- Designing PTASs for MIN-SUM Scheduling Problems.- On Robust Algorithms for the Maximum Weight Stable Set Problem.- Multicasting in Optical Networks.- WEA Regular Papers.- Structured Randomized Rounding and Coloring.- Optimal Online Flow Time with Resource Augmentation.- New Results for Path Problems in Generalized Stars, Complete Graphs, and Brick Wall Graphs.- On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks.- Approximation Algorithms for Time-Dependent Orienteering.- On Complexityof Colouring Mixed Hypertrees.- Combining Arithmetic and Geometric Rounding Techniques for Knapsack Problems.- The Complexity of Maximum Matroid-Greedoid Intersection.