![](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
22. MFCS 1997: Bratislava, Slovakia
- Igor Prívara, Peter Ruzicka:
Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS'97, Bratislava, Slovakia, August 25-29, 1997, Proceedings. Lecture Notes in Computer Science 1295, Springer 1997, ISBN 3-540-63437-1
Invited Papers
- Samson Abramsky
:
Game Semantics for Programming Languages (Abstract). 3-4 - László Babai
:
Communication Complexity. 5-18 - Hans L. Bodlaender:
Treewidth: Algorithmic Techniques and Results. 19-36 - Nachum Dershowitz:
When are Two Rewrite Systems More than None? 37-43 - Cynthia Dwork:
Positive Applications of Lattices to Cryptography. 44-51 - Gian-Luigi Ferrari
, Ugo Montanari:
A Tile-Based Coordination View of Asynchronous pi-Calculus. 52-70 - Juraj Hromkovic, Georg Schnitger:
Communication Complexity and Sequential Compuation. 71-84 - Jan Krajícek:
Lower Bounds for a Proof System with an Expentential Speed-up over Constant-Depth Frege Systems and over Polynomial Calculus. 85-90 - Maciej Liskiewicz, Rüdiger Reischuk:
Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds. 91-107 - Dan Roth:
Learning to Perform Knowledge-Intensive Inferences. 108-109 - Uwe Schöning:
Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity. 110-116
Contributed Papers
- Foto N. Afrati, Irène Guessarian, Michel de Rougemont:
The Expressiveness of Datalog Circuits (DAC). 119-128 - Martin Mundhenk, Judy Goldsmith, Eric Allender
:
The Complexity of Policy Evaluation for Finite-Horizon Partially-Observable Markov Decision Processes. 129-138 - Luca Bernardinello, Lucia Pomello:
A Category of Transition Systems and Its Relations with Orthomodular Posets. 139-148 - Béatrice Bérard, Claudine Picaronny:
Accepting Zeno Words Without Making Time Stand Still. 149-158 - Beate Bollig, Ingo Wegener:
Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams. 159-168 - Marcello M. Bonsangue, Joost N. Kok:
Specifying Computations Using Hyper Transition Systems. 169-178 - Gianpiero Cattaneo, Enrico Formenti
, Luciano Margara
, Jacques Mazoyer:
A Shift-Invariant Metric on Szz Inducing a Non-trivial Tolology. 179-188 - Gang Chen:
Subtyping Calculus of Construction (Extended Abstract). 189-198 - Christian Choffrut, Giovanni Pighizzini:
Distances Between Languages and Reflexivity of Relations. 199-208 - Isabelle Ryl, Yves Roos
, Mireille Clerbout:
Partial Characterization of Synchronization Languages. 209-218 - Reiko Heckel, Hartmut Ehrig, Uwe Wolter, Andrea Corradini:
Integrating the Specification Techniques of Graph Transformation and Temporal Logic. 219-228 - Frank Drewes:
On the Generation of Trees by Hyperedge Replacement. 229-238 - Henning Fernau
, Ralf Stiebe:
Regulations by Valences. 239-248 - Wan J. Fokkink, Jaco van de Pol:
Simulation as a Correct Transformation of Rewrite Systems. 249-258 - Cyril Gavoille:
On the Dilation of Interval Routing. 259-268 - Zurab Khasidashvili, John R. W. Glauert:
Relating Conflict-Free Stable Transition and Event Models (Extended Abstract). 269-278 - Andreas Goerdt:
The Giant Component Threshold for Random Regular Graphs with Edge Faults. 279-288 - Bernhard Heinemann:
A Topological Generalization of Propositional Linear Time Temporal Logic. 289-297 - Markus Holzer
:
Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations. 299-308 - Kazuo Iwama:
Complexity of Finding Short Resolution Proofs. 309-318 - Stasys Jukna
, Alexander A. Razborov, Petr Savický, Ingo Wegener:
On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs. 319-326 - Georg Karner, Werner Kuich:
A Characterization of Abstract Families of Algebraic Power Series. 327-336 - Yuji Kobayashi, Friedrich Otto:
Repetitiveness of D0L-Languages Is Decidable in Polynomial Time. 337-346 - Roman M. Kolpakov
, Gregory Kucherov:
Minimal Letter Frequency in n-th Power-Free Binary Words. 347-357 - Ivan Korec:
Real-Time Generation of Primes by a One-Dimensional Cellular Automaton with 11 States. 358-367 - Drago Krznaric, Christos Levcopoulos:
Optimal Algorithms for Complete Linkage Clustering in d Dimensions. 368-377 - Giovanni Manzini, Luciano Margara
:
Invertible Linear Cellular Automata over zm: Algorithmic and Dynamical Aspects. 378-387 - Carlos Martín-Vide, Joan Miquel-Verges, Gheorghe Paun:
Two-Level Contextual Grammars: The Internal Case. 388-397 - Klaus Meer:
Counting Problems over the Reals. 398-407 - Christoph Meinel, Thorsten Theobald:
On the Influence of the State Encoding on OBDD-Representations of Finite State Machines. 408-417 - Raphaël Meyer, Antoine Petit:
Decomposition of TrPTL Formulas. 418-427 - Martin Mundhenk:
NP-Hard Sets Have Many Hard Instances. 428-437 - Arfst Nickelsen:
Deciding Verbose Languages with Linear Advice. 438-447 - Holger Petersen:
Homomorphic Images os Sentential Forms and Terminating Grammars (Extended Abstract). 448-457 - Detlef Plump:
Simplification Orders for Term Graph Rewriting. 458-467 - Arend Rensink, Heike Wehrheim:
Dependency-Based Action Refinement. 468-477 - Petr Savický, Stanislav Zák:
A Hierarchy for (1, +k)-Branching Programs with Respect of k. 478-487 - Jop F. Sibeyn:
Routing with Finite Speeds of Memory and Network. 488-497 - Jerzy Tyszkiewicz
:
Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines (Extended Abstract). 498-507 - Walter Vogler:
Partial Order Semantics and Read Arcs. 508-517
![](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.