Fundamentals of Computation Theory 13th International Symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings /
| Corporate Author: | |
|---|---|
| Other Authors: | |
| Format: | Electronic eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg :
Springer Berlin Heidelberg : Imprint: Springer,
2001.
|
| Edition: | 1st ed. 2001. |
| Series: | Lecture Notes in Computer Science,
2138 |
| Subjects: | |
| Online Access: | Full Text via HEAL-Link |
Table of Contents:
- 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.
