Catálogo de publicaciones - libros
Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August29-September 2. 2005, Proceedings
Joanna Jȩdrzejowicz ; Andrzej Szepietowski (eds.)
En conferencia: 30º International Symposium on Mathematical Foundations of Computer Science (MFCS) . Gdańsk, Poland . August 29, 2005 - September 2, 2005
Resumen/Descripción – provisto por la editorial
No disponible.
Palabras clave – provistas por la editorial
Theory of Computation; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Discrete Mathematics in Computer Science; Data Structures; Logics and Meanings of Programs
Disponibilidad
Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
---|---|---|---|---|
No detectada | 2005 | SpringerLink |
Información
Tipo de recurso:
libros
ISBN impreso
978-3-540-28702-5
ISBN electrónico
978-3-540-31867-5
Editor responsable
Springer Nature
País de edición
Reino Unido
Fecha de publicación
2005
Información sobre derechos de publicación
© Springer-Verlag Berlin Heidelberg 2005
Cobertura temática
Tabla de contenidos
doi: 10.1007/11549345_1
Page Migration in Dynamic Networks
Marcin Bienkowski; Friedhelm Meyer auf der Heide
In the last couple of decades, network connected systems have gradually replaced centralized parallel computing machines. To provide smooth operation of network applications, the underlying system has to provide so-called . One of the most crucial services is to provide a transparent access to data like variables, databases, memory pages, or .les, which are shared by the instances of programs running at nodes of the network.
- Invited Lectures | Pp. 1-14
doi: 10.1007/11549345_2
Knot Theory, Jones Polynomial and Quantum Computing
Rūsiņš Freivalds
Knot theory emerged in the nineteenth century for needs of physics and chemistry as these needs were understood those days. After that the interest of physicists and chemists was lost for about a century. Nowadays knot theory has made a comeback. Knot theory and other areas of topology are no more considered as abstract areas of classical mathematics remote from anything of practical interest. They have made deep impact on quantum field theory, quantum computation and complexity of computation.
- Invited Lectures | Pp. 15-25
doi: 10.1007/11549345_3
Interactive Algorithms 2005
Yuri Gurevich
A sequential algorithm just follows its instructions and thus cannot make a nondeterministic choice all by itself, but it can be instructed to solicit outside help to make a choice. Similarly, an object-oriented program cannot create a new object all by itself; a create-a-new-object command solicits outside help. These are but two examples of intra-step interaction of an algorithm with its environment. Here we motivate and survey recent work on interactive algorithms within the Behavioral Computation Theory project.
- Invited Lectures | Pp. 26-38
doi: 10.1007/11549345_4
Some Computational Issues in Membrane Computing
Oscar H. Ibarra
Membrane computing is a branch of molecular computing that aims to develop models and paradigms that are biologically motivated. It identifies an unconventional computing model, namely a P system, from natural phenomena of cell evolutions and chemical reactions. Because of the nature of maximal parallelism inherent in the model, P systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems (in much the same way as the promise of quantum and DNA computing) once future bio-technology (or silicon-technology) gives way to a practical bio-realization (or chip realization). Here we report on recent results that answer some interesting and fundamental open questions in the field. These concern computational issues such as determinism versus nondeterminism, membrane and alphabet-size hierarchies, and various notions of parallelism.
- Invited Lectures | Pp. 39-51
doi: 10.1007/11549345_5
The Generalization of Dirac’s Theorem for Hypergraphs
Endre Szemerédi; Andrzej Ruciński; Vojtěch Rödl
A substantial amount of research in graph theory continues to concentrate on the existence of hamiltonian cycles and perfect matchings. A classic theorem of Dirac states that a sufficient condition for an -vertex graph to be hamiltonian, and thus, for even, to have a perfect matching, is that the minimum degree is at least /2. Moreover, there are obvious counterexamples showing that this is best possible.
- Invited Lectures | Pp. 52-56
doi: 10.1007/11549345_6
On the Communication Complexity of Co-linearity Problems
Andrew C. Yao
In the -party simultaneous message model, –1 parties holding respectively ,, ⋯, wish to compute the value of some boolean function (,,..., ), by each sending a stochastically chosen message to a -th party, the , who then decides on the value of with probability at least 2/3 of being correct. Let () be the minimum number of total communication bits needed to compute by any such algorithm.
The (,)- is defined by (,,...,) = 1, if and only if ⊕=0 (where are -bit strings). It is well known that, for any fixed ≥ 3, , and that the bound is tight for =3. It is an interesting open question whether the bound is tight for >3. In this talk we present some new results on this question. Specifically, we prove that the above bound is tight in the , in which all the transmitted message bits are linear functions of the input bits. We also discuss ’s quantum communication complexity, which also has received considerable attention in recent years.
- Invited Lectures | Pp. 57-57
doi: 10.1007/11549345_7
An Invitation to Play
Wiesław Zielonka
Parity games and their subclasses and variants pop up in various contexts: -calculus, tree automata, program verification [3,1,8]. Such games provide only binary information indicating the winning player. However, in classical games theory [12] the emphasis is rather on how much we win or lose. Can we incorporate the information about the profits and losses into parity games?
- Invited Lectures | Pp. 58-70
doi: 10.1007/11549345_8
The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem
Eric Allender; Michael Bauland; Neil Immerman; Henning Schnoor; Heribert Vollmer
Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer’s dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are distinct if and only if P ≠ NP). We show that if one considers AC isomorphisms, then there are exactly six isomorphism types (assuming that the complexity classes NP, P, ⊕L, NL, and L are all distinct).
- Papers | Pp. 71-82
doi: 10.1007/11549345_9
On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions
César L. Alonso; Josè L. Montaña; Luis M. Pardo
Semi-algebraic objects are subsets or functions that can be described by finite boolean combinations of polynomials with real coefficients. In this paper we provide sharp estimates for the the precision and the number of trials needed in the MonteCarlo integration method to achieve a given error with a fixed confidence when approximating the mean value of semi-algebraic functions. Our study extends to the functional case the results of P. Koiran ([7]) for approximating the volume of semi-algebraic sets.
- Papers | Pp. 83-94
doi: 10.1007/11549345_10
Pure Nash Equilibria in Games with a Large Number of Actions
Carme Àlvarez; Joaquim Gabarró; Maria Serna
We study the computational complexity of deciding the existence of a Pure Nash Equilibrium in multi-player strategic games. We address two fundamental questions: how can we represent a game? and how can we represent a game with polynomial pay-off functions? Our results show that the computational complexity of deciding the existence of a pure Nash equilibrium in a strategic game depends on two parameters: the number of players and the size of the sets of strategies. In particular we show that deciding the existence of a Nash equilibrium in a strategic game is NP-complete when the number of players is large and the number of strategies for each player is constant, while the problem is Σ-complete when the number of players is a constant and the size of the sets of strategies is exponential (with respect to the length of the strategies).
- Papers | Pp. 95-106