%%% -*-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",
}