Mathematical foundations of computer science 2001. 26th international symposium, MFCS 2001, Mariánské Lázně, Czech Republic, August 27--31, 2001. Proceedings (Q5943786)

The articles of this volume will be reviewed individually. The preceding symposium (25th, 2000) has been reviewed (see Zbl 0944.00070). Indexed articles: \textit{Scott, Dana S.}, A new category for semantics, 1-2 [Zbl 1005.68881] \textit{Bürgisser, Peter}, On implications between P-NP-hypotheses: Decision versus computation in algebraic complexity, 3-17 [Zbl 0999.68083] \textit{Demaine, Erik D.}, Playing games with algorithms: Algorithmic combinatorial game theory, 18-32 [Zbl 1021.91009] \textit{Gottlob, Georg; Leone, Nicola; Scarcello, Francesco}, Hypertree decompositions: A survey, 37-57 [Zbl 1001.05087] \textit{Hofmann, Martin}, The strength of non-size-increasing computation (introduction and summary), 58-61 [Zbl 0999.68514] \textit{Høyer, Peter}, Introduction to recent quantum algorithms, 62-73 [Zbl 0999.68511] \textit{Randall, Dana}, Decomposition methods and sampling circuits in the Cartesian lattice, 74-86 [Zbl 1004.60076] \textit{Schöning, Uwe}, New algorithms for \(k\)-SAT based on the local search principle, 87-95 [Zbl 0999.68205] \textit{Wilke, Thomas}, Linear temporal logic and finite semigroups, 96-110 [Zbl 1005.03507] \textit{Alber, Jochen; Fan, Hongbing; Fellows, Michael R.; Fernau, Henning; Niedermeier, Rolf; Rosamond, Fran; Stege, Ulrike}, Refined search tree technique for DOMINATING SET on planar graphs, 111-122 [Zbl 0999.68158] \textit{Amano, Kazuyuki; Hirosawa, Tsukuru; Watanabe, Yusuke; Maruoka, Akira}, The computational power of a family of decision forests, 123-134 [Zbl 0999.68516] \textit{Ambainis, Andris; Kikusts, Arnolds}, Exact result for accepting probabilities of quantum automata, 135-147 [Zbl 0999.68102] \textit{Atserias, Albert}, Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms, 148-158 [Zbl 0999.03052] \textit{Barrett, Chris; Hunt, Harry B. III; Marathe, Madhav V.; Ravi, S. S.; Rosenkrantz, Daniel J.; Stearns, Richard E.}, Analysis problems for sequential dynamical systems and communicating state machines, 159-172 [Zbl 1006.37012] \textit{Beaudry, Martin; Holzer, Markus}, The complexity of tensor circuit evaluation (extended abstract), 173-185 [Zbl 0999.68515] \textit{Bläser, Markus}, Computing reciprocals of bivariate power series, 186-197 [Zbl 0999.68087] \textit{Bouajjani, Ahmed; Habermehl, Peter; Mayr, Richard}, Automatic verification of recursive procedures with one integer parameter, 198-211 [Zbl 1005.68096] \textit{Brosenne, Henrik; Homeister, Matthias; Waack, Stephan}, Graph-driven free parity BDDs: Algorithms and lower bounds, 212-223 [Zbl 0999.68068] \textit{Brattka, Vasco}, Computable versions of Baire's category theorem, 224-235 [Zbl 0999.03057] \textit{Bruyère, Véronique; Carton, Olivier}, Automata on linear orderings, 236-247 [Zbl 0999.68100] \textit{Cervelle, Julien; Durand, Bruno; Formenti, Enrico}, Algorithmic information theory and cellular automata dynamics, 248-259 [Zbl 0999.68091] \textit{Chrobak, Marek; Larmore, Lawrence L.; Rytter, Wojciech}, The \(k\)-median problem for directed trees (extended abstract), 260-271 [Zbl 0999.68536] \textit{Cryan, Mary; Miltersen, Peter Bro}, On pseudorandom generators in \({\mathbf {NC^0}}\), 272-284 [Zbl 0999.68072] \textit{Cucker, Felipe; Grigoriev, Dima}, There are no sparse \(\text{NP}_W\)-hard sets, 285-291 [Zbl 0999.68082] \textit{Di Crescenzo, Giovanni}, Sharing one secret vs. sharing many secrets: Tight bounds for the max improvement ratio, 292-303 [Zbl 1012.94553] \textit{Díaz, Josep; Serna, Maria; Thilikos, Dimitrios M.}, (\(H,C,K\))-coloring: Fast, easy, and hard cases, 304-315 [Zbl 0999.68157] \textit{Downey, Rod G.; Hirschfeldt, Denis R.; LaForte, Geoff}, Randomness and reducibility, 316-327 [Zbl 0999.03038] \textit{Ďuriš, Pavol; Maňuch, Ján}, On the computational complexity of infinite words, 328-337 [Zbl 0999.68105] \textit{Epstein, Leah; van Stee, Rob}, Lower bounds for on-line single-maschine scheduling, 338-350 [Zbl 0999.68502] \textit{Erlebach, Thomas}, Approximation algorithms and complexity results for path problems in trees of rings, 351-362 [Zbl 0999.68537] \textit{Espelage, Wolfgang; Wanke, Egon}, A 3-approximation algorithm for movement minimization in conveyor flow shop processing, 363-374 [Zbl 1003.90019] \textit{Fournier, Hervé}, Quantifier rank for parity of embedded finite models, 375-386 [Zbl 0999.03029] \textit{Geffert, Viliam}, Space hierarchy theorem revised, 387-397 [Zbl 1005.68073] \textit{Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni}, Converting two-way nondeterministic unary automata into simpler automata, 398-407 [Zbl 1005.68090] \textit{Hoang, Thanh Minh; Thierauf, Thomas}, The complexity of the minimal polynomial, 408-420 [Zbl 0999.68263] \textit{Jirásková, Galina}, Note on minimal finite automata, 421-431 [Zbl 0999.68104] \textit{Kari, Jarkko}, Synchronizing finite automata on Eulerian digraphs, 432-438 [Zbl 0999.68108] \textit{Klein, Andreas; Kutrib, Martin}, A time hierarchy for bounded one-way cellular automata, 439-450 [Zbl 0999.68131] \textit{Klin, Bartek; Hoffman, Piotr; Tarlecki, Andrzej; Schöder, Lutz; Mossakowski, Till}, Checking amalgamability conditions for CASL architectural specifications, 451-463 [Zbl 0999.68506] \textit{Koo, Chiu-Yuen; Lam, Tak-Wah; Ngan, Tsuen-Wan; To, Kar-Keung}, On-line scheduling with tight deadlines, 464-473 [Zbl 0999.68503] \textit{Král, Daniel; Kratochvíl, Jan; Voss, Heinz-Jürgen}, Complexity note on mixed hypergraphs, 474-485 [Zbl 1001.05055] \textit{Krumke, Sven O.; de Paepe, Willem E.; Poensgen, Diana; Stougie, Leen}, News from the online traveling repairman, 487-499 [Zbl 1003.90047] \textit{Lohrey, Markus}, Word problems for 2-homogeneous monoids and symmetric logspace, 500-511 [Zbl 0999.03037] \textit{Mignosi, Filippo; Shallit, Jeffrey; Wang, Ming-wei}, Variations on a theorem of Fine \& Wilf, 512-523 [Zbl 0999.68166] \textit{Monien, Burkhard; Preis, Robert}, Upper bounds on the bisection width of 3- and 4-regular graphs, 524-536 [Zbl 0999.68159] \textit{Moore, Cristopher; Tesson, Pascal; Thérien, Denis}, Satisfiability of systems of equations over finite monoids, 537-547 [Zbl 0999.68262] \textit{Morvan, Christophe; Stirling, Colin}, Rational graphs trace context-sensitive languages, 548-559 [Zbl 0999.68107] \textit{Neven, Frank; Schwentick, Thomas; Vianu, Victor}, Towards regular languages over infinite alphabets, 560-572 [Zbl 0999.68110] \textit{Nickelsen, Arfst}, Partial information and special case algorithms, 573-584 [Zbl 0999.68106] \textit{Ogihara, Mitsunori; Toda, Seinosuke}, The complexity of computing the number of self-avoiding walks in two-dimensional grid graphs and in hypercube graphs, 585-597 [Zbl 0999.68088] \textit{Piterman, Nir; Vardi, Moshe Y.}, From bidirectionality to alternation, 598-610 [Zbl 0999.68103] \textit{Polák, Libor}, Syntactic semiring of a language. (Extended abstract), 611-620 [Zbl 1005.68526] \textit{Pudlák, Pavel}, On reducibility and symmetry of disjoint NP-pairs, 621-632 [Zbl 0999.68080] \textit{Rettinger, Robert; Zheng, Xizhong}, Hierarchy of monotonically computable real numbers (extended abstract), 633-644 [Zbl 0999.03510] \textit{Santocanale, Luigi}, On the equational definition of the least prefixed point, 645-656 [Zbl 0999.03026] \textit{Shur, Arseny M.; Konovalova, Yulia V.}, On the periods of partial words, 657-665 [Zbl 0999.68165] \textit{Sutner, Klaus}, The size of power automata, 666-677 [Zbl 0999.68109] \textit{Thimm, Martin}, On the approximability of the Steiner tree problem, 678-689 [Zbl 0999.68081] \textit{Wang, Zhuozhi; Zhang, Kaizhong}, Alignment between two RNA structures, 690-702 [Zbl 1070.92515] \textit{Wich, Klaus}, Characterization of context-free languages with polynomially bounded ambiguity, 703-714 [Zbl 0999.68101]