default search action
20. MFCS 1995: Prague, Czech Republic
- Jirí Wiedermann, Petr Hájek:
Mathematical Foundations of Computer Science 1995, 20th International Symposium, MFCS'95, Prague, Czech Republic, August 28 - September 1, 1995, Proceedings. Lecture Notes in Computer Science 969, Springer 1995, ISBN 3-540-60246-1
Invited Papers
- Micah Adler, John W. Byers, Richard M. Karp:
Scheduling Parallel Communication: The h-relation Problem. 1-20 - Stefan Arnborg:
Decomposable Structures, Boolean Function Representations, and Optimization. 21-36 - Michele Flammini, Jan van Leeuwen, Alberto Marchetti-Spaccamela
:
The Complexity of Interval Routing on Random Graphs. 37-49 - Viliam Geffert:
Bridging Across the log(n) Space Frontier. 50-65 - Georg Gottlob, Nicola Leone, Helmut Veith:
Second Order Logic and the Weak Exponential Hierarchies. 66-81 - Juris Hartmanis:
On the Computing Paradigm and Computational Complexity. 82-92 - Daniel Lehmann:
Ranked Structures in Nonmonotonic Reasoning and Belief Revision: Abstract. 93 - Dominique Perrin:
Symbolic Dynamics and Finite Automata. 94-104 - Alexander A. Razborov:
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract). 105 - Paul M. B. Vitányi:
Physics and the New Computation. 106-128
Structural Complexity Theory
- Eric Allender
Measure on P: Robustness of the Notion. 129-138 - Hans-Jörg Burtschick:
Comparing Counting Classes for Logspace, One-way Logspace, and First-order. 139-148 - Carsten Damm, Markus Holzer
Automata That Take Advice. 149-158 - Steven Homer, Sarah Mocas:
Nonuniform Lower Bounds for Exponential Time Classes. 159-168 - Susanne Kaufmann, Martin Kummer:
On a Quantitative Notion of Uniformity. 169-178 - Wolfgang Merkle, Yongge Wang
Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities. 179-190
Algorithms
- Danièle Beauquier, Dima Burago, Anatol Slissenko:
On the Complexity of Finite Memory Policies for Markov Decision Processes. 191-200 - Thomas Hofmeister, Hanno Lefmann:
Derandomization for Sparse Approximations and Independent Sets. 201-210 - Jyrki Katajainen, Tomi Pasanen
Asymptotically Efficient In-Place Merging. 211-220
Complexity Theory
- Peter Heusch:
The Complexity of the Falsifiability Problem for Pure Implicational Formulas. 221-226 - Viggo Kann:
Strong Lower Bounds on the Approximability of some NPO PB-Complete Maximization Problems. 227-236 - Hanno Lefmann, Petr Savický:
Some Typical Properties of Large AND/OR Boolean Formulas. 237-246
Graph Models of Computations
- Martin Hühne
The Hedge: An Efficient Storage Device for Turing Machines with One Head (Extended Abstract). 247-256 - Osamu Maruyama, Satoru Miyano:
Graph Inference from a Walk for TRees of Bounded Degree 3 is NP-Complete. 257-266 - Ivan Stojmenovic:
Honecomb Networks. 267-276 - Sophie Fischer, Lane A. Hemaspaandra
Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract). 277-287
Lower Bounds
- Claudia Bertram-Kretzberg, Thomas Hofmeister:
Multiple Product Modulo Arbitrary Numbers. 288-298 - Christoph Meinel, Stephan Waack:
Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems. 299-308 - Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini:
Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages. 309-318 - Stanislav Zák:
A Superpolynomial Lower Bound for (1, +k(n))-Branching Programs. 319-325
Formal Languages
- Luca Breveglieri, Alessandra Cherubini, Stefano Crespi-Reghizzi:
Deterministic Parsing for Augmented Context-free Grammars. 326-336 - Filippo Mignosi, Antonio Restivo, Sergio Salemi:
A Periodicity Theorem on Words and Applications. 337-348 - Günter Hotz, Gisela Pitsch:
A New Approach to Analyse Coupled-Context-Free Languages. 349-358
Unification, Rewriting, Type Theory
- Miki Hermann, Phokion G. Kolaitis:
Computational Complexity of Simultaneous Elementary Matching Problems (Extended Abstract). 359-370 - M. R. K. Krishna Rao:
Graph Reducibility of Term Rewriting Systems. 371-381 - Pawel Urzyczyn:
Positive Recursive Type Assignment. 382-391
Distributed Computation
- Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio:
String Recognition on Anonymous Rings. 392-401 - Zsuzsanna Róka
The Firing Squad Synchronization Problem on Cayley Graphs. 402-411 - Jop F. Sibeyn, Michael Kaufmann:
Solving Cheap Graph Problems an Meshes. 412-422
Concurrency
- Olaf Burkart, Didier Caucal, Bernhard Steffen:
An Elementary Bisimulation Decision Procedure for Arbitrary Context-Free Processes. 423-433 - Serge Bauget, Paul Gastin:
On Congruences and Partial Orders. 434-443 - Flavio Corradini, Roberto Gorrieri, Marco Roccetti:
Performance Preorder: Ordering Processes with Respect to Speed. 444-453 - William Ferreira, Matthew Hennessy:
Towards a Semantic Theory of CML (Extended Abstract). 454-466 - Sébastien Huguet, Antoine Petit:
Modular Constructions of Distributing Automata. 467-478 - Davide Sangiorgi:
On the Proof Method for Bisimulation (Extended Abstract). 479-488
Semantics
- Clare E. Martin
Towards a Calculus of Predicate Transformers. 489-498 - Martín Abadi, Stephan Merz:
An Abstract Account of Composition. 499-508 - Roel van der Goot, Arie de Bruin:
Syntax and Semantics of Procol. 509-518
Model Checking
- Jens Chr. Godskesen, Kim Guldstrand Larsen:
Synthesizing Distinguishing Formulae for Real Time Systems (Extended Abstract). 519-528 - François Laroussinie, Kim Guldstrand Larsen, Carsten Weise:
From Timed Automata to Logic - and Back. 529-539 - Johann A. Makowsky, Elena V. Ravve:
Incremental Model Checking for Decomposable Structures (Extended Abstract). 540-551
Formal Calculi
- David Janin, Igor Walukiewicz:
Automata for the Modal mu-Calculus and related Results. 552-562 - Peter Niebert:
A v-Calculus with Local Views for Systems of Sequential Agents. 563-573 - Philip Feinsilver, René Schott:
An Operator Calculus Approach to the Evolution of Dynamic Data Structures. 574-586
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.
last updated on 2024-12-17 20:46 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: