×

zbMATH — the first resource for mathematics

Mathematical foundations of computer science 2008. 33rd international symposium, MFCS 2008, Toruń Poland, August 25–29, 2008. Proceedings. (English) Zbl 1154.68021
Lecture Notes in Computer Science 5162. Berlin: Springer (ISBN 978-3-540-85237-7/pbk). xiv, 626 p. (2008).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding symposium has been reviewed (see Zbl 1143.68009).
Indexed articles:
Blass, Andreas; Gurevich, Yuri, One useful logic that defines its own truth, 1-15 [Zbl 1173.03306]
van Glabbeek, Rob; Goltz, Ursula; Schicke, Jens-Wolfhard, On synchronous and asynchronous interaction in distributed systems, 16-35 [Zbl 1173.68585]
Gómez, Antonio Cano; Pin, Jean-Éric, A robust class of regular languages, 36-51 [Zbl 1173.68554]
Královič, Rastislav; Královič, Richard, Deterministic models of communication faults, 52-67 [Zbl 1173.68525]
Sankowski, Piotr, Algebraic graph algorithms, 68-82 [Zbl 1173.05354]
Abbasi, Sarmad; Sheikh, Numan, Question/answer games on towers and pyramids, 83-95 [Zbl 1173.91320]
Alekseev, Vladimir E.; Lozin, Vadim; Malyshev, Dmitriy; Milanič, Martin, The maximum independent set problem in planar graphs, 96-107 [Zbl 1173.68534]
Bilò, Vittorio; Fanelli, Angelo; Flammini, Michele; Moscardelli, Luca, When ignorance helps: Graphical multicast cost sharing games, 108-119 [Zbl 1173.91322]
Biskup, Marek Tomasz, Shortest synchronizing strings for Huffman codes. (Extended abstract), 120-131 [Zbl 1173.94411]
Björklund, Henrik; Martens, Wim; Schwentick, Thomas, Optimizing conjunctive queries over trees using schema information, 132-143 [Zbl 1173.68473]
Bodlaender, Hans L.; Fellows, Michael R.; Heggernes, Pinar; Mancini, Federico; Papadopoulos, Charis; Rosamond, Frances, Clustering with partial information, 144-155 [Zbl 1173.68596]
Böckenhauer, Hans-Joachim; Komm, Dennis, Reoptimization of the metric deadline TSP. (Extended abstract), 156-167 [Zbl 1173.90505]
Boyar, Joan; Matthews, Philip; Peralta, René, On the shortest linear straight-line program for computing linear forms, 168-179 [Zbl 1173.68875]
Brévilliers, Mathieu; Chevallier, Nicolas; Schmitt, Dominique, Flip algorithm for segment triangulations, 180-192 [Zbl 1173.68760]
Broersma, Hajo; Paulusma, Daniël, Computing sharp 2-factors in claw-free graphs, 193-204 [Zbl 1173.05348]
Caragiannis, Ioannis; Monaco, Gianpiero, A 6/5-approximation algorithm for the maximum 3-cover problem, 205-216 [Zbl 1173.90507]
Carayol, Arnaud; Slaats, Michaela, Positional strategies for higher-order pushdown parity games, 217-228 [Zbl 1173.68547]
Chakaravarthy, Venkatesan T.; Roy, Sambuddha, Arthur and Merlin as oracles, 229-240 [Zbl 1173.68524]
Charlier, Emilie; Rigo, Michel, A decision problem for ultimately periodic sets in non-standard numeration systems, 241-252 [Zbl 1173.68548]
Cherubini, Alessandra; Crespi Reghizzi, Stefano; Pradella, Matteo, Regional languages and tiling: A unifying approach to picture grammars, 253-264 [Zbl 1173.68549]
Czeizler, Elena; Kari, Lila; Seki, Shinnosuke, On a special class of primitive words, 265-277 [Zbl 1173.68618]
David, Claire, Complexity of data tree patterns over XML documents, 278-289 [Zbl 1173.68477]
Dragan, Feodor F.; Fomin, Fedor V.; Golovach, Petr A., A PTAS for the sparsest spanners problem on apex-minor-free graphs, 290-298 [Zbl 1173.68602]
Elberfeld, Michael; Tantau, Till, Computational complexity of perfect-phylogeny-related haplotyping problems, 299-310 [Zbl 1173.68536]
Erdélyi, Gábor; Nowak, Markus; Rothe, Jörg, Sincere-strategy preference-based approval voting broadly resists control, 311-322 [Zbl 1173.91351]
Finkel, Alain; Sangnier, Arnaud, Reversal-bounded counter machines revisited, 323-334 [Zbl 1173.68562]
Fomin, Fedor V.; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket, Iterative compression and exact algorithms, 335-346 [Zbl 1173.68537]
Fournier, Hervé; Gardy, Danièle; Genitrini, Antoine; Gittenberger, Bernhard, Complexity and limiting ratio of Boolean functions over implication, 347-362 [Zbl 1173.03301]
Gelade, Wouter, Succinctness of regular expressions with interleaving, intersection and counting, 363-374 [Zbl 1173.68552]
Guillon, Pierre; Richard, Gaétan, Nilpotency and limit sets of cellular automata, 375-386 [Zbl 1173.68572]
Hoàng, Chính T.; Kamiński, Marcin; Lozin, Vadim; Sawada, Joe; Shu, Xiao, A note on \(k\)-colorability of \(P _{5}\)-free graphs, 387-394 [Zbl 1173.05351]
Hundt, Christian; Liśkiewicz, Maciej, Combinatorial bounds and algorithmic aspects of image matching under projective transformations, 395-406 [Zbl 1173.68787]
Jansen, Maurice J., Lower bounds for syntactically multilinear algebraic branching programs, 407-418 [Zbl 1173.68520]
Kari, Jarkko; Ollinger, Nicolas, Periodicity and immortality in reversible computing, 419-430 [Zbl 1173.68521]
Klonowski, Marek; Krzywiecki, Łukasz; Kutyłowski, Mirosław; Lauks, Anna, Step-out ring signatures, 431-442 [Zbl 1173.94432]
Kufleitner, Manfred, The height of factorization forests, 443-454 [Zbl 1173.68567]
Mahajan, Meena; Raghavendra Rao, B. V., Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae, 455-466 [Zbl 1173.68522]
Manthey, Bodo; Tantau, Till, Smoothed analysis of binary search trees and quicksort under additive noise, 467-478 [Zbl 1173.68458]
Manzonetto, Giulio; Salibra, Antonino, From \(\lambda \)-calculus to universal algebra and back, 479-490 [Zbl 1173.03302]
Mardare, Radu; Policriti, Alberto, A complete axiomatic system for a process-based spatial logic, 491-502 [Zbl 1173.03307]
Mavronicolas, Marios; Monien, Burkhard; Papadopoulou, Vicky G.; Schoppmann, Florian, Voronoi games on cycle graphs, 503-514 [Zbl 1173.91327]
McGrae, Andrew R.; Zito, Michele, Colouring random empire trees, 515-526 [Zbl 1173.05322]
Muchnik, Andrei; Romashchenko, Andrei, A random oracle does not help extract the mutual information, 527-538 [Zbl 1173.68541]
Plociennik, Kai, Approximating independent set and coloring in random uniform hypergraphs, 539-550 [Zbl 1173.05341]
Raible, Daniel; Fernau, Henning, A new upper bound for Max-2-SAT: A graph-theoretic approach, 551-562 [Zbl 1173.68539]
Regnault, Damien, Directed percolation arising in stochastic cellular automata analysis, 563-574 [Zbl 1173.68577]
Rhodes, Mark, Resolution width and cutting plane rank are incomparable, 575-587 [Zbl 1173.03309]
Sakarovitch, Jacques; de Souza, Rodrigo, On the decidability of bounded valuedness for transducers. (Extended abstract), 588-600 [Zbl 1173.68557]
Szeider, Stefan, Monadic second order logic on graphs with local cardinality constraints, 601-612 [Zbl 1173.03300]
Wojdyga, Aleksander, Short proofs of strong normalization, 613-623 [Zbl 1173.03303]

MSC:
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Qxx Theory of computing
00B25 Proceedings of conferences of miscellaneous specific interest
PDF BibTeX XML Cite
Full Text: DOI