30. MFCS 2005:
Gdansk,
Poland
Joanna Jedrzejowicz, Andrzej Szepietowski (Eds.):
Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005, Proceedings.
Lecture Notes in Computer Science 3618 Springer 2005, ISBN 3-540-28702-7 BibTeX
Invited Lectures
Papers
- Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer:
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
71-82
Electronic Edition (link) BibTeX
- César Luis Alonso, José Luis Montaña, Luis Miguel Pardo:
On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions.
83-94
Electronic Edition (link) BibTeX
- Carme Àlvarez, Joaquim Gabarró, Maria J. Serna:
Pure Nash Equilibria in Games with a Large Number of Actions.
95-106
Electronic Edition (link) BibTeX
- Kazuyuki Amano, Akira Maruoka:
On the Complexity of Depth-2 Circuits with Threshold Gates.
107-118
Electronic Edition (link) BibTeX
- Michael Bauland, Edith Hemaspaandra:
Isomorphic Implication.
119-130
Electronic Edition (link) BibTeX
- Valérie Berthé, Michel Rigo:
Abstract Numeration Systems and Tilings.
131-143
Electronic Edition (link) BibTeX
- Maria J. Blesa, Daniel Calzada, Antonio Fernández, Luis López, Andrés L. Martínez, Agustín Santos, Maria J. Serna:
Adversarial Queueing Model for Continuous Network Dynamics.
144-155
Electronic Edition (link) BibTeX
- Julia Böttcher:
Coloring Sparse Random k-Colorable Graphs in Polynomial Expected Time.
156-167
Electronic Edition (link) BibTeX
- Arnaud Carayol:
Regular Sets of Higher-Order Pushdown Stacks.
168-179
Electronic Edition (link) BibTeX
- Arnaud Carayol, Antoine Meyer:
Linearly Bounded Infinite Graphs.
180-191
Electronic Edition (link) BibTeX
- Julien Cervelle, Enrico Formenti, Benoît Masson:
Basic Properties for Sand Automata.
192-211
Electronic Edition (link) BibTeX
- Jérémie Chalopin, Yves Métivier:
A Bridge Between the Asynchronous Message Passing Model and Local Computations in Graphs.
212-223
Electronic Edition (link) BibTeX
- Ho-Leung Chan, Jesper Jansson, Tak Wah Lam, Siu-Ming Yiu:
Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix.
224-235
Electronic Edition (link) BibTeX
- Wun-Tat Chan, Tak Wah Lam, Kin-Shing Liu, Prudence W. H. Wong:
New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling.
236-247
Electronic Edition (link) BibTeX
- Ho-Lun Cheng, Tony Tan:
Approximating Polygonal Objects by Deformable Smooth Surfaces.
248-259
Electronic Edition (link) BibTeX
- Dimitri Chubarov, Andrei Voronkov:
Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications.
260-270
Electronic Edition (link) BibTeX
- Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Ugo Vaccaro:
Asynchronous Deterministic Rendezvous in Graphs.
271-282
Electronic Edition (link) BibTeX
- David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, Philippe Moser:
Zeta-Dimension.
283-294
Electronic Edition (link) BibTeX
- Leah Epstein, Meital Levy:
Online Interval Coloring with Packing Constraints.
295-307
Electronic Edition (link) BibTeX
- Piotr Faliszewski, Mitsunori Ogihara:
Separating the Notions of Self- and Autoreducibility.
308-315
Electronic Edition (link) BibTeX
- Nazim Fatès, Michel Morvan, Nicolas Schabanel, Eric Thierry:
Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata.
316-327
Electronic Edition (link) BibTeX
- Guillaume Fertin, Romeo Rizzi, Stéphane Vialette:
Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs.
328-339
Electronic Edition (link) BibTeX
- Jirí Fiala, Daniël Paulusma, Jan Arne Telle:
Matrix and Graph Orders Derived from Locally Constrained Graph Homomorphisms.
340-351
Electronic Edition (link) BibTeX
- Aleksei V. Fishkin, Olga Gerber, Klaus Jansen, Roberto Solis-Oba:
Packing Weighted Rectangles into a Square.
352-363
Electronic Edition (link) BibTeX
- Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse:
Nondeterministic Graph Searching: From Pathwidth to Treewidth.
364-375
Electronic Edition (link) BibTeX
- Joxe Gaintzarain, Montserrat Hermo, Marisa Navarro:
Goals in the Propositional Horn Language Are Monotone Boolean Circuits.
376-386
Electronic Edition (link) BibTeX
- Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang:
Autoreducibility, Mitoticity, and Immunity.
387-398
Electronic Edition (link) BibTeX
- Christian Glaßer, Alan L. Selman, Liyu Zhang:
Canonical Disjoint NP-Pairs of Propositional Proof Systems.
399-409
Electronic Edition (link) BibTeX
- Judy Goldsmith, Matthias Hagen, Martin Mundhenk:
Complexity of DNF and Isomorphism of Monotone Formulas.
410-421
Electronic Edition (link) BibTeX
- Martin Grohe, Stephan Kreutzer, Nicole Schweikardt:
The Expressive Power of Two-Variable Least Fixed-Point Logics.
422-434
Electronic Edition (link) BibTeX
- Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov:
Languages Representable by Vertex-Labeled Graphs.
435-446
Electronic Edition (link) BibTeX
- Leonid Gurvits:
On the Complexity of Mixed Discriminants and Related Problems.
447-458
Electronic Edition (link) BibTeX
- Uffe Flarup Hansen, Klaus Meer:
Two Logical Hierarchies of Optimization Problems over the Real Numbers.
459-470
Electronic Edition (link) BibTeX
- Bernhard Heinemann:
Algebras as Knowledge Structures.
471-482
Electronic Edition (link) BibTeX
- André Hernich, Arfst Nickelsen:
Combining Self-reducibility and Partial Information Algorithms.
483-494
Electronic Edition (link) BibTeX
- Paul Hunter, Anuj Dawar:
Complexity Bounds for Regular Games.
495-506
Electronic Edition (link) BibTeX
- Ryszard Janicki:
Basic Mereology with Equivalence Relations.
507-519
Electronic Edition (link) BibTeX
- Jesper Jansson, Zeshan Peng:
Online and Dynamic Recognition of Squarefree Strings.
520-531
Electronic Edition (link) BibTeX
- Tomasz Jurdzinski, Friedrich Otto:
Shrinking Restarting Automata.
532-543
Electronic Edition (link) BibTeX
- Christos A. Kapoutsis:
Removing Bidirectionality from Nondeterministic Finite Automata.
544-555
Electronic Edition (link) BibTeX
- Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich:
Generating All Minimal Integral Solutions to Monotone and, or-Systems of Linear, Transversal and Polymatroid Inequalities.
556-567
Electronic Edition (link) BibTeX
- Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith:
On the Parameterized Complexity of Exact Satisfiability Problems.
568-579
Electronic Edition (link) BibTeX
- Petr Kolman:
Approximating Reversal Distance for Strings with Bounded Number of Duplicates.
580-590
Electronic Edition (link) BibTeX
- Konstantin Korovin, Andrei Voronkov:
Random Databases and Threshold for Monotone Non-recursive Datalog.
591-602
Electronic Edition (link) BibTeX
- Daniel Král, Ondrej Pangrác:
An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems.
603-614
Electronic Edition (link) BibTeX
- Piotr Krysta:
Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing.
615-627
Electronic Edition (link) BibTeX
- Fredrik Kuivinen:
Tight Approximability Results for the Maximum Solution Equation Problem over Zp.
628-639
Electronic Edition (link) BibTeX
- Martin Lange, Rafal Somla:
The Complexity of Model Checking Higher Order Fixpoint Logic.
640-651
Electronic Edition (link) BibTeX
- Minming Li, Frances F. Yao:
An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules.
652-663
Electronic Edition (link) BibTeX
- Markus Lohrey, Nicole Ondrusch:
Inverse Monoids: Decidability and Complexity of Algebraic Questions.
664-675
Electronic Edition (link) BibTeX
- María López-Valdés, Elvira Mayordomo:
Dimension Is Compression.
676-685
Electronic Edition (link) BibTeX
- Rémi Morin:
Concurrent Automata vs. Asynchronous Systems.
686-698
Electronic Edition (link) BibTeX
- Hidenosuke Nishio:
Completeness and Degeneracy in Information Dynamics of Cellular Automata.
699-707
Electronic Edition (link) BibTeX
- Alexander Okhotin:
Strict Language Inequalities and Their Decision Problems.
708-719
Electronic Edition (link) BibTeX
- G. Michele Pinna:
Event Structures for the Collective Tokens Philosophy of Inhibitor Nets.
720-732
Electronic Edition (link) BibTeX
- Tobias Riege, Jörg Rothe:
An Exact 2.9416n Algorithm for the Three Domatic Number Problem.
733-744
Electronic Edition (link) BibTeX
- Mohammad Ali Safari:
D-Width: A More Natural Measure for Directed Tree Width.
745-756
Electronic Edition (link) BibTeX
- Jakob Grue Simonsen:
On Beta-Shifts Having Arithmetical Languages.
757-768
Electronic Edition (link) BibTeX
- Jaco van de Pol, Olga Tveretina:
A BDD-Representation for the Logic of Equality and Uninterpreted Functions.
769-780
Electronic Edition (link) BibTeX
- Falk Unger:
On Small Hard Leaf Languages.
781-792
Electronic Edition (link) BibTeX
- Virginia Vassilevska:
Explicit Inapproximability Bounds for the Shortest Superstring Problem.
793-800
Electronic Edition (link) BibTeX
- Michal Wrona:
Stratified Boolean Grammars.
801-812
Electronic Edition (link) BibTeX
Copyright © Sat May 16 23:29:35 2009
by Michael Ley (ley@uni-trier.de)
