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

Towards Axiomatic Basis of Inductive Inference....Pages 1-13
Approximation Algorithms for Fractional Covering and Packing Problems, and Applications....Pages 14-14
Challenges of Commutation....Pages 15-23
Approximating Bounded Degree Instances of NP-Hard Problems....Pages 24-34
Universal Algebra and Computer Science....Pages 35-44
Quantum Algorithms....Pages 45-46
A Discrete Approximation and Communication Complexity Approach to the Superposition Problem....Pages 47-58
On Computational Power of Quantum Branching Programs....Pages 59-70
Efficient Computation of Singular Moduli with Application in Cryptography....Pages 71-82
Ambainis-Freivalds’ Algorithm for Measure-Once Automata....Pages 83-93
Are There Essentially Incomplete Knowledge Representation Systems?....Pages 94-105
Best Increments for the Average Case of Shellsort....Pages 106-117
Approximating Minimum Cocolourings....Pages 118-125
Curved Edge Routing....Pages 126-137
Time/Space Efficient Compressed Pattern Matching....Pages 138-149
Modelling Change with the Aid of Knowledge and Time....Pages 150-161
If P ≠ NP then Some Strongly Noninvertible Functions Are Invertible....Pages 162-171
Prediction-Preserving Reducibility with Membership Queries on Formal Languages....Pages 172-183
Dense Families and Key Functions of Database Relation Instances....Pages 184-192
On the Complexity of Decidable Cases of Commutation Problem for Languages....Pages 193-203
Cones, Semi-AFPs, and AFPs of Algebraic Power Series....Pages 204-216
New Small Universal Circular Post Machines....Pages 217-226
Divisibility Monoids: Presentation, Word Problem, and Rational Languages....Pages 227-239
Concurrency in Timed Automata....Pages 240-251
How Powerful Are Infinite Time Machines?....Pages 252-263
Equivalence Problem of Composite Class Diagrams....Pages 264-274
Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2....Pages 275-286
On the Category of Event Structures with Dense Time....Pages 287-298
Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions....Pages 299-310
Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case....Pages 311-322
Relating Automata-Theoretic Hierarchies to Complexity-Theoretic Hierarchies....Pages 323-334
Polynomial Time Algorithms for Finding Unordered Tree Patterns with Internal Variables....Pages 335-346
Piecewise and Local Threshold Testability of DFA....Pages 347-358
Compositional Homomorphisms of Relational Structures....Pages 359-371
Representation of Autonomous Automata....Pages 372-375
Quantum Reversibility and a New Model of Quantum Automaton....Pages 376-379
Space-Efficient 1.5-Way Quantum Turing Machine....Pages 380-383
A Combinatorial Aggregation Algorithm for Stationary Distribution of a Large Markov Chain....Pages 384-387
A Primitive for Proving the Security of Every Bit and about Universal Hash Functions & Hard Core Bits....Pages 388-391
Pythagorean Triples in Unification Theory of Nilpotent Rings....Pages 392-395
Two-States Bilinear Intrinsically Universal Cellular Automata....Pages 396-399
Linear Time Recognizer for Subsets of ℤ 2 ....Pages 400-403
Fuzzy Sets and Algorithms of Distributed Task Allocation for Cooperative Agents....Pages 404-407
On Recursively Enumerable Subsets of N and Rees Matrix Semigroups over (Z 3 ; + )....Pages 408-411
Quantum Real - Time Turing Machine....Pages 412-415
Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control....Pages 416-419
Linear Automata and Recognizable Subsets in Free Semirings....Pages 420-423
On Logical Method for Counting Dedekind Numbers....Pages 424-427
A General Method for Graph Isomorphism....Pages 428-431
Designing PTASs for MIN-SUM Scheduling Problems....Pages 432-444
On Robust Algorithms for the Maximum Weight Stable Set Problem....Pages 445-458
Multicasting in Optical Networks....Pages 459-460
Structured Randomized Rounding and Coloring....Pages 461-471
Optimal Online Flow Time with Resource Augmentation....Pages 472-482
New Results for Path Problems in Generalized Stars, Complete Graphs, and Brick Wall Graphs....Pages 483-494
On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks....Pages 495-507
Approximation Algorithms for Time-Dependent Orienteering....Pages 508-515
On Complexity of Colouring Mixed Hypertrees....Pages 516-524
Combining Arithmetic and Geometric Rounding Techniques for Knapsack Problems....Pages 525-534
The Complexity of Maximum Matroid-Greedoid Intersection....Pages 535-539