Buch, Englisch, 550 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 844 g
13th International Symposium, FCT 2001, Riga, Latvia, August 22-24, 2001. Proceedings
Buch, Englisch, 550 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 844 g
Reihe: Lecture Notes in Computer Science
ISBN: 978-3-540-42487-1
Verlag: Springer
ThesymposiaonFundamentalsofComputationTheoryareheldeverytwoyears. Following the tradition established at the ?rst FCT 1977, the conference brings together specialists in theoretical ?elds of Computer Science from various co- tries and stimulates mathematical research in theoretical computer science. - pics of interest for the satellite workshop onE?cientAlgorithms WEA2001 are: computational complexity, graph and network algorithms, ?ow and routing - gorithms,coloringandpartitioning,cutsandconnectivity,packingandcovering, scheduling algorithms, approximation algorithms, inapproximability results, - line problems, randomized algorithms, integer programming, semide?nite p- gramming, algorithmic geometry, polyhedral combinatorics, branch and bound algorithms, cutting plane algorithms, and various applications. The 13th FCT was held in Riga-Lielupe, August 22-24, 2001 with an - ditional day (August 25) for the satellite workshop WEA2001. The previous meetings were held in the following cities: – Poznan-K´ ornik, Poland, 1977 – Wendish-Rietz, Germany, 1979 – Szeged, Hungary, 1981 – Borgholm, Sweden, 1983 – Cottbus, Germany, 1985 – Kazan, Russia, 1987 – Szeged, Hungary, 1989 – Gosen-Berlin, Germany, 1991 – Szeged, Hungary, 1993 – Dresden, Germany, 1995 – Krak´ ow, Poland, 1997 – Iasi, Romania, 1999 Thisyearthenumberofsubmittedpaperswashigh.TheProgramCommittee decided to accept 28 submissions as regular papers and 15 submissions as short papers. Additionally, the Program Committee of WEA2001 accepted 8 papers.
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Grafikprogrammierung
- Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
- Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
Weitere Infos & Material
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 Complexityof Colouring Mixed Hypertrees.- Combining Arithmetic and Geometric Rounding Techniques for Knapsack Problems.- The Complexity of Maximum Matroid-Greedoid Intersection.
