Journal of the ACM -- 1982

Volume 29, Number 1, January 1982

• George W. Ernst and Michael M. Goldstein. Mechanical discovery of classes of problem-solving strategies. Journal of the ACM, 29(1):1-23, January 1982. [BibTeX entry]

• Eugene C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24-32, January 1982. Citations. [BibTeX entry]

• Drew McDermott. Nonmonotonic logic II: Nonmonotonic modal theories. Journal of the ACM, 29(1):33-57, January 1982. Citations. [BibTeX entry]

• Ronald I. Becker, Stephen R. Schach, and Yehoshua Perl. A shifting algorithm for min-max tree partitioning. Journal of the ACM, 29(1):58-67, January 1982. [BibTeX entry]

• Christoph M. Hoffmann and Michael J. O'Donnell. Pattern matching in trees. Journal of the ACM, 29(1):68-95, January 1982. Citations. [BibTeX entry]

• Zvi Galil. An almost linear-time algorithm for computing a dependency basis in a relational database. Journal of the ACM, 29(1):96-102, January 1982. Citations. [BibTeX entry]

• Yehoshua Sagiv and Scott F. Walecka. Subset dependencies and a completeness result for a subclass of embedded multivalued dependencies. Journal of the ACM, 29(1):103-117, January 1982. Citations. [BibTeX entry]

• H. A. Maurer, A. Salomaa, and D. Wood. Dense hierarchies of grammatical families. Journal of the ACM, 29(1):118-126, January 1982. [BibTeX entry]

• D. Chow and C. T. Yu. On the construction of feedback queries. Journal of the ACM, 29(1):127-151, January 1982. [BibTeX entry]

• C. T. Yu, K. Lam, and G. Salton. Term weighting in information retrieval using the term precision model. Journal of the ACM, 29(1):152-170, January 1982. [BibTeX entry]

• Ronald V. Book. Confluent and other types of Thue systems. Journal of the ACM, 29(1):171-182, January 1982. Citations. [BibTeX entry]

• James E. Burns, Paul Jackson, Nancy A. Lynch, Michael J. Fischer, and Gary L. Peterson. Data requirements for implementation of N-process mutual exclusion using a single shared variable. Journal of the ACM, 29(1):183-205, January 1982. Citations. [BibTeX entry]

• H.-D. Ehrich. On the theory of specification, implementation, and parametrization of abstract data types. Journal of the ACM, 29(1):206-227, January 1982. Citations. [BibTeX entry]

• H. B. Hunt, III. On the complexity of flowchart and loop program schemes and programming languages. Journal of the ACM, 29(1):228-249, January 1982. [BibTeX entry]

• Michael L. Fredman. The complexity of maintaining an array and computing its partial sums. Journal of the ACM, 29(1):250-260, January 1982. Citations. [BibTeX entry]

• Charles Rackoff. Relativized questions involving probabilistic algorithms. Journal of the ACM, 29(1):261-268, January 1982. Citations. [BibTeX entry]

Volume 29, Number 2, April 1982

• Steve Winker. Generation and verification of finite models and counterexamples using an automated theorem prover answering two open questions. Journal of the ACM, 29(2):273-284, April 1982. Citations. [BibTeX entry]

• Christos H. Papadimitriou and Mihalis Yannakakis. The complexity of restricted spanning tree problems. Journal of the ACM, 29(2):285-309, April 1982. Citations. [BibTeX entry]

• Barry E. Jacobs. On database logic. Journal of the ACM, 29(2):310-332, April 1982. Citations. [BibTeX entry]

• Y. Edmund Lien. On the equivalence of database models. Journal of the ACM, 29(2):333-362, April 1982. Citations. [BibTeX entry]

• Fereidoon Sadri and Jeffrey D. Ullman. Template dependencies: A large class of dependencies in relational databases and its complete axiomatization. Journal of the ACM, 29(2):363-372, April 1982. Citations. [BibTeX entry]

• Edward Sciore. A complete axiomatization of full join dependencies. Journal of the ACM, 29(2):373-393, April 1982. Citations. [BibTeX entry]

• Ravi Sethi. Useless actions make a difference: Strict serializability of database updates. Journal of the ACM, 29(2):394-403, April 1982. [BibTeX entry]

• Christopher Bader and Arnaldo Moura. A generalization of Ogden's lemma. Journal of the ACM, 29(2):404-407, April 1982. Citations. [BibTeX entry]

• Jacques Cohen, Timothy Hickey, and Joel Katcoff. Upper bounds for speedup in parallel parsing. Journal of the ACM, 29(2):408-428, April 1982. Citations. [BibTeX entry]

• H. B. Hunt, III. On the decidability of grammar problems. Journal of the ACM, 29(2):429-447, April 1982. [BibTeX entry]

• Theodore Brown. Determination of the conditional response for quantum allocation algorithms. Journal of the ACM, 29(2):448-460, April 1982. [BibTeX entry]

• R. M. Bryant. Maximum processing rates of memory bound systems. Journal of the ACM, 29(2):461-477, April 1982. [BibTeX entry]

• Hisao Kameda. A finite-source queue with different customers. Journal of the ACM, 29(2):478-491, April 1982. [BibTeX entry]

• Simon S. Lam. Dynamic scaling and growth behavior of queuing network normalization constants. Journal of the ACM, 29(2):492-513, April 1982. Citations. [BibTeX entry]

• Manfred Ruschitzka. The performance of job classes with distinct policy functions. Journal of the ACM, 29(2):514-526, April 1982. [BibTeX entry]

• Percy Tzelnic and Izidor Gertner. An approach to program behavior modeling and optimal memory control. Journal of the ACM, 29(2):527-554, April 1982. [BibTeX entry]

• Albert R. Meyer and Joseph Y. Halpern. Axiomatic definitions of programming languages: A theoretical assessment. Journal of the ACM, 29(2):555-576, April 1982. Citations. [BibTeX entry]

• Michael A. Arbib and Ernest G. Manes. The pattern-of-calls expansion is the canonical fixpoint for recursive definitions. Journal of the ACM, 29(2):577-602, April 1982. Citations. [BibTeX entry]

Volume 29, Number 3, July 1982

• Robert W. Floyd and Jeffrey D. Ullman. The compilation of regular expressions into integrated circuits. Journal of the ACM, 29(3):603-622, July 1982. [BibTeX entry]

• K. Takamizawa, T. Nishizeki, and N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs. Journal of the ACM, 29(3):623-641, July 1982. Citations. [BibTeX entry]

• David Nassimi and Sartaj Sahni. Parallel permutation and sorting algorithms and a new generalized connection network. Journal of the ACM, 29(3):642-667, July 1982. Citations. [BibTeX entry]

• Peter Honeyman. Testing satisfaction of functional dependencies. Journal of the ACM, 29(3):668-677, July 1982. Citations. [BibTeX entry]

• Seymour Ginsburg and Sami Mohammed Zaiddan. Properties of functional-dependency families. Journal of the ACM, 29(3):678-698, July 1982. Citations. [BibTeX entry]

• Anthony Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. Journal of the ACM, 29(3):699-717, July 1982. Citations. [BibTeX entry]

• Mihalis Yannakakis. A theory of safe locking policies in database systems. Journal of the ACM, 29(3):718-740, July 1982. Citations. [BibTeX entry]

• Dana Angluin. Inference of reversible languages. Journal of the ACM, 29(3):741-765, July 1982. Citations. [BibTeX entry]

• Harold N. Gabow. An almost-linear algorithm for two-processor scheduling. Journal of the ACM, 29(3):766-780, July 1982. Citations. [BibTeX entry]

• Errol L. Lloyd. Critical path scheduling with resource and processor constraints. Journal of the ACM, 29(3):781-811, July 1982. [BibTeX entry]

• Charles Martel. Preemptive scheduling with release times, deadlines, and due times. Journal of the ACM, 29(3):812-829, July 1982. Citations. [BibTeX entry]

• Christopher L. Samelson and William G. Bulgren. A note on product-form solution for queuing networks with Poisson arrivals and general service-time distributions with finite means. Journal of the ACM, 29(3):830-840, July 1982. [BibTeX entry]

• Krzysztof R. Apt and M. H. Van Emden. Contributions to the theory of logic programming. Journal of the ACM, 29(3):841-862, July 1982. Citations. [BibTeX entry]

• Eitan M. Gurari and Oscar H. Ibarra. Two-way counter machines and Diophantine equations. Journal of the ACM, 29(3):863-873, July 1982. Citations. [BibTeX entry]

• Mark Jerrum and Marc Snir. Some exact complexity results for straight-line computations over semirings. Journal of the ACM, 29(3):874-897, July 1982. Citations. [BibTeX entry]

• Andrew Chi-Chih Yao. On parallel computation for the knapsack problem. Journal of the ACM, 29(3):898-903, July 1982. Citations. [BibTeX entry]

• R. P. Brent and H. T. Kung. Corrigendum: ``The area-time complexity of binary multiplication''. Journal of the ACM, 29(3):904, July 1982. References. [BibTeX entry]

Volume 29, Number 4, October 1982

• Fouad A. Tobagi. Distributions of packet delay and interdeparture time in slotted ALOHA and carrier sense multiple access. Journal of the ACM, 29(4):907-927, October 1982. References, etc. [BibTeX entry]

• James A. Storer and Thomas G. Szymanski. Data compression via textural substitution. Journal of the ACM, 29(4):928-951, October 1982. References, Citations, etc. [BibTeX entry]

• Ronald Fagin. Horn clauses and database dependencies. Journal of the ACM, 29(4):952-985, October 1982. References, Citations, etc. [BibTeX entry]

• John Grant and Barry E. Jacobs. On the family of generalized dependency constraints. Journal of the ACM, 29(4):986-997, October 1982. References, Citations, etc. [BibTeX entry]

• Christos H. Papadimitriou. A theorem in database concurrency control. Journal of the ACM, 29(4):998-1006, October 1982. References, Citations, etc. [BibTeX entry]

• John C. Beatty. On the relationship between LL(1) and LR(1) grammars. Journal of the ACM, 29(4):1007-1022, October 1982. References, etc. [BibTeX entry]

• Toshimi Minoura. Deadlock avoidance revisited. Journal of the ACM, 29(4):1023-1048, October 1982. References, etc. [BibTeX entry]

• Eugene W. Stark. Semaphore primitives and starvation-free mutual exclusion. Journal of the ACM, 29(4):1049-1072, October 1982. References, Citations, etc. [BibTeX entry]

• Leslie M. Goldschlager. A universal interconnection pattern for parallel computers. Journal of the ACM, 29(4):1073-1086, October 1982. References, Citations, etc. [BibTeX entry]

• Thomas Lengauer and Robert E. Tarjan. Asymptotically tight bounds on time-space trade-offs in a pebble game. Journal of the ACM, 29(4):1087-1130, October 1982. References, etc. [BibTeX entry]

• David W. Matula. Basic digit sets for radix representation. Journal of the ACM, 29(4):1131-1143, October 1982. Citations, etc. [BibTeX entry]

• Carl H. Smith. The power of pluralism for automatic program synthesis. Journal of the ACM, 29(4):1144-1165, October 1982. References, Citations, etc. [BibTeX entry]

• Esko Ukkonen. The equivalence problem for some non-real-time deterministic pushdown automata. Journal of the ACM, 29(4):1166-1181, October 1982. References, etc. [BibTeX entry]

Shortcuts: