@article{Bagchi-Mahanti/83a,
AUTHOR = {Bagchi, A. and Mahanti, A.},
TITLE = {Search algorithms under different kinds of heuristics - a comparative study},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {1-21},
YEAR = {1983},
KEYWORDS = {Heuristic search, admissibility, nonmisleading heuristic, proper heuristic, path-dependent heuristic, branch-and-bound algorithms},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{de_Champeaux/83,
AUTHOR = {de Champeaux, D.},
TITLE = {Bidirectional heuristic search again},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {22-32},
YEAR = {1983},
KEYWORDS = {Bidirectional search, shortest path, consistency, optimality theorem},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Sarwate/83,
AUTHOR = {Sarwate, D.V.},
TITLE = {A note on ``a note on multiple error detection in ASCII numeric data communication''},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {33-35},
YEAR = {1983},
KEYWORDS = {Multiple error detection, error correction, parity checks, Reed-Solomon codes},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Klug/83,
AUTHOR = {Klug, A.},
TITLE = {Locking expressions for increased database concurrency},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {36-54},
YEAR = {1983},
KEYWORDS = {Expression lock, concurrency control, relational database, tableau, chase},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Korth/83,
AUTHOR = {Korth, H.F.},
TITLE = {Locking primitives in a database system},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {55-79},
YEAR = {1983},
KEYWORDS = {Concurrency control, locking, serializability},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Frederickson/83a,
AUTHOR = {Frederickson, G.N.},
TITLE = {Implicit data structures for the dictionary problem},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {80-94},
YEAR = {1983},
KEYWORDS = {Implicit data structure dictionary, on-line complexity, partial match retrieval, average performance},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Maurer-Salomaa-Wood/83a,
AUTHOR = {Maurer, H.A. and Salomaa, A. and Wood, D.},
TITLE = {A supernormal-form theorem for context-free grammars},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {95-102},
YEAR = {1983},
KEYWORDS = {Normal forms, grammar forms, completeness},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Lord-Kowalik-Kumar/83,
AUTHOR = {Lord, R.E. and Kowalik, J.S. and Kumar, S.P.},
TITLE = {Solving linear algebraic equations on an MIMD computer},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {103-117},
YEAR = {1983},
KEYWORDS = {MIMD computer, Gaussian elimination, Givens triangularization},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Gavish/83,
AUTHOR = {Gavish, B.},
TITLE = {Formulations and algorithms for the capacitated minimal directed tree problem},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {118-132},
YEAR = {1983},
KEYWORDS = {Capacitated tree problems},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Kannan/83b,
AUTHOR = {Kannan, R.},
TITLE = {Polynomial-time aggregation of integer programming problems},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {133-145},
YEAR = {1983},
KEYWORDS = {Polynomial-time algorithm, aggregation, Diophantine equations, knapsack problem},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Schassberger-Daduna/83,
AUTHOR = {Schassberger, R. and Daduna, H.},
TITLE = {The time for a round trip in a cycle of exponential queues},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {146-150},
YEAR = {1983},
KEYWORDS = {Queuing networks, cycle of queues, cycle time distribution, FIFO queues},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fortune-Leivant-ODonnell/83,
AUTHOR = {Fortune, S. and Leivant, D. and O'Donnell, M.},
TITLE = {The expressiveness of simple and second-order type structures},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {151-185},
YEAR = {1983},
KEYWORDS = {$\lambda$ calculus, type structures, polymorphism, independence, simple types, second-order types, Peano arithmetic},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Strong/83,
AUTHOR = {Strong, H.R.},
TITLE = {Vector execution of flow graphs},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {186-196},
YEAR = {1983},
KEYWORDS = {Vector processing, parallelism},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Apt/83,
AUTHOR = {Apt, K.R.},
TITLE = {Formal justification of a proof system for communicating sequential processes},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {197-216},
YEAR = {1983},
KEYWORDS = {Partial correctness, CSP, operational semantics, cooperating proofs, soundness, relative completeness, total correctness},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Ibarra-Moran/83a,
AUTHOR = {Ibarra, O.H. and Moran, S.},
TITLE = {Probabilistic algorithms for deciding equivalence of straigth-line programs},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {1},
PAGES = {217-228},
YEAR = {1983},
KEYWORDS = {Straight-line program, equivalence problem, NP-hard, infinite field, characteristic of a field},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Vitter/83,
AUTHOR = {Vitter, J.S.},
TITLE = {Analysis of the search performance of coalesced hashing},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {2},
PAGES = {231-258},
YEAR = {1983},
KEYWORDS = {Analysis of algorithms, coalesced hashing, hashing, data structures, asymptotic analysis, average case, optimization, hash function},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Sippu-Soisalon-Soininen-Ukkonen/83,
AUTHOR = {Sippu, S. and Soisalon-Soininen, E. and Ukkonen, E.},
TITLE = {The complexity of LALR(k) testing},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {2},
PAGES = {259-270},
YEAR = {1983},
KEYWORDS = {Computational complexity, context-free grammars, parsing, LALR(k) grammars},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Stewart/83,
AUTHOR = {Stewart, G.W.},
TITLE = {Computable error bounds for aggregated Markov chains},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {2},
PAGES = {271-285},
YEAR = {1983},
KEYWORDS = {Markov chains, decomposability, stationary probability, eigenvalues},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Chandy-Martin/83,
AUTHOR = {Chandy, K.M. and Martin, A.J.},
TITLE = {A characterization of product-form queuing networks},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {2},
PAGES = {286-299},
YEAR = {1983},
KEYWORDS = {Networks, product form},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Jaffe/83,
AUTHOR = {Jaffe, J.M.},
TITLE = {Decentralized simulation of resource managers},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {2},
PAGES = {300-322},
YEAR = {1983},
KEYWORDS = {Distributed control, resource allocation},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Brand-Zafiropulo/83,
AUTHOR = {Brand, D. and Zafiropulo, P.},
TITLE = {On communicating finite-state machines},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {2},
PAGES = {323-342},
YEAR = {1983},
KEYWORDS = {Communications},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Nourani/83,
AUTHOR = {Nourani, C.F.},
TITLE = {Abstract implementations and their correctness proofs},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {2},
PAGES = {343-359},
YEAR = {1983},
KEYWORDS = {Program verification and synthesis, equational theories, formal specifications, initial algebras},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Tarsi/83,
AUTHOR = {Tarsi, M.},
TITLE = {Optimal search on some game trees},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {389-396},
YEAR = {1983},
KEYWORDS = {Game strategies, alpha-beta pruning, average optimal algorithms},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Rosenberg/83,
AUTHOR = {Rosenberg, A.L.},
TITLE = {Three-dimensional VLSI: A case study},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {397-416},
YEAR = {1983},
KEYWORDS = {three-dimensional circuit realizations, graph embeddings, permutation networks, FFT circuits},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Matula-Beck/83,
AUTHOR = {Matula, D.W. and Beck, L.L.},
TITLE = {Smallest-last ordering and clustering and graph coloring algorithms},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {417-427},
YEAR = {1983},
KEYWORDS = {Adjacency structure, cluster analysis, degree structure, graph coloring, hierarchical cluster analysis, linear-time algorithms, linkage clustering, priority search, smallest-last coloring, smallest-last ordering},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Supowit/83,
AUTHOR = {Supowit, K.J.},
TITLE = {The relative neighborhood graph, with an application to minimum spanning trees},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {428-448},
YEAR = {1983},
KEYWORDS = {Relative neighborhood graph, minimum spanning tree},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Arjomandi-Fischer-Lynch/83,
AUTHOR = {Arjomandi, E. and Fischer, M.J. and Lynch, N.A.},
TITLE = {Efficiency of synchronous versus asynchronous distributed systems},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {449-456},
YEAR = {1983},
KEYWORDS = {Synchronous system, asynchronous system, clock, distributed system},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Coffman-Sethi/83,
AUTHOR = {Coffman, E.G., Jr. and Sethi, R.},
TITLE = {Instruction sets for evaluating arithmetic expressions},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {457-478},
YEAR = {1983},
KEYWORDS = {Register-oriented machines, stack-oriented machines, arithmetic expression trees},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Beeri-Fagin-Maier-Yannakakis/83,
AUTHOR = {Beeri, C. and Fagin, R. and Maier, D. and Yannakakis, M.},
TITLE = {On the desirability of acyclic database schemes},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {479-513},
YEAR = {1983},
KEYWORDS = {Acyclicity, hypergraph, database scheme, relational database, multivalued dependency, join dependency, conflict-freedom},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Fagin/83,
AUTHOR = {Fagin, R.},
TITLE = {Degrees of acyclicity for hypergraphs and relational database schemes},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {514-550},
YEAR = {1983},
KEYWORDS = {Acyclicity, hypergraph, database scheme, relational database, join dependency, loop-free Bachman diagram},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Gusfield/83,
AUTHOR = {Gusfield, D.},
TITLE = {Parametric combinatorial computing and a problem of program module distribution},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {551-563},
YEAR = {1983},
KEYWORDS = {Combinatorial computing, parametric programming},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Suri/83,
AUTHOR = {Suri, R.},
TITLE = {Robustness of queuing network formulas},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {564-594},
YEAR = {1983},
KEYWORDS = {Closed queuing networks, analytical models, sensitivity analysis, performance bounds},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Raoult-Sethi/83,
AUTHOR = {Raoult, J.-C. and Sethi, R.},
TITLE = {Properties of a notation for combining functions},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {595-611},
YEAR = {1983},
KEYWORDS = {Combinators, continuations},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Clarke-German-Halpern/83,
AUTHOR = {Clarke, E.M., Jr. and German, S.M. and Halpern, J.Y.},
TITLE = {Effective axiomatizations of Hoare logics},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {612-636},
YEAR = {1983},
KEYWORDS = {Partial-correctness assertions, total-correctness assertions, termination assertions, sound and relatively complete axiomatization expressiveness, Lipton's theorem},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Gati/83,
AUTHOR = {Gati, G.},
TITLE = {The complexity of solving polynomial equations by quadrature},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {637-640},
YEAR = {1983},
KEYWORDS = {Square roots, sharp lower bounds for computational complexity, Galois theory, computation of roots of polynomials, problems solvable by ruler and compass},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Ibarra-Leininger/83,
AUTHOR = {Ibarra, O.H. and Leininger, B.S.},
TITLE = {On the simplification and equivalence problems for straight-line programs},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {641-656},
YEAR = {1983},
KEYWORDS = {Equivalence, one-equivalence, simplification, straight-line program, decidability, undecidability, Hilbert's tenth problem},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Jaja/83,
AUTHOR = {J{\'a}j{\'a}, J.},
TITLE = {Time-space trade-offs for some algebraic problems},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {657-667},
YEAR = {1983},
KEYWORDS = {Time-space trade-offs},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Lamport/83,
AUTHOR = {Lamport, L.},
TITLE = {The weak Byzantine generals problem},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {668-676},
YEAR = {1983},
KEYWORDS = {Agreement, interactive consistency, distributed systems},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Xu-Doner-Book/83,
AUTHOR = {Xu, M.-R. and Doner, J.E. and Book, R.V.},
TITLE = {Refining nondeterminism in relativizations of complexity classes},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {3},
PAGES = {677-685},
YEAR = {1983},
KEYWORDS = {Oracle machines, bounded oracle queries, nondeterminism, complexity theory},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Nau/83,
AUTHOR = {Nau, D.S.},
TITLE = {Decision quality as a function of search depth on game trees},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {687-708},
YEAR = {1983},
KEYWORDS = {Decison analysis, game playing, pathology},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Hong-Mehlhorn-Rosenberg/83,
AUTHOR = {Hong, J.-W. and Mehlhorn, K. and Rosenberg, A.L.},
TITLE = {Cost trade-offs in graph embedding, with applications},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {709-728},
YEAR = {1983},
KEYWORDS = {Graph embeddings, dilation-cost, expansion-cost, cost trade-offs, generic graphs},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Wigderson/83,
AUTHOR = {Wigderson, A.},
TITLE = {Improving the performance guarantee for approximate graph coloring},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {729-735},
YEAR = {1983},
KEYWORDS = {Approximation algorithms, graph coloring, NP-completeness, performance guarantee},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Ibaraki-Abdel-Wahab-Kameda/83,
AUTHOR = {Ibaraki, T. and Abdel-Wahab, H.M. and Kameda, T.},
TITLE = {Design of minimum-cost deadlock-free systems},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {736-751},
YEAR = {1983},
KEYWORDS = {Deadlock-free systems, efficient algorithms, spanning trees},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Ausiello-dAtri-Sacca/83,
AUTHOR = {Ausiello, G. and d'Atri, A. and Sacc{\'a}, D.},
TITLE = {Graph algorithms for functional dependency manipulation},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {752-766},
YEAR = {1983},
KEYWORDS = {Closure, computational complexity, functional dependency, FD-graph, minimal coverings, relational database},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Goodman-Shmueli/83a,
AUTHOR = {Goodman, N. and Shmueli, O.},
TITLE = {Syntactic characterization of tree database schemas},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {767-786},
YEAR = {1983},
KEYWORDS = {Acyclic scheme, acyclic hypergraph, semijoin, chordal graph, conformal hypergraph},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Kedem-Silberschatz/83,
AUTHOR = {Kedem, Z.M. and Silberschatz, A.},
TITLE = {Locking protocols: From exclusive to shared locks},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {787-804},
YEAR = {1983},
KEYWORDS = {Consistency, locking, serializability},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Larson/83,
AUTHOR = {Larson, P.-{\AA}.},
TITLE = {Analysis of uniform hashing},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {805-819},
YEAR = {1983},
KEYWORDS = {Uniform hashing, random probing, double hashing, open addressing, frequency loading, file organization},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Krevner-Yehudai/83,
AUTHOR = {Krevner, Y. and Yehudai, A.},
TITLE = {An iteration theorem for simple precedence languages},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {820-833},
YEAR = {1983},
KEYWORDS = {Simple precedence grammars, iteration theorem, pumping lemma, parsing},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Hajek/83,
AUTHOR = {Hajek, B.},
TITLE = {The proof of a folk theorem on queuing delay with applications to routing in networks},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {834-851},
YEAR = {1983},
KEYWORDS = {Queues, routing, networks of queues, routing in queuing networks, packet communications},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}
@article{Megiddo/83,
AUTHOR = {Megiddo, N.},
TITLE = {Applying parallel computation algorithms in the design of serial algorithms},
JOURNAL = {J. ACM},
VOLUME = {30},
NUMBER = {4},
PAGES = {852-865},
YEAR = {1983},
KEYWORDS = {Parallel algorithms, parametric computation, spanning tree, scheduling, min-ratio cycle, algorithms on trees, max-flow-related problems},
PUBLISHER = {ACM Press},
ADDRESS = {New York},
}