Front matter
1-13
Towards Axiomatic Basis of Inductive Inference
Jānis Bārzdiņš, Rūsiņš Freivalds and Carl H. Smith
14
Approximation Algorithms for Fractional Covering and Packing Problems, and Applications
Klaus Jansen
15-23
Challenges of Commutation
An Advertisement
Juhani Karhumäki
24-34
Approximating Bounded Degree Instances of NP-Hard Problems
Marek Karpinski
35-44
Universal Algebra and Computer Science
Boris Plotkin and Tanya Plotkin
45-46
Quantum Algorithms
Umesh Vazirani
47-58
A Discrete Approximation and Communication Complexity Approach to the Superposition Problem
Farid Ablayev and Svetlana Ablayeva
59-70
On Computational Power of Quantum Branching Programs
Farid Ablayev, Aida Gainutdinova and Marek Karpinski
71-82
Efficient Computation of Singular Moduli with Application in Cryptography
Harald Baier
83-93
Ambainis-Freivalds’ Algorithm for Measure-Once Automata
Aija Bērziņa and Richard Bonner
94-105
Are There Essentially Incomplete Knowledge Representation Systems?
Jānis Cīrulis
106-117
Best Increments for the Average Case of Shellsort
Marcin Ciura
118-125
Approximating Minimum Cocolourings
Fedor V. Fomin, Dieter Kratsch and Jean-Christophe Novelli
126-137
Curved Edge Routing
Kārlis Freivalds
138-149
Time/Space Efficient Compressed Pattern Matching
Leszek Gasieniec and Igor Potapov
150-161
Modelling Change with the Aid of Knowledge and Time
Bernhard Heinemann
162-171
If P ≠ NP then Some Strongly Noninvertible Functions Are Invertible
Lane A. Hemaspaandra, Kari Pasanen and Jörg Rothe
172-183
Prediction-Preserving Reducibility with Membership Queries on Formal Languages
Kouichi Hirata and Hiroshi Sakamoto
184-192
Dense Families and Key Functions of Database Relation Instances
Jouni Järvinen
193-203
On the Complexity of Decidable Cases of Commutation Problem for Languages
Extended Abstract
Juhani Karhumäki, Wojciech Plandowski and Wojciech Rytter
204-216
Cones, Semi-AFPs, and AFPs of Algebraic Power Series
Werner Kuich
217-226
New Small Universal Circular Post Machines
Manfred Kudlek and Yurii Rogozhin
227-239
Divisibility Monoids: Presentation, Word Problem, and Rational Languages
Dietrich Kuske
240-251
Concurrency in Timed Automata
Ruggero Lanotte, Andrea Maggiolo-Schettini and Simone Tini
252-263
How Powerful Are Infinite Time Machines?
Grégory Lafitte
264-274
Equivalence Problem of Composite Class Diagrams
Ģirts Linde
275-286
Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2
Extended Abstract
Jérôme Monnot, Vangelis T. Paschos and Sophie Toulouse
287-298
On the Category of Event Structures with Dense Time
Nataly S. Moskaljova and Irina B. Virbitskaite
299-310
Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions
Arfst Nickelsen and Till Tantau
311-322
Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case
Robert Rettinger and Rutger Verbeek
323-334
Relating Automata-Theoretic Hierarchies to Complexity-Theoretic Hierarchies
V. L. Selivanov
335-346
Polynomial Time Algorithms for Finding Unordered Tree Patterns with Internal Variables
Takayoshi Shoudai, Tomoyuki Uchida and Tetsuhiro Miyahara
347-358
Piecewise and Local Threshold Testability of DFA
A. N. Trahtman
359-371
Compositional Homomorphisms of Relational Structures
Modeled as Multialgebras
Michał Walicki, Adis Hodzic and Sigurd Meldal
372-375
Representation of Autonomous Automata
Jānis Buls, Vaira Buža and Roberts Glaudiņš
376-379
Quantum Reversibility and a New Model of Quantum Automaton
Massimo Pica Ciamarra
380-383
Space-Efficient 1.5-Way Quantum Turing Machine
Andrej Dubrovsky
384-387
A Combinatorial Aggregation Algorithm for Stationary Distribution of a Large Markov Chain
Extended Abstract
Anna Gambin and Piotr Pokarowski
388-391
A Primitive for Proving the Security of Every Bit and about Universal Hash Functions & Hard Core Bits
Eike Kiltz
392-395
Pythagorean Triples in Unification Theory of Nilpotent Rings
Ruvim Lipyanski
396-399
Two-States Bilinear Intrinsically Universal Cellular Automata
Nicolas Ollinger
400-403
Linear Time Recognizer for Subsets of ℤ2
Christophe Papazian and Eric Rémila
404-407
Fuzzy Sets and Algorithms of Distributed Task Allocation for Cooperative Agents
Tanya Plotkin
408-411
On Recursively Enumerable Subsets of N and Rees Matrix Semigroups over (Z3 ; + )
Bella V. Rozenblat
412-415
Quantum Real - Time Turing Machine
Oksana Scegulnaja
416-419
Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control
Andrew V. Sokolov
420-423
Linear Automata and Recognizable Subsets in Free Semirings
Olga Sokratova
424-427
On Logical Method for Counting Dedekind Numbers
Mati Tombak, Ain Isotamm and Tõnu Tamme
428-431
A General Method for Graph Isomorphism
Gabriel Valiente
432-444
Designing PTASs for MIN-SUM Scheduling Problems
Short Version
F. Afrati and I. Milis
445-458
On Robust Algorithms for the Maximum Weight Stable Set Problem
Andreas Brandstädt
459-460
Multicasting in Optical Networks
Luisa Gargano
461-471
Structured Randomized Rounding and Coloring
Extended Abstract
Benjamin Doerr
472-482
Optimal Online Flow Time with Resource Augmentation
Leah Epstein and Rob van Stee
483-494
New Results for Path Problems in Generalized Stars, Complete Graphs, and Brick Wall Graphs
Thomas Erlebach and Danica Vukadinović
495-507
On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks
Aleksei V. Fishkin, Klaus Jansen and Lorant Porkolab
508-515
Approximation Algorithms for Time-Dependent Orienteering
Fedor V. Fomin and Andrzej Lingas
516-524
On Complexity of Colouring Mixed Hypertrees
Daniel Král’
525-534
Combining Arithmetic and Geometric Rounding Techniques for Knapsack Problems
Monaldo Mastrolilli
535-539
The Complexity of Maximum Matroid-Greedoid Intersection
Taneli Mielikäinen and Esko Ukkonen
Back matter