![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
23. MFCS 1998: Brno, Czech Republic
- Lubos Brim, Jozef Gruska, Jirí Zlatuska:
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
Invited Papers
- Giorgio Ausiello, Giuseppe F. Italiano, Umberto Nanni
:
Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithms. 1-16 - Egon Börger, Wolfram Schulte:
Defining the Java Virtual Machine as Platform for Provably Correct Java Compilation. 17-35 - David Harel:
Towards a Theory of Recursive Structures. 36-53 - Yonit Kesten, Amir Pnueli:
Modularization and Abstraction: The Keys to Practical Formal Verification. 54-71 - Wolfgang Maass:
On the Role of Time and Space in Neural Computation. 72-83 - Kurt Mehlhorn, Stefan Näher:
From Algorithms to Working Programs: On the Use of Program Checking in LEDA. 84-93 - Silvio Micali:
Computationally-Sound Checkers. 94-116 - Mogens Nielsen:
Reasoning About the Past. 117-128 - Pavel Pudlák:
Satisfiability - Algorithms and Logic. 129-141 - Colin Stirling:
The Joys of Bisimulation. 142-151 - Jirí Wiedermann
:
Towards Algorithmic Explanation of Mind Evolution and Functioning. 152-166
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 - Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi:
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. 176-184 - Marek Chrobak, Christoph Dürr:
Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms. 185-193 - Nikolai N. Kuzjurin:
Locally Explicit Construction of Rödl's Asymptotically Good Packings. 194-202
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 - Richard F. Bonner, Rusins Freivalds, Janis Lapins, Antra Lukjanska:
Nonstochastic Languages as Projections of 2-Tape Quasideterministic Languages. 213-219 - Flemming Nielson, Hanne Riis Nielson:
Flow Logic for Imperative Objects. 220-228 - Alexander Moshe Rabinovich:
Expressive Completeness of Temporal Logic of Action. 229-238
Rewriting
- Maria C. F. Ferreira, Delia Kesner, Laurence Puel:
Reducing AC-Termination to Termination. 239-247 - Zoltán Fülöp, Eija Jurvanen, Magnus Steinby, Sándor Vágvölgyi:
On One-Pass Term Rewriting. 248-256 - Miki Hermann, Gernot Salzer
:
On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations. 257-266 - Hélène Touzet:
Encoding the Hydra Battle as a Rewrite System. 267-276
Automata and Transducers
- Christian Hagenah, Anca Muscholl:
Computing epsilon-Free NFA from Regular Expressions in O(n log²(n)) Time. 277-285 - Michel Latteux, David Simplot, Alain Terlutte:
Iterated Length-Preserving Rational Transductions. 286-295 - Holger Petersen:
The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses. 296-304 - Géraud Sénizergues:
The Equivalence Problem for Deterministic Pushdown Transducers into Abelian Groups. 305-315
Typing
- Gilles Barthe
:
The Semi-Full Closure of Pure Type Systems. 316-325 - Marcin Benke:
Predicative Polymorphic Subtyping. 326-335 - Gavin M. Bierman:
A Computational Interpretation of the lambda-µ-Calculus. 336-345 - Jacek Chrzaszcz:
Polymorphic Subtyping Without Distributivity. 346-355
Concurrency - Semantics - Logic
- Paul Gastin, Raphaël Meyer, Antoine Petit:
A (Non-elementary) Modular Decision Procedure for LTrL. 356-365 - Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari
:
Complete Abstract Interpretations Made Constructive. 366-377 - Thomas Hune, Mogens Nielsen:
Timed Bisimulation and Open Maps. 378-387 - Jirí Srba:
Deadlocking States in Context-Free Process Algebra. 388-398
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 - Andris Ambainis, David A. Mix Barrington, Huong LeThanh:
On Counting AC0 Circuits with Negative Constants. 409-417 - Lane A. Hemaspaandra
, Jörg Rothe:
A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. 418-426
Programming
- E. Allen Emerson, Richard J. Trefler:
Model Checking Real-Time Properties of Symmetric Systems. 427-436 - Martin Grohe, Thomas Schwentick:
Locality of Order-Invariant First-Order Formulas. 437-445 - Alessandra Di Pierro
, Herbert Wiklicky:
Probabilistic Concurrent Constraint Programming: Towards a Fully Abstract Model. 446-455 - Alex K. Simpson:
Lazy Functional Algorithms for Exact Real Functionals. 456-464
Structural Complexity
- Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt:
Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets. 465-473 - Levke Bentzien:
Positive Turing and Truth-Table Completeness for NEXP Are Incomparable. 474-482 - Judy Goldsmith, Mitsunori Ogihara, Jörg Rothe:
Tally NP Sets and Easy Census Functions. 483-492 - Johannes Köbler, Rainer Schuler:
Average-Case Intractability vs. Worst-Case Intractability. 493-502
Formal Languages
- Tero Harju
, Alexandru Mateescu, Arto Salomaa:
Shuffle on Trajectories: The Schützenberger Product and Related Operations. 503-511 - Werner Kuich:
Gaußian Elimination and a Characterization of Algebraic Power Series. 512-521 - Luis-Miguel Lopez, Philippe Narbel:
D0L-Systems and Surface Automorphisms. 522-532 - Isabelle Ryl, Yves Roos
, Mireille Clerbout:
About Synchronization Languages. 533-542
Graphs and Hypergraphs
- Klaus Barthelmann:
When Can an Equational Simple Graph Be Generated by Hyperedge Replacement? 543-552 - Martin Große-Rhode, Francesco Parisi-Presicce, Marta Simeoni:
Spatial and Temporal Refinement of Typed Graph Transformation Systems. 553-561 - Thomas Hofmeister, Hanno Lefmann:
Approximating Maximum Independent Sets in Uniform Hypergraphs. 562-570 - Salvatore La Torre
, Margherita Napoli:
Representing Hyper-Graphs by Regular Languages. 571-579
Turing Complexity and Logic
- Kazuo Iwama, Chuzo Iwamoto:
Improved Time and Space Hierarchies of One-Tape Off-Line TMs. 580-588 - Pawel Mielniczuk, Leszek Pacholski:
Tarskian Set Constraints Are in NEXPTIME. 589-596 - Sergei G. Vorobyov:
forall exists*-Equational Theory of Context Unification is Pi10-Hard. 597-606 - Jirí Wiedermann
:
Speeding-Up Nondeterministic Single-Tape Off-Line Computations by One Alternation. 607-615
Binary Decision Diagrams
- Bruno Courcelle, Denis Lapoire:
Facial Circuits of Planar Graphs and Context-Free Languages. 616-624 - Kazuo Iwama, Mitsushi Nouzoe, Shuzo Yajima:
Optimizing OBDDs Is Still Intractable for Monotone Functions. 625-635 - Harry Preuß, Anand Srivastav:
Blockwise Variable Orderings for Shared BDDs. 636-644 - Anna Slobodová:
On the Composition Problem for OBDDs with Multiple Variable Orders. 645-655
Combinatorics on Words
- Christian Choffrut, Sándor Horváth:
Equations in Transfinite Strings. 656-664 - Maxime Crochemore, Filippo Mignosi, Antonio Restivo:
Minimal Forbidden Words and Factor Automata. 665-673 - Juhani Karhumäki, Ján Manuch, Wojciech Plandowski:
On Defect Effect of Bi-Infinite Words. 674-682 - Roman M. Kolpakov
, Gregory Kucherov, Yuriy V. Tarannikov
:
On Repetition-Free Binary Words of Minimal Density. 683-692
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 - Hans L. Bodlaender, Torben Hagerup:
Tree Decompositions of Small Diameter. 702-712 - Hajo Broersma
, Andreas Huck, Ton Kloks, Otto R. Koppius, Dieter Kratsch, Haiko Müller
, Hilde Tuinstra:
Degree-Preserving Forests. 713-721 - Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, Peter Sanders:
A Parallelization of Dijkstra's Shortest Path Algorithm. 722-731
Picture Languages - Function Systems/Complexity
- Bruno Durand, Sylvain Porrot:
Comparison Between the Complexity of a Function and the Complexity of Its Graph. 732-739 - Henning Fernau
, Ludwig Staiger
:
IFS and Control Languages. 740-750 - Oliver Matz:
One Quantifier Will Do in Existential Monadic Second-Order Logic over Pictures. 751-759 - Klaus Reinhardt:
On Some Recognizable Picture-Languages. 760-770
Communication - Computable Real Numbers
- Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano:
On the Complexity of Wavelength Converters. 771-779 - Carsten Damm
:
On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols. 780-788 - Juraj Hromkovic:
Communication Complexity and Lower Bounds on Multilective Computations. 789-797 - Klaus Weihrauch, Xizhong Zheng:
A Finite Hierarchy of the Recursively Enumerable Real Numbers. 798-806
Cellular Automata
- Thomas Buchholz, Andreas Klein, Martin Kutrib
:
One Guess One-Way Cellular Arrays. 807-815 - Gianpiero Cattaneo, Luciano Margara
:
Topological Definitions of Chaos Applied to Cellular Automata Dynamics. 816-824 - Giovanni Manzini:
Characterization of Sensitive Linear Cellular Automata with Respect to the Counting Distance. 825-833 - Jacques Mazoyer, Ivan Rapaport:
Additive Cellular Automata over Zp and the Bottom of (CA, <=). 834-843
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.