13. FCT 2001: Riga, Latvia

@proceedings{DBLP:conf/fct/2001,
  editor    = {Rusins Freivalds},
  title     = {Fundamentals of Computation Theory, 13th International Symposium,
               FCT 2001, Riga, Latvia, August 22-24, 2001, Proceedings},
  booktitle = {FCT},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {2138},
  year      = {2001},
  isbn      = {3-540-42487-3},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Papers

• Janis Barzdins, Rusins Freivalds, Carl H. Smith:
  Towards Axiomatic Basis of Inductive Inference. 1-13
  
• Klaus Jansen:
  Approximation Algorithms for Fractional Covering and Packing Problems, and Applications. 14
  
• Juhani Karhumäki:
  Challenges of Commutation. 15-23
  
• Marek Karpinski:
  Approximating Bounded Degree Instances of NP-Hard Problems. 24-34
  
• Boris I. Plotkin, Tanya Plotkin:
  Universal Algebra and Computer Science. 35-44
  
• Umesh V. Vazirani:
  Quantum Algorithms. 45-46
  

Regular Papers

• Farid M. Ablayev, Svetlana Ablayeva:
  A Discrete Approximation and Communication Complexity Approach to the Superposition Problem. 47-58
  
• Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski:
  On Computational Power of Quantum Branching Programs. 59-70
  
• Harald Baier:
  Efficient Computation of Singular Moduli with Application in Cryptography. 71-82
  
• Aija Berzina, Richard F. Bonner:
  Ambainis-Freivalds' Algorithm for Measure-Once Automata. 83-93
  
• Janis Cirulis:
  Are There Essentially Incomplete Knowledge Representation Systems? 94-105
  
• Marcin Ciura:
  Best Increments for the Average Case of Shellsort. 106-117
  
• Fedor V. Fomin, Dieter Kratsch, Jean-Christophe Novelli:
  Approximating Minimum Cocolourings. 118-125
  
• Karlis Freivalds:
  Curved Edge Routing. 126-137
  
• Leszek Gasieniec, Igor Potapov:
  Time/Space Efficient Compressed Pattern Matching. 138-149
  
• Bernhard Heinemann:
  Modelling Change with the Aid of Knowledge and Time. 150-161
  
• Lane A. Hemaspaandra, Kari Pasanen, Jörg Rothe:
  If P != NP Then Some Strongly Noninvertible Functions Are Invertible. 162-171
  
• Kouichi Hirata, Hiroshi Sakamoto:
  Prediction-Preserving Reducibility with Membership Queries on Formal Languages. 172-183
  
• Jouni Järvinen:
  Dense Families and Key Functions of Database Relation Instances. 184-192
  
• Juhani Karhumäki, Wojciech Plandowski, Wojciech Rytter:
  On the Complexity of Decidable Cases of Commutation Problem for Languages. 193-203
  
• Werner Kuich:
  Cones, Semi-AFPs, and AFPs of Algebraic Power Series. 204-216
  
• Manfred Kudlek, Yurii Rogozhin:
  New Small Universal Circular Post Machines. 217-226
  
• Dietrich Kuske:
  Divisibility Monoids: Presentation, Word Problem, and Rational Languages. 227-239
  
• Ruggero Lanotte, Andrea Maggiolo-Schettini, Simone Tini:
  Concurrency in Timed Automata. 240-251
  
• Grégory Lafitte:
  How Powerful Are Infinite Time Machines? 252-263
  
• Girts Linde:
  Equivalence Problem of Composite Class Diagrams. 264-274
  
• Jérôme Monnot, Vangelis Th. Paschos, Sophie Toulouse:
  Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2. 275-286
  
• Nataly S. Moskaljova, Irina Virbitskaite:
  On the Category of Event Structures with Dense Time. 287-298
  
• Arfst Nickelsen, Till Tantau:
  Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions. 299-310
  
• Robert Rettinger, Rutger Verbeek:
  Monte-Carlo Polynomial Versus Linear Time - The Truth-Table Case. 311-322
  
• Victor L. Selivanov:
  Relating Automata-Theoretic Hierarchies to Complexity-Theoretic Hierarchies. 323-334
  
• Takayoshi Shoudai, Tomoyuki Uchida, Tetsuhiro Miyahara:
  Polynomial Time Algorithms for Finding Unordered Tree Patterns with Internal Variables. 335-346
  
• A. N. Trahtman:
  Piecewise and Local Threshold Testability of DFA. 347-358
  
• Michal Walicki, Adis Hodzic, Sigurd Meldal:
  Compositional Homomorphisms of Relational Structures. 359-371
  
• Janis Buls, Vaira Buza, Roberts Glaudins:
  Representation of Autonomous Automata. 372-375
  
• Massimo Pica Ciamarra:
  Quantum Reversibility and a New Model of Quantum Automaton. 376-379
  
• Andrej Dubrovsky:
  Space-Efficient 1.5-Way Quantum Turing Machine. 380-383
  
• Anna Gambin, Piotr Pokarowski:
  A Combinatorial Aggregation Algorithm for Stationary Distribution of a Large Markov Chain. 384-387
  
• Eike Kiltz:
  A Primitive for Proving the Security of Every Bit and About Universal Hash Functions & Hard Core Bits. 388-391
  
• Ruvim Lipyanski:
  Pythagorean Triples in Unification Theory of Nilpotent Rings. 392-395
  
• Nicolas Ollinger:
  Two-States Bilinear Intrinsically Universal Cellular Automata. 396-399
  
• Christophe Papazian, Eric Rémila:
  Linear Time Recognizer for Subsets of Z². 400-403
  
• Tanya Plotkin:
  Fuzzy Sets and Algorithms of Distributed Task Allocation for Cooperative Agents. 404-407
  
• Bella V. Rozenblat:
  On Recursively Enumerable Subsets of N and Rees Matrix Semigroups over (Z₃ ; + ). 408-411
  
• Oksana Scegulnaja:
  Quantum Real-Time Turing Machine. 412-415
  
• Andrew V. Sokolov:
  Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control. 416-419
  
• Olga Sokratova:
  Linear Automata and Recognizable Subsets in Free Semirings. 420-423
  
• Mati Tombak, Ain Isotamm, Tõnu Tamme:
  On Logical Method for Counting Dedekind Numbers. 424-427
  
• Gabriel Valiente:
  A General Method for Graph Isomorphism. 428-431
  

WEA Invited Papers

• Foto N. Afrati, Ioannis Milis:
  Designing PTASs for MIN-SUM Scheduling Problems. 432-444
  
• Andreas Brandstädt:
  On Robust Algorithms for the Maximum Weight Stable Set Problem. 445-458
  
• Luisa Gargano:
  Multicasting in Optical Networks. 459-460
  

WEA Regular Papers

• Benjamin Doerr:
  Structured Randomized Rounding and Coloring. 461-471
  
• Leah Epstein, Rob van Stee:
  Optimal Online Flow Time with Resource Augmentation. 472-482
  
• Thomas Erlebach, Danica Vukadinovic:
  New Results for Path Problems in Generalized Stars, Complete Graphs, and Brick Wall Graphs. 483-494
  
• Aleksei V. Fishkin, Klaus Jansen, Lorant Porkolab:
  On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks. 495-507
  
• Fedor V. Fomin, Andrzej Lingas:
  Approximation Algorithms for Time-Dependent Orienteering. 508-515
  
• Daniel Král:
  On Complexity of Colouring Mixed Hypertrees. 516-524
  
• Monaldo Mastrolilli:
  Combining Arithmetic and Geometric Rounding Techniques for Knapsack Problems. 525-534
  
• Taneli Mielikäinen, Esko Ukkonen:
  The Complexity of Maximum Matroid-Greedoid Intersection. 535-540