Mathematical foundations of computer science 2003. 28th international symposium, MFCS 2003, Bratislava, Slovakia, August 25--29, 2003. Proceedings (Q1414356)

The articles of this volume will be reviewed individually. The preceding symposium has been reviewed (see Zbl 0997.00033). Indexed articles: \textit{Buhrman, Harry; Röhrig, Hein}, Distributed quantum computing, 1-20 [Zbl 1124.68361] \textit{Feldmann, R.; Gairing, M.; Lücking, Thomas; Monien, Burkhard; Rode, Manuel}, Selfish routing in non-cooperative networks: A survey, 21-45 [Zbl 1124.68305] \textit{Gorrieri, Roberto; Martinelli, Fabio}, Process algebraic frameworks for the specification and analysis of cryptographic protocols, 46-67 [Zbl 1124.94302] \textit{Hannay, Jo; Katsumata, Shin-ya; Sannella, Donald}, Semantic and syntactic approaches to simulation relations, 68-91 [Zbl 1124.68342] \textit{Mauri, Giancarlo; Leporati, Alberto}, On the computational complexity of conservative computing, 92-112 [Zbl 1124.68363] \textit{Thomas, Wolfgang}, Constructing infinite graphs with a decidable MSO-theory, 113-124 [Zbl 1124.03314] \textit{Wegener, Ingo}, Towards a theory of randomized search heuristics, 125-141 [Zbl 1124.68434] \textit{Àlvarez, C.; Blesa, M.; Díaz, J.; Fernández, A.; Serna, M.}, Adversarial models for priority-based networks, 142-151 [Zbl 1124.68301] \textit{Amano, Kazuyuki; Maruoka, Akira}, On optimal merging networks, 152-161 [Zbl 1124.68350] \textit{Ambos-Spies, Klaus}, Problems which cannot be reduced to any proper subproblems, 162-168 [Zbl 1124.03323] \textit{Anantharaman, Siva; Narendran, Paliath; Rusinowitch, Michael}, ACID-unification is NEXPTIME-decidable, 169-178 [Zbl 1124.68370] \textit{Ausiello, G.; Bazgan, C.; Demange, M.; Paschos, V. Th.}, Completeness in differential approximation classes, 179-188 [Zbl 1124.68365] \textit{Baba, Kensuke; Tsuruta, Satoshi; Shinohara, Ayumi; Takeda, Masayuki}, On the length of the minimum solution of word equations in one variable, 189-197 [Zbl 1124.68404] \textit{Banderier, Cyril; Beier, René; Mehlhorn, Kurt}, Smoothed analysis of three combinatorial problems, 198-207 [Zbl 1124.68371] \textit{Bannai, Hideo; Inenaga, Shunsuke; Shinohara, Ayumi; Takeda, Masayuki}, Inferring strings from graphs and arrays, 208-217 [Zbl 1124.68348] \textit{Benkoczi, Robert; Bhattacharya, Binay; Chrobak, Marek; Larmore, Lawrence L.; Rytter, Wojciech}, Faster algorithms for \(k\)-medians in trees, 218-227 [Zbl 1124.68452] \textit{Blanchard, F.; Cervelle, J.; Formenti, E.}, Periodicity and transitivity for cellular automata in Besicovitch topologies, 228-238 [Zbl 1124.68390] \textit{Bodlaender, Hans L.; Fellows, Michael R.; Thilikos, Dimitrios M.}, Starting with nondeterminism: The systematic derivation of linear-time graph layout algorithms, 239-248 [Zbl 1124.68397] \textit{Böhler, Elmar; Glaßer, Christian; Meister, Daniel}, Error-bounded probabilistic computations between MA and AM, 249-258 [Zbl 1124.68366] \textit{Bonsma, Paul S.; Brueggemann, Tobias; Woeginger, Gerhard J.}, A faster FPT algorithm for finding spanning trees with many leaves, 259-268 [Zbl 1124.68398] \textit{Boreale, Michele; Buscemi, Maria Grazia}, Symbolic analysis of crypto-protocols based on modular exponentiation, 269-278 [Zbl 1124.94301] \textit{Boreale, Michele; Gadducci, Fabio}, Denotational testing semantics in coinductive form, 279-289 [Zbl 1124.68383] \textit{Brosenne, Henrik; Homeister, Matthias; Waack, Stephan}, Lower bounds for general graph-driven read-once parity branching programs, 290-299 [Zbl 1124.68360] \textit{Bucciarelli, Antonio; Salibra, Antonino}, The minimal graph model of lambda calculus, 300-307 [Zbl 1124.03315] \textit{Carton, Olivier}, Unambiguous automata on bi-infinite words, 308-317 [Zbl 1124.68379] \textit{Černá, Ivana; Pelánek, Radek}, Relating hierarchy of temporal properties to model checking, 318-327 [Zbl 1124.68385] \textit{Chen, Hubie}, Arithmetic constant-depth circuit complexity classes, 328-337 [Zbl 1124.68367] \textit{Chen, Hubie}, Inverse NP problems, 338-347 [Zbl 1124.68368] \textit{Chen, Zhi-Zhong; Kouno, Mitsuharu}, A linear-time algorithm for 7-coloring 1-planar graphs, 348-357 [Zbl 1124.68400] \textit{Dalmau, Victor; Ford, Daniel K.}, Generalized satisfiability with limited occurrences per variable: A study through delta-matroid parity, 358-367 [Zbl 1124.68372] \textit{De Marco, Gianluca; Pelc, Andrzej}, Randomized algorithms for determining the majority on graphs, 368-377 [Zbl 1124.68401] \textit{Delhommé, Christian; Knapik, Teodor; Thomas, D. Gnanaraj}, Using transitive-closure logic for deciding linear properties of monoids, 378-387 [Zbl 1124.03313] \textit{Duval, Jean-Pierre; Kolpakov, Roman; Kucherov, Gregory; Lecroq, Thierry; Lefebvre, Arnaud}, Linear-time computation of local periods, 388-397 [Zbl 1124.68405] \textit{Epstein, Leah}, Two dimensional packing: The power of rotation, 398-407 [Zbl 1124.68431] \textit{Epstein, Leah; Tassa, Tamir}, Approximation schemes for the min-max starting time problem, 408-418 [Zbl 1124.68328] \textit{Friedl, Katalin; Magniez, Frédéric; Santha, Miklos; Sen, Pranab}, Quantum testers for hidden group properties, 419-428 [Zbl 1124.68362] \textit{Gastin, Paul; Mukund, Madhavan; Kumar, K. Narayan}, Local LTL with past constants is expressively complete for Mazurkiewicz traces, 429-438 [Zbl 1124.68391] \textit{Gastin, Paul; Oddoux, Denis}, LTL with past and two-way very-weak alternating automata, 439-448 [Zbl 1124.68387] \textit{Geser, Alfons; Hofbauer, Dieter; Waldmann, Johannes}, Match-bounded string rewriting systems, 449-459 [Zbl 1124.68378] \textit{Gramlich, Gregor}, Probabilistic and nondeterministic unary automata, 460-469 [Zbl 1124.68381] \textit{Hliněný, Petr}, On matroid properties definable in the MSO logic, 470-479 [Zbl 1124.68373] \textit{Ibarra, Oscar H.; Dang, Zhe; Egecioglu, Omer; Saxena, Gaurav}, Characterizations of catalytic membrane computing systems, 480-489 [Zbl 1124.68364] \textit{Ishii, Toshimasa; Hagiwara, Masayuki}, Augmenting local edge-connectivity between vertices and vertex subsets in undirected graphs, 490-499 [Zbl 1124.68403] \textit{Krysta, Piotr; Sanders, Peter; Vöcking, Berthold}, Scheduling and traffic allocation for tasks with bounded splittability, 500-510 [Zbl 1124.68329] \textit{Kutyłowski, Mirosław; Letkiewicz, Daniel}, Computing average value in ad hoc networks, 511-520 [Zbl 1124.68311] \textit{Lasota, Sławomir}, A polynomial-time algorithm for deciding true concurrency equivalences of basic parallel processes, 521-530 [Zbl 1124.68392] \textit{Löding, Christof; Rohde, Philipp}, Solving the sabotage game is PSPACE-hard, 531-540 [Zbl 1124.68369] \textit{Loyer, Yann; Straccia, Umberto}, The approximate well-founded semantics for logic programs with uncertainty, 541-550 [Zbl 1124.68339] \textit{Lücking, Thomas; Mavronicolas, Marios; Monien, Burkhard; Rode, Manuel; Spirakis, Paul; Vrto, Imrich}, Which is the worst-case Nash equilibrium?, 551-561 [Zbl 1124.68330] \textit{Luttik, Bas}, A unique decomposition theorem for ordered monoids with applications in process theory, 562-571 [Zbl 1124.68393] \textit{Martínez, Conrado; Molinero, Xavier}, Generic algorithms for the generation of combinatorial objects, 572-581 [Zbl 1124.68396] \textit{Meer, K.}, On the complexity of some problems in interval arithmetic, 582-591 [Zbl 1124.65300] \textit{Meghini, Carlo; Tzitzikas, Yannis; Spyratos, Nicolas}, An abduction-based method for index relaxation in taxonomy-based sources, 592-601 [Zbl 1124.68437] \textit{Merkle, Wolfgang; Reimann, Jan}, On selection functions that do not preserve normality, 602-611 [Zbl 1124.68382] \textit{Miltersen, Peter Bro; Radhakrishnan, Jaikumar; Wegener, Ingo}, On converting CNF to DNF, 612-621 [Zbl 1124.06302] \textit{Pisanti, N.; Crochemore, M.; Grossi, R.; Sagot, M.-F.}, A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum, 622-631 [Zbl 1124.68454] \textit{Reith, Steffen}, On the complexity of some equivalence problems for propositional calculi, 632-641 [Zbl 1124.68375] \textit{Riedweg, Stéphane; Pinchinat, Sophie}, Quantified mu-calculus for control synthesis, 642-651 [Zbl 1124.68388] \textit{Rychlik, Marcin}, On probabilistic quantified satisfiability games, 652-661 [Zbl 1124.68376] \textit{Salehi, Saeed}, A completeness property of Wilke's tree algebras, 662-670 [Zbl 1124.68389] \textit{Woelfel, Philipp}, Symbolic topological sorting with OBDDs, 671-680 [Zbl 1124.68352] \textit{Zheng, Xizhong; Rettinger, Robert; Gengler, Romain}, Ershov's hierarchy of real numbers, 681-690 [Zbl 1124.03324]