%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.02", %%% date = "05 April 2013", %%% time = "07:30:11 MDT", %%% filename = "stoc1970.bib", %%% University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "58192 4236 14584 152831", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "ACM Symposium on Theory of Computing (STOC)", %%% license = "public domain", %%% supported = "yes", %%% docstring = "This is a COMPLETE bibliography of %%% publications in the ACM Symposium on Theory %%% of Computing (STOC) conference proceedings %%% for the decade 1970--1979. Companion %%% bibliographies stoc19xx.bib and stoc20xx.bib %%% cover other decades, and stoc.bib contains %%% entries for just the proceedings volumes %%% themselves. %%% %%% At version 1.02, the year coverage looked %%% like this: %%% %%% 1970 ( 28) 1974 ( 36) 1978 ( 39) %%% 1971 ( 24) 1975 ( 32) 1979 ( 38) %%% 1972 ( 30) 1976 ( 31) %%% 1973 ( 31) 1977 ( 33) %%% %%% InProceedings: 312 %%% Proceedings: 10 %%% %%% Total entries: 322 %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb = "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Publisher abbreviations: @String{pub-ACM = "ACM Press"} @String{pub-ACM:adr = "New York, NY, USA"} %%% ==================================================================== %%% Bibliography entries: @InProceedings{Constable:1970:SPS, author = "Robert L. Constable", title = "On the size of programs in subrecursive formalisms", crossref = "ACM:1970:CRS", pages = "1--9", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cudia:1970:DHU, author = "Dennis F. Cudia", title = "The degree hierarchy of undecidable problems of formal grammars", crossref = "ACM:1970:CRS", pages = "10--21", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lewis:1970:UCC, author = "F. D. Lewis", title = "Unsolvability considerations in computational complexity", crossref = "ACM:1970:CRS", pages = "22--30", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Landweber:1970:RPA, author = "L. H. Landweber and E. L. Robertson", title = "Recursive properties of abstract complexity classes (Preliminary Version)", crossref = "ACM:1970:CRS", pages = "31--36", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Bass:1970:HBC, author = "L. J. Bass and Paul R. Young", title = "Hierarchies based on computational complexity and irregularities of class determining measured sets (Preliminary Report)", crossref = "ACM:1970:CRS", pages = "37--40", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ausiello:1970:BNS, author = "Giorgio Ausiello", title = "On bounds on the number of steps to compute functions", crossref = "ACM:1970:CRS", pages = "41--47", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rosenberg:1970:DGA, author = "Arnold L. Rosenberg", title = "Data graphs and addressing schemes (Extended Abstract)", crossref = "ACM:1970:CRS", pages = "48--61", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Burkhard:1970:CPR, author = "W. A. Burkhard", title = "Complexity problems in real time computation", crossref = "ACM:1970:CRS", pages = "62--69", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1970:PSL, author = "Stephen A. Cook", title = "Path systems and language recognition", crossref = "ACM:1970:CRS", pages = "70--72", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Morris:1970:RRB, author = "James B. Morris", title = "A result on the relationship between simple precedence languages and reducing transition languages", crossref = "ACM:1970:CRS", pages = "73--80", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lindstrom:1970:DPI, author = "G. Lindstrom", title = "The design of parsers for incremental language processors", crossref = "ACM:1970:CRS", pages = "81--91", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Book:1970:TTB, author = "Ronald V. Book and Sheila A. Greibach and Ben Wegbreit", title = "Tape- and time-bounded {Turing} acceptors and {AFLs} (Extended Abstract)", crossref = "ACM:1970:CRS", pages = "92--99", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lewis:1970:CFL, author = "David J. Lewis", title = "Closure of families of languages under substitution operators", crossref = "ACM:1970:CRS", pages = "100--108", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rounds:1970:TOP, author = "William C. Rounds", title = "Tree-oriented proofs of some theorems on context-free and indexed languages", crossref = "ACM:1970:CRS", pages = "109--116", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rosen:1970:TMS, author = "Barry K. Rosen", title = "Tree-manipulating systems and {Church--Rosser Theorems}", crossref = "ACM:1970:CRS", pages = "117--127", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Martin:1970:SDT, author = "David F. Martin and Steven A. Vere", title = "On syntax-directed transduction and tree transducers", crossref = "ACM:1970:CRS", pages = "129--135", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Aho:1970:TSL, author = "A. V. Aho and J. D. Ullman", title = "Transformations on straight line programs --- (Preliminary Version)", crossref = "ACM:1970:CRS", pages = "136--148", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{McGowan:1970:CMS, author = "Clement L. McGowan", title = "The correctness of a modified {SECD} machine", crossref = "ACM:1970:CRS", pages = "149--157", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Manna:1970:SOM, author = "Zohar Manna", title = "Second-order mathematical theory of computation", crossref = "ACM:1970:CRS", pages = "158--168", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{King:1970:IOT, author = "James C. King and Robert W. Floyd", title = "An interpretation oriented theorem prover over integers", crossref = "ACM:1970:CRS", pages = "169--179", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Reiter:1970:PES, author = "Raymond Reiter", title = "The predicate elimination strategy in theorem proving", crossref = "ACM:1970:CRS", pages = "180--183", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Strong:1970:TRE, author = "H. R. Strong", title = "Translating recursion equations into flow charts", crossref = "ACM:1970:CRS", pages = "184--197", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ellis:1970:PTA, author = "Clarence A. Ellis", title = "Probabilistic {Tree Automata}", crossref = "ACM:1970:CRS", pages = "198--205", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Chang:1970:ATD, author = "Shi-Kuo Chang", title = "The analysis of two-dimensional patterns using picture processing grammars", crossref = "ACM:1970:CRS", pages = "206--216", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Perrot:1970:RBF, author = "J-F. Perrot", title = "On the relationship between finite automata, finite monoids, and prefix codes", crossref = "ACM:1970:CRS", pages = "217--220", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Nivat:1970:SFL, author = "Maurice Nivat", title = "On some families of languages related to the {Dyck} language", crossref = "ACM:1970:CRS", pages = "221--225", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ullian:1970:TTA, author = "Joseph S. Ullian", title = "Three theorems on abstract families of languages", crossref = "ACM:1970:CRS", pages = "226--230", year = "1970", bibdate = "Wed Feb 20 18:33:27 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Stanat:1971:FLP, author = "D. F. Stanat", title = "Formal languages and power series", crossref = "ACM:1971:CRT", pages = "1--11", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Wagner:1971:ATR, author = "Eric G. Wagner", title = "An algebraic theory of recursive definitions and recursive languages", crossref = "ACM:1971:CRT", pages = "12--23", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Constable:1971:LS, author = "Robert L. Constable", title = "Loop schemata", crossref = "ACM:1971:CRT", pages = "24--39", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Munro:1971:SRC, author = "Ian Munro", title = "Some results concerning efficient and optimal algorithms", crossref = "ACM:1971:CRT", pages = "40--44", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fiduccia:1971:FMM, author = "Charles M. Fiduccia", title = "Fast matrix multiplication", crossref = "ACM:1971:CRT", pages = "45--49", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Meyers:1971:LRT, author = "W. J. Meyers", title = "Linear representation of tree structure --- a mathematical theory of parenthesis-free notations", crossref = "ACM:1971:CRT", pages = "50--62", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Buttelmann:1971:GFA, author = "H. W. Buttelmann", title = "On generalized finite automata and unrestricted generative grammars", crossref = "ACM:1971:CRT", pages = "63--77", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Levy:1971:SRT, author = "L. S. Levy and A. K. Joshi", title = "Some results in tree automata", crossref = "ACM:1971:CRT", pages = "78--85", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Berry:1971:BSE, author = "Daniel M. Berry", title = "Block structure (Extended Abstract): {Retention} or deletion?", crossref = "ACM:1971:CRT", pages = "86--100", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Chang:1971:PCL, author = "Shi-Kuo Chang", title = "On the parallel computation of local operations", crossref = "ACM:1971:CRT", pages = "101--115", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Boasson:1971:ITO, author = "L. Boasson", title = "An iteration theorem for one-counter languages", crossref = "ACM:1971:CRT", pages = "116--120", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ginsburg:1971:ICF, author = "Seymour Ginsburg and Jonathan Goldstine", title = "Intersection-closed full {AFL} and the recursively enumerable languages", crossref = "ACM:1971:CRT", pages = "121--131", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rajlich:1971:APG, author = "Vaclav Rajlich", title = "Absolutely parallel grammars and two-way deterministic finite-state transducers", crossref = "ACM:1971:CRT", pages = "132--137", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rosenberg:1971:ADG, author = "Arnold L. Rosenberg", title = "Addressable data graphs (Extended Abstract)", crossref = "ACM:1971:CRT", pages = "138--150", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1971:CTP, author = "Stephen A. Cook", title = "The complexity of theorem-proving procedures", crossref = "ACM:1971:CRT", pages = "151--158", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Aho:1971:CFL, author = "Alfred V. Aho and Jeffrey D. Ullman", title = "The care and feeding of {LR(k)} grammars", crossref = "ACM:1971:CRT", pages = "159--170", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Wise:1971:DAA, author = "David S. Wise", title = "{Domolki}'s algorithm applied to generalized overlap resolvable grammars", crossref = "ACM:1971:CRT", pages = "171--184", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Terrine:1971:AGD, author = "G{\'e}rard Terrine", title = "An algorithm generating the decision table of a deterministic bottom up parser for a subset of context free grammars", crossref = "ACM:1971:CRT", pages = "185--205", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{McNaughton:1971:DPG, author = "Robert McNaughton", title = "A decision procedure for generalized sequential mapability-onto of regular sets", crossref = "ACM:1971:CRT", pages = "206--218", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Santos:1971:AST, author = "Eugene S. Santos", title = "Algebraic structure theory of stochastic machines", crossref = "ACM:1971:CRT", pages = "219--243", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Constable:1971:CFT, author = "R. L. Constable and J. Hartmanis", title = "Complexity of formal translations and speed-up results", crossref = "ACM:1971:CRT", pages = "244--250", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Machtey:1971:CCF, author = "Michael Machtey", title = "Classification of computable functions by primitive recursive classes", crossref = "ACM:1971:CRT", pages = "251--257", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Robertson:1971:CCP, author = "Edward L. Robertson", title = "Complexity classes of partial recursive functions (Preliminary Version)", crossref = "ACM:1971:CRT", pages = "258--266", year = "1971", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Constable:1972:SPS, author = "Robert L. Constable and Steven S. Muchnick", title = "Subrecursive program schemata {I} \& {II} ({I}. {Undecidable} equivalence problems, {II}. {Decidable} equivalence problems)", crossref = "ACM:1972:CRF", pages = "1--17", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Walker:1972:CFR, author = "S. A. Walker and H. R. Strong", title = "Characterizations of flowchartable recursions short version", crossref = "ACM:1972:CRF", pages = "18--34", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Morris:1972:RSL, author = "James H. Morris", title = "Recursion schemes with lists", crossref = "ACM:1972:CRF", pages = "35--43", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Plaisted:1972:FSC, author = "David A. Plaisted", title = "Flowchart schemata with counters", crossref = "ACM:1972:CRF", pages = "44--51", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Chandra:1972:PSE, author = "Ashok K. Chandra and Zohar Manna", title = "Program schemas with equality", crossref = "ACM:1972:CRF", pages = "52--64", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Garland:1972:ES, author = "Stephen J. Garland and David C. Luckham", title = "On the equivalence of schemes", crossref = "ACM:1972:CRF", pages = "65--72", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1972:TBR, author = "Stephen A. Cook and Robert A. Reckhow", title = "Time-bounded random access machines", crossref = "ACM:1972:CRF", pages = "73--80", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Warkentin:1972:PMR, author = "John C. Warkentin and Patrick C. Fischer", title = "Predecessor machines and regressing functions", crossref = "ACM:1972:CRF", pages = "81--87", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fiduccia:1972:PED, author = "Charles M. Fiduccia", title = "Polynomial evaluation via the division algorithm the fast {Fourier} transform revisited", crossref = "ACM:1972:CRF", pages = "88--93", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kirkpatrick:1972:ANC, author = "David Kirkpatrick", title = "On the additions necessary to compute certain functions", crossref = "ACM:1972:CRF", pages = "94--101", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kung:1972:BME, author = "H. T. Kung", title = "A bound on the multiplication efficiency of iteration", crossref = "ACM:1972:CRF", pages = "102--107", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Horowitz:1972:ARF, author = "Ellis Horowitz", title = "Algorithms for rational function arithmetic operations", crossref = "ACM:1972:CRF", pages = "108--118", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Blum:1972:LTB, author = "Manuel Blum and Robert W. Floyd and Vaughan Pratt and Ronald L. Rivest and Robert E. Tarjan", title = "Linear time bounds for median computations", crossref = "ACM:1972:CRF", pages = "119--124", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Karp:1972:RIR, author = "Richard M. Karp and Raymond E. Miller and Arnold L. Rosenberg", title = "Rapid identification of repeated patterns in strings, trees and arrays", crossref = "ACM:1972:CRF", pages = "125--136", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Nievergelt:1972:BST, author = "J. Nievergelt and E. M. Reingold", title = "Binary search trees of bounded balance", crossref = "ACM:1972:CRF", pages = "137--142", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Garey:1972:WCA, author = "M. R. Garey and R. L. Graham and J. D. Ullman", title = "Worst-case analysis of memory allocation algorithms", crossref = "ACM:1972:CRF", pages = "143--150", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Savitch:1972:MRA, author = "Walter J. Savitch", title = "Maze recognizing automata (Extended Abstract)", crossref = "ACM:1972:CRF", pages = "151--156", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Jones:1972:TMS, author = "Neil D. Jones and Alan L. Selman", title = "{Turing} machines and the spectra of first-order formulas with equality", crossref = "ACM:1972:CRF", pages = "157--167", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Schnorr:1972:PCE, author = "C. P. Schnorr", title = "The process complexity and effective random tests", crossref = "ACM:1972:CRF", pages = "168--176", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Symes:1972:CFF, author = "D. M. Symes", title = "The computation of finite functions", crossref = "ACM:1972:CRF", pages = "177--182", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Meyer:1972:PSE, author = "A. R. Meyer and A. Bagchi", title = "Program size and economy of descriptions: {Preliminary Report}", crossref = "ACM:1972:CRF", pages = "183--186", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1972:HNT, author = "Stephen A. Cook", title = "A hierarchy for nondeterministic time complexity", crossref = "ACM:1972:CRF", pages = "187--192", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hamlet:1972:PPA, author = "R. G. Hamlet", title = "A patent problem for abstract programming languages; machine-independent computations", crossref = "ACM:1972:CRF", pages = "193--197", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ogden:1972:CTT, author = "W. F. Ogden and W. C. Rounds", title = "Compositions of n tree transducers", crossref = "ACM:1972:CRF", pages = "198--206", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Carlyle-Greibach:1972:UEA, author = "Sheila Carlyle-Greibach and Seymour Ginsburg and Jonathan Goldstine", title = "Uniformly erasable {AFL}", crossref = "ACM:1972:CRF", pages = "207--213", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lindenmayer:1972:DSL, author = "A. Lindenmayer and G. Rozenberg", title = "Developmental systems and languages", crossref = "ACM:1972:CRF", pages = "214--221", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sethi:1972:VRA, author = "Ravi Sethi", title = "Validating register allocations for straight line programs", crossref = "ACM:1972:CRF", pages = "222--237", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hecht:1972:FGR, author = "Matthew S. Hecht and Jeffrey D. Ullman", title = "Flow graph reducibility", crossref = "ACM:1972:CRF", pages = "238--250", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Aho:1972:TSL, author = "Alfred V. Aho and Jeffrey D. Ullman", title = "A technique for speeding up {LR(k)} parsers", crossref = "ACM:1972:CRF", pages = "251--263", year = "1972", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Stockmeyer:1973:WPR, author = "L. J. Stockmeyer and A. R. Meyer", title = "Word problems requiring exponential time (Preliminary Report)", crossref = "ACM:1973:CRF", pages = "1--9", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hunt:1973:TTC, author = "H. B. Hunt", title = "On the time and tape complexity of languages {I}", crossref = "ACM:1973:CRF", pages = "10--19", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Greibach:1973:JPD, author = "Sheila A. Greibach", title = "Jump {PDA}'s, deterministic context-free languages principal {AFDLs} and polynomial time recognition --- (Extended Abstract)", crossref = "ACM:1973:CRF", pages = "20--28", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1973:OTS, author = "Stephen A. Cook", title = "An observation on time-storage trade off", crossref = "ACM:1973:CRF", pages = "29--33", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Oppen:1973:EBP, author = "Derek C. Oppen", title = "Elementary bounds for {Presburger} arithmetic", crossref = "ACM:1973:CRF", pages = "34--37", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Johnson:1973:AAC, author = "David S. Johnson", title = "Approximation algorithms for combinatorial problems", crossref = "ACM:1973:CRF", pages = "38--49", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Miller:1973:TMV, author = "Webb Miller", title = "Toward mechanical verification of properties of roundoff error propagation", crossref = "ACM:1973:CRF", pages = "50--58", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Wand:1973:UAP, author = "Mitchell Wand", title = "An unusual application of program-proving", crossref = "ACM:1973:CRF", pages = "59--66", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fischer:1973:FLI, author = "Michael J. Fischer and Larry J. Stockmeyer", title = "Fast on-line integer multiplication", crossref = "ACM:1973:CRF", pages = "67--72", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hopcroft:1973:DAC, author = "J. Hopcroft and J. Musinski", title = "Duality applied to the complexity of matrix multiplications and other bilinear forms", crossref = "ACM:1973:CRF", pages = "73--87", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Brockett:1973:OES, author = "Roger W. Brockett and David Dobkin", title = "On the optimal evaluation of a set of bilinear forms", crossref = "ACM:1973:CRF", pages = "88--95", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Tarjan:1973:TFG, author = "Robert Tarjan", title = "Testing flow graph reducibility", crossref = "ACM:1973:CRF", pages = "96--107", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Constable:1973:TTC, author = "Robert L. Constable", title = "Type two computational complexity", crossref = "ACM:1973:CRF", pages = "108--121", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ladner:1973:PTR, author = "Richard E. Ladner", title = "Polynominal time reducibility", crossref = "ACM:1973:CRF", pages = "122--129", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lynch:1973:SDH, author = "Nancy Lynch and Albert Meyer and Michael Fischer", title = "Sets that don't help", crossref = "ACM:1973:CRF", pages = "130--134", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Gentleman:1973:AAC, author = "W. M. Gentleman and S. C. Johnson", title = "Analysis of algorithms, a case study: {Determinants} of polynomials", crossref = "ACM:1973:CRF", pages = "135--141", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Moenck:1973:FCG, author = "R. T. Moenck", title = "Fast computation of {GCDs}", crossref = "ACM:1973:CRF", pages = "142--151", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kung:1973:CCA, author = "H. T. Kung", title = "The computational complexity of algebraic numbers", crossref = "ACM:1973:CRF", pages = "152--159", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lewis:1973:ATE, author = "P. M. Lewis and D. J. Rosenkrantz and R. E. Stearns", title = "Attributed translations (Extended Abstract)", crossref = "ACM:1973:CRF", pages = "160--171", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Pager:1973:LTA, author = "David Pager", title = "The lane tracing algorithm for constructing {LR(k)} parsers", crossref = "ACM:1973:CRF", pages = "172--181", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sethi:1973:CRA, author = "Ravi Sethi", title = "Complete register allocation problems", crossref = "ACM:1973:CRF", pages = "182--195", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Teitelbaum:1973:CFE, author = "Ray Teitelbaum", title = "Context-free error analysis by evaluation of algebraic power series", crossref = "ACM:1973:CRF", pages = "196--199", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Baker:1973:TTF, author = "Brenda S. Baker", title = "Tree transductions and families of tree languages", crossref = "ACM:1973:CRF", pages = "200--206", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Weiner:1973:NSA, author = "P. Weiner and S. L. Savage and A. Bagchi", title = "Neighborhood search algorithms for finding optimal traveling salesman tours must be inefficient", crossref = "ACM:1973:CRF", pages = "207--213", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Wagner:1973:APL, author = "Eric G. Wagner", title = "From algebras to programming languages", crossref = "ACM:1973:CRF", pages = "214--223", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Vuillemin:1973:COI, author = "Jean Vuillemin", title = "Correct and optimal implementations of recursion in a simple programming language", crossref = "ACM:1973:CRF", pages = "224--239", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kosaraju:1973:ASP, author = "S. Rao Kosaraju", title = "Analysis of structured programs", crossref = "ACM:1973:CRF", pages = "240--252", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Aho:1973:FLC, author = "A. V. Aho and J. E. Hopcroft and J. D. Ullman", title = "On finding lowest common ancestors in trees", crossref = "ACM:1973:CRF", pages = "253--265", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Eilenberg:1973:CSC, author = "Samuel Eilenberg", title = "Classes of semigroups and classes of sets", crossref = "ACM:1973:CRF", pages = "266--267", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Pratt:1973:CPD, author = "Vaughan R. Pratt", title = "Computing permutations with double-ended queues, parallel stacks and parallel queues", crossref = "ACM:1973:CRF", pages = "268--277", year = "1973", bibdate = "Wed Feb 20 18:33:28 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Chandra:1974:DTC, author = "Ashok K. Chandra", title = "Degrees of translatability and canonical forms in program schemas: {Part I}", crossref = "ACM:1974:CRS", pages = "1--12", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Courcelle:1974:SAS, author = "B. Courcelle and J. Vuillemin", title = "Semantics and axiomatics of a simple recursive language", crossref = "ACM:1974:CRS", pages = "13--26", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Valiant:1974:DED, author = "Leslie G. Valiant", title = "The decidability of equivalence for deterministic finite-turn pushdown automata", crossref = "ACM:1974:CRS", pages = "27--32", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1974:SRD, author = "Stephen Cook and Ravi Sethi", title = "Storage requirements for deterministic\slash polynomial time recognizable languages", crossref = "ACM:1974:CRS", pages = "33--39", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Jones:1974:CPD, author = "Neil D. Jones and William T. Laaser", title = "Complete problems for deterministic polynomial time", crossref = "ACM:1974:CRS", pages = "40--46", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Garey:1974:SSN, author = "M. R. Garey and D. S. Johnson and L. Stockmeyer", title = "Some simplified {NP}-complete problems", crossref = "ACM:1974:CRS", pages = "47--63", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hunt:1974:CPB, author = "H. B. Hunt and D. J. Rosenkrantz", title = "Computational parallels between the regular and context-free languages", crossref = "ACM:1974:CRS", pages = "64--74", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ehrenfeucht:1974:CMR, author = "Andrzej Ehrenfeucht and Paul Zeiger", title = "Complexity measures for regular expressions", crossref = "ACM:1974:CRS", pages = "75--79", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Pratt:1974:PNT, author = "Vaughan R. Pratt", title = "The power of negative thinking in multiplying {Boolean} matrices", crossref = "ACM:1974:CRS", pages = "80--83", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kirkpatrick:1974:DGP, author = "David Kirkpatrick", title = "Determining graph properties from matrix representations", crossref = "ACM:1974:CRS", pages = "84--90", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Gill:1974:CCP, author = "John T. Gill", title = "Computational complexity of probabilistic {Turing} machines", crossref = "ACM:1974:CRS", pages = "91--95", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Mehlhorn:1974:PAS, author = "Kurt Mehlhorn", title = "Polynomial and abstract subrecursive classes", crossref = "ACM:1974:CRS", pages = "96--109", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ladner:1974:CPT, author = "Richard Ladner and Nancy Lynch and Alan Selman", title = "Comparison of polynomial-time reducibilities", crossref = "ACM:1974:CRS", pages = "110--121", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Pratt:1974:CPV, author = "Vaughan R. Pratt and Michael O. Rabin and Larry J. Stockmeyer", title = "A characterization of the power of vector machines", crossref = "ACM:1974:CRS", pages = "122--134", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1974:LPP, author = "Stephen Cook and Robert Reckhow", title = "On the lengths of proofs in the propositional calculus (Preliminary Version)", crossref = "ACM:1974:CRS", pages = "135--148", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rackoff:1974:CTW, author = "Charles Rackoff", title = "On the complexity of the theories of weak direct products (Preliminary Report)", crossref = "ACM:1974:CRS", pages = "149--160", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Robertson:1974:SCW, author = "Edward L. Robertson", title = "Structure of complexity in the weak monadic second-order theories of the natural numbers", crossref = "ACM:1974:CRS", pages = "161--171", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hopcroft:1974:LTA, author = "J. E. Hopcroft and J. K. Wong", title = "Linear time algorithm for isomorphism of planar graphs (Preliminary Report)", crossref = "ACM:1974:CRS", pages = "172--184", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Tarjan:1974:TGC, author = "R. Endre Tarjan", title = "Testing graph connectivity", crossref = "ACM:1974:CRS", pages = "185--193", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Horvath:1974:ESS, author = "Edward C. Horvath", title = "Efficient stable sorting with minimal extra space", crossref = "ACM:1974:CRS", pages = "194--215", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hyafil:1974:EAC, author = "L. Hyafil and F. Prusker and J. Vuillemin", title = "An efficient algorithm for computing optimal disk merge patterns. (Extended Abstract)", crossref = "ACM:1974:CRS", pages = "216--229", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lipton:1974:LSP, author = "R. J. Lipton", title = "Limitations of synchronization primitives with conditional branching and global variables", crossref = "ACM:1974:CRS", pages = "230--241", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Millen:1974:CPD, author = "Jonathan K. Millen", title = "Construction with parallel derivatives of the closure of a parallel program schema", crossref = "ACM:1974:CRS", pages = "242--247", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Vairavan:1974:PSP, author = "K. Vairavan and R. A. DeMillo", title = "Parallel scheduling of programs in a restricted model of computation", crossref = "ACM:1974:CRS", pages = "248--255", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Greibach:1974:SRW, author = "Sheila A. Greibach", title = "Some restrictions on {W}-grammars", crossref = "ACM:1974:CRS", pages = "256--265", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hammer:1974:NGT, author = "Michael Hammer", title = "A new grammatical transformation into {LL(k)} form (Extended Abstract)", crossref = "ACM:1974:CRS", pages = "266--275", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Seiferas:1974:ONM, author = "Joel I. Seiferas", title = "Observations on nondeterministic multidimensional iterative arrays", crossref = "ACM:1974:CRS", pages = "276--289", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Book:1974:ILC, author = "Ronald Book and Maurice Nivat and Michael Paterson", title = "Intersections of linear context-free languages and reversal-bounded multipushdown machines (Extended Abstract)", crossref = "ACM:1974:CRS", pages = "290--296", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rosenberg:1974:MSE, author = "Arnold L. Rosenberg", title = "Managing storage for extendible arrays (Extended Abstract)", crossref = "ACM:1974:CRS", pages = "297--302", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{vanLeeuwen:1974:PSR, author = "Jan van Leeuwen", title = "A partial solution to the reachability-problem for vector-addition systems", crossref = "ACM:1974:CRS", pages = "303--309", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Dobkin:1974:SGB, author = "David Dobkin and R. J. Lipton", title = "On some generalizations of binary search", crossref = "ACM:1974:CRS", pages = "310--316", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Miller:1974:CCN, author = "Webb Miller", title = "Computational complexity and numerical stability", crossref = "ACM:1974:CRS", pages = "317--322", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kung:1974:NAL, author = "H. T. Kung", title = "New algorithms and lower bounds for the parallel evaluation of certain rational expressions", crossref = "ACM:1974:CRS", pages = "323--333", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kedem:1974:CDR, author = "Zvi M. Kedem", title = "Combining dimensionality and rate of growth arguments for establishing lower bounds on the number of multiplications", crossref = "ACM:1974:CRS", pages = "334--341", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Borodin:1974:NAC, author = "Allan Borodin and Stephen Cook", title = "On the number of additions to compute specific polynomials (Preliminary Version)", crossref = "ACM:1974:CRS", pages = "342--347", year = "1974", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lipton:1975:CMH, author = "Richard J. Lipton and David Dobkin", title = "Complexity measures and hierarchies for the evaluation of integers, polynomials, and $n$-linear forms", crossref = "ACM:1975:CRS", pages = "1--5", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rivest:1975:GPA, author = "Ronald L. Rivest and Jean Vuillemin", title = "A generalization and proof of the {Aanderaa-Rosenberg} conjecture", crossref = "ACM:1975:CRS", pages = "6--11", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hyafil:1975:CPE, author = "L. Hyafil and H. T. Kung", title = "The complexity of parallel evaluation of linear recurrence", crossref = "ACM:1975:CRS", pages = "12--22", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Yao:1975:CMQ, author = "Andrew Chi-Chih Yao", title = "On computing the minima of quadratic forms (Preliminary Report)", crossref = "ACM:1975:CRS", pages = "23--26", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Paul:1975:LBC, author = "Wolfgang J. Paul", title = "A $2.5n$-lower bound on the combinational complexity of {Boolean} functions", crossref = "ACM:1975:CRS", pages = "27--36", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fischer:1975:LBS, author = "Michael J. Fischer and Albert R. Meyer and Michael S. Paterson", title = "Lower bounds on the size of {Boolean} formulas: {Preliminary Report}", crossref = "ACM:1975:CRS", pages = "37--44", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Valiant:1975:NLL, author = "Leslie G. Valiant", title = "On non-linear lower bounds in computational complexity", crossref = "ACM:1975:CRS", pages = "45--53", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hunt:1975:CGR, author = "H. B. Hunt and T. G. Szymanski", title = "On the complexity of grammar and related problems", crossref = "ACM:1975:CRS", pages = "54--65", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Even:1975:CPW, author = "Shimon Even and R. Endre Tarjan", title = "A combinatorial problem which is complete in polynomial space", crossref = "ACM:1975:CRS", pages = "66--71", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Galil:1975:VCB, author = "Zvi Galil", title = "On the validity and complexity of bounded resolution", crossref = "ACM:1975:CRS", pages = "72--82", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1975:FCP, author = "Stephen A. Cook", title = "Feasibly constructive proofs and the propositional calculus (Preliminary Version)", crossref = "ACM:1975:CRS", pages = "83--97", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Egli:1975:CCP, author = "Herbert Egli and Robert L. Constable", title = "Computability concepts for programming language semantics", crossref = "ACM:1975:CRS", pages = "98--106", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Oppen:1975:PAA, author = "Derek C. Oppen and Stephen A. Cook", title = "Proving assertions about programs that manipulate data structures", crossref = "ACM:1975:CRS", pages = "107--116", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ehrenfeucht:1975:PFL, author = "A. Ehrenfeucht and G. Rozenberg", title = "On (un)predictability of formal languages (Extended Abstract)", crossref = "ACM:1975:CRS", pages = "117--120", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Skyum:1975:DLD, author = "Sven Skyum", title = "On decomposing languages defined by parallel devices", crossref = "ACM:1975:CRS", pages = "121--125", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Perrault:1975:ITT, author = "C. Raymond Perrault", title = "Intercalation theorems for tree transducer languages", crossref = "ACM:1975:CRS", pages = "126--136", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ehrenfeucht:1975:CSL, author = "A. Ehrenfeucht and G. Rozenberg", title = "On the (combinatorial) structure of {L} languages without interactions (Extended Abstract)", crossref = "ACM:1975:CRS", pages = "137--144", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Wotschke:1975:DLP, author = "Detlef Wotschke", title = "Degree-languages, polynomial time recognition, and the {LBA} problem", crossref = "ACM:1975:CRS", pages = "145--152", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ginsburg:1975:CCG, author = "Seymour Ginsburg and Nancy Lynch", title = "Comparative complexity of grammar forms", crossref = "ACM:1975:CRS", pages = "153--158", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rosenberg:1975:HSE, author = "Arnold L. Rosenberg and Larry J. Stockmeyer", title = "Hashing schemes for extendible arrays (Extended Abstract)", crossref = "ACM:1975:CRS", pages = "159--166", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Pratt:1975:FMA, author = "Terrence Pratt", title = "Four models for the analysis and optimization of program control structures", crossref = "ACM:1975:CRS", pages = "167--176", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Aho:1975:NLR, author = "A. V. Aho and J. D. Ullman", title = "Node listings for reducible flow graphs", crossref = "ACM:1975:CRS", pages = "177--185", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lipton:1975:CCS, author = "R. J. Lipton and S. C. Eisenstat and R. A. DeMillo", title = "The complexity of control structures and data structures", crossref = "ACM:1975:CRS", pages = "186--193", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Manna:1975:OFR, author = "Zohar Manna and Adi Shamir", title = "The optimal fixedpoint of recursive programs", crossref = "ACM:1975:CRS", pages = "194--206", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Aho:1975:OCG, author = "A. V. Aho and S. C. Johnson", title = "Optimal code generation for expression trees", crossref = "ACM:1975:CRS", pages = "207--217", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Wagner:1975:CES, author = "Robert A. Wagner", title = "On the complexity of the {Extended String-to-String Correction Problem}", crossref = "ACM:1975:CRS", pages = "218--223", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Shamos:1975:GC, author = "Michael Ian Shamos", title = "Geometric complexity", crossref = "ACM:1975:CRS", pages = "224--233", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Miller:1975:RHT, author = "Gary L. Miller", title = "{Riemann's Hypothesis} and tests for primality", crossref = "ACM:1975:CRS", pages = "234--239", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fredman:1975:TAP, author = "Michael L. Fredman", title = "Two applications of a probabilistic search technique: {Sorting X+Y} and building balanced search trees", crossref = "ACM:1975:CRS", pages = "240--244", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rose:1975:AAV, author = "Donald J. Rose and R. Endre Tarjan", title = "Algorithmic aspects of vertex elimination", crossref = "ACM:1975:CRS", pages = "245--254", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Booth:1975:LAR, author = "Kellogg S. Booth and George S. Lueker", title = "Linear algorithms to recognize interval graphs and test for the consecutive ones property", crossref = "ACM:1975:CRS", pages = "255--265", year = "1975", bibdate = "Wed Feb 20 18:33:29 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Papadimitriou:1976:SCR, author = "Christos H. Papadimitriou and Kenneth Steiglitz", title = "Some complexity results for the {Traveling Salesman Problem}", crossref = "ACM:1976:CRE", pages = "1--9", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Garey:1976:SNC, author = "M. R. Garey and R. L. Graham and D. S. Johnson", title = "Some {NP}-complete geometric problems", crossref = "ACM:1976:CRE", pages = "10--22", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Manders:1976:NCD, author = "Kenneth Manders and Leonard Adleman", title = "{NP}-complete decision problems for quadratic polynomials", crossref = "ACM:1976:CRE", pages = "23--29", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hartmanis:1976:IDN, author = "J. Hartmanis and L. Berman", title = "On isomorphisms and density of {NP} and other complete sets", crossref = "ACM:1976:CRE", pages = "30--40", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Schaefer:1976:CDP, author = "Thomas J. Schaefer", title = "Complexity of decision problems based on finite two-person perfect-information games", crossref = "ACM:1976:CRE", pages = "41--49", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cardoza:1976:ESC, author = "E. Cardoza and R. Lipton and A. R. Meyer", title = "Exponential space complete problems for {Petri} nets and commutative semigroups (Preliminary Report)", crossref = "ACM:1976:CRE", pages = "50--54", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hirschberg:1976:PAT, author = "D. S. Hirschberg", title = "Parallel algorithms for the transitive closure and the connected component problems", crossref = "ACM:1976:CRE", pages = "55--57", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Thompson:1976:SMC, author = "C. D. Thompson and H. T. Kung", title = "Sorting on a mesh-connected parallel computer", crossref = "ACM:1976:CRE", pages = "58--64", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Doeppner:1976:APP, author = "Thomas W. Doeppner", title = "On abstractions of parallel programs", crossref = "ACM:1976:CRE", pages = "65--72", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Owicki:1976:CCD, author = "Susan Owicki", title = "A consistent and complete deductive system for the verification of parallel programs", crossref = "ACM:1976:CRE", pages = "73--86", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Wand:1976:NIR, author = "Mitchell Wand", title = "A new incompleteness result for {Hoare}'s system", crossref = "ACM:1976:CRE", pages = "87--91", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kimura:1976:ASP, author = "Takayuki Kimura", title = "An algebraic system for process structuring and interprocess communication", crossref = "ACM:1976:CRE", pages = "92--100", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kosaraju:1976:SFP, author = "S. Rao Kosaraju", title = "On structuring flowcharts (Preliminary Version)", crossref = "ACM:1976:CRE", pages = "101--111", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Graham:1976:LCF, author = "Susan L. Graham and Michael A. Harrison and Walter L. Ruzzo", title = "On line context free language recognition in less than cubic time (Extended Abstract)", crossref = "ACM:1976:CRE", pages = "112--120", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fong:1976:FDF, author = "Amelia C. Fong and Jeffrey D. Ullman", title = "Finding the depth of a flow graph", crossref = "ACM:1976:CRE", pages = "121--125", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hunt:1976:DRF, author = "H. B. Hunt and T. G. Szymanski", title = "Dichotomization, reachability, and the forbidden subgraph problem (Extended Abstract)", crossref = "ACM:1976:CRE", pages = "126--134", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ibarra:1976:UDS, author = "Oscar H. Ibarra and Chul E. Kim", title = "A useful device for showing the solvability of some decision problems", crossref = "ACM:1976:CRE", pages = "135--140", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sudborough:1976:DCF, author = "I. H. Sudborough", title = "On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store", crossref = "ACM:1976:CRE", pages = "141--148", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Paul:1976:SBG, author = "Wolfgang J. Paul and Robert Endre Tarjan and James R. Celoni", title = "Space bounds for a game on graphs", crossref = "ACM:1976:CRE", pages = "149--160", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Galil:1976:RTA, author = "Zvi Galil", title = "Real-time algorithms for string-matching and palindrome recognition", crossref = "ACM:1976:CRE", pages = "161--173", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lipton:1976:EPS, author = "Richard J. Lipton and Larry J. Stockmeyer", title = "Evaluation of polynomials with super-preconditioning", crossref = "ACM:1976:CRE", pages = "174--180", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Paterson:1976:LU, author = "M. S. Paterson and M. N. Wegman", title = "Linear unification", crossref = "ACM:1976:CRE", pages = "181--186", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Guibas:1976:ADH, author = "Leo J. Guibas and Endre Szemeredi", title = "The analysis of double hashing (Extended Abstract)", crossref = "ACM:1976:CRE", pages = "187--191", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Yao:1976:ABS, author = "Andrew Chi-chih Yao", title = "On the average behavior of set merging algorithms (Extended Abstract)", crossref = "ACM:1976:CRE", pages = "192--195", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Valiant:1976:UCP, author = "Leslie G. Valiant", title = "Universal circuits (Preliminary Report)", crossref = "ACM:1976:CRE", pages = "196--203", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Pippenger:1976:RMB, author = "Nicholas Pippenger", title = "The realization of monotone {Boolean} functions (Preliminary Version)", crossref = "ACM:1976:CRE", pages = "204--210", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Burkhard:1976:ART, author = "Walter A. Burkhard", title = "Associative retrieval trie hash-coding (Extended Abstract)", crossref = "ACM:1976:CRE", pages = "211--219", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Bentley:1976:DCM, author = "Jon Louis Bentley and Michael Ian Shamos", title = "Divide-and-conquer in multidimensional space", crossref = "ACM:1976:CRE", pages = "220--230", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lee:1976:LPP, author = "D. T. Lee and F. P. Preparata", title = "Location of a point in a planar subdivision and its applications", crossref = "ACM:1976:CRE", pages = "231--235", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Machtey:1976:SGN, author = "Michael Machtey and Paul Young", title = "Simple {G{\"o}del} numberings, translations, and the $p$-hierarchy (Preliminary Report)", crossref = "ACM:1976:CRE", pages = "236--243", year = "1976", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Itai:1977:FMC, author = "Alon Itai and Michael Rodeh", title = "Finding a minimum circuit in a graph", crossref = "ACM:1977:CRN", pages = "1--10", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Yao:1977:LBS, author = "Andrew C. Yao and David M. Avis and Ronald L. Rivest", title = "An ${\Omega}(n^2 \log n)$ lower bound to the shortest paths problem", crossref = "ACM:1977:CRN", pages = "11--17", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Tarjan:1977:RMR, author = "Robert Endre Tarjan", title = "Reference machines require non-linear time to maintain disjoint sets", crossref = "ACM:1977:CRN", pages = "18--29", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Angluin:1977:FPA, author = "Dana Angluin and Leslie G. Valiant", title = "Fast probabilistic algorithms for {Hamiltonian} circuits and matchings", crossref = "ACM:1977:CRN", pages = "30--41", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Brown:1977:CPQ, author = "Mark R. Brown", title = "The complexity of priority queue maintenance", crossref = "ACM:1977:CRN", pages = "42--48", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Guibas:1977:NRL, author = "Leo J. Guibas and Edward M. McCreight and Michael F. Plass and Janet R. Roberts", title = "A new representation for linear lists", crossref = "ACM:1977:CRN", pages = "49--60", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sacerdote:1977:DRP, author = "George S. Sacerdote and Richard L. Tenney", title = "The decidability of the reachability problem for vector addition systems (Preliminary Version)", crossref = "ACM:1977:CRN", pages = "61--76", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Chandra:1977:OIC, author = "Ashok K. Chandra and Philip M. Merlin", title = "Optimal implementation of conjunctive queries in relational data bases", crossref = "ACM:1977:CRN", pages = "77--90", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Peterson:1977:ESC, author = "Gary L. Peterson and Michael J. Fischer", title = "Economical solutions for the critical section problem in a distributed system (Extended Abstract)", crossref = "ACM:1977:CRN", pages = "91--97", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rosenthal:1977:NDP, author = "Arnie Rosenthal", title = "Nonserial dynamic programming is optimal", crossref = "ACM:1977:CRN", pages = "98--105", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Carter:1977:UCH, author = "J. Lawrence Carter and Mark N. Wegman", title = "Universal classes of hash functions (Extended Abstract)", crossref = "ACM:1977:CRN", pages = "106--112", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Gonnet:1977:AIH, author = "Gaston Gonnet and Ian Munro", title = "The analysis of an improved hashing technique", crossref = "ACM:1977:CRN", pages = "113--121", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Beatty:1977:ITL, author = "John C. Beatty", title = "Iteration theorems for {LL(k)} languages (Extended Abstract)", crossref = "ACM:1977:CRN", pages = "122--131", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Prabhala:1977:CIS, author = "Bhaskaram Prabhala and Ravi Sethi", title = "A comparison of instruction sets for stack machines", crossref = "ACM:1977:CRN", pages = "132--142", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Miller:1977:GIG, author = "Gary L. Miller", title = "Graph isomorphism, general remarks", crossref = "ACM:1977:CRN", pages = "143--150", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Adleman:1977:RRI, author = "Leonard Adleman and Kenneth Manders", title = "Reducibility, randomness, and intractibility (Abstract)", crossref = "ACM:1977:CRN", pages = "151--163", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kozen:1977:CFP, author = "Dexter Kozen", title = "Complexity of finitely presented algebras", crossref = "ACM:1977:CRN", pages = "164--177", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kintala:1977:CRN, author = "Chandra M. R. Kintala and Patrick C. Fischer", title = "Computations with a restricted number of nondeterministic steps (Extended Abstract)", crossref = "ACM:1977:CRN", pages = "178--185", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Simon:1977:PRU, author = "Istvan Simon and John Gill", title = "Polynomial reducibilities and upward diagonalizations", crossref = "ACM:1977:CRN", pages = "186--194", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Simon:1977:FNP, author = "Janos Simon", title = "On feasible numbers (Preliminary Version)", crossref = "ACM:1977:CRN", pages = "195--207", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sudborough:1977:STB, author = "I. H. Sudborough", title = "Separating tape bounded auxiliary pushdown automata classes", crossref = "ACM:1977:CRN", pages = "208--217", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Paul:1977:TH, author = "W. J. Paul", title = "On time hierarchies", crossref = "ACM:1977:CRN", pages = "218--222", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hartmanis:1977:RBD, author = "J. Hartmanis", title = "Relations between diagonalization, proof systems, and complexity gaps", crossref = "ACM:1977:CRN", pages = "223--227", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lynch:1977:ERB, author = "Nancy A. Lynch and Edward K. Blum", title = "Efficient reducibility between programming systems (Preliminary Report)", crossref = "ACM:1977:CRN", pages = "228--238", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Leong:1977:NRT, author = "Benton Leong and Joel Seiferas", title = "New real-time simulations of multihead tape units", crossref = "ACM:1977:CRN", pages = "239--248", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Harel:1977:CAS, author = "David Harel and Amir Puneli and Jonathan Stavi", title = "A complete axiomatic system for proving deductions about recursive programs", crossref = "ACM:1977:CRN", pages = "249--260", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Harel:1977:CCL, author = "D. Harel and A. R. Meyer and V. R. Pratt", title = "Computability and completeness in logics of programs (Preliminary Report)", crossref = "ACM:1977:CRN", pages = "261--268", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Constable:1977:TPL, author = "Robert L. Constable", title = "On the theory of programming logics", crossref = "ACM:1977:CRN", pages = "269--285", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fischer:1977:PML, author = "Michael J. Fischer and Richard E. Ladner", title = "Propositional modal logic of programs", crossref = "ACM:1977:CRN", pages = "286--294", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{ODonnell:1977:SRS, author = "Mike O'Donnell", title = "Subtree replacement systems: {A} unifying theory for recursive equations, {LISP}, lucid and combinatory logic", crossref = "ACM:1977:CRN", pages = "295--305", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hennessy:1977:PPM, author = "M. C. B. Hennessy and E. A. Ashcroft", title = "Parameter-passing mechanisms and nondeterminism", crossref = "ACM:1977:CRN", pages = "306--311", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Anonymous:1977:ASI, author = "Anonymous", title = "Author and subject index", crossref = "ACM:1977:CRN", pages = "312--314", year = "1977", bibdate = "Wed Feb 20 18:33:30 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Megiddo:1978:COR, author = "Nimrod Megiddo", title = "Combinatorial optimization with rational objective functions", crossref = "ACM:1978:CRT", pages = "1--12", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lueker:1978:MPG, author = "George S. Lueker", title = "Maximization problems on graphs with edge weights chosen from a normal distribution (Extended Abstract)", crossref = "ACM:1978:CRT", pages = "13--18", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Brown:1978:RLL, author = "Mark R. Brown and Robert E. Tarjan", title = "A representation for linear lists with movable fingers", crossref = "ACM:1978:CRT", pages = "19--29", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Storer:1978:MMD, author = "James A. Storer and Thomas G. Szymanski", title = "The macro model for data compression (Extended Abstract)", crossref = "ACM:1978:CRT", pages = "30--39", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{LaPaugh:1978:SHP, author = "Andrea S. LaPaugh and Ronald L. Rivest", title = "The subgraph homeomorphism problem", crossref = "ACM:1978:CRT", pages = "40--50", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Miller:1978:ITP, author = "Gary L. Miller", title = "On the $n\log n$ isomorphism technique ({A} Preliminary Report)", crossref = "ACM:1978:CRT", pages = "51--58", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Carter:1978:EAM, author = "Larry Carter and Robert Floyd and John Gill and George Markowsky and Mark Wegman", title = "Exact and approximate membership testers", crossref = "ACM:1978:CRT", pages = "59--65", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Engelfriet:1978:TTS, author = "J. Engelfriet and G. Rozenberg and G. Slutzki", title = "Tree transducers, {$L$} systems and two-way machines (Extended Abstract)", crossref = "ACM:1978:CRT", pages = "66--74", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Raoult:1978:OSE, author = "Jean-Claude Raoult and Jean Vuillemin", title = "Operational and semantic equivalence between recursive programs", crossref = "ACM:1978:CRT", pages = "75--85", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Katseff:1978:NSC, author = "Howard P. Katseff", title = "A new solution to the critical section problem", crossref = "ACM:1978:CRT", pages = "86--88", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Goldschlager:1978:UAM, author = "Leslie M. Goldschlager", title = "A unified approach to models of synchronous parallel machines", crossref = "ACM:1978:CRT", pages = "89--94", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sciore:1978:CTA, author = "E. Sciore and A. Tang", title = "Computability theory in admissible domains", crossref = "ACM:1978:CRT", pages = "95--104", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Miller:1978:FSS, author = "Raymond E. Miller and Chee K. Yap", title = "On formulating simultaneity for studying parallelism and synchronization", crossref = "ACM:1978:CRT", pages = "105--113", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fortune:1978:PRA, author = "Steven Fortune and James Wyllie", title = "Parallelism in random access machines", crossref = "ACM:1978:CRT", pages = "114--118", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Thatcher:1978:DTS, author = "James W. Thatcher and Eric G. Wagner and Jesse B. Wright", title = "Data type specification: {Parameterization} and the power of specification techniques", crossref = "ACM:1978:CRT", pages = "119--132", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Filotti:1978:EAD, author = "I. S. Filotti", title = "An efficient algorithm for determining whether a cubic graph is toroidal", crossref = "ACM:1978:CRT", pages = "133--142", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Wegener:1978:SFW, author = "Ingo Wegener", title = "Switching functions whose monotone complexity", crossref = "ACM:1978:CRT", pages = "143--149", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lynch:1978:SLP, author = "Nancy A. Lynch", title = "Straight-line program length as a parameter for complexity measures", crossref = "ACM:1978:CRT", pages = "150--161", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Pan:1978:CCC, author = "V. Ya. Pan", title = "Computational complexity of computing polynomials over the fields of real and complex numbers", crossref = "ACM:1978:CRT", pages = "162--172", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ja:1978:OEP, author = "Joseph Ja' Ja'", title = "Optimal evaluation of pairs of bilinear forms", crossref = "ACM:1978:CRT", pages = "173--183", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Gabow:1978:AEC, author = "Harold N. Gabow and Oded Kariv", title = "Algorithms for edge coloring bipartite graphs", crossref = "ACM:1978:CRT", pages = "184--192", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Hyafil:1978:PEM, author = "Laurent Hyafil", title = "On the parallel evaluation of multivariate polynomials", crossref = "ACM:1978:CRT", pages = "193--195", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Tompa:1978:TST, author = "Martin Tompa", title = "Time-space tradeoffs for computing functions, using connectivity properties of their circuits", crossref = "ACM:1978:CRT", pages = "196--204", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Gurari:1978:NCN, author = "Eitan M. Gurari and Oscar H. Ibarra", title = "An {NP}-complete number-theoretic problem", crossref = "ACM:1978:CRT", pages = "205--215", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Schaefer:1978:CSP, author = "Thomas J. Schaefer", title = "The complexity of satisfiability problems", crossref = "ACM:1978:CRT", pages = "216--226", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rivest:1978:CEB, author = "R. L. Rivest and A. R. Meyer and D. J. Kleitman", title = "Coping with errors in binary search procedures (Preliminary Report)", crossref = "ACM:1978:CRT", pages = "227--232", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Bruss:1978:TSC, author = "Anni R. Bruss and Albert R. Meyer", title = "On time-space classes and their relation to the theory of real addition", crossref = "ACM:1978:CRT", pages = "233--239", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kirkpatrick:1978:CGM, author = "David G. Kirkpatrick and Pavol Hell", title = "On the completeness of a generalized matching problem", crossref = "ACM:1978:CRT", pages = "240--245", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Dowd:1978:PRA, author = "Martin Dowd", title = "Propositional representation of arithmetic proofs (Preliminary Version)", crossref = "ACM:1978:CRT", pages = "246--252", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Yannakakis:1978:NED, author = "Mihalis Yannakakis", title = "Node-and edge-deletion {NP}-complete problems", crossref = "ACM:1978:CRT", pages = "253--264", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lewis:1978:CMS, author = "John M. Lewis", title = "On the complexity of the {Maximum Subgraph Problem}", crossref = "ACM:1978:CRT", pages = "265--274", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sakoda:1978:NST, author = "William J. Sakoda and Michael Sipser", title = "Nondeterminism and the size of two way finite automata", crossref = "ACM:1978:CRT", pages = "275--286", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kozen:1978:ISC, author = "Dexter Kozen", title = "Indexing of subrecursive classes", crossref = "ACM:1978:CRT", pages = "287--295", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Anonymous:1978:AFA, author = "Anonymous", title = "An analysis of the full alpha-beta pruning algorithm", crossref = "ACM:1978:CRT", pages = "296--313", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Case:1978:AHM, author = "John Case and Carl Smith", title = "Anomaly hierarchies of mechanized inductive inference", crossref = "ACM:1978:CRT", pages = "314--319", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Reddy:1978:PAB, author = "C. R. Reddy and D. W. Loveland", title = "{Presburger} arithmetic with bounded quantifier alternation", crossref = "ACM:1978:CRT", pages = "320--325", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Pratt:1978:PDM, author = "V. R. Pratt", title = "A practical decision method for propositional dynamic logic (Preliminary Report)", crossref = "ACM:1978:CRT", pages = "326--337", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rackoff:1978:RQI, author = "Charles Rackoff", title = "Relativized questions involving probabilistic algorithms", crossref = "ACM:1978:CRT", pages = "338--342", year = "1978", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Valdes:1979:RSP, author = "Jacobo Valdes and Robert E. Tarjan and Eugene L. Lawler", title = "The recognition of {Series Parallel} digraphs", crossref = "ACM:1979:CRE", pages = "1--12", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Galil:1979:NFG, author = "Zvi Galil and Amnon Naamad", title = "Network flow and generalized path compression", crossref = "ACM:1979:CRE", pages = "13--26", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Filotti:1979:DGG, author = "I. S. Filotti and Gary L. Miller and John Reif", title = "On determining the genus of a graph in {$O(v^{O(g)})$} steps (Preliminary Report)", crossref = "ACM:1979:CRE", pages = "27--37", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Chazelle:1979:DPC, author = "Bernard Chazelle and David Dobkin", title = "Decomposing a polygon into its convex parts", crossref = "ACM:1979:CRE", pages = "38--48", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Flajolet:1979:CIC, author = "P. Flajolet and J. Fran{\c{c}}on and J. Vuillemin", title = "Computing integrated costs of sequences of operations with application to dictionaries", crossref = "ACM:1979:CRE", pages = "49--61", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Fredman:1979:NOD, author = "Michael L. Fredman", title = "A near optimal data structure for a type of range query problem", crossref = "ACM:1979:CRE", pages = "62--66", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kosaraju:1979:MSP, author = "S. Rao Kosaraju", title = "On a multidimensional search problem (Preliminary Version)", crossref = "ACM:1979:CRE", pages = "67--73", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sedgewick:1979:CFP, author = "Robert Sedgewick and Thomas G. Szymanski", title = "The complexity of finding periods", crossref = "ACM:1979:CRE", pages = "74--80", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Thompson:1979:ATC, author = "C. D. Thompson", title = "Area-time complexity for {VLSI}", crossref = "ACM:1979:CRE", pages = "81--88", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Toueg:1979:DFP, author = "Sam Toueg and Jeffrey D. Ullman", title = "Deadlock-free packet switching networks", crossref = "ACM:1979:CRE", pages = "89--98", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Rosenberg:1979:SRT, author = "Arnold L. Rosenberg and Derick Wood and Zvi Galil", title = "Storage representations for tree-like data structures", crossref = "ACM:1979:CRE", pages = "99--107", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Munro:1979:IDS, author = "J. Ian Munro and Hendra Suwanda", title = "Implicit data structures (Preliminary Draft)", crossref = "ACM:1979:CRE", pages = "108--117", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Shamir:1979:CKS, author = "Adi Shamir", title = "On the cryptocomplexity of knapsack systems", crossref = "ACM:1979:CRE", pages = "118--129", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Angluin:1979:FPC, author = "Dana Angluin", title = "Finding patterns common to a set of strings (Extended Abstract)", crossref = "ACM:1979:CRE", pages = "130--141", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Gurari:1979:CEP, author = "Eitan M. Gurari and Oscar H. Ibarra", title = "The complexity of the equivalence problem for counter machines, semilinear sets, and simple programs", crossref = "ACM:1979:CRE", pages = "142--152", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{DeMillo:1979:SCB, author = "Richard A. DeMillo and Richard J. Lipton", title = "Some connections between mathematical logic and complexity theory", crossref = "ACM:1979:CRE", pages = "153--159", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Berman:1979:CTA, author = "Francine Berman", title = "A completeness technique for $d$-axiomatizable semantics", crossref = "ACM:1979:CRE", pages = "160--166", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Meyer:1979:EPD, author = "Albert R. Meyer and Karl Winklmann", title = "On the expressive power of {Dynamic Logic} (Preliminary Report)", crossref = "ACM:1979:CRE", pages = "167--175", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{ODonnell:1979:PLT, author = "Michael O'Donnell", title = "A programming language theorem which is independent of {Peano Arithmetic}", crossref = "ACM:1979:CRE", pages = "176--188", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Valiant:1979:NCE, author = "L. G. Valiant", title = "Negation can be exponentially powerful", crossref = "ACM:1979:CRE", pages = "189--196", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{JaJa:1979:CBF, author = "Joseph Ja'Ja'", title = "On the complexity of bilinear forms with commutativity", crossref = "ACM:1979:CRE", pages = "197--208", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Yao:1979:SCQ, author = "Andrew Chi-Chih Yao", title = "Some complexity questions related to distributive computing (Preliminary Report)", crossref = "ACM:1979:CRE", pages = "209--213", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ladner:1979:CPS, author = "Richard E. Ladner", title = "The complexity of problems in systems of communicating sequential processes (Extended Abstract)", crossref = "ACM:1979:CRE", pages = "214--223", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Peterson:1979:TST, author = "G. L. Peterson", title = "Time-space trade-offs for asynchronous parallel models (Reducibilities and Equivalences)", crossref = "ACM:1979:CRE", pages = "224--230", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kosaraju:1979:FPP, author = "S. Rao Kosaraju", title = "Fast parallel processing array algorithms for some graph problems (Preliminary Version)", crossref = "ACM:1979:CRE", pages = "231--236", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Gilbert:1979:PPC, author = "John R. Gilbert and Thomas Lengauer and Robert Endre Tarjan", title = "The pebbling problem is complete in polynomial space", crossref = "ACM:1979:CRE", pages = "237--248", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Valiant:1979:CCA, author = "L. G. Valiant", title = "Completeness classes in algebra", crossref = "ACM:1979:CRE", pages = "249--261", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Lengauer:1979:ULB, author = "Thomas Lengauer and Robert Endre Tarjan", title = "Upper and lower bounds on time-space tradeoffs", crossref = "ACM:1979:CRE", pages = "262--277", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Long:1979:GRV, author = "Timothy J. Long", title = "On $\gamma$-reducibility versus polynomial time many-one reducibility (Extended Abstract)", crossref = "ACM:1979:CRE", pages = "278--287", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Reif:1979:UGI, author = "John H. Reif", title = "Universal games of incomplete information", crossref = "ACM:1979:CRE", pages = "288--308", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Chandra:1979:CQR, author = "Ashok K. Chandra and David Harel", title = "Computable queries for relational data bases (Preliminary Report)", crossref = "ACM:1979:CRE", pages = "309--318", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Beeri:1979:ERD, author = "Catriel Beeri and Alberto O. Mendelzon and Yehoshua Sagiv and Jeffrey D. Ullman", title = "Equivalence of relational database schemes", crossref = "ACM:1979:CRE", pages = "319--329", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Maier:1979:MCR, author = "David Maier", title = "Minimum covers in the relational database model (Extended Abstract)", crossref = "ACM:1979:CRE", pages = "330--337", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Cook:1979:DCA, author = "Stephen A. Cook", title = "Deterministic {CFL}'s are accepted simultaneously in polynomial time and log squared space", crossref = "ACM:1979:CRE", pages = "338--345", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Kosaraju:1979:RTS, author = "S. Rao Kosaraju", title = "Real-time simulation of concatenable double-ended queues by double-ended queues (Preliminary Version)", crossref = "ACM:1979:CRE", pages = "346--351", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Ruzzo:1979:TSB, author = "Walter L. Ruzzo", title = "Tree-size bounded alternation (Extended Abstract)", crossref = "ACM:1979:CRE", pages = "352--359", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } @InProceedings{Sipser:1979:LBS, author = "Michael Sipser", title = "Lower bounds on the size of sweeping automata", crossref = "ACM:1979:CRE", pages = "360--364", year = "1979", bibdate = "Wed Feb 20 18:33:31 MST 2002", bibsource = "http://portal.acm.org/; http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, } %%% ==================================================================== %%% Cross-referenced entries must come last: @Proceedings{ACM:1970:CRS, editor = "{ACM}", booktitle = "Conference record of second annual {ACM} Symposium on Theory of Computing: papers presented at the symposium, Northampton, Massachusetts, May 4, 5, 6, 1970", title = "Conference record of second annual {ACM} Symposium on Theory of Computing: papers presented at the symposium, Northampton, Massachusetts, May 4, 5, 6, 1970", publisher = pub-ACM, address = pub-ACM:adr, pages = "v + 230", year = "1970", LCCN = "QA75.5 .A22 1970", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "electronic digital computers --- programming --- congresses; computational complexity --- congresses", xxISBN = "none", } @Proceedings{ACM:1971:CRT, editor = "{ACM}", booktitle = "Conference record of third annual {ACM} Symposium on Theory of Computing: papers presented at the symposium, Shaker Heights, Ohio, May 3, 4, 5, 1971", title = "Conference record of third annual {ACM} Symposium on Theory of Computing: papers presented at the symposium, Shaker Heights, Ohio, May 3, 4, 5, 1971", publisher = pub-ACM, address = pub-ACM:adr, pages = "v + 266", year = "1971", LCCN = "QA75.5 .A22 1971", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "electronic digital computers --- programming --- congresses; computational complexity --- congresses", xxISBN = "none", } @Proceedings{ACM:1972:CRF, editor = "{ACM}", booktitle = "Conference record, Fourth Annual {ACM} Symposium on Theory of Computing: papers presented at the symposium, Denver, Colorado, May 1, 2, 3, 1972", title = "Conference record, Fourth Annual {ACM} Symposium on Theory of Computing: papers presented at the symposium, Denver, Colorado, May 1, 2, 3, 1972", publisher = pub-ACM, address = pub-ACM:adr, pages = "v + 263", year = "1972", LCCN = "QA76.6 .A13 1972", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "electronic data processing --- congresses; programming (electronic computers) --- congresses", xxISBN = "none", } @Proceedings{ACM:1973:CRF, editor = "{ACM}", booktitle = "Conference record of Fifth Annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Austin, Texas, April 30--May 2, 1973", title = "Conference record of Fifth Annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Austin, Texas, April 30--May 2, 1973", publisher = pub-ACM, address = pub-ACM:adr, pages = "iv + 277", year = "1973", LCCN = "QA76.6 .A16 1973", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "electronic digital computers --- programming --- congresses; computational complexity --- congresses; machine theory --- congresses", xxISBN = "none", } @Proceedings{ACM:1974:CRS, editor = "{ACM}", booktitle = "Conference record of sixth annual {ACM} Symposium on Theory of Computing: papers presented at the symposium, Seattle, Washington, April 30--May 2, 1974", title = "Conference record of sixth annual {ACM} Symposium on Theory of Computing: papers presented at the symposium, Seattle, Washington, April 30--May 2, 1974", publisher = pub-ACM, address = pub-ACM:adr, pages = "iv + 347", year = "1974", LCCN = "QA76.6 .A13 1974", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "electronic digital computers --- programming --- congresses; computational complexity --- congresses", xxISBN = "none", } @Proceedings{ACM:1975:CRS, editor = "ACM", booktitle = "Conference record of Seventh Annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Albuquerque, New Mexico, May 5--May 7, 1975", title = "Conference record of Seventh Annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Albuquerque, New Mexico, May 5--May 7, 1975", publisher = pub-ACM, address = pub-ACM:adr, pages = "v + 265", year = "1975", LCCN = "QA76.6 .A16 1975", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "electronic digital computers --- programming --- congresses; computational complexity --- congresses; machine theory --- congresses", xxISBN = "none", } @Proceedings{ACM:1976:CRE, editor = "ACM", booktitle = "Conference record of the eighth annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Hershey, Pennsylvania, May 3--5, 1976", title = "Conference record of the eighth annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Hershey, Pennsylvania, May 3--5, 1976", publisher = pub-ACM, address = pub-ACM:adr, pages = "iv + 246", year = "1976", LCCN = "QA 76.6 A12 1976", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "electronic digital computers --- programming --- congresses; computational complexity --- congresses", xxISBN = "none", } @Proceedings{ACM:1977:CRN, editor = "ACM", booktitle = "Conference record of the ninth annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Boulder, Colorado, May 2--4, 1977", title = "Conference record of the ninth annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Boulder, Colorado, May 2--4, 1977", publisher = pub-ACM, address = pub-ACM:adr, pages = "v + 314", year = "1977", LCCN = "QA76.6 .A13 1977", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "computational complexity --- congresses; electronic digital computers --- programming --- congresses", xxISBN = "none", } @Proceedings{ACM:1978:CRT, editor = "ACM", booktitle = "Conference record of the tenth annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, San Diego, California, May 1--3, 1978", title = "Conference record of the tenth annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, San Diego, California, May 1--3, 1978", publisher = pub-ACM, address = pub-ACM:adr, pages = "iv + 346", year = "1978", LCCN = "QA76.6.A13 1978", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "computational complexity --- congresses; electronic digital computers --- programming --- congresses", xxISBN = "none", } @Proceedings{ACM:1979:CRE, editor = "{ACM}", booktitle = "Conference record of the eleventh annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Atlanta, Georgia, April 30--May 2, 1979", title = "Conference record of the eleventh annual {ACM} Symposium on Theory of Computing: papers presented at the Symposium, Atlanta, Georgia, April 30--May 2, 1979", publisher = pub-ACM, address = pub-ACM:adr, pages = "vii + 368", year = "1979", LCCN = "QA75.5.A14 1979", bibdate = "Thu Dec 3 07:11:18 MST 1998", bibsource = "http://www.math.utah.edu/pub/tex/bib/stoc1970.bib", acknowledgement = ack-nhfb, keywords = "computational complexity --- congresses", xxISBN = "none", }