Fundamentals of Computation Theory

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