Fundamentals of Computation Theory: 13th International Symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings

ISBN-13: 9783540424871 / Angielski / Miękka / 2001 / 550 str.

Rusins Freivalds

Opis

This volume constitutes the refereed proceedings of the 13th International Symposium Fundamentals of Computation Theory, FCT 2001, as well as of the International Workshop on Efficient Algorithms, WEA 2001, held in Riga, Latvia, in August 2001. The 28 revised full FCT papers and 15 short papers presented together with six invited contributions and 8 revised full WEA papers as well as three invited WEA contributions have been carefully reviewed and selected. Among the topics addressed are a broad variety of topics from theoretical computer science, algorithmics and programming theory. The WEA papers deal with graph and network algorithms, flow and routing problems, scheduling and approximation algorithms.

Spis treści

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 Complexity of Colouring Mixed Hypertrees.- Combining Arithmetic and Geometric Rounding Techniques for Knapsack Problems.- The Complexity of Maximum Matroid-Greedoid Intersection.