MFCS'98: Accepted Papers

Gaussian elimination and a characterization of algebraic power series
                     by Werner Kuich

Flow Logic for Imperative Objects
                     by Flemming Nielson, Hanne Riis Nielson

Locally explicit construction of Rodl's asymptotically good packings
                     by Nikolai N. Kuzjurin

Combinatorial Hardness Proofs for Polynomial Evaluation
                     by Mikel ALDAZ, Joos HEINTZ, Guillermo MATERA, Jose L. MONTANA, Luis M. PARDO

On One-pass Term Rewriting
                     by Zoltan Fulop, Eija Jurvanen, Magnus Steinby, Sandor Vagvolgyi

On some recognizable picture-languages
                     by Klaus Reinhardt

Blockwise Variable Orderings for Shared BDDs
                     by Harry Preuss, Anand Srivastav

Topological Definitions of Chaos applied to Cellular Automata Dynamics
                     by G. Cattane, L. Margara

Shuffle on trajectories: a simplified approach to the Schutzenberger product and related operations
                     by Tero Harju, Alexandru Mateescu, Arto Salomaa

Equations in transfinite strings
                     by Christian Choffrut, Sandor Horvath

A Finite Hierarchy of the Recursively Enumerable Real Numbers
                     by Klaus Weihrauch, Xizhong Zheng

Minimal forbidden words and factor automata
                     by M. Crochemore, F. Mignosi, A. Restivo

Communication complexity and Lower Bounds on Multilective Computations
                     by Juraj Hromkovic

On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations
                     by Miki Hermann, Gernot Salzer

Characterization of Sensitive Linear Cellular Automata with Respect to the Counting Distance
                     by giovanni manzini

Average-Case Intractability vs. Worst-Case Intractability
                     by Johannes Koebler, Rainer Schuler

One Quantifier Will Do in Existential Monadic Second-Order Logic over Pictures
                     by Oliver Matz

A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem
                     by Lane A. Hemaspaandra, Joerg Rothe

On repetition-free binary words of minimal density
                     by Roman Kolpakov, Gregory Kucherov, Yuri Tarannikov

Encoding the Hydra Battle as a rewrite system
                     by H. Touzet

Lazy Functional Algorithms for Exact Real Functionals
                     by Alex K. Simpson

Locality of order-invariant first-order formulas
                     by Martin Grohe, Thomas Schwentick

Spatial and Temporal Refinement of Typed Graph Transformation Systems
                     by M. Grosse--Rhode, F. Parisi--Presicce, M. Simeoni

Predicative Polymorphic Subtyping
                     by Marcin Benke

On defect effect of bi-infinite words
                     by Juhani Karhumaeki, Jan Manuch, Wojciech Plandowski

Tally NP Sets and Easy Census Functions
                     by Judy Goldsmith, Mitsunori Ogihara, Joerg Rothe

Minimum Propositional Proof Length is NP-Hard to Linearly Approximate
                     by Michael Alekhnovich, Sam Buss, Shlomo Moran, Toniann Pitassi

A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)loglog n Negation Gates
                     by Kazuyuki Amano, Akira Maruoka

Degree-preserving forests
                     by Hajo Broersma, Andreas Huck, Ton Kloks,Otto Koppius, Dieter Kratsch, Haiko Mueller, Hilde Tuinstra

The semi-full closure of Pure Type Systems
                     by Gilles Barthe

Proof Theory of Fuzzy Logics: Urquhart's C and Related Logics
                     by Matthias Baaz, Agata Ciabattoni, Christian Fermueller, Helmut Veith

Facial circuits of planar graphs and context-free languages.
                     by Bruno Courcelle, Denis Lapoire

The equivalence problem for deterministic pushdown transducers into abelian groups
                     by Geraud SENIZERGUES

Nonstochastic languages being projections of 2-tape quasideterministic languages
                     by Richard Bonner, Rusins Freivalds, Janis Lapins, Antra Lukjanska

forallexists^ast-Equational Theory of Context Unification is Pi_1^0-Hard
                     by Sergei Vorobyov

Tree decompositions of small diameter
                     by Hans L. Bodlaender, Torben Hagerup

Speeding-up Nondeterministic Single-Tape Off-Line Computations by One Alterantion
                     by Jiri Wiedermann

Iterated Length-Preserving Transductions
                     by Michel Latteux, David Simplot, Alain Terlutte

Comparison between the complexity of a function and the complexity of its graph
                     by Bruno Durand, Sylvain Porrot

Representing Hyper-Graphs by Regular Languages
                     by Salvatore La Torre, Margherita Napoli

Computing epsilon-Free NFA from Regular Expressions in O(n log^2(n)) Time
                     by Christian Hagenah, Anca Muscholl

Reducing AC-Termination to Termination
                     by Maria Ferreira, Delia Kesner, Laurence Puel

About Synchronization Languages
                     by Isabelle Ryl, Yves Roos, Mireille Clerbout

A (non-elementary) modular decision procedure for LTrL
                     by Paul Gastin, Raphael Meyer, Antoine Petit

When Can an Equational Simple Graph Be Generated by Hyperedge Replacement?
                     by Klaus Barthelmann

Positive Turing and Truth-Table Completeness for NEXP Are Incomparable
                     by Levke Bentzien

Improved Time and Space Hierarchies of One-Tape Off-Line TMs
                     by Kazuo Iwama, Chuzo Iwamoto

Deadlocking States in Context-free Process Algebra
                     by Jiri Srba

Expressive Completeness of Temporal Logic of Action
                     by Alexander Rabinovich

On the Complexity of Wavelength Converters
                     by Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano

Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets
                     by Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt

A Parallelization of Dijkstra's Shortest Path Algorithm
                     by A. Crauser, K. Mehlhorn, U. Meyer, P. Sanders

D0L-Systems and Surface Automorphisms
                     by Luis-Miguel Lopez, Philippe Narbel

Probabilistic Concurrent Constraint Programming: Towards a Fully Abstract Model
                     by Alessandra Di Pierro, Herbert Wiklicky

Embedding of Hypercubes into Grids
                     by Sergej Bezrukov,Joe Chavez,Larry Harper,Markus Roettger,Ulf-Peter Schroeder

Approximating Maximum Independent Sets in Uniform Hypergraphs
                     by Thomas Hofmeister,Hanno Lefmann

Iterated Function Systems and Control Languages
                     by Henning Fernau, Ludwig Staiger

Additive Cellular Automata over {Z}_p and the Bottom of (CA,leq)
                     by I. Rapaport, J. Mazoyer

On the Composition Problem for OBDDs With Different Variable Orderings
                     by Anna Slobodova

A Computational Interpretation of the lambdamu-calculus
                     by G.M. Bierman

Complete Abstract Interpretations made Constructive
                     by Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari

On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols
                     by Carsten Damm

Model Checking Real-Time Properties of Symmetric Systems
                     by E. Allen Emerson, Richard J. Trefler

On counting AC^0 circuits with negative constants
                     by Andris Ambainis, David Mix Barrington, Huong LeThanh

Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms
                     by Marek Chrobak, Christoph Durr

Polymorhic subtyping without distributivity
                     by Jacek Chrzaszcz

One guess one-way cellular arrays
                     by Thomas Buchholz, Andreas Klein, Martin Kutrib

Timed Bisimulation and Open Maps
                     by Thomas Hune, Mogens Nielsen

Optimizing OBDDs Is Still Intractable for Monotone Functions
                     by Kazuo Iwama, Mitsushi Nozoe

Tarskian set constraints are in NEXPTIME
                     by Pawel Mielniczuk, Leszek Pacholski

The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses
                     by Holger Petersen

A Separation of Planar Circuits
                     by B. Csaba, A. Pluhar, T. Szeles