23. MFCS 1998: Brno, Czech Republic

Lubos Brim, Jozef Gruska, Jirí Zlatuska (Eds.): Mathematical Foundations of Computer Science 1998, 23rd International Symposium, MFCS'98, Brno, Czech Republic, August 24-28, 1998, Proceedings. Lecture Notes in Computer Science 1450 Springer 1998, ISBN 3-540-64827-5 BibTeX

Invited Papers

Giorgio Ausiello, Giuseppe F. Italiano, Umberto Nanni:
Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithms. 1-16
Electronic Edition (Springer LINK) BibTeX
Egon Börger, Wolfram Schulte:
Defining the Java Virtual Machine as Platform for Provably Correct Java Compilation. 17-35
Electronic Edition (Springer LINK) BibTeX
David Harel:
Towards a Theory of Recursive Structures. 36-53
Electronic Edition (Springer LINK) BibTeX
Yonit Kesten, Amir Pnueli:
Modularization and Abstraction: The Keys to Practical Formal Verification. 54-71
Electronic Edition (Springer LINK) BibTeX
Wolfgang Maass:
On the Role of Time and Space in Neural Computation. 72-83
Electronic Edition (Springer LINK) BibTeX
Kurt Mehlhorn, Stefan Näher:
From Algorithms to Working Programs: On the Use of Program Checking in LEDA. 84-93
Electronic Edition (Springer LINK) BibTeX
Silvio Micali:
Computationally-Sound Checkers. 94-116
Electronic Edition (Springer LINK) BibTeX
Mogens Nielsen:
Reasoning About the Past. 117-128
Electronic Edition (Springer LINK) BibTeX
Pavel Pudlák:
Satisfiability - Algorithms and Logic. 129-141
Electronic Edition (Springer LINK) BibTeX
Colin Stirling:
The Joys of Bisimulation. 142-151
Electronic Edition (Springer LINK) BibTeX
Jirí Wiedermann:
Towards Algorithmic Explanation of Mind Evolution and Functioning. 152-166
Electronic Edition (Springer LINK) BibTeX

Complexity of Hard Problems

Mikel Aldaz, Joos Heintz, Guillermo Matera, José Luis Montaña, Luis Miguel Pardo:
Combinatorial Hardness Proofs for Polynomial Evaluation. 167-175
Electronic Edition (Springer LINK) BibTeX
Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi:
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. 176-184
Electronic Edition (Springer LINK) BibTeX
Marek Chrobak, Christoph Dürr:
Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms. 185-193
Electronic Edition (Springer LINK) BibTeX
Nikolai N. Kuzjurin:
Locally Explicit Construction of Rödl's Asymptotically Good Packings. 194-202
Electronic Edition (Springer LINK) BibTeX

Logic - Semantics - Automata

Matthias Baaz, Agata Ciabattoni, Christian G. Fermüller, Helmut Veith:
Proof Theory of Fuzzy Logics: Urquhart's C and Related Logics. 203-212
Electronic Edition (Springer LINK) BibTeX
Richard F. Bonner, Rusins Freivalds, Janis Lapins, Antra Lukjanska:
Nonstochastic Languages as Projections of 2-Tape Quasideterministic Languages. 213-219
Electronic Edition (Springer LINK) BibTeX
Flemming Nielson, Hanne Riis Nielson:
Flow Logic for Imperative Objects. 220-228
Electronic Edition (Springer LINK) BibTeX
Alexander Moshe Rabinovich:
Expressive Completeness of Temporal Logic of Action. 229-238
Electronic Edition (Springer LINK) BibTeX

Rewriting

Maria C. F. Ferreira, Delia Kesner, Laurence Puel:
Reducing AC-Termination to Termination. 239-247
Electronic Edition (Springer LINK) BibTeX
Zoltán Fülöp, Eija Jurvanen, Magnus Steinby, Sándor Vágvölgyi:
On One-Pass Term Rewriting. 248-256
Electronic Edition (Springer LINK) BibTeX
Miki Hermann, Gernot Salzer:
On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations. 257-266
Electronic Edition (Springer LINK) BibTeX
Hélène Touzet:
Encoding the Hydra Battle as a Rewrite System. 267-276
Electronic Edition (Springer LINK) BibTeX

Automata and Transducers

Christian Hagenah, Anca Muscholl:
Computing epsilon-Free NFA from Regular Expressions in O(n log²(n)) Time. 277-285
Electronic Edition (Springer LINK) BibTeX
Michel Latteux, David Simplot, Alain Terlutte:
Iterated Length-Preserving Rational Transductions. 286-295
Electronic Edition (Springer LINK) BibTeX
Holger Petersen:
The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses. 296-304
Electronic Edition (Springer LINK) BibTeX
Géraud Sénizergues:
The Equivalence Problem for Deterministic Pushdown Transducers into Abelian Groups. 305-315
Electronic Edition (Springer LINK) BibTeX

Typing

Gilles Barthe:
The Semi-Full Closure of Pure Type Systems. 316-325
Electronic Edition (Springer LINK) BibTeX
Marcin Benke:
Predicative Polymorphic Subtyping. 326-335
Electronic Edition (Springer LINK) BibTeX
Gavin M. Bierman:
A Computational Interpretation of the lambda-µ-Calculus. 336-345
Electronic Edition (Springer LINK) BibTeX
Jacek Chrzaszcz:
Polymorphic Subtyping Without Distributivity. 346-355
Electronic Edition (Springer LINK) BibTeX

Concurrency - Semantics - Logic

Paul Gastin, Raphaël Meyer, Antoine Petit:
A (Non-elementary) Modular Decision Procedure for LTrL. 356-365
Electronic Edition (Springer LINK) BibTeX
Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari:
Complete Abstract Interpretations Made Constructive. 366-377
Electronic Edition (Springer LINK) BibTeX
Thomas Hune, Mogens Nielsen:
Timed Bisimulation and Open Maps. 378-387
Electronic Edition (Springer LINK) BibTeX
Jirí Srba:
Deadlocking States in Context-Free Process Algebra. 388-398
Electronic Edition (Springer LINK) BibTeX

Circuit Complexity

Kazuyuki Amano, Akira Maruoka:
A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with At Most (1/6) log log n Negation Gates. 399-408
Electronic Edition (Springer LINK) BibTeX
Andris Ambainis, David A. Mix Barrington, Huong LeThanh:
On Counting AC⁰ Circuits with Negative Constants. 409-417
Electronic Edition (Springer LINK) BibTeX
Lane A. Hemaspaandra, Jörg Rothe:
A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. 418-426
Electronic Edition (Springer LINK) BibTeX

Programming

E. Allen Emerson, Richard J. Trefler:
Model Checking Real-Time Properties of Symmetric Systems. 427-436
Electronic Edition (Springer LINK) BibTeX
Martin Grohe, Thomas Schwentick:
Locality of Order-Invariant First-Order Formulas. 437-445
Electronic Edition (Springer LINK) BibTeX
Alessandra Di Pierro, Herbert Wiklicky:
Probabilistic Concurrent Constraint Programming: Towards a Fully Abstract Model. 446-455
Electronic Edition (Springer LINK) BibTeX
Alex K. Simpson:
Lazy Functional Algorithms for Exact Real Functionals. 456-464
Electronic Edition (Springer LINK) BibTeX

Structural Complexity

Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt:
Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets. 465-473
Electronic Edition (Springer LINK) BibTeX
Levke Bentzien:
Positive Turing and Truth-Table Completeness for NEXP Are Incomparable. 474-482
Electronic Edition (Springer LINK) BibTeX
Judy Goldsmith, Mitsunori Ogihara, Jörg Rothe:
Tally NP Sets and Easy Census Functions. 483-492
Electronic Edition (Springer LINK) BibTeX
Johannes Köbler, Rainer Schuler:
Average-Case Intractability vs. Worst-Case Intractability. 493-502
Electronic Edition (Springer LINK) BibTeX

Formal Languages

Tero Harju, Alexandru Mateescu, Arto Salomaa:
Shuffle on Trajectories: The Schützenberger Product and Related Operations. 503-511
Electronic Edition (Springer LINK) BibTeX
Werner Kuich:
Gaußian Elimination and a Characterization of Algebraic Power Series. 512-521
Electronic Edition (Springer LINK) BibTeX
Luis-Miguel Lopez, Philippe Narbel:
D0L-Systems and Surface Automorphisms. 522-532
Electronic Edition (Springer LINK) BibTeX
Isabelle Ryl, Yves Roos, Mireille Clerbout:
About Synchronization Languages. 533-542
Electronic Edition (Springer LINK) BibTeX

Graphs and Hypergraphs

Klaus Barthelmann:
When Can an Equational Simple Graph Be Generated by Hyperedge Replacement? 543-552
Electronic Edition (Springer LINK) BibTeX
Martin Große-Rhode, Francesco Parisi-Presicce, Marta Simeoni:
Spatial and Temporal Refinement of Typed Graph Transformation Systems. 553-561
Electronic Edition (Springer LINK) BibTeX
Thomas Hofmeister, Hanno Lefmann:
Approximating Maximum Independent Sets in Uniform Hypergraphs. 562-570
Electronic Edition (Springer LINK) BibTeX
Salvatore La Torre, Margherita Napoli:
Representing Hyper-Graphs by Regular Languages. 571-579
Electronic Edition (Springer LINK) BibTeX

Turing Complexity and Logic

Kazuo Iwama, Chuzo Iwamoto:
Improved Time and Space Hierarchies of One-Tape Off-Line TMs. 580-588
Electronic Edition (Springer LINK) BibTeX
Pawel Mielniczuk, Leszek Pacholski:
Tarskian Set Constraints Are in NEXPTIME. 589-596
Electronic Edition (Springer LINK) BibTeX
Sergei G. Vorobyov:
forall exists*-Equational Theory of Context Unification is Pi₁⁰-Hard. 597-606
Electronic Edition (Springer LINK) BibTeX
Jirí Wiedermann:
Speeding-Up Nondeterministic Single-Tape Off-Line Computations by One Alternation. 607-615
Electronic Edition (Springer LINK) BibTeX

Binary Decision Diagrams

Bruno Courcelle, Denis Lapoire:
Facial Circuits of Planar Graphs and Context-Free Languages. 616-624
Electronic Edition (Springer LINK) BibTeX
Kazuo Iwama, Mitsushi Nouzoe, Shuzo Yajima:
Optimizing OBDDs Is Still Intractable for Monotone Functions. 625-635
Electronic Edition (Springer LINK) BibTeX
Harry Preuß, Anand Srivastav:
Blockwise Variable Orderings for Shared BDDs. 636-644
Electronic Edition (Springer LINK) BibTeX
Anna Slobodová:
On the Composition Problem for OBDDs with Multiple Variable Orders. 645-655
Electronic Edition (Springer LINK) BibTeX

Combinatorics on Words

Christian Choffrut, Sándor Horváth:
Equations in Transfinite Strings. 656-664
Electronic Edition (Springer LINK) BibTeX
Maxime Crochemore, Filippo Mignosi, Antonio Restivo:
Minimal Forbidden Words and Factor Automata. 665-673
Electronic Edition (Springer LINK) BibTeX
Juhani Karhumäki, Ján Manuch, Wojciech Plandowski:
On Defect Effect of Bi-Infinite Words. 674-682
Electronic Edition (Springer LINK) BibTeX
Roman M. Kolpakov, Gregory Kucherov, Yuriy Tarannikov:
On Repetition-Free Binary Words of Minimal Density. 683-692
Electronic Edition (Springer LINK) BibTeX

Trees and Embeddings

Sergei L. Bezrukov, Joe D. Chavez, L. H. Harper, Markus Röttger, Ulf-Peter Schroeder:
Embedding of Hypercubes into Grids. 693-701
Electronic Edition (Springer LINK) BibTeX
Hans L. Bodlaender, Torben Hagerup:
Tree Decompositions of Small Diameter. 702-712
Electronic Edition (Springer LINK) BibTeX
Hajo Broersma, Andreas Huck, Ton Kloks, Otto R. Koppius, Dieter Kratsch, Haiko Müller, Hilde Tuinstra:
Degree-Preserving Forests. 713-721
Electronic Edition (Springer LINK) BibTeX
Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, Peter Sanders:
A Parallelization of Dijkstra's Shortest Path Algorithm. 722-731
Electronic Edition (Springer LINK) BibTeX

Picture Languages - Function Systems/Complexity

Bruno Durand, Sylvain Porrot:
Comparison Between the Complexity of a Function and the Complexity of Its Graph. 732-739
Electronic Edition (Springer LINK) BibTeX
Henning Fernau, Ludwig Staiger:
IFS and Control Languages. 740-750
Electronic Edition (Springer LINK) BibTeX
Oliver Matz:
One Quantifier Will Do in Existential Monadic Second-Order Logic over Pictures. 751-759
Electronic Edition (Springer LINK) BibTeX
Klaus Reinhardt:
On Some Recognizable Picture-Languages. 760-770
Electronic Edition (Springer LINK) BibTeX

Communication - Computable Real Numbers

Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano:
On the Complexity of Wavelength Converters. 771-779
Electronic Edition (Springer LINK) BibTeX
Carsten Damm:
On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols. 780-788
Electronic Edition (Springer LINK) BibTeX
Juraj Hromkovic:
Communication Complexity and Lower Bounds on Multilective Computations. 789-797
Electronic Edition (Springer LINK) BibTeX
Klaus Weihrauch, Xizhong Zheng:
A Finite Hierarchy of the Recursively Enumerable Real Numbers. 798-806
Electronic Edition (Springer LINK) BibTeX

Cellular Automata

Thomas Buchholz, Andreas Klein, Martin Kutrib:
One Guess One-Way Cellular Arrays. 807-815
Electronic Edition (Springer LINK) BibTeX
Gianpiero Cattaneo, Luciano Margara:
Topological Definitions of Chaos Applied to Cellular Automata Dynamics. 816-824
Electronic Edition (Springer LINK) BibTeX
Giovanni Manzini:
Characterization of Sensitive Linear Cellular Automata with Respect to the Counting Distance. 825-833
Electronic Edition (Springer LINK) BibTeX
Jacques Mazoyer, Ivan Rapaport:
Additive Cellular Automata over Z_p and the Bottom of (CA, <=). 834-843
Electronic Edition (Springer LINK) BibTeX