Mathematical foundations of computer science 2002. 27th symposium, MFCS 2002, Warsaw, Poland, August 26--30, 2002. Proceedings (Q1848535)

The articles of this volume will be reviewed individually. The preceding symposium (26th, 2001) has been reviewed (see Zbl 0969.00078). Indexed articles: \textit{Bidoit, Michel; Sannella, Donald; Tarlecki, Andrzej}, Global development via local observational construction steps, 1-24 [Zbl 1014.68099] \textit{Gibbons, Alan; Sant, Paul}, Edge-colouring pairs of binary trees: Towards a concise proof of the four-colour theorem of planar maps, 25-39 [Zbl 1016.05032] \textit{Karhumäki, Juhani}, Applications of finite automata, 40-58 [Zbl 1014.68083] \textit{Karpinski, Marek}, Approximability of the minimum bisection problem: An algorithmic challenge, 59-67 [Zbl 1014.68115] \textit{Peleg, David}, Low stretch spanning trees, 68-80 [Zbl 1014.68116] \textit{Andreou, Maria I.; Fotakis, Dimitris A.; Nikoletseas, Sotiris E.; Papadopoulou, Vicky G.; Spirakis, Paul G.}, On radiocoloring hierarchically specified planar graphs: PSPACE-completeness and approximations, 81-92 [Zbl 1014.68118] \textit{Angelsmark, Ola; Dahllöf, Vilhelm; Jonsson, Peter}, Finite domain constraint satisfaction using quantum computation, 93-103 [Zbl 1014.68217] \textit{Bein, Wolfgang W.; Brucker, Peter; Larmore, Lawrence L.; Park, James K.}, Fast algorithms with algebraic Monge properties, 104-117 [Zbl 1014.90076] \textit{Beis, Mihalis; Duckworth, William; Zito, Michele}, Packing edges in random regular graphs, 118-130 [Zbl 1016.05064] \textit{Bollig, Beate; Woelfel, Philipp}, A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications, 131-142 [Zbl 1014.68504] \textit{Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Khachiyan, Leonid}, Matroid intersections, polymatroid inequalities, and related problems, 143-154 [Zbl 1016.05022] \textit{Carton, Olivier}, Accessibility in automata on scattered linear orderings, 155-164 [Zbl 1014.68081] \textit{Caucal, Didier}, On infinite terms having a decidable monadic theory, 165-176 [Zbl 1014.68077] \textit{Caucal, Didier; Knapik, Teodor}, A Chomsky-like hierarchy of infinite graphs, 177-187 [Zbl 1014.68114] \textit{Chan, Wun-Tat; Lam, Tak-Wah; Ting, Hing-Fung; Wong, Prudence W. H.}, Competitive analysis of on-line stream merging algorithms, 188-200 [Zbl 1014.68237] \textit{Coja-Oghlan, Amin}, Coloring \(k\)-colorable semirandom graphs in polynomial expected time via semidefinite programming, 201-211 [Zbl 1014.68238] \textit{Dabrowski, Robert; Plandowski, Wojtek}, On word equations in one variable, 212-220 [Zbl 1014.68124] \textit{Ebert, Todd; Merkle, Wolfgang}, Autoreducibility of random sets: A sharp bound on the density of guessed bits, 221-233 [Zbl 1014.03046] \textit{Engelfriet, Joost; Maneth, Sebastian}, Two-way finite state transducers with nested pebbles, 234-244 [Zbl 1014.68087] \textit{Epstein, Leah; Favrholdt, Lene M.}, Optimal non-preemptive semi-online scheduling on two related machines, 245-256 [Zbl 1014.68017] \textit{Epstein, Leah; Imreh, Csanád; van Stee, Rob}, More on weighted servers or FIFO is better than LRU, 257-268 [Zbl 1014.68014] \textit{Fishkin, Aleksei V.; Zhang, Guochuan}, On maximizing the throughput of multiprocessor tasks, 269-279 [Zbl 1014.68015] \textit{Goerdt, Andreas; Jurdziński, Tomasz}, Some results on random unsatisfiable \(k\)-Sat instances and approximation algorithms applied to random structures, 280-291 [Zbl 1014.68227] \textit{Groult, Richard; Léonard, Martine; Mouchard, Laurent}, Evolutive tandem repeats using Hamming distance, 292-304 [Zbl 1014.68123] \textit{Hajiaghayi, Mohammad Taghi; Nishimura, Naomi}, Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth, 305-318 [Zbl 1016.05066] \textit{Hirvensalo, Mika; Karhumäki, Juhani}, Computing partial information out of intractable one -- the first digit of \(2^n\) at base \(3\) as an example, 319-327 [Zbl 1023.11062] \textit{Ilie, Lucian; Yu, Sheng}, Algorithms for computing small NFAs, 328-340 [Zbl 1014.68082] \textit{Inenaga, Shunsuke; Shinohara, Ayumi; Takeda, Masayuki; Bannai, Hideo; Arikawa, Setsuo}, Space-economical construction of index structures for all suffixes of a string, 341-352 [Zbl 1014.68125] \textit{Iwama, Kazuo; Morizumi, Hiroki}, An explicit lower bound of \(5n-o(n)\) for Boolean circuits, 353-364 [Zbl 1023.94550] \textit{Iwamoto, Chuzo; Andou, Takeshi; Morita, Kenichi; Imai, Katsunobu}, Computational complexity in the hyperbolic plane, 365-374 [Zbl 1014.68101] \textit{Janicki, Ryszard}, On a mereological system for relational software specifications, 375-386 [Zbl 1014.68050] \textit{Johannsen, Jan; Narayanaswamy, N. S.}, An optimal lower bound for resolution with 2-conjunctions, 387-398 [Zbl 1014.03016] \textit{Kanj, Iyad A.; Perković, Ljubomir}, Improved parameterized algorithms for planar dominating set, 399-410 [Zbl 1014.68218] \textit{Kára, Jan; Král', Daniel}, Optimal free binary decision diagrams for computation of EAR\(_n\), 411-422 [Zbl 1014.68051] \textit{Klíma, Ondčej}, Unification modulo associativity and idempotency is NP-complete, 423-432 [Zbl 1014.68229] \textit{Kučera, Antonín; Mayr, Richard}, On the complexity of semantic equivalences for pushdown automata and BPA, 433-445 [Zbl 1014.68103] \textit{Kupferman, Orna; Zuhovitzky, Sharon}, An improved algorithm for the membership problem for extended regular expressions, 446-458 [Zbl 1014.68088] \textit{Lin, Yaw-Ling; Jiang, Tao; Chao, Kun-Mao}, Efficient algorithms for locating the length-constrained heaviest segments, with applications to biomolecular sequence analysis, 459-470 [Zbl 1014.68219] \textit{Lombardy, Sylvain; Sakarovitch, Jacques}, Derivation of rational expressions with multiplicity, 471-482 [Zbl 1014.68085] \textit{Loyer, Yann; Spyratos, Nicolas}, Hypothesis-founded semantics for Datalog programs with negation, 483-494 [Zbl 1014.68042] \textit{Lücking, Thomas; Monien, Burkhard; Rode, Manuel}, On the problem of scheduling flows on distributed networks, 495-505 [Zbl 1014.68016] \textit{Machado, Patricia D. L.; Sannella, Donald}, Unit testing for CASL architectural specifications, 506-518 [Zbl 1014.68100] \textit{Martinelli, Fabio}, Symbolic semantics and analysis for crypto-CCS with (almost) generic inference systems, 519-531 [Zbl 1014.94552] \textit{Marx, Dániel}, The complexity of tree multicolorings, 532-542 [Zbl 1014.68117] \textit{Masson, Benoît; Schnoebelen, Ph.}, On verifying fair lossy channel systems, 543-555 [Zbl 1014.68004] \textit{McCartin, Catherine}, Parameterized counting problems, 556-567 [Zbl 1014.68108] \textit{Merkle, Wolfgang; Mihailović, Nenad}, On the construction of effective random sets, 568-580 [Zbl 1014.03047] \textit{Messner, Jochen}, On the structure of the simulation order of proof systems, 581-592 [Zbl 1014.03518] \textit{Mossakowski, Till}, Comorphism-based Grothendieck logics, 593-604 [Zbl 1014.68098] \textit{Richomme, Gwenael; Wlazinski, Francis}, Finite test-sets for overlap-free morphisms, 605-614 [Zbl 1014.68506] \textit{Rigo, Michel}, Characterizing simpler recognizable sets of integers, 615-624 [Zbl 1014.68084] \textit{Tantau, Till}, Towards a cardinality theorem for finite automata, 625-636 [Zbl 1014.68086] \textit{Villemaire, Roger}, An approximation semantics for the propositional mu-calculus, 637-649 [Zbl 1014.03036]