Fundamentals of computation theory. 13th international symposium, FCT 2001, Riga, Latvia, August 22--24, 2001. Proceedings (Q5943787)

The articles of mathematical interest will be reviewed individually. The preceding symposium (12th, 1999) has been reviewed (see Zbl 0921.00033). Indexed articles: \textit{Bārzdiņš, Jānis; Freivalds, Rūsiņš; Smith, Carl H.}, Towards axiomatic basis of inductive inference, 1-13 [Zbl 1004.68078] \textit{Jansen, Klaus}, Approximation algorithms for fractional covering and packing problems, and applications, 14 [Zbl 0999.68547] \textit{Karhumäki, Juhani}, Challenges of commutation. An advertisement, 15-23 [Zbl 0999.68517] \textit{Karpinski, Marek}, Approximating bounded degree instances of NP-hard problems, 24-34 [Zbl 1003.90055] \textit{Plotkin, Boris; Plotkin, Tanya}, Universal algebra and computer science, 35-44 [Zbl 0999.08005] \textit{Vazirani, Umesh}, Quantum algorithms, 45-46 [Zbl 0999.68546] \textit{Ablayev, Farid; Ablayeva, Svetlana}, A discrete approximation and communication complexity approach to the superposition problem, 47-58 [Zbl 1005.68081] \textit{Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek}, On computational power of quantum branching programs, 59-70 [Zbl 0999.68071] \textit{Baier, Harald}, Efficient computation of singular moduli with application in cryptography, 71-82 [Zbl 1001.11057] \textit{Bērziņa, Aija; Bonner, Richard}, Ambainis-Freivalds' algorithm for measure-once automata, 83-93 [Zbl 0999.68510] \textit{Cīrulis, Jānis}, Are there essentially incomplete knowledge representation systems?, 94-105 [Zbl 0999.68211] \textit{Ciura, Marcin}, Best increments for the average case of Shellsort, 106-117 [Zbl 0999.68543] \textit{Fomin, Fedor V.; Kratsch, Dieter; Novelli, Jean-Christophe}, Approximating minimum cocolourings, 118-125 [Zbl 1001.05054] \textit{Freivalds, Kārlis}, Curved edge routing, 126-137 [Zbl 0999.68544] \textit{Gasieniec, Leszek; Potapov, Igor}, Time/space efficient compressed pattern matching, 138-149 [Zbl 0999.68538] \textit{Heinemann, Bernhard}, Modelling change with the aid of knowledge and time, 150-161 [Zbl 0999.68212] \textit{Hemaspaandra, Lane A.; Pasanen, Kari; Rothe, Jörg}, If \(\text{P} \neq \text{NP}\) then some strongly noninvertible functions are invertible, 162-171 [Zbl 0999.68076] \textit{Hirata, Kouichi; Sakamoto, Hiroshi}, Prediction-preserving reducibility with membership queries on formal languages, 172-183 [Zbl 0999.68520] \textit{Järvinen, Jouni}, Dense families and key functions of database relation instances, 184-192 [Zbl 0999.68508] \textit{Karhumäki, Juhani; Plandowski, Wojciech; Rytter, Wojciech}, On the complexity of decidable cases of commutation problem for languages (extended abstract), 193-203 [Zbl 0999.68522] \textit{Kuich, Werner}, Cones, semi-AFPs, and AFPs of algebraic power series, 204-216 [Zbl 0999.68128] \textit{Kudlek, Manfred; Rogozhin, Yurii}, New small universal circular Post machines, 217-226 [Zbl 0999.68070] \textit{Kuske, Dietrich}, Divisibility monoids: Presentation, word problem, and rational languages, 227-239 [Zbl 0999.68129] \textit{Lanotte, Ruggero; Maggiolo-Schettini, Andrea; Tini, Simone}, Concurrency in timed automata, 240-251 [Zbl 0999.68135] \textit{Lafitte, Grégory}, How powerful are infinite time machines?, 252-263 [Zbl 0999.68069] \textit{Linde, Ģirts}, Equivalence problem of composite class diagrams, 264-274 [Zbl 0999.68541] \textit{Monnot, Jérôme; Paschos, Vangelis Th.; Toulouse, Sophie}, Differential approximation results for the traveling salesman problem with distances 1 and 2 (extended abstract), 275-286 [Zbl 1003.90035] \textit{Moskaljova, Nataly S.; Virbitskaite, Irina B.}, On the category of event structures with dense time, 287-298 [Zbl 0999.68136] \textit{Nickelsen, Arfst; Tandau, Till}, Closure of polynomial time partial information classes under polynomial time reduction, 299-310 [Zbl 1005.68074] \textit{Rettinger, Robert; Verbeek, Rutger}, Monte-Carlo polynomial versus linear time -- the truth-table case, 311-322 [Zbl 0999.68077] \textit{Selivanov, V. L.}, Relating automata-theoretic hierarchies to complexity-theoretic hierarchies, 323-334 [Zbl 0999.68078] \textit{Shoudai, Takayoshi; Uchida, Tomoyuki; Miyahara, Tetsuhiro}, Polynomial time algorithms for finding unordered tree patterns with internal variables, 335-346 [Zbl 0999.68111] \textit{Trahtman, A. N.}, Piecewise and local threshold testability of DFA, 347-358 [Zbl 0999.68519] \textit{Walicki, Michał; Hodzic, Adis; Meldal, Sigurd}, Compositional homomorphisms of relational structures (modeled as multialgebras), 359-371 [Zbl 0999.08004] \textit{Buls, Jānis; Buža, Vaira; Glaudiš, Roberts}, Representation of autonomous automata, 372-375 [Zbl 0999.68521] \textit{Ciamarra, Massimo Pica}, Quantum reversibility and a new model of quantum automaton, 376-379 [Zbl 0999.68512] \textit{Dubrovsky, Andrej}, Space-efficient 1. 5-way quantum Turing machine, 380-383 [Zbl 0999.68513] \textit{Gambin, Anna; Pokarowski, Piotr}, A combinatorial aggregation algorithm for stationary distribution of a large Markov chain. (Extended abstract), 384-387 [Zbl 1008.60508] \textit{Kiltz, Eike}, A primitive for proving the security of every bit and about universal hash functions \& hard core bits, 388-391 [Zbl 0999.94520] \textit{Lipyanski, Ruvim}, Pythagorean triples in unification theory of nilpotent rings, 392-395 [Zbl 1007.16013] \textit{Ollinger, Nicolas}, Two-states bilinear intrinsically universal cellular automata, 396-399 [Zbl 0999.68526] \textit{Papazian, Christophe; Rémila, Eric}, Linear time recognizer for subsets of \({\mathbb Z}^2\), 400-403 [Zbl 0999.68518] \textit{Plotkin, Tanya}, Fuzzy sets and algorithms of distributed task allocation for cooperative agents, 404-407 [Zbl 0999.68540] \textit{Rozenblat, Bella V.}, On recursively enumerable subsets of \(\mathbb{N}\) and Rees matrix semigroups over \((\mathbb{Z}_3;+)\), 408-411 [Zbl 1005.03041] \textit{Scegulnaja, Oksana}, Quantum real-time Turing machine, 412-415 [Zbl 1005.68067] \textit{Sokolov, Andrew V.}, Mathematical models and optimal algorithms of dynamic data structure control, 416-419 [Zbl 0999.68507] \textit{Sokratova, Olga}, Linear automata and recognizable subsets in free semirings, 420-423 [Zbl 0999.68525] \textit{Tombak, Mati; Isotamm, Ain; Tamme, Tõnu}, On logical method for counting Dedekind numbers, 424-427 [Zbl 0999.03504] \textit{Valiente, Gabriel}, A general method for graph isomorphism, 428-431 [Zbl 1001.05085] \textit{Afrati, F.; Milis, I.}, Designing PTASs for MIN-SUM scheduling problems (short version), 432-444 [Zbl 0999.68501] \textit{Brandstädt, Andreas}, On robust algorithms for the maximum weight stable set problem, 445-458 [Zbl 1001.05111] \textit{Doerr, Benjamin}, Structured randomized rounding and coloring (extended abstract), 461-471 [Zbl 0999.68535] \textit{Epstein, Leah; van Stee, Rob}, Optimal online flow time with resource augmentation, 472-482 [Zbl 0999.68023] \textit{Erlebach, Thomas; Vukadinović, Danica}, New results for path problems in generalized stars, complete graphs, and brick wall graphs, 483-494 [Zbl 0999.68160] \textit{Fishkin, Aleksei V.; Jansen, Klaus; Porkolab, Lorant}, On minimizing average weighted completion time: A PTAS for scheduling general multiprocessor tasks, 495-507 [Zbl 0999.68024] \textit{Fomin, Fedor V.; Lingas, Andrzej}, Approximation algorithms for time-dependent orienteering, 508-515 [Zbl 1003.90046] \textit{Král', Daniel}, On complexity of colouring mixed hypertrees, 516-524 [Zbl 1001.05110] \textit{Mastrolilli, Monaldo}, Combining arithmetic and geometric rounding techniques for knapsack problems, 525-534 [Zbl 1003.90034] \textit{Mielikäinen, Taneli; Ukkonen, Esko}, The complexity of maximum matroid-greedoid intersection, 535-539 [Zbl 0999.68534]