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

Jānis Bārzdiņš, Rūsiņš Freivalds, Carl H. Smith (auth.), Rūsiņš Freivalds (eds.)3540424873, 9783540424871

This book 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, etc.

---

Table of contents :
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