Mathematical foundations of computer science 2004. 29th international symposium, MFCS 2004, Prague, Czech Republic, August 22--27, 2004. Proceedings. (Q1769767)

The articles of this volume will be reviewed individually. The preceding symposium has been reviewed (see Zbl 1025.00004). Indexed articles: \textit{Tiuryn, Jerzy; Rudnicki, Ryszard; Wójtowicz, Damian}, A case study of genome evolution: From continuous to discrete time model, 1-24 [Zbl 1097.92036] \textit{Halldórsson, Magnús M.; Kortsarz, Guy}, Multicoloring: Problems and techniques, 25-41 [Zbl 1096.68684] \textit{Downey, Rod}, Some recent progress in algorithmic randomness, 42-83 [Zbl 1096.03055] \textit{Niedermeier, Rolf}, Ubiquitous parameterization -- invitation to fixed-parameter algorithms, 84-103 [Zbl 1096.68068] \textit{Vishkin, Uzi}, PRAM-On-Chip: A quest for not-so-obvious non-obviousness, 104-105 [Zbl 1096.68580] \textit{Brand, Matthew; Frisken, Sarah; Lesh, Neal; Marks, Joe; Nikovski, Daniel; Perry, Ron; Yedidia, Jonathan}, Theory and applied computing: Observations and anecdotes, 106-118 [Zbl 1097.68665] \textit{Bonelli, Eduardo; Compagnoni, Adriana; Dezani-Ciancaglini, Mariangiola; Garralda, Pablo}, Boxed ambients with communication interfaces, 119-148 [Zbl 1097.68083] \textit{Weil, Pascal}, Algebraic recognizability of languages, 149-175 [Zbl 1097.68078] \textit{Welzl, Emo}, Geometric optimization and unique sink orientations of cubes, 176-176 [Zbl 1097.90569] \textit{Koutsoupias, Elias}, Congestion games and coordination mechanisms, 177-179 [Zbl 1096.68517] \textit{Bodlaender, Hans L.; Fomin, Fedor V.}, Equitable colorings of bounded treewidth graphs, 180-190 [Zbl 1096.68116] \textit{Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M.}, The bidimensional theory of bounded-genus graphs, 191-203 [Zbl 1100.05095] \textit{Broersma, Hajo; Fomin, Fedor V.; Woeginger, Gerhard J.}, Parallel knock-out schemes in networks, 204-214 [Zbl 1096.68118] \textit{Caragiannis, Ioannis; Fishkin, Aleksei; Kaklamanis, Christos; Papaioannou, Evi}, Online algorithms for disk graphs, 215-226 [Zbl 1096.68119] \textit{Böckenhauer, Hans-Joachim; Bongartz, Dirk}, Protein folding in the HP model on grid lattices with diagonals (extended abstract), 227-238 [Zbl 1097.92507] \textit{Chen, Hubie; Pál, Martin}, Optimization, games, and quantified constraint satisfaction, 239-250 [Zbl 1096.90028] \textit{Gronemeier, Andre}, Approximating Boolean functions by OBDDs, 251-262 [Zbl 1096.68032] \textit{Chlebík, Miroslav; Chlebíková, Janka}, On approximation hardness of the minimum 2SAT-DELETION problem, 263-273 [Zbl 1096.68061] \textit{Král', Daniel; Nejedlý, Pavel}, Group coloring and list group coloring are \(\Pi_{2}^{\text{P}}\)-complete (extended abstract), 274-286 [Zbl 1096.68627] \textit{Hemaspaandra, Edith; Hemaspaandra, Lane A.; Radziszowski, Stanisław; Tripathi, Rahul}, Complexity results in graph reconstruction, 287-297 [Zbl 1096.68121] \textit{Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Khachiyan, Leonid; Makino, Kazuhisa}, Generating paths and cuts in multi-pole (di)graphs, 298-309 [Zbl 1096.68117] \textit{Nutov, Zeev; Yuster, Raphael}, Packing directed cycles efficiently, 310-321 [Zbl 1096.68123] \textit{Travers, Stephen D.}, The complexity of membership problems for circuits over sets of integers, 322-333 [Zbl 1096.68065] \textit{Hansen, Kristoffer Arnsfelt; Miltersen, Peter Bro}, Some meet-in-the-middle circuit lower bounds, 334-345 [Zbl 1096.68062] \textit{Beygelzimer, Alina; Ogihara, Mitsunori}, The enumerability of P collapses P to NC, 346-355 [Zbl 1096.68059] \textit{De Santis, Alfredo; Di Crescenzo, Giovanni; Persiano, Giuseppe}, On NC\(^{1}\) Boolean circuit composition of non-interactive perfect zero-knowledge, 356-367 [Zbl 1096.68060] \textit{Hemaspaandra, Edith; Hemaspaandra, Lane A.; Hempel, Harald}, All superlinear inverse schemes are coNP-hard, 368-379 [Zbl 1096.68064] \textit{Nordh, Gustav}, The complexity of equivalence and isomorphism of systems of equations over finite groups, 380-391 [Zbl 1096.68069] \textit{Böhler, Elmar; Glaßer, Christian; Schwarz, Bernhard; Wagner, Klaus}, Generation problems, 392-403 [Zbl 1096.68067] \textit{Bab, Sebastian; Nickelsen, Arfst}, One query reducibilities between partial information classes, 404-415 [Zbl 1096.68058] \textit{Bernardi, Vincent; Durand, Bruno; Formenti, Enrico; Kari, Jarkko}, A new dimension sensitive property for cellular automata, 416-426 [Zbl 1096.68098] \textit{Theyssier, Guillaume}, Captive cellular automata, 427-438 [Zbl 1096.68100] \textit{Poupet, Victor}, Simulating 3D cellular automata with 2D cellular automata, 439-450 [Zbl 1096.68099] \textit{Fraigniaud, Pierre; Ilcinkas, David; Peer, Guy; Pelc, Andrzej; Peleg, David}, Graph exploration by a finite automaton, 451-462 [Zbl 1096.68080] \textit{Lee, Troy; Romashchenko, Andrei}, On polynomially time bounded symmetry of information, 463-475 [Zbl 1096.68074] \textit{Hitchcock, John M.; López-Valdés, María; Mayordomo, Elvira}, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, 476-487 [Zbl 1096.68073] \textit{Fernau, Henning; Juedes, David}, A geometric approach to parameterized algorithms for domination problems on planar graphs, 488-499 [Zbl 1096.68167] \textit{Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge}, Polynomial time approximation schemes and parameterized complexity, 500-512 [Zbl 1096.68166] \textit{Loyer, Yann; Straccia, Umberto}, Epistemic foundation of the well-founded semantics over bilattices, 513-524 [Zbl 1096.68016] \textit{Lanotte, Ruggero; Maggiolo-Schettini, Andrea; Peron, Adriano}, Structural model checking for communicating hierarchical machines, 525-536 [Zbl 1096.68092] \textit{Ly, Olivier}, Compositional verification: Decidability issues using graph substitutions, 537-549 [Zbl 1096.68093] \textit{van Glabbeek, Rob; Plotkin, Gordon}, Event structures for resolvable conflict, 550-561 [Zbl 1096.68114] \textit{Epstein, Leah; Tassa, Tamir}, Optimal preemptive scheduling for general target functions, 562-573 [Zbl 1096.90015] \textit{Gairing, Martin; Lücking, Thomas; Mavronicolas, Marios; Monien, Burkhard}, The price of anarchy for polynomial social cost, 574-585 [Zbl 1096.68010] \textit{Elsässer, Robert; Lorenz, Ulf; Sauerwald, Thomas}, Agent-based information handling in large networks, 586-598 [Zbl 1096.68009] \textit{Baumann, Nadine; Köhler, Ekkehard}, Approximating earliest arrival flows with flow-dependent transit times, 599-610 [Zbl 1096.90003] \textit{Béal, Marie-Pierre; Fiorenzi, Francesca; Perrin, Dominique}, A hierarchy of irreducible sofic shifts, 611-622 [Zbl 1096.68078] \textit{Lisitsa, Alexei; Potapov, Igor}, Membership and reachability problems for row-monomial transformations, 623-634 [Zbl 1096.68108] \textit{Polák, Libor}, On pseudovarieties of semiring homomorphisms, 635-647 [Zbl 1096.68097] \textit{Ésik, Zoltán; Kuich, Werner}, An algebraic generalization of \(\omega\)-regular languages, 648-659 [Zbl 1096.68096] \textit{Crasmaru, Marcel; Glaßer, Christian; Regan, Kenneth W.; Sengupta, Samik}, A protocol for serializing unique strategies, 660-672 [Zbl 1097.68046] \textit{Björklund, Henrik; Sandberg, Sven; Vorobyov, Sergei}, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, 673-685 [Zbl 1097.91020] \textit{Gimbert, Hugo; Zielonka, Wiesław}, When can you play positionally?, 686-697 [Zbl 1097.91022] \textit{Okhotin, Alexander}, The dual of concatenation, 698-710 [Zbl 1097.68068] \textit{Ambos-Spies, Klaus; Busse, Edgar}, Computational aspects of disjunctive sequences, 711-722 [Zbl 1097.03033] \textit{Domaratzki, Michael; Salomaa, Kai}, Decidability of trajectory-based equations, 723-734 [Zbl 1097.68057] \textit{Biedl, Therese; Hasan, Masud; López-Ortiz, Alejandro}, Efficient view point selection for silhouettes of convex polyhedra, 735-747 [Zbl 1097.68130] \textit{Biedl, Therese; Lubiw, Anna; Spriggs, Michael J.}, Angles and lengths in reconfigurations of polygons and polyhedra, 748-759 [Zbl 1097.68132] \textit{Doerr, Benjamin; Hebbinghaus, Nils; Werth, Sören}, Improved bounds and schemes for the declustering problem, 760-771 [Zbl 1097.68037] \textit{Hliněný, Petr}, Crossing number is hard for cubic graphs, 772-782 [Zbl 1097.68047] \textit{Selivanov, Victor L.; Wagner, Klaus W.}, A reducibility for the dot-depth hierarchy, 783-793 [Zbl 1097.03035] \textit{Wich, Klaus}, Sublogarithmic ambiguity, 794-806 [Zbl 1097.68069] \textit{Petre, Elena}, An elementary proof for the non-parametrizability of the equation \(xyz=zvx\), 807-817 [Zbl 1097.68112] \textit{Ilie, Lucian; Ochem, Pascal; Shallit, Jeffrey}, A generalization of repetition threshold, 818-826 [Zbl 1097.68110] \textit{Nishimura, Harumichi; Yamakami, Tomoyuki}, An algorithmic argument for nonadaptive query complexity lower bounds on advised quantum computation (extended abstract), 827-838 [Zbl 1097.68567] \textit{Kawachi, Akinori; Kobayashi, Hirotada; Koshiba, Takeshi; Putra, Raymond H.}, Universal test for quantum one-way permutations, 839-850 [Zbl 1097.68038] \textit{Beaudry, Martin; Fernandez, José M.; Holzer, Markus}, A common algebraic description for probabilistic and quantum computations (extended abstract), 851-862 [Zbl 1097.68566] \textit{André, Yves; Caron, Anne-Cécile; Debarbieux, Denis; Roos, Yves; Tison, Sophie}, Extraction and implication of path constraints, 863-875 [Zbl 1097.68028] \textit{Bouchou, Béatrice; Duarte, Denio; Halfeld Ferrari Alves, Mírian; Laurent, Dominique; Musicante, Martin A.}, Schema evolution for XML: A consistency-preserving approach, 876-888 [Zbl 1097.68550] \textit{Martens, Wim; Neven, Frank; Schwentick, Thomas}, Complexity of decision problems for simple regular expressions, 889-900 [Zbl 1097.68066]