Skip to main content
  • Conference proceedings
  • © 2005

Mathematical Foundations of Computer Science 2005

30th International Symposium, MFCS 2005, Gdansk, Poland, August29-September 2. 2005, Proceedings

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 3618)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Conference series link(s): MFCS: International Symposium on Mathematical Foundations of Computer Science

Conference proceedings info: MFCS 2005.

Buy it now

Buying options

eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (69 papers)

  1. Front Matter

  2. Invited Lectures

    1. Page Migration in Dynamic Networks

      • Marcin Bienkowski, Friedhelm Meyer auf der Heide
      Pages 1-14
    2. Knot Theory, Jones Polynomial and Quantum Computing

      • Rūsiņš Freivalds
      Pages 15-25
    3. Interactive Algorithms 2005

      • Yuri Gurevich
      Pages 26-38
    4. The Generalization of Dirac’s Theorem for Hypergraphs

      • Endre Szemerédi, Andrzej Ruciński, Vojtěch Rödl
      Pages 52-56
    5. An Invitation to Play

      • Wiesław Zielonka
      Pages 58-70
  3. Papers

    1. The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem

      • Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer
      Pages 71-82
    2. On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions

      • César L. Alonso, Josè L. Montaña, Luis M. Pardo
      Pages 83-94
    3. Pure Nash Equilibria in Games with a Large Number of Actions

      • Carme Àlvarez, Joaquim Gabarró, Maria Serna
      Pages 95-106
    4. On the Complexity of Depth-2 Circuits with Threshold Gates

      • Kazuyuki Amano, Akira Maruoka
      Pages 107-118
    5. Isomorphic Implication

      • Michael Bauland, Edith Hemaspaandra
      Pages 119-130
    6. Abstract Numeration Systems and Tilings

      • Valérie Berthé, Michel Rigo
      Pages 131-143
    7. Adversarial Queueing Model for Continuous Network Dynamics

      • María J. Blesa, Daniel Calzada, Antonio Fernández, Luis López, Andrés L. Martínez, Agustín Santos et al.
      Pages 144-155
    8. Regular Sets of Higher-Order Pushdown Stacks

      • Arnaud Carayol
      Pages 168-179
    9. Linearly Bounded Infinite Graphs

      • Arnaud Carayol, Antoine Meyer
      Pages 180-191
    10. Basic Properties for Sand Automata

      • J. Cervelle, E. Formenti, B. Masson
      Pages 192-211

Other Volumes

  1. Mathematical Foundations of Computer Science 2005

Editors and Affiliations

  • Institute of Mathematics, Gdansk University, Gdansk, Poland

    Joanna Jȩdrzejowicz, Andrzej Szepietowski

Bibliographic Information

Buy it now

Buying options

eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access