31. MFCS 2006: Stará Lesná, Slovakia

Rastislav Kralovic, Pawel Urzyczyn (Eds.): Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings. Lecture Notes in Computer Science 4162 Springer 2006, ISBN 3-540-37791-3 BibTeX

Invited Talks

Vincent Cremet, François Garillot, Sergueï Lenglet, Martin Odersky:
A Core Calculus for Scala Type Checking. 1-23
Electronic Edition (link) BibTeX
Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc:
Tree Exploration with an Oracle. 24-37
Electronic Edition (link) BibTeX
Cyril Gavoille:
Distributed Data Structures: A Survey on Informative Labeling Schemes. 38
Electronic Edition (link) BibTeX
Herman Geuvers, Iris Loeb:
From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of Deductions. 39-57
Electronic Edition (link) BibTeX
Martin Grohe:
The Structure of Tractable Constraint Satisfaction Problems. 58-72
Electronic Edition (link) BibTeX
Dexter Kozen:
On the Representation of Kleene Algebras with Tests. 73-83
Electronic Edition (link) BibTeX
Ming Li:
From Three Ideas in TCS to Three Applications in Bioinformatics. 84-85
Electronic Edition (link) BibTeX

Contributed Papers

Oswin Aichholzer, Clemens Huemer, S. Kappes, Bettina Speckmann, Csaba D. Tóth:
Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles. 86-97
Electronic Edition (link) BibTeX
Lyudmil Aleksandrov, Hristo Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jörg-Rüdiger Sack:
Approximate Shortest Path Queries on Weighted Polyhedral Surfaces. 98-109
Electronic Edition (link) BibTeX
Cyril Allauzen, Mehryar Mohri:
A Unified Construction of the Glushkov, Follow, and Antimirov Automata. 110-121
Electronic Edition (link) BibTeX
Pablo Arrighi:
Algebraic Characterizations of Unitary Linear Quantum Cellular Automata. 122-133
Electronic Edition (link) BibTeX
Vikraman Arvind, Piyush P. Kurur:
A Polynomial Time Nilpotence Test for Galois Groups and Related Results. 134-145
Electronic Edition (link) BibTeX
Richard Beigel, William I. Gasarch, James Glenn:
The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems. 146-156
Electronic Edition (link) BibTeX
Jean Berstel, Alessandra Savelli:
Crochemore Factorization of Sturmian and Other Infinite Words. 157-166
Electronic Edition (link) BibTeX
Francine Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis:
Equations on Partial Words. 167-178
Electronic Edition (link) BibTeX
Joan Boyar, René Peralta:
Concrete Multiplicative Complexity of Symmetric Functions. 179-189
Electronic Edition (link) BibTeX
Laurent Boyer, Victor Poupet, Guillaume Theyssier:
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures. 190-201
Electronic Edition (link) BibTeX
Ulrik Brandes, Jürgen Lerner:
Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities. 202-213
Electronic Edition (link) BibTeX
Arnaud Carayol, Didier Caucal:
The Kleene Equality for Graphs. 214-225
Electronic Edition (link) BibTeX
Arturo Carpi:
On the Repetition Threshold for Large Alphabets. 226-237
Electronic Edition (link) BibTeX
Jianer Chen, Iyad A. Kanj, Ge Xia:
Improved Parameterized Upper Bounds for Vertex Cover. 238-249
Electronic Edition (link) BibTeX
Qi Cheng:
On Comparing Sums of Square Roots of Small Integers. 250-255
Electronic Edition (link) BibTeX
Alessandra Cherubini, Pawel Gawrychowski, Andrzej Kisielewicz, B. Piochi:
A Combinatorial Approach to Collapsing Words. 256-266
Electronic Edition (link) BibTeX
Johanne Cohen, Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Gregory Kucherov:
Optimal Linear Arrangement of Interval Graphs. 267-279
Electronic Edition (link) BibTeX
Sorin Constantinescu, Lucian Ilie:
The Lempel-Ziv Complexity of Fixed Points of Morphisms. 280-291
Electronic Edition (link) BibTeX
Volker Diekert, Markus Lohrey, Alexander Miller:
Partially Commutative Inverse Monoids. 292-304
Electronic Edition (link) BibTeX
Norbert Dojer:
Learning Bayesian Networks Does Not Have to Be NP-Hard. 305-314
Electronic Edition (link) BibTeX
Michael Domaratzki, Kai Salomaa:
Lower Bounds for the Transition Complexity of NFAs. 315-326
Electronic Edition (link) BibTeX
Miroslaw Dynia, Jaroslaw Kutylowski, Friedhelm Meyer auf der Heide, Christian Schindelhauer:
Smart Robot Teams Exploring Sparse Trees. 327-338
Electronic Edition (link) BibTeX
Wael El Oraiby, Dominique Schmitt:
k-Sets of Convex Inclusion Chains of Planar Point Sets. 339-350
Electronic Edition (link) BibTeX
Robert Elsässer:
Toward the Eigenvalue Power Law. 351-362
Electronic Edition (link) BibTeX
Angelo Fanelli, Michele Flammini, Giovanna Melideo, Luca Moscardelli:
Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves. 363-374
Electronic Edition (link) BibTeX
Lance Fortnow, Mitsunori Ogihara:
Very Sparse Leaf Languages. 375-386
Electronic Edition (link) BibTeX
Anna Gál, Vladimir Trifonov:
On the Correlation Between Parity and Modular Polynomials. 387-398
Electronic Edition (link) BibTeX
Luisa Gargano, Adele A. Rescigno:
Optimally Fast Data Gathering in Sensor Networks. 399-411
Electronic Edition (link) BibTeX
Viliam Geffert:
Magic Numbers in the State Hierarchy of Finite Automata. 412-423
Electronic Edition (link) BibTeX
Beat Gfeller, Leon Peeters, Birgitta Weber, Peter Widmayer:
Online Single Machine Batch Scheduling. 424-435
Electronic Edition (link) BibTeX
Christian Glaßer, Stephen D. Travers:
Machines that Can Output Empty Words. 436-446
Electronic Edition (link) BibTeX
Sergey Goncharov, Lutz Schröder, Till Mossakowski:
Completeness of Global Evaluation Logic. 447-458
Electronic Edition (link) BibTeX
Andre Gronemeier:
NOF-Multiparty Information Complexity Bounds for Pointer Jumping. 459-470
Electronic Edition (link) BibTeX
Xiaoyang Gu, Jack H. Lutz:
Dimension Characterizations of Complexity Classes. 471-479
Electronic Edition (link) BibTeX
Refael Hassin, Jérôme Monnot, Danny Segev:
Approximation Algorithms and Hardness Results for Labeled Connectivity Problems. 480-491
Electronic Edition (link) BibTeX
Yoram Hirshfeld, Alexander Moshe Rabinovich:
An Expressive Temporal Logic for Real Time. 492-504
Electronic Edition (link) BibTeX
Petr Hlinený:
On Matroid Representability and Minor Problems. 505-516
Electronic Edition (link) BibTeX
Martin Hoefer:
Non-cooperative Tree Creation. 517-527
Electronic Edition (link) BibTeX
Christopher M. Homan, Lane A. Hemaspaandra:
Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners. 528-539
Electronic Edition (link) BibTeX
Kazuo Iwama, Hiroki Morizumi:
Reductions for Monotone Boolean Circuits. 540-548
Electronic Edition (link) BibTeX
Peter Jonsson, Gustav Nordh:
Generalised Integer Programming Based on Logically Defined Relations. 549-560
Electronic Edition (link) BibTeX
Tomasz Jurdzinski:
Probabilistic Length-Reducing Automata. 561-572
Electronic Edition (link) BibTeX
Marcin Kik:
Sorting Long Sequences in a Single Hop Radio Network. 573-583
Electronic Edition (link) BibTeX
Ondrej Klíma, Benoit Larose, Pascal Tesson:
Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture. 584-595
Electronic Edition (link) BibTeX
Pascal Koiran, Sylvain Perifel:
Valiant's Model: From Exponential Sums to Exponential Products. 596-607
Electronic Edition (link) BibTeX
Alexander E. Kostin:
A Reachability Algorithm for General Petri Nets Based on Transition Invariants. 608-621
Electronic Edition (link) BibTeX
Fredrik Kuivinen:
Approximability of Bounded Occurrence Max Ones. 622-633
Electronic Edition (link) BibTeX
Martin Kutrib, Andreas Malcher:
Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability. 634-645
Electronic Edition (link) BibTeX
Slawomir Lasota, Wojciech Rytter:
Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes. 646-657
Electronic Edition (link) BibTeX
François Le Gall:
Quantum Weakly Nondeterministic Communication Complexity. 658-669
Electronic Edition (link) BibTeX
Rodrigo S. C. Leão, Valmir C. Barbosa:
Minimal Chordal Sense of Direction and Circulant Graphs. 670-680
Electronic Edition (link) BibTeX
Yury Lifshits, Markus Lohrey:
Querying and Embedding Compressed Texts. 681-692
Electronic Edition (link) BibTeX
María López-Valdés:
Lempel-Ziv Dimension for Lempel-Ziv Compression. 693-703
Electronic Edition (link) BibTeX
Guillaume Malod, Natacha Portier:
Characterizing Valiant's Algebraic Complexity Classes. 704-716
Electronic Edition (link) BibTeX
Marios Mavronicolas, Loizos Michael, Vicky G. Papadopoulou, Anna Philippou, Paul G. Spirakis:
The Price of Defense. 717-728
Electronic Edition (link) BibTeX
Linh Anh Nguyen:
The Data Complexity of MDatalog in Basic Modal Logics. 729-740
Electronic Edition (link) BibTeX
Aris Pagourtzis, Stathis Zachos:
The Complexity of Counting Functions with Easy Decision Version. 741-752
Electronic Edition (link) BibTeX
Giuseppe Persiano, Ivan Visconti:
On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model. 753-764
Electronic Edition (link) BibTeX
Sasanka Roy, Arindam Karmakar, Sandip Das, Subhas C. Nandy:
Constrained Minimum Enclosing Circle with Center on a Query Line Segment. 765-776
Electronic Edition (link) BibTeX
Holger Spakowski, Rahul Tripathi:
Hierarchical Unambiguity. 777-788
Electronic Edition (link) BibTeX
A. N. Trahtman:
An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Cerny Conjecture. 789-800
Electronic Edition (link) BibTeX
Damian Wójtowicz, Jerzy Tiuryn:
On Genome Evolution with Innovation. 801-811
Electronic Edition (link) BibTeX