stoc81.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 1981</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>13. <a href="index.html">STOC</a> 1981</h1> Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA. ACM 1981 <ul> <li><a name="CulikH81" href="../../indices/a-tree/c/Culik_II:Karel.html">Karel Culik II</a>, <a href="../../indices/a-tree/h/Harju:Tero.html">Tero Harju</a>: The omega-Sequence Equivalence Problem for DOL Systems Is Decidable. 1-6 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CulikH81">BibTeX</a></font> <li><a name="Chew81" href="../../indices/a-tree/c/Chew:Paul.html">Paul Chew</a>: Unique Normal Forms in Term Rewriting Systems with Repeated Variables. 7-18 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Chew81">BibTeX</a></font> <li><a name="HawrusikVY81" href="../../indices/a-tree/h/Hawrusik:Frank_M=.html">Frank M. Hawrusik</a>, <a href="../../indices/a-tree/v/Venkataraman:K=_N=.html">K. N. Venkataraman</a>, <a href="../../indices/a-tree/y/Yasuhara:Ann.html">Ann Yasuhara</a>: Classes of Functions for Computing on Binary Trees (Extended Abstract). 19-27 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HawrusikVY81">BibTeX</a></font> <li><a name="KrishnamurthyM81" href="../../indices/a-tree/k/Krishnamurthy:Balakrishnan.html">Balakrishnan Krishnamurthy</a>, <a href="../../indices/a-tree/m/Moll:Robert_N=.html">Robert N. Moll</a>: Examples of Hard Tautologies in the Propositional Calculus. 28-37 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KrishnamurthyM81">BibTeX</a></font> <li><a name="Leivant81" href="../../indices/a-tree/l/Leivant:Daniel.html">Daniel Leivant</a>: The Complexity of Parameter Passing in Polymorphic Procedures (or: Programming Language Theorems Independent of Very Strong Theories). 38-45 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Leivant81">BibTeX</a></font> <li><a name="MullerS81" href="../../indices/a-tree/m/Muller:David_E=.html">David E. Muller</a>, <a href="../../indices/a-tree/s/Schupp:Paul_E=.html">Paul E. Schupp</a>: Pushdown Automata, Graphs, Ends, Second-Order Logic, and Reachability Problems. 46-54 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MullerS81">BibTeX</a></font> <li><a name="JosephY81" href="../../indices/a-tree/j/Joseph:Deborah.html">Deborah Joseph</a>, <a href="../../indices/a-tree/y/Young:Paul.html">Paul Young</a>: Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (Preliminary Abstract). 55-61 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/JosephY81">BibTeX</a></font> <li><a name="Kosaraju81" href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>: Localized Search in Sorted Lists. 62-69 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kosaraju81">BibTeX</a></font> <li><a name="Chazelle81" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: Convex Decompositions of Polyhedra. 70-79 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Chazelle81">BibTeX</a></font> <li><a name="KimR81" href="../../indices/a-tree/k/Kim:Chul_E=.html">Chul E. Kim</a>, <a href="../../indices/a-tree/r/Rosenfeld:Azriel.html">Azriel Rosenfeld</a>: Digital Straightness and Convexity (Extended Abstract). 80-89 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KimR81">BibTeX</a></font> <li><a name="GonnetM81" href="../../indices/a-tree/g/Gonnet:Gaston_H=.html">Gaston H. Gonnet</a>, <a href="../../indices/a-tree/m/Munro:J=_Ian.html">J. Ian Munro</a>: A Linear Probing Sort and its Analysis (Preliminary Draft). 90-95 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GonnetM81">BibTeX</a></font> <li><a name="Fich81" href="../../indices/a-tree/f/Fich:Faith_E=.html">Faith E. Fich</a>: Lower Bounds for the Cycle Detection Problem. 96-105 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Fich81">BibTeX</a></font> <li><a name="GalilS81" href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/s/Seiferas:Joel_I=.html">Joel I. Seiferas</a>: Time-Space-Optimal String Matching. 106-113 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GalilS81">BibTeX</a></font> <li><a name="SleatorT81" href="../../indices/a-tree/s/Sleator:Daniel_Dominic.html">Daniel Dominic Sleator</a>, <a href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>: A Data Structure for Dynamic Trees. 114-122 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SleatorT81">BibTeX</a></font> <li><a name="Yao81" href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: On the Parallel Computation for the Knapsack Problem. 123-127 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Yao81">BibTeX</a></font> <li><a name="ArjomandiFL81" href="../../indices/a-tree/a/Arjomandi:Eshrat.html">Eshrat Arjomandi</a>, <a href="../../indices/a-tree/f/Fischer:Michael_J=.html">Michael J. Fischer</a>, <a href="../../indices/a-tree/l/Lynch:Nancy_A=.html">Nancy A. Lynch</a>: A Difference in Efficiency between Synchronous and Asynchronous Systems. 128-132 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ArjomandiFL81">BibTeX</a></font> <li><a name="ReifS81" href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>, <a href="../../indices/a-tree/s/Spirakis:Paul_G=.html">Paul G. Spirakis</a>: Distributed Algorithms for Synchronizing Interprocess Communication within Real Time. 133-145 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ReifS81">BibTeX</a></font> <li><a name="Chan81" href="../../indices/a-tree/c/Chan:Tat=hung.html">Tat-hung Chan</a>: Reversal Complexity of Counter Machines. 146-157 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Chan81">BibTeX</a></font> <li><a name="Simon81" href="../../indices/a-tree/s/Simon:Janos.html">Janos Simon</a>: Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (Preliminary Version). 158-167 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Simon81">BibTeX</a></font> <li><a name="BertoniMS81" href="../../indices/a-tree/b/Bertoni:Alberto.html">Alberto Bertoni</a>, <a href="../../indices/a-tree/m/Mauri:Giancarlo.html">Giancarlo Mauri</a>, <a href="../../indices/a-tree/s/Sabadini:Nicoletta.html">Nicoletta Sabadini</a>: A Characterization of the Class of Functions Computable in Polynomial Time on Random Access Machines. 168-176 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BertoniMS81">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>: Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version). 177-188 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DurisG81">BibTeX</a></font> <li><a name="King81" href="../../indices/a-tree/k/King:K=_N=.html">K. N. King</a>: Measures of Parallelism in Alternating Computation Trees (Extended Abstract). 189-201 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/King81">BibTeX</a></font> <li><a name="UkkonenS81" href="../../indices/a-tree/u/Ukkonen:Esko.html">Esko Ukkonen</a>, <a href="../../indices/a-tree/s/Soisalon=Soininen:Eljas.html">Eljas Soisalon-Soininen</a>: LALR(k) Testing is PSPACE-Complete. 202-206 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/UkkonenS81">BibTeX</a></font> <li><a name="MonienS81" href="../../indices/a-tree/m/Monien:Burkhard.html">Burkhard Monien</a>, <a href="../../indices/a-tree/s/Sudborough:Ivan_Hal.html">Ivan Hal Sudborough</a>: Bandwidth Constrained NP-Complete Problems. 207-217 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MonienS81">BibTeX</a></font> <li><a name="Orlin81" href="../../indices/a-tree/o/Orlin:James_B=.html">James B. Orlin</a>: The Complexity of Dynamic Languages and Dynamic Optimization Problems. 218-227 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Orlin81">BibTeX</a></font> <li><a name="AdachiIK81" href="../../indices/a-tree/a/Adachi:Akeo.html">Akeo Adachi</a>, <a href="../../indices/a-tree/i/Iwata:Shigeki.html">Shigeki Iwata</a>, <a href="../../indices/a-tree/k/Kasai:Takumi.html">Takumi Kasai</a>: Low Level Complexity for Combinatorial Games. 228-237 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AdachiIK81">BibTeX</a></font> <li><a name="Mayr81" href="../../indices/a-tree/m/Mayr:Ernst_W=.html">Ernst W. Mayr</a>: An Algorithm for the General Petri Net Reachability Problem. 238-246 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Mayr81">BibTeX</a></font> <li><a name="GalilP81" href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/p/Paul:Wolfgang_J=.html">Wolfgang J. Paul</a>: An Efficient General Purpose Parallel Computer. 247-262 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GalilP81">BibTeX</a></font> <li><a name="ValiantB81" href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>, <a href="../../indices/a-tree/b/Brebner:Gordon_J=.html">Gordon J. Brebner</a>: Universal Schemes for Parallel Communication. 263-277 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ValiantB81">BibTeX</a></font> <li><a name="KleitmanLLM81" href="../../indices/a-tree/k/Kleitman:Daniel_J=.html">Daniel J. Kleitman</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/l/Lepley:Margaret.html">Margaret Lepley</a>, <a href="../../indices/a-tree/m/Miller:Gary_L=.html">Gary L. Miller</a>: New Layouts for the Shuffle-Exchange Graph (Extended Abstract). 278-292 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KleitmanLLM81">BibTeX</a></font> <li><a name="PatersonRS81" href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>, <a href="../../indices/a-tree/r/Ruzzo:Walter_L=.html">Walter L. Ruzzo</a>, <a href="../../indices/a-tree/s/Snyder:Lawrence.html">Lawrence Snyder</a>: Bounds on Minimax Edge Length for Complete Binary Trees (Extended Abstract). 293-299 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PatersonRS81">BibTeX</a></font> <li><a name="LiptonS81" href="../../indices/a-tree/l/Lipton:Richard_J=.html">Richard J. Lipton</a>, <a href="../../indices/a-tree/s/Sedgewick:Robert.html">Robert Sedgewick</a>: Lower Bounds for VLSI. 300-307 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LiptonS81">BibTeX</a></font> <li><a name="DolevKSSU81" href="../../indices/a-tree/d/Dolev:Danny.html">Danny Dolev</a>, <a href="../../indices/a-tree/k/Karplus:Kevin.html">Kevin Karplus</a>, <a href="../../indices/a-tree/s/Siegel:Alan.html">Alan Siegel</a>, <a href="../../indices/a-tree/s/Strong:Alex.html">Alex Strong</a>, <a href="../../indices/a-tree/u/Ullman:Jeffrey_D=.html">Jeffrey D. Ullman</a>: Optimal Wiring between Rectangles. 312-317 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DolevKSSU81">BibTeX</a></font> <li><a name="ChazelleM81" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>, <a href="../../indices/a-tree/m/Monier:Louis.html">Louis Monier</a>: A Model of Computation for VLSI with Related Complexity Results. 318-325 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChazelleM81">BibTeX</a></font> <li><a name="HongK81" href="../../indices/a-tree/h/Hong:Jia=Wei.html">Jia-Wei Hong</a>, <a href="../../indices/a-tree/k/Kung:H=_T=.html">H. T. Kung</a>: I/O Complexity: The Red-Blue Pebble Game. 326-333 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HongK81">BibTeX</a></font> <li><a name="HongR81" href="../../indices/a-tree/h/Hong:Jia=Wei.html">Jia-Wei Hong</a>, <a href="../../indices/a-tree/r/Rosenberg:Arnold_L=.html">Arnold L. Rosenberg</a>: Graphs that Are Almost Binary Trees (Preliminary Version). 334-341 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HongR81">BibTeX</a></font> <li><a name="ChandraLM81" href="../../indices/a-tree/c/Chandra:Ashok_K=.html">Ashok K. Chandra</a>, <a href="../../indices/a-tree/l/Lewis:Harry_R=.html">Harry R. Lewis</a>, <a href="../../indices/a-tree/m/Makowsky:Johann_A=.html">Johann A. Makowsky</a>: Embedded Implicational Dependencies and their Inference Problem. 342-354 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChandraLM81">BibTeX</a></font> <li><a name="BeeriFMMUY81" href="../../indices/a-tree/b/Beeri:Catriel.html">Catriel Beeri</a>, <a href="../../indices/a-tree/f/Fagin:Ronald.html">Ronald Fagin</a>, <a href="../../indices/a-tree/m/Maier:David.html">David Maier</a>, <a href="../../indices/a-tree/m/Mendelzon:Alberto_O=.html">Alberto O. Mendelzon</a>, <a href="../../indices/a-tree/u/Ullman:Jeffrey_D=.html">Jeffrey D. Ullman</a>, <a href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: Properties of Acyclic Database Schemes. 355-362 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BeeriFMMUY81">BibTeX</a></font> <li><a name="Yannakakis81" href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: Issues of Correctness in Database Concurrency Control by Locking. 363-367 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Yannakakis81">BibTeX</a></font> <li><a name="Parisi-Presicce81" href="../../indices/a-tree/p/Parisi=Presicce:Francesco.html">Francesco Parisi-Presicce</a>: On the Faithful Regular Extensions of Iterative Algebras. 368-374 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Parisi-Presicce81">BibTeX</a></font> <li><a name="Streett81" href="../../indices/a-tree/s/Streett:Robert_S=.html">Robert S. Streett</a>: Propositional Dynamic Logic of Looping and Converse. 375-383 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Streett81">BibTeX</a></font> <li><a name="ChandraHMP81" href="../../indices/a-tree/c/Chandra:Ashok_K=.html">Ashok K. Chandra</a>, <a href="../../indices/a-tree/h/Halpern:Joseph_Y=.html">Joseph Y. Halpern</a>, <a href="../../indices/a-tree/m/Meyer:Albert_R=.html">Albert R. Meyer</a>, <a href="../../indices/a-tree/p/Parikh:Rohit.html">Rohit Parikh</a>: Equations between Regular Terms and an Application to Process Logic. 384-390 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChandraHMP81">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:43:09 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
