default search action
21st FOCS 1980: Syracuse, New York, USA
- 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980. IEEE Computer Society 1980
Session I
- Richard M. Karp, Christos H. Papadimitriou:
On Linear Characterizations of Combinatorial Optimization Problems. 1-9 - Mihalis Yannakakis:
On a Class of Totally Unimodular Matrices. 10-16 - Silvio Micali, Vijay V. Vazirani:
An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs. 17-27 - T. C. Hu, M. T. Shing:
Some Theorems about Matrix Multiplication (Extended Abstract). 28-35 - Merrick L. Furst, John E. Hopcroft, Eugene M. Luks:
Polynomial-Time Algorithms for Permutation Groups. 36-41 - Eugene M. Luks:
Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time. 42-49 - Barbara Simons:
A Fast Algorithm for Multiprocessor Scheduling. 50-53
Session II
- Stephen R. Mahaney:
Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis. 54-60 - Ivan Hal Sudborough:
Efficient Algorithms for Path System Problems and Applications to Alternating and Time-Space Complexity Classes. 62-73 - Neil Immerman:
Upper and Lower Bounds for First Order Expressibility. 74-82 - Eitan M. Gurari:
The Equivalence Problem for Deterministic Two-Way Sequential Transducers Is Decidable. 83-85 - Gary L. Peterson:
Succinct Representation, Random Strings, and Complexity Classes. 86-95
Session III
- Gérard P. Huet, Jean-Marie Hullot:
Proofs by Induction in Equational Theories with Constructors. 96-107 - Paul Chew:
An Improved Algorithm for Computing With Equations. 108-117 - Robert L. Constable:
Programs and Types. 118-128 - David Harel, Dexter Kozen, Rohit Parikh:
Process Logic: Expressiveness, Decidability, Completeness. 129-142 - Nissim Francez, Daniel Lehmann, Amir Pnueli:
A Linear History Semantics for Distributed Languages (Extended Abstract). 143-151 - Harry B. Hunt III, Daniel J. Rosenkrantz:
The Complexity of Recursion Schemes and Recursive Programming Languages (Extended Abstract). 152-160 - Bruno Courcelle, Paul Franchi-Zannettacci:
On the Expressive Power of Attribute Grammars. 161-172 - A. J. Kfoury:
Loop Elimination and Loop Reduction-A Model-Theoretic Analysis of Programs (Partial Report). 173-184 - Neil D. Jones, Steven S. Muchnick:
Complexity of Flow Analysis, Inductive Assertion Synthesis and a Language Due to Dijkstra. 185-190
Session IV
- Michael L. Fredman:
The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries. 191-199 - David P. Dobkin, J. Ian Munro:
Efficient Uses of the Past. 200-206 - Philippe Flajolet, Andrew M. Odlyzko:
Exploring Binary Trees and Other Simple Trees. 207-216 - Jon Louis Bentley, Donna J. Brown:
A General Class of Resource Tradeoffs (Extended Abstract). 217-228 - Ernst-Erich Doberkat:
Some Observations on the Average Behavior of Heapsort (Preliminary Report). 229-237 - Jeffrey Scott Vitter:
Tuning the Coalesced Hashing Method to Obtain Optimum Performance (Detailed Abstract). 238-247 - Samuel W. Bent, Daniel Dominic Sleator, Robert Endre Tarjan:
Biased 2-3 Trees. 248-254 - Greg N. Frederickson:
Implicit Data Structures with Fast Update (Preliminary Report). 255-259
Session V
- Robert W. Floyd, Jeffrey D. Ullman:
The Compilation of Regular Expressions into Integrated Circuits (Extended Abstract). 260-269 - Charles E. Leiserson:
Area-Efficient Graph Layouts (for VLSI). 270-281 - Andrea S. LaPaugh:
A Polynomial Time Algorithm for Optimal Routing around a Rectangle (Extended Abstract). 282-293 - Jean Vuillemin:
A Combinatorial Limit to the Computing Power of V.L.S.I. Circuits (Extended Abstract). 294-300 - F. Frances Yao:
On the Priority Approach to Hidden-Surface Algorithms (Preliminary Report). 301-307 - Dov Harel:
A Linear Time Algorithm for the Lowest Common Ancestors Problem (Extended Abstract). 308-319 - Mark N. Wegman:
Parsing for Structural Editors (Extended Abstract). 320-327 - Mihalis Yannakakis, Christos H. Papadimitriou:
Algebraic Dependencies (Extended Abstract). 328-332 - Ashok K. Chandra, David Harel:
Structure and Complexity of Relational Queries. 333-347
Session VI
- Jia-Wei Hong:
On Similarity and Duality of Computation (Extended Abstract). 348-359 - Patrick W. Dymond, Stephen A. Cook:
Hardware Complexity and Parallel Computation (Preliminary Version). 360-372 - Nissim Francez, Michael Rodeh:
A Distributed Abstract Data Type Implemented by a Probabilistic Communication Scheme. 373-379 - Gilles Brassard:
A Time-Luck Tradeoff in Cryptography. 380-386 - Leonard M. Adleman:
On Distinguishing Prime Numbers from Composite Numbers (Abstract). 387-406 - Michael O. Rabin:
N-Process Synchronization by 4 log _2 N-Valued Shared Variables. 407-410
Late Paper
- Burchard von Braunmühl, Rutger Verbeek:
A Recognition Algorithm for Deterministic CFLS optimal in Time and Space. 411-420
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 21:06 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: