focs81.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>22. FOCS 1981: Nashville, Tennessee</title><link href="../../../dblp.css" rel="stylesheet" type="text/css" /></head><body> <table width="100%"><tr><td align="left"><a href="../../index.html"><img alt="dblp.uni-trier.de" src="../../Logo.gif" border=0 height=60 width=170></a></td> <td align="right"><a href="http://www.uni-trier.de"><img alt="www.uni-trier.de" src="../../logo_universitaet-trier.gif" border=0 height=48 width=215></a></td></tr></table> <h1>22. <a href="index.html">FOCS</a> 1981: Nashville, Tennessee</h1> 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, 28-30 October 1981. IEEE Computer Society <ul> <li><a name="Leighton81" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>: New Lower Bound Techniques for VLSI. 1-12 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Leighton81">BibTeX</a></font> <li><a name="LiptonV81" href="../../indices/a-tree/l/Lipton:Richard_J=.html">Richard J. Lipton</a>, <a href="../../indices/a-tree/v/Valdes:Jacobo.html">Jacobo Valdes</a>: Census Functions: an Approach to VLSI Upper Bounds (Preliminary Version). 13-22 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LiptonV81">BibTeX</a></font> <li><a name="LeisersonS81" href="../../indices/a-tree/l/Leiserson:Charles_E=.html">Charles E. Leiserson</a>, <a href="../../indices/a-tree/s/Saxe:James_B=.html">James B. Saxe</a>: Optimizing Synchronous Systems. 23-36 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeisersonS81">BibTeX</a></font> <li><a name="KedemZ81" href="../../indices/a-tree/k/Kedem:Zvi_M=.html">Zvi M. Kedem</a>, <a href="../../indices/a-tree/z/Zorat:Alessandro.html">Alessandro Zorat</a>: On Relations Between Input and Communication/Computation in VLSI (Preliminary Report). 37-44 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KedemZ81">BibTeX</a></font> <li><a name="GurariI81" href="../../indices/a-tree/g/Gurari:Eitan_M=.html">Eitan M. Gurari</a>, <a href="../../indices/a-tree/i/Ibarra:Oscar_H=.html">Oscar H. Ibarra</a>: Two-Way Counter Machines and Diophantine Equations. 45-52 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GurariI81">BibTeX</a></font> <li><a name="DurisG81" href="../../indices/a-tree/d/Duris:Pavol.html">Pavol Duris</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>: A Time-Space Tradeoff for Language Recognition. 53-57 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DurisG81">BibTeX</a></font> <li><a name="Loui81" href="../../indices/a-tree/l/Loui:Michael_C=.html">Michael C. Loui</a>: Simulations among Multidimensional Turing Machines (Preliminary Version). 58-67 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Loui81">BibTeX</a></font> <li><a name="Paul81" href="../../indices/a-tree/p/Paul:Wolfgang_J=.html">Wolfgang J. Paul</a>: On Heads Versus Tapes. 68-73 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Paul81">BibTeX</a></font> <li><a name="StearnsH81" href="../../indices/a-tree/s/Stearns:Richard_Edwin.html">Richard Edwin Stearns</a>, <a href="../../indices/a-tree/h/Hunt_III:Harry_B=.html">Harry B. Hunt III</a>: On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Grammars, and Automata. 74-81 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/StearnsH81">BibTeX</a></font> <li><a name="CoppersmithW81" href="../../indices/a-tree/c/Coppersmith:Don.html">Don Coppersmith</a>, <a href="../../indices/a-tree/w/Winograd:Shmuel.html">Shmuel Winograd</a>: On the Asymptotic Complexity of Matrix Multiplication (Extended Summary). 82-90 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CoppersmithW81">BibTeX</a></font> <li><a name="FeigW81" href="../../indices/a-tree/f/Feig:Ephraim.html">Ephraim Feig</a>, <a href="../../indices/a-tree/w/Winograd:Shmuel.html">Shmuel Winograd</a>: On the Direct Sum Conjecture (Extended Summary). 91-94 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeigW81">BibTeX</a></font> <li><a name="JaJa81" href="../../indices/a-tree/j/J=aacute=J=aacute=:Joseph.html">Joseph JáJá</a>: Computation of Algebraic Functions with Root Extractions. 95-100 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JaJa81">BibTeX</a></font> <li><a name="Blum81" href="../../indices/a-tree/b/Blum:Norbert.html">Norbert Blum</a>: An Omega(n^4/3) Lower Bound on the Monotone Network Complexity of n-th Degree Convolution. 101-108 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Blum81">BibTeX</a></font> <li><a name="Klawe81" href="../../indices/a-tree/k/Klawe:Maria_M=.html">Maria M. Klawe</a>: Non-Existence of One-Dimensional Expanding Graphs. 109-114 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Klawe81">BibTeX</a></font> <li><a name="Post81" href="../../indices/a-tree/p/Post:Mark_J=.html">Mark J. Post</a>: A Minimum Spanning Ellipse Algorithm. 115-122 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Post81">BibTeX</a></font> <li><a name="AviadS81" href="../../indices/a-tree/a/Aviad:Z=.html">Z. Aviad</a>, <a href="../../indices/a-tree/s/Shamir:E=.html">E. Shamir</a>: A Direct Dynamic Solution to Range Search and Related Problems for Product Regions. 123-126 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AviadS81">BibTeX</a></font> <li><a name="Vitter81" href="../../indices/a-tree/v/Vitter:Jeffrey_Scott.html">Jeffrey Scott Vitter</a>: Deletion Algorithms for Hashing that Preserve Randomness (detailed abstract). 127-132 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Vitter81">BibTeX</a></font> <li><a name="Frederickson81" href="../../indices/a-tree/f/Frederickson:Greg_N=.html">Greg N. Frederickson</a>: Implicit Data Structures for the Weighted Dictionary Problem (preliminary version). 133-139 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Frederickson81">BibTeX</a></font> <li><a name="RoundsB81" href="../../indices/a-tree/r/Rounds:William_C=.html">William C. Rounds</a>, <a href="../../indices/a-tree/b/Brookes:Stephen_D=.html">Stephen D. Brookes</a>: Possible Futures, Acceptances, Refusals, and Communicating Processes. 140-149 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RoundsB81">BibTeX</a></font> <li><a name="ItaiR81" href="../../indices/a-tree/i/Itai:Alon.html">Alon Itai</a>, <a href="../../indices/a-tree/r/Rodeh:Michael.html">Michael Rodeh</a>: Symmetry Breaking in Distributive Networks. 150-158 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ItaiR81">BibTeX</a></font> <li><a name="Dolev81" href="../../indices/a-tree/d/Dolev:Danny.html">Danny Dolev</a>: Unanimity in an Unknown and Unreliable Environment. 159-168 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Dolev81">BibTeX</a></font> <li><a name="Burns81" href="../../indices/a-tree/b/Burns:James_E=.html">James E. Burns</a>: Symmetry in Systems of Asynchronous Processes. 169-174 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Burns81">BibTeX</a></font> <li><a name="Sethi81" href="../../indices/a-tree/s/Sethi:Ravi.html">Ravi Sethi</a>: A model of concurrent database transactions (summary). 175-184 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sethi81">BibTeX</a></font> <li><a name="KanellakisP81" href="../../indices/a-tree/k/Kanellakis:Paris_C=.html">Paris C. Kanellakis</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: The Complexity of Distributed Concurrency Control. 185-197 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KanellakisP81">BibTeX</a></font> <li><a name="Vardi81" href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>: Global Decision Problems for Relational Databases. 198-202 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Vardi81">BibTeX</a></font> <li><a name="JohnsonK81" href="../../indices/a-tree/j/Johnson:David_S=.html">David S. Johnson</a>, <a href="../../indices/a-tree/k/Klug:Anthony_C=.html">Anthony C. Klug</a>: Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract). 203-211 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JohnsonK81">BibTeX</a></font> <li><a name="Reischuk81" href="../../indices/a-tree/r/Reischuk:R=uuml=diger.html">Rüdiger Reischuk</a>: A Fast Probabilistic Parallel Sorting Algorithm. 212-219 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Reischuk81">BibTeX</a></font> <li><a name="ManberT81" href="../../indices/a-tree/m/Manber:Udi.html">Udi Manber</a>, <a href="../../indices/a-tree/t/Tompa:Martin.html">Martin Tompa</a>: The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem. 220-227 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ManberT81">BibTeX</a></font> <li><a name="Verbeek81" href="../../indices/a-tree/v/Verbeek:Rutger.html">Rutger Verbeek</a>: Time-Space Trade-Offs for General Recursion. 228-234 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Verbeek81">BibTeX</a></font> <li><a name="SkyumV81" href="../../indices/a-tree/s/Skyum:Sven.html">Sven Skyum</a>, <a href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>: A Complexity Theory Based on Boolean Algebra. 244-253 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SkyumV81">BibTeX</a></font> <li><a name="BookWX81" href="../../indices/a-tree/b/Book:Ronald_V=.html">Ronald V. Book</a>, <a href="../../indices/a-tree/w/Wilson:Christopher_B=.html">Christopher B. Wilson</a>, <a href="../../indices/a-tree/x/Xu:Mei=rui.html">Mei-rui Xu</a>: Relativizing Time and Space (Preliminary Report). 254-259 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BookWX81">BibTeX</a></font> <li><a name="FurstSS81" href="../../indices/a-tree/f/Furst:Merrick_L=.html">Merrick L. Furst</a>, <a href="../../indices/a-tree/s/Saxe:James_B=.html">James B. Saxe</a>, <a href="../../indices/a-tree/s/Sipser:Michael.html">Michael Sipser</a>: Parity, Circuits, and the Polynomial-Time Hierarchy. 260-270 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FurstSS81">BibTeX</a></font> <li><a name="Mahaney81" href="../../indices/a-tree/m/Mahaney:Stephen_R=.html">Stephen R. Mahaney</a>: On the Number of P-Isomorphism Classes of NP-Complete Sets. 271-278 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Mahaney81">BibTeX</a></font> <li><a name="Statman81" href="../../indices/a-tree/s/Statman:Richard.html">Richard Statman</a>: Number Theoretic Functions Computable by Polymorphic Programs (Extended Abstract). 279-282 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Statman81">BibTeX</a></font> <li><a name="Smith81" href="../../indices/a-tree/s/Smith:Carl_H=.html">Carl H. Smith</a>: The Power of Parallelism for Automatic Program Synthesis. 283-295 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Smith81">BibTeX</a></font> <li><a name="Gacs81" href="../../indices/a-tree/g/G=aacute=cs:P=eacute=ter.html">Péter Gács</a>: On the Relation between Descriptional Complexity and Algorithmic Probability. 296-303 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gacs81">BibTeX</a></font> <li><a name="HarelPS81" href="../../indices/a-tree/h/Harel:David.html">David Harel</a>, <a href="../../indices/a-tree/p/Pnueli:Amir.html">Amir Pnueli</a>, <a href="../../indices/a-tree/s/Stavi:Jonathan.html">Jonathan Stavi</a>: Propositional Dynamic Logic of Context-Free Programs. 310-321 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HarelPS81">BibTeX</a></font> <li><a name="HalpernR81" href="../../indices/a-tree/h/Halpern:Joseph_Y=.html">Joseph Y. Halpern</a>, <a href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: The Propositional Dynamic Logic of Deterministic, Well-Structured Programs (Extended Abstract). 322-334 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HalpernR81">BibTeX</a></font> <li><a name="Tiuryn81" href="../../indices/a-tree/t/Tiuryn:Jerzy.html">Jerzy Tiuryn</a>: Unbounded Program Memory Adds to the Expressive Power of First-Order Dynamic Logic (Extended Abstract). 335-339 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Tiuryn81">BibTeX</a></font> <li><a name="Wolper81" href="../../indices/a-tree/w/Wolper:Pierre.html">Pierre Wolper</a>: Temporal Logic Can Be More Expressive. 340-348 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Wolper81">BibTeX</a></font> <li><a name="DolevY81" href="../../indices/a-tree/d/Dolev:Danny.html">Danny Dolev</a>, <a href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: On the Security of Public Key Protocols (Extended Abstract). 350-357 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DolevY81">BibTeX</a></font> <li><a name="PapadimitriouY81" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>, <a href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract). 358-363 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PapadimitriouY81">BibTeX</a></font> <li><a name="KarpS81" href="../../indices/a-tree/k/Karp:Richard_M=.html">Richard M. Karp</a>, <a href="../../indices/a-tree/s/Sipser:Michael.html">Michael Sipser</a>: Maximum Matchings in Sparse Random Graphs. 364-375 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KarpS81">BibTeX</a></font> <li><a name="MegiddoHGJP81" href="../../indices/a-tree/m/Megiddo:Nimrod.html">Nimrod Megiddo</a>, <a href="../../indices/a-tree/h/Hakimi:S=_Louis.html">S. Louis Hakimi</a>, <a href="../../indices/a-tree/g/Garey:M=_R=.html">M. R. Garey</a>, <a href="../../indices/a-tree/j/Johnson:David_S=.html">David S. Johnson</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: The Complexity of Searching a Graph (Preliminary Version). 376-385 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MegiddoHGJP81">BibTeX</a></font> <li><a name="FlajoletS81" href="../../indices/a-tree/f/Flajolet:Philippe.html">Philippe Flajolet</a>, <a href="../../indices/a-tree/s/Steyaert:Jean=Marc.html">Jean-Marc Steyaert</a>: A Complexity Calculus for Classes of Recursive Search Programs over Tree Structures. 386-393 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FlajoletS81">BibTeX</a></font> <li><a name="Ben-Or81" href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>: Probabilistic Algorithms in Finite Fields. 394-398 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-Or81">BibTeX</a></font> <li><a name="Megiddo81" href="../../indices/a-tree/m/Megiddo:Nimrod.html">Nimrod Megiddo</a>: Applying Parallel Computation Algorithms in the Design of Serial Algorithms. 399-408 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Megiddo81">BibTeX</a></font> <li><a name="AdlemanO81" href="../../indices/a-tree/a/Adleman:Leonard_M=.html">Leonard M. Adleman</a>, <a href="../../indices/a-tree/o/Odlyzko:Andrew_M=.html">Andrew M. Odlyzko</a>: Irreducibility Testing and Factorization of Polynomials (Extended Abstract). 409-418 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AdlemanO81">BibTeX</a></font> <li><a name="Pratt81" href="../../indices/a-tree/p/Pratt:Vaughan_R=.html">Vaughan R. Pratt</a>: A Decidable mu-Calculus: Preliminary Report. 421-427 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Pratt81">BibTeX</a></font> </ul><p><div class="footer"> <a href="../../index.html">Home</a> | <a href="../indexa.html">Conferences</a> | <a href="../../journals/index.html">Journals</a> | <a href="../../series/index.html">Series</a> | <a href="../../about/faq.html">FAQ</a> — Search: <a href="http://dblp.l3s.de">Faceted</a> | <a href="http://dblp.mpi-inf.mpg.de/dblp-mirror/index.php">Complete</a> | <a href="../../indices/a-tree/index.html">Author</a></div> <small><a href="../../copyright.html">Copyright ©</a> Sat May 16 23:12:24 2009 by <a href="http://www.informatik.uni-trier.de/~ley/addr.html">Michael Ley</a> (<a href="mailto:ley@uni-trier.de">ley@uni-trier.de</a>)</small></p></body></html>
SIGMOD News
