31. MFCS 2006: Stará Lesná, Slovakia

Invited Talks

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

Contributed Papers

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

Last update Fri May 17 15:39:02 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page