[TYPES/announce] MFCS 2006 accepted papers

[Pawel Urzyczyn]

                      MFCS 2006 - accepted papers

Viliam Geffert. Magic Numbers in the State Hierarchy of Finite Automata

Pascal Koiran and Sylvain Prifel. Valiant's model: from exponential sums 
to exponential products

Rodrigo Leo and Valmir Barbosa. Minimal Chordal Sense of Direction and 
Circulant Graphs

Petr Hlineny. On Matroid Representability and Minor Problems

Yury Lifshits and Markus Lohrey. Querying and Embedding Compressed Texts

Linh Anh Nguyen. The Data Complexity of MDatalog in Basic Modal Logics

Sergey Goncharov, Lutz Schrder and Till Mossakowski. Completeness of 
Global Evaluation Logic

Lance Fortnow and Mitsunori Ogihara. Very Sparse Leaf Languages

Christian Glasser and Stephen David Travers. Machines that can Output 
Empty Words

Johanne Cohen, Fedor Fomin, Pinar Heggernes, Dieter Kratsch and Gregory 
Kucherov. Optimal Linear Arrangement of Interval Graphs

Marcin Kik. Sorting Long Sequence in a Single Hop Radio Network

Peter Jonsson and Gustav Nordh. Generalised Integer Programming Based 
on Logically Defined Relations

F. Blanchet-Sadri, D. Dakota Blair and Rebeca V. Lewis. Equations on 
Partial Words

Martin Kutrib and Andreas Malcher. Fast Iterative Arrays with Restricted 
Inter-Cell Communication: Constructions and Decidability

Fredrik Kuivinen. Approximability of Bounded Occurrence Max Ones

Miroslaw Dynia, Jaroslaw Kutylowski, Friedhelm Meyer auf der Heide and 
Christian Schindelhauer. Smart Robot Teams Exploring Sparse Trees

Sorin Constantinescu and Lucian Ilie. The Lempel--Ziv complexity of fixed 
points of morphisms

Richard Beigel, William Gasarch and James Glenn. The Multiparty Communication 
Complexity of Exact-T

Xiaoyang Gu and Jack H. Lutz. Dimension Characterizations of Complexity Classes

Anna Gal and Vladimir Trifonov. On the Correlation Between Parity and Modular 
Polynomials

Refael Hassin, Jerome Monnot and Danny Segev. Approximation Algorithms and 
Hardness Results for Labeled Connectivity Problems

Giuseppe Persiano and Ivan Visconti. On Non-Interactive Zero-Knowledge Proofs 
of Knowledge in the Shared Random String Model

Christopher Homan and Lane A. Hemaspaandra. Guarantees for the Success 
Frequency of an Algorithm for Finding Dodgson-Election Winners

Jianer Chen, Iyad kanj and Ge Xia. Improved Parameterized Upper Bounds for 
Vertex Cover

A.N. Trahtman. An efficient algorithm finds noticeable trends and
examples concerning the Cerny conjecture

Alessandra Savelli and Jean Berstel. Crochemore factorization of
Sturmian and other infinite words

Michael Domaratzki and Kai Salomaa. Lower Bounds for the Transition
Complexity of NFAs

Andre Gronemeier. NOF-Multiparty Information Complexity Bounds for
Pointer Jumping

Alessandra Cherubini, Pawel Gawrychowski, Andrzej Kisielewicz and
Brunetto Piochi. A Combinatorial Approach to Collapsing Words

Alexander Kostin. A Reachability Algorithm for General Petri Nets
Based on Transition Invariants

Guillaume Malod and Natacha Portier. Characterizing Valiant's
algebraic complexity classes

Adele Rescigno and Luisa Gargano. Optimally Fast Data Gathering in
Sensor Networks

Beat Gfeller, Leon Peeters, Birgitta Weber and Peter Widmayer. Online
Single Machine Batch Scheduling

VIkraman Arvind and Piyush P Kurur. A Polynomial Time Nilpotence Test
for Galois Groups and Related Results

Francois Le Gall. Quantum Weakly Nondeterministic Communication
Complexity

Tomasz Jurdzinski. Probabilistic Length-Reducing Automata

Volker Diekert, Markus Lohrey and Alexander Miller. Partially
commutative inverse monoids

Sasanka Roy, Arindam Karmakar, Sandip Das and Subhas
C. Nandy. Constrained Minimum Enclosing Circle with Center on a Query
Line Segment

Norbert Dojer. A polynomial-time algorithm for learning Bayesian
networks from data

Slawomir Lasota and Wojciech Rytter. Faster Algorithm for Bisimulation
Equivalence of Normed Context-Free Processes

Arturo Carpi. On the repetition threshold for large alphabets

Wael El-Oraiby and Dominique Schmitt. $k$-sets of convex inclusion
chains of planar point sets

Oswin Aichholzer, Clemens Huemer, Sarah Kappes, Bettina Speckmann and
Csaba D. Toth. On Decompositions, Partitions, and Coverings with
Convex Polygons and Pseudo-Triangles

Martin Hoefer. Non-cooperative Tree Creation

Guillaume Theyssier, Victor Poupet and Laurent Boyer. On the
Complexity of Limit Sets of Cellular Automata Associated with
Probability Measures

Qi Cheng. On comparing sums of square roots of small integers

Angelo Fanelli, Michele Flammini, Giovanna Melideo and Luca
Moscardelli. Multicast Transmissions in Non-Cooperative Networks with
a Limited Number of Selfish Moves

Ulrik Brandes and Juergen Lerner. Coloring Random 3-Colorable Graphs
with Non-Uniform Edge Probabilities

Pablo Arrighi. Algebraic characterizations of unitary one dimensional
quantum cellular automata

Aris Pagourtzis and Stathis Zachos. The Complexity of Counting
Functions with Easy Decision Version

Damian Wojtowicz and Jerzy Tiuryn. On genome evolution with innovation

Lyudmil Aleksandrov, Hristo N. Djidjev, Hua Guo, Anil Maheshwari,
Doron Nussbaum and Jorg Sack. Approximate Shortest Path Queries on
Weighted Polyhedral Surfaces

Kazuo Iwama and Hiroki Morizumi. Reductions for Monotone Boolean
Circuits

Yoram Hirshfeld and Alexander Rabinovich. An Expressive Temporal Logic
for Real Time

Ondrej Klima, Benoit Larose and Pascal Tesson. Systems of Equations
over Finite Semigroups and the #CSP Dichotomy Conjecture

Rahul Tripathi. Hierarchical Unambiguity

Cyril Allauzen and Mehryar Mohri. A Unified Construction of the
Glushkov, Follow, and Antimirov Automata

Maria Lopez-Valdes. Lempel-Ziv Dimension for Lempel-Ziv Compression

Marios Mavronicolas, Loizos Michael, Vicky Papadopoulou, Anna
Philippou and Paul Spirakis. The Price of Defense

rene peralta and Joan Boyar. Concrete multiplicative complexity of
symmetric functions

Robert Elsaesser. Toward the Eigenvalue Power Law

Arnaud Carayol and Didier Caucal. The Kleene equality for graphs
-----------------------------------------------------------------