%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.03",
%%% date = "07 October 1999",
%%% time = "12:44:38 MDT",
%%% filename = "tcs1975.bib",
%%% address = "Center for Scientific Computing
%%% University of Utah
%%% Department of Mathematics, 322 INSCC
%%% 155 S 1400 E RM 233
%%% Salt Lake City, UT 84112-0090
%%% USA",
%%% telephone = "+1 801 581 5254",
%%% FAX = "+1 801 585 1640, +1 801 581 4148",
%%% URL = "http://www.math.utah.edu/~beebe",
%%% checksum = "49157 4697 18868 172485",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at ieee.org (Internet)",
%%% codetable = "ISO/ASCII",
%%% keywords = "BibTeX, bibliography, Theoretical Computer
%%% Science",
%%% supported = "yes",
%%% docstring = "This is a bibliography of publications in
%%% the journal Theoretical Computer Science
%%% (CODEN TCSCDI, ISSN 0304-3975), which
%%% began publishing in 1975.
%%%
%%% This file covers the years 1975--1979;
%%% companion files tcs19xx.bib each cover
%%% other pentads.
%%%
%%% The journal has World-Wide Web home sites
%%% at several locations:
%%%
%%% Title pages:
%%% http://www.elsevier.nl/locate/issn/03043975 (Europe)
%%% http://www.elsevier.com/locate/issn/03043975 (North America)
%%% http://www.elsevier.co.jp/locate/issn/03043975 (Japan)
%%% http://www.sciencedirect.com/science/journal/03043975
%%%
%%% Tables of contents:
%%% http://www.elsevier.nl/locate/tcs
%%% http://www.elsevier.nl/locate/estoc/03043975 (Europe)
%%% http://www.elsevier.com/locate/estoc/03043975 (North America)
%%% http://www.elsevier.co.jp/locate/estoc/03043975 (Japan)
%%%
%%% Elsevier Science alert page:
%%% http://www.elsevier.nl/mcs/tcs/Menu.html (Europe)
%%%
%%% The tables of contents sites begin coverage
%%% with Volume 91, Number 1, 1992, and have full
%%% text of articles from Volume 190, Number 1,
%%% 1998.
%%%
%%% At version 1.03, the year coverage looked
%%% like this:
%%%
%%% 1975 ( 11) 1977 ( 40) 1979 ( 48)
%%% 1976 ( 62) 1978 ( 35)
%%%
%%% Article: 196
%%%
%%% Total entries: 196
%%%
%%% This bibliography was prepared by merging
%%% data from the TeX Users Group bibliography
%%% archive, the BibNet Project archive, the OCLC
%%% Contents1st database, the Compendex database,
%%% and the IEEE INSPEC database.
%%%
%%% Numerous errors in the sources noted above
%%% have been corrected. Spelling has been
%%% verified with the UNIX spell and GNU ispell
%%% programs using the exception dictionary
%%% stored in the companion file with extension
%%% .sok.
%%%
%%% BibTeX citation tags are uniformly chosen
%%% as name:year:abbrev, where name is the
%%% family name of the first author or editor,
%%% year is a 4-digit number, and abbrev is a
%%% 3-letter condensation of important title
%%% words. Citation tags were automatically
%%% generated by software developed for the
%%% BibNet Project.
%%%
%%% In this bibliography, entries are sorted in
%%% publication order within each journal,
%%% using bibsort -byvolume.
%%%
%%% 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.",
%%% }
%%% ====================================================================
@Preamble{"\hyphenation{
Bai-er
He-ma-chan-dra
Ko-ba-ya-shi
Kri-zanc
Lett-mann
Mal-u-szyn-ski
Mar-chet-ti
Mar-u-o-ka
Och-man-ski
Pal-a-mi-des-si
Piet-rzy-kow-ski
Pros-ku-row-ski
Pu-ru-sho-tha-man
Ros-en-krantz
Spor-tel-li
Sturt-i-vant
Ta-ka-da
Vau-zeilles
Win-kow-ski
Win-skel
to-po-log-ique
}"}
%=======================================================================
% Acknowledgement abbreviations:
@String{ack-nhfb = "Nelson H. F. Beebe,
Center for Scientific Computing,
University of Utah,
Department of Mathematics, 322 INSCC,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 585 1640, +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@ieee.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
%=======================================================================
% Journal abbreviations:
@String{j-THEOR-COMP-SCI = "Theoretical Computer Science"}
%=======================================================================
% Bibliography entries, sorted in publication order:
@Article{Schonhage:1975:LBL,
author = "A. Schonhage",
title = "A lower bound for the length of addition chains",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "1",
pages = "1--12",
month = jun,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Univ. Math. Inst., Tubingen, West Germany",
keywords = "addition chains; addition/subtraction chains; binary
expansion; digital arithmetic",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Paterson:1975:CMN,
author = "M. S. Paterson",
title = "Complexity of monotone networks for {Boolean} matrix
product",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "1",
pages = "13--20",
month = jun,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
keywords = "Boolean functions; Boolean matrix product;
computational complexity; conjunction; disjunction;
monotone networks",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Strassen:1975:CCS,
author = "V. Strassen",
title = "The computational complexity of symbolic
differentiation of interpolating polynomials",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "1",
pages = "21--25",
month = jun,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0290D (Functional analysis); B0290M (Numerical
integration and differentiation); C4120 (Functional
analysis); C4160 (Numerical integration and
differentiation); C4240 (Programming and algorithm
theory)",
corpsource = "Univ. Zurich, Zurich, Switzerland",
keywords = "computational complexity; derivative; differentiation;
divisions; function evaluation; interpolation;
multiplications; polynomial; polynomials",
language = "German",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Huet:1975:UAT,
author = "G. P. Huet",
title = "A unification algorithm for typed lambda -calculus",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "1",
pages = "27--57",
month = jun,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IRIA-Lab., Rocquencourt, France",
keywords = "calculus; convergence; directionality; formal logic;
lambda calculus; search space; semidecision algorithm;
unification algorithm",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrenfeucht:1975:SCV,
author = "A. Ehrenfeucht and K. P. Lee and G. Rozenberg",
title = "Subword complexities of various classes of
deterministic developmental languages without
interactions",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "1",
pages = "59--75",
month = jun,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder,
CO, USA",
keywords = "0L systems; deterministic 0L system; deterministic
developmental languages without interactions;
deterministic restriction; finite alphabet; formal
languages; singleton; subword complexities",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Reedy:1975:TDI,
author = "A. Reedy and W. J. Savitch",
title = "The {Turing} degree of the inherent ambiguity problem
for context-free languages",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "1",
pages = "77--91",
month = jun,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Div. of Math. Sci., Univ. of Iowa, Iowa City, IA,
USA",
keywords = "context free languages; context-free languages;
inherent ambiguity problem; r.e. sets; Turing degree;
Turing machine; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Restivo:1975:CPC,
author = "A. Restivo",
title = "A combinatorial property of codes having finite
synchronization delay",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "2",
pages = "95--101",
month = dec,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Lab. di Cibernetica, CNR, Arco Felice, Napoli, Italy",
keywords = "automata theory; codes; combinatorial property of
codes; finite synchronisation delay; free monoid;
minimal automaton",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ladner:1975:CPT,
author = "R. E. Ladner and N. A. Lynch and A. L. Selman",
title = "A comparison of polynomial time reducibilities",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "2",
pages = "103--123",
month = dec,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Univ. of Washington, Seattle, WA, USA",
keywords = "bounded truth table; computational complexity;
nondeterminism; polynomial time reducibilities;
recursive function theory; recursive functions; truth
table; Turing reducibility",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Plotkin:1975:CCL,
author = "G. D. Plotkin",
title = "Call-by-name, call-by-value and the lambda -calculus",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "2",
pages = "125--159",
month = dec,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4290 (Other computer
theory)",
corpsource = "Dept. of Machine Intelligence, Univ. of Edinburgh,
Edinburgh, UK",
keywords = "call by name; call by value; continuation technique;
formal languages; ISWIM; lambda calculus; programming
languages; SECD machine; simulations; standardisation
theorem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Harper:1975:CBF,
author = "L. H. Harper and W. N. Hsieh and J. E. Savage",
title = "A class of {Boolean} functions with linear
combinational complexity",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "2",
pages = "161--133",
month = dec,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4230 (Switching theory)",
corpsource = "Dept. of Math., Univ. of California, Riverside, CA,
USA",
keywords = "Boolean functions; combinational networks; linear
combinational complexity",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Preparata:1975:FSS,
author = "F. P. Preparata",
title = "A fast stable sorting algorithm with absolutely
minimum storage",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "2",
pages = "185--190",
month = dec,
year = "1975",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics); C6130 (Data handling
techniques)",
corpsource = "Istituto di Sci. dell'Informazione, Univ. di Pisa,
Pisa, Italy",
keywords = "fast stable sorting algorithm; minimum storage;
sorting; stability",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Moll:1976:OET,
author = "R. Moll",
title = "An operator embedding theorem for complexity classes
of recursive functions",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "3",
pages = "193--198",
month = feb,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Univ. of Massachusetts, Amherst, MA, USA",
keywords = "complexity; computational complexity; operator
embedding theorem; recursive functions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Leeuwen:1976:DTH,
author = "J. Leeuwen and D. Wood",
title = "A decomposition theorem for hyper-algebraic extensions
of language families",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "3",
pages = "199--214",
month = feb,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Utrecht, Utrecht,
Netherlands",
keywords = "alphabetic homomorphism theorem; decomposition
theorem; extension of languages; formal language;
formal languages; hyper algebraic; language families;
translation theorem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Book:1976:TLP,
author = "R. V. Book",
title = "Translational lemmas, polynomial time, and $(\log
n)^j$ --- space",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "3",
pages = "215--216",
month = feb,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Tue Jul 20 10:47:23 1999",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., Yale Univ., New Haven, CT,
USA",
keywords = "complexity; computational complexity; polynomial time;
translational lemmas; Turing acceptor",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Mignotte:1976:ARD,
author = "M. Mignotte",
title = "Algorithms relating to the decomposition of
polynomials",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "3",
pages = "227--235",
month = feb,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0210 (Algebra); C1110 (Algebra)",
corpsource = "Univ. Louis Pasteur, Strasbourg, France",
keywords = "algorithm of H. Zassenhaus; decomposition; integer
coefficients; irreducibility tests; linear factors;
polynomials",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Garey:1976:SSN,
author = "M. R. Garey and D. S. Johnson",
title = "Some simplified {NP-complete} graph problems",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "3",
pages = "237--267",
month = feb,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Bell Labs., Murray Hill, NJ, USA",
keywords = "directed Hamiltonian path problems; graph; graph
theory; node cover; NP complete; optimal linear
arrangement; simple max cut; upper bounds",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Greibach:1976:RCN,
author = "S. A. Greibach",
title = "Remarks on the complexity of nondeterministic counter
languages",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "4",
pages = "269--288",
month = apr,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of System Sci., Univ. of California, Los
Angeles, CA, USA",
keywords = "complexity; computational complexity; counters;
multicounter machines; nondeterministic counter
languages; offline; online; polynomial time",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Schnorr:1976:CCE,
author = "C. P. Schnorr",
title = "The combinational complexity of equivalence",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "4",
pages = "289--295",
month = apr,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Fachbereich Math., Univ. Frankfurt, Frankfurt, West
Germany",
keywords = "binary Boolean operations; Boolean computation;
Boolean functions; computational complexity;
equivalence",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Friedman:1976:IPS,
author = "E. P. Friedman",
title = "The inclusion problem for simple languages",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "4",
pages = "297--316",
month = apr,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of System Sci., Univ. of California, Los
Angeles, CA, USA",
keywords = "automata theory; deterministic pushdown acceptor; free
monadic recursion schemes; LL(k) languages; pushdown
automata; simple machine; undecidable inclusion",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Karhumaki:1976:TTC,
author = "J. Karhumaki",
title = "Two theorems concerning recognizable {N}-subsets of
sigma *",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "4",
pages = "317--323",
month = apr,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
keywords = "automata theory; D0L; formal languages; length
sequence; N subsets; nonnegative integers",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrenfeucht:1976:RBE,
author = "A. Ehrenfeucht and G. Rozenberg and S. Skyum",
title = "A relationship between {ET0L} and {EDT0L} languages",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "4",
pages = "325--330",
month = apr,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder,
CO, USA",
keywords = "EDT0L; ET0L; formal languages; L systems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Marek:1976:ISR,
author = "W. Marek and Z. Pawlak",
title = "Information storage and retrieval systems:
mathematical foundations",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "4",
pages = "331--354",
month = apr,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6120 (File organisation); C7250 (Information
storage and retrieval)",
corpsource = "Inst. of Math., Polish Acad. of Sci., Warsaw, Poland",
keywords = "Boolean algebra; describable sets; file organisation;
information retrieval systems; information storage;
languages; mathematical model; semantics",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Fredman:1976:HGI,
author = "M. L. Fredman",
title = "How good is the information theory bound in sorting?",
journal = j-THEOR-COMP-SCI,
volume = "1",
number = "4",
pages = "355--361",
month = apr,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6130 (Data handling techniques)",
corpsource = "Dept. of Math., MIT, Cambridge, MA, USA",
keywords = "disjoint subsets; information theory bound; nonempty
subsets; sorting",
pubcountry = "Netherlands",
treatment = "A Application; T Theoretical or Mathematical",
}
@Article{Meznik:1976:SSC,
author = "I. Meznik",
title = "On some subclasses of the class of generable
languages",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "1--7",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Math., Tech. Univ. of Brno, Brno,
Czechoslovakia",
keywords = "(k) machine; formal languages; generable languages;
relational machine",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Engelfriet:1976:STL,
author = "J. Engelfriet",
title = "Surface tree languages and parallel derivation trees",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "9--27",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Tech. Univ. Twente, Enschede, Netherlands",
keywords = "ET0L; formal languages; L systems; monadic trees;
parallel derivation trees; surface tree languages; tree
homomorphism; tree transformation languages; trees
(mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ginsburg:1976:SUE,
author = "S. Ginsburg and J. Goldstine and S. Greibach",
title = "Some uniformly erasable families of languages",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "29--44",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Computer Sci. Program, Univ. of Southern California,
Los Angeles, CA, USA",
keywords = "AFA; automata theory; context-free languages; finite
automata; homomorphism; languages; one counter
languages; one letter languages; uniformly erasable",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Chaitin:1976:ICR,
author = "G. J. Chaitin",
title = "Information-theoretic characterizations of recursive
infinite strings",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "45--48",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights,
NY, USA",
keywords = "Loveland's method; Meyer's theorem; recursive
functions; recursive infinite strings",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Vitanyi:1976:DLL,
author = "P. M. B. Vitanyi",
title = "Deterministic {Lindenmayer} languages, nonterminals
and homomorphisms",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "49--71",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Math. Centrum, Amsterdam, Netherlands",
keywords = "deterministic Lindenmayer systems; formal languages;
homomorphisms; linear bounded automata; nonterminals;
one sided context; recursively enumerable languages;
two sided context",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Machtey:1976:MPP,
author = "M. Machtey",
title = "Minimal pairs of polynomial degrees with
subexponential complexity",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "73--76",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Math. and Computer Sci., Purdue Univ., West
Lafayette, IN, USA",
keywords = "arbitrary functions; computability; computability and
decidability; computational complexity; natural
numbers; polynomial degrees; subexponential complexity;
Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hack:1976:QPV,
author = "M. Hack",
title = "The quality problem for vector addition systems is
undecidable",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "77--95",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Project MAC, MIT, Cambridge, MA, USA",
keywords = "computability and decidability; equality problem;
Petri nets; reachability sets; undecidability; vector
addition systems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Levy:1976:AIL,
author = "J.-J. Levy",
title = "An algebraic interpretation of the lambda beta
{K}-calculus; and an application of a labelled
lambda-calculus",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "97--114",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IRIA-Lab., Rocquencourt, France",
keywords = "algebraic interpretation; approximations; formal
logic; inside out reductions; labelled lambda calculus;
lambda beta k calculus",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Herman:1976:SSB,
author = "G. T. Herman and A. Walker",
title = "On the stability of some biological schemes with
cellular interactions",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "1",
pages = "115--130",
month = jun,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., State Univ. of New York,
Amherst, NY, USA",
keywords = "adult language; biological organisms; biological
schemes; cellular arrays; cellular interactions; formal
language; formal languages; grammars; limited erasing;
multicellular growth; stability; theorem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Egli:1976:CCP,
author = "H. Egli and R. L. Constable",
title = "Computability concepts for programming language
semantics",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "2",
pages = "133--145",
month = "????",
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Forshungsinst. fur Math., ETH, Zurich, Switzerland",
keywords = "computability; computability and decidability; lambda
calculus; programming language semantics; recursive
function; recursive functions; Scott models",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Seiferas:1976:RR,
author = "J. I. Seiferas and R. McNaughton",
title = "Regularity-preserving relations",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "2",
pages = "147--154",
month = "????",
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Pennsylvania State Univ., University Park, PA, USA",
keywords = "formal languages; language; proportional removals;
regular languages; regularity; regularity preserving",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{DeBakker:1976:LFP,
author = "J. W. {De Bakker}",
title = "Least fixed points revisited",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "2",
pages = "155--181",
month = "????",
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Math. Centre, Amsterdam, Netherlands",
keywords = "call by name; call by value; formal language; formal
languages; lambda calculus; least fixed points;
parameter mechanisms; recursive procedures",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Rosen:1976:CPP,
author = "B. K. Rosen",
title = "Correctness of parallel programs: the {Church-Rosser}
approach",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "2",
pages = "183--207",
month = "????",
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Computer Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
keywords = "abstract formulation; abstract machines; asynchronous
parallel programs; Church Rosser approach; computer
assisted proofs; correctness proofs; parallel
processing; parallel programs; programming theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Boasson:1976:ALI,
author = "L. Boasson",
title = "Algebraic languages, iterative pairs and rational
transductions",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "2",
pages = "209--223",
month = "????",
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "UER de Math., Univ. de Picardie, Amiens, France",
keywords = "context free languages; context-free languages;
iterative pairs; methodological results; rational
transductions",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Trakhtenbrot:1976:RBC,
author = "M. B. Trakhtenbrot",
title = "Relationships between classes of monotonic functions",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "2",
pages = "228--247",
month = "????",
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Computing Center, Novosibirsk, USSR",
keywords = "composition; monotonic functions; parallel functions;
programming theory; recursion; sequential functions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Vilfan:1976:LBS,
author = "B. Vilfan",
title = "Lower bounds for the size of expressions for certain
functions in $d$-ary logic",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "2",
pages = "249--269",
month = "????",
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4230 (Switching theory)",
corpsource = "Jozef Stefan Inst., Ljubljana, Yugoslavia",
keywords = "Boolean functions; d ary logic; functions; size of
expressions; theorem of Specker; threshold function",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ibarra:1976:FAM,
author = "O. H. Ibarra and S. K. Sahni and C. E. Kim",
title = "Finite automata with multiplication",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "271--294",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., Univ. of Minnesota,
Minneapolis, MN, USA",
keywords = "closure properties; finite automata; finite automaton
with multiplication; positive rational number;
register",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Springsteel:1976:PLS,
author = "F. N. Springsteel",
title = "On the {pre-AFL} of (log n) space and related families
of languages",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "295--304",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. of Montana, Missoula, MT, USA",
keywords = "(log n) space; context free languages; context-free
languages; families of languages; pre AFL",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Schnorr:1976:LBN,
author = "C. P. Schnorr",
title = "A lower bound on the number of additions in monotone
computations",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "305--315",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4140 (Linear
algebra); C4290 (Other computer theory)",
corpsource = "Fachbereich Math., Univ. Frankfurt, Frankfurt, West
Germany",
keywords = "computational complexity; graph theory; graphs; lower
bound; monotone computations; number of additions;
polynomials; rational polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Soittola:1976:PRS,
author = "M. Soittola",
title = "Positive rational sequences",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "317--322",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
keywords = "formal languages; growths of D0L systems; languages;
positive rational sequences; regular; stochastic",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Dezani-Ciancaglini:1976:CNF,
author = "M. Dezani-Ciancaglini",
title = "Characterization of normal forms possessing inverse in
the $\lambda-\beta-\eta$-calculus",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "323--337",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Istituto di Sci. dell'Informazione, Torino, Italy",
keywords = "calculus; characterization; hereditarily finite
permutators; inverse; lambda calculus; normal forms;
permutators",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Even:1976:CS,
author = "S. Even and R. E. Tarjan",
title = "Computing an st-numbering",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "339--344",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Dept. Computer Sci., Technion, Haifa, Israel",
keywords = "biconnected graph; computing; graph theory;
st-numbering",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Minicozzi:1976:SNP,
author = "E. Minicozzi",
title = "Some natural properties of strong-identification in
inductive inference",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "345--360",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Istituto di Sci. dell'Informazione, Univ. di Torino,
Torino, Italy",
keywords = "algorithm; formal logic; inductive inference; machine;
natural properties; partial recursive function; strong
identification",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hunt:1976:CPL,
author = "H. B. Hunt and D. J. Rosenkrantz and T. G. Szymanski",
title = "The covering problem for linear context-free
grammars",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "361--382",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Center for Res. in Computing Technol., Harvard Univ.,
Cambridge, MA, USA",
keywords = "context-free grammars; covering problem; grammatical
covering; linear context free grammars; similarity;
structural equivalence",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Paul:1976:RBF,
author = "W. J. Paul",
title = "Realizing {Boolean} functions on disjoint sets of
variables",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "383--396",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4230 (Switching theory)",
corpsource = "Cornell Univ., Ithaca, NY, USA",
keywords = "Ashenhurst decomposition; Boolean functions;
combinational complexity; disjoint sets of variables;
switching functions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Paterson:1976:CSN,
author = "M. S. Paterson and L. G. Valiant",
title = "Circuit size is nonlinear in depth",
journal = j-THEOR-COMP-SCI,
volume = "2",
number = "3",
pages = "397--400",
month = sep,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4230 (Switching theory)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
keywords = "Boolean function; Boolean functions; circuit depth;
circuit size; computational complexity; fundamental
complexity measures; nonlinear in depth",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Stockmeyer:1976:PH,
author = "L. J. Stockmeyer",
title = "The polynomial-time hierarchy",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "1",
pages = "1--22",
month = oct,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4290 (Other computer theory)",
corpsource = "Math. Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
keywords = "computational complexity; hierarchy; Kleene
arithmetical hierarchy; polynomial time; properties;
space complexity; word problem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Wrathall:1976:CSP,
author = "C. Wrathall",
title = "Complete sets and the polynomial-time hierarchy",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "1",
pages = "23--33",
month = oct,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4290 (Other computer theory)",
corpsource = "Dept. of Computer Sci., Yale Univ., New Haven, CT,
USA",
keywords = "complete sets; computational complexity; polynomial
time hierarchy",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Lallement:1976:RSD,
author = "G. Lallement",
title = "Regular semigroups with {D}={R} as syntactic monoids
of prefix codes",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "1",
pages = "35--49",
month = oct,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4210 (Formal logic)",
corpsource = "Pennsylvania State Univ., University Park, PA, USA",
keywords = "alphabet; formal languages; group theory; language;
prefix codes; regular semigroups; syntactic monoids",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hotz:1976:CBT,
author = "G. Hotz",
title = "Conditions for balanced trees on weighted
distributions",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "1",
pages = "51--59",
month = oct,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Univ. des Saarlandes, Saarbrucken, West Germany",
keywords = "balanced trees; binary; ternary; trees (mathematics);
weak conditions; weighted distributions",
language = "German",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Monien:1976:RGC,
author = "B. Monien",
title = "A recursive and a grammatical characterization of the
exponential-time languages",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "1",
pages = "61--74",
month = oct,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Abteilung Informatik, Univ. Dortmund, Dortmund, West
Germany",
keywords = "characterization; exponential time languages; formal
languages; grammatical; recursive",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Culik:1976:DSE,
author = "K. {Culik, II}",
title = "On the decidability of the sequence equivalence
problem for {D0L-systems}",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "1",
pages = "75--84",
month = oct,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo,
Ont., Canada",
keywords = "computability and decidability; D0L systems;
decidability; sequence equivalence problem;
smoothness",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Araki:1976:SDP,
author = "T. Araki and T. Kasami",
title = "Some decision problems related to the reachability
problem for {Petri} nets",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "1",
pages = "85--104",
month = oct,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Information and Computer Sci., Osaka Univ.,
Toyonaka, Osaka, Japan",
keywords = "computability and decidability; decision problems;
firing sequences; formal logic; Petri nets;
reachability problem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Jones:1976:CPD,
author = "N. D. Jones and W. T. Laaser",
title = "Complete problems for deterministic polynomial time",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "1",
pages = "105--117",
month = oct,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4290 (Other computer theory)",
corpsource = "Computer Sci. Dept., Univ. of Kansas, Lawrence, KS,
USA",
keywords = "completeness; complexity; computational complexity;
deterministic polynomial time",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Jensen:1976:MOT,
author = "D. C. Jensen and T. Pietrzykowski",
title = "Mechanizing omega-order type theory through
unification",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "2",
pages = "123--171",
month = nov,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1230 (Artificial intelligence); C4210 (Formal
logic)",
corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo,
Ont., Canada",
keywords = "formal logic; mechanical theorem proving; omega order
type theory; theorem proving; type theory; unification
problem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Park:1976:FM,
author = "D. Park",
title = "Finiteness is mu-ineffable",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "2",
pages = "173--181",
month = nov,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
keywords = "formal logic; formal system; minimal fixpoint
operator; mu calculus; predicate logic",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Lipski:1976:ISR,
author = "W. {Lipski, Jr.}",
title = "Information storage and retrieval-mathematical
foundations {II}. Combinatorial problems",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "2",
pages = "183--211",
month = nov,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6120 (File organisation)",
corpsource = "Computation Centre, Polish Acad. of Sci., Warsaw,
Poland",
keywords = "combinatorial problem; file organisation; file
organisations; information retrieval; information
storage",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hartmanis:1976:TBS,
author = "J. Hartmanis and L. Berman",
title = "On tape bounds for single letter alphabet language
processing",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "2",
pages = "213--224",
month = nov,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., Cornell Univ., Ithaca, NY,
USA",
keywords = "formal languages; single letter alphabet language;
single letter alphabets; tape bounded complexity; tape
bounds; Turing machine; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Barendregt:1976:GRR,
author = "H. Barendregt",
title = "A global representation of the recursive functions in
the lambda -calculus",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "2",
pages = "225--242",
month = nov,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Math. Inst., Univ. of Utrecht, Utrecht, Netherlands",
keywords = "Church Rosser theorem; formal logic; lambda calculus;
recursive functions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Schutzenberger:1976:RRB,
author = "M. P. Schutzenberger",
title = "On the rational relations between free monoids",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "2",
pages = "243--259",
month = nov,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Univ. de Paris VII, Paris, France",
keywords = "automata theory; Eilenberg's theory; free monoids;
rational relation; transducer method",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Starke:1976:ASA,
author = "P. H. Starke",
title = "Analysis and synthesis of asynchronous {ND-automata}",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "2",
pages = "261--266",
month = nov,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Sektion Math., Humboldt Univ., Berlin, East Germany",
keywords = "asynchronous nondeterministic automata; decidable
property; finite automata",
language = "German",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Schonhage:1976:EPS,
author = "A. Schonhage",
title = "An elementary proof for {Strassen}'s degree bound",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "2",
pages = "267--272",
month = nov,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Inst. of Math., Univ. of Tubingen, Tubingen, West
Germany",
keywords = "algebraic geometry; computational complexity;
multiplications/divisions; polynomials; Strassen's
degree bound; symmetric polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Szymanski:1976:CBG,
author = "T. G. Szymanski",
title = "Concerning bounded-right-context grammars",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "3",
pages = "273--282",
month = dec,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Electrical Engng. and Computer Sci.,
Princeton Univ., Princeton, NJ, USA",
keywords = "bounded right context grammar; context free grammar;
context-free grammars",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ruohonen:1976:ZZF,
author = "K. Ruohonen",
title = "Zeros of {Z}-rational functions and {D0L}
equivalence",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "3",
pages = "283--292",
month = dec,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Math. Dept., Univ. of Turku, Turku, Finland",
keywords = "computability and decidability; D0L equivalence;
decidability; equivalence problem; findability;
solvability; Z-rational functions; zeros",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Chandra:1976:AAS,
author = "A. K. Chandra and D. S. Hirschberg and C. K. Wong",
title = "Approximate algorithms for some generalized knapsack
problems",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "3",
pages = "293--304",
month = dec,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1180 (Optimisation techniques)",
corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights,
NY, USA",
keywords = "approximate algorithms; binary multiple choice;
generalized knapsack problems; integer multiple choice;
multidimensional; optimisation",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Beeri:1976:IVD,
author = "C. Beeri",
title = "An improvement on {Valiant}'s decision procedure for
equivalence of deterministic finite turn pushdown
machines",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "3",
pages = "305--320",
month = dec,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Electrical Engng. and Computer Sci.,
Princeton Univ., Princeton, NJ, USA",
keywords = "computational complexity; decision procedure;
deterministic finite turn pushdown machines;
equivalence; finite automata; time complexity",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Knuth:1976:ASF,
author = "D. E. Knuth and L. T. Pardo",
title = "Analysis of a simple factorization algorithm",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "3",
pages = "321--348",
month = dec,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Computer Sci. Dept., Stanford Univ., Stanford, CA,
USA",
keywords = "factorization algorithm; largest prime factor; limit;
number theory; probability",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Lipton:1976:CMH,
author = "R. J. Lipton and D. Dobkin",
title = "Complexity measures and hierarchies for the evaluation
of integers and polynomials",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "3",
pages = "349--357",
month = dec,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., Yale Univ., New Haven, CT,
USA",
keywords = "complexity; computational complexity; evaluation;
hierarchies; integers; polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Wise:1976:SPL,
author = "D. S. Wise",
title = "A strong pumping lemma for context-free languages",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "3",
pages = "359--369",
month = dec,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Dept., Indiana Univ., Bloomington, IN,
USA",
keywords = "context free language; context-free languages; strong
pumping lemma",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Rivest:1976:RGP,
author = "R. L. Rivest and J. Vuillemin",
title = "On recognizing graph properties from adjacency
matrices",
journal = j-THEOR-COMP-SCI,
volume = "3",
number = "3",
pages = "371--384",
month = dec,
year = "1976",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Lab. for Computer Sci., MIT, Cambridge, MA, USA",
keywords = "adjacency matrices; graph properties; graph theory;
transitive permutation group",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Milner:1977:FAM,
author = "R. Milner",
title = "Fully abstract models of typed lambda -calculi",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "1",
pages = "1--22",
month = feb,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Dept., Edinburgh Univ., Edinburgh, UK",
keywords = "denotational semantic definition; formal languages;
fully abstract models; programming language; typed
lambda-calculi",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Galil:1977:CRR,
author = "Z. Galil",
title = "On the complexity of regular resolution and the
{{Davis-Putnam}} procedure",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "1",
pages = "23--46",
month = feb,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Dept., IBM Thomas J. Watson Res. Centre,
Yorktown Heights, NY, USA",
keywords = "Boolean; Boolean algebra; complexity; computational
complexity; Davis Putnam procedure; regular
resolution",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Schutzenberger:1977:VSF,
author = "H. P. Schutzenberger",
title = "On a variant of sequential functions",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "1",
pages = "47--57",
month = feb,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4230D (Sequential switching theory)",
corpsource = "Univ. de Paris VII, Rocquencourt, France",
keywords = "Eilenberg theorem; Ginsberg theorem; Rose theorem;
sequential functions; sequential switching;
subsequential functions; switching functions",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Lehmann:1977:AST,
author = "D. J. Lehmann",
title = "Algebraic structures for transitive closure",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "1",
pages = "59--76",
month = feb,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
keywords = "algebraic structures; algorithm theory; Dijkstra's
algorithm; semirings; transitive closure",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Vuillemin:1977:HVC,
author = "J. Vuillemin",
title = "How to verify the connectivity of a group table",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "1",
pages = "77--82",
month = feb,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra)",
corpsource = "Dept. d'Informatique, Univ. de Paris-Sud, Orsay,
France",
keywords = "algorithm; group; group theory; groupoid; testing",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Linna:1977:DRD,
author = "M. Linna",
title = "A decidability result for deterministic
omega-context-free languages",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "1",
pages = "83--98",
month = feb,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
keywords = "computability and decidability; context-free
languages; decidability; deterministic; omega context
free languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Araki:1977:DPS,
author = "T. Araki and T. Kasami",
title = "Decidable problems on the strong connectivity of
{Petri} net reachability sets",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "1",
pages = "99--119",
month = feb,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Information and Computer Sci., Faculty of
Engng. Sci., Osaka Univ., Toyonaka, Osaka, Japan",
keywords = "computability and decidability; decidable; Petri net;
reachability sets; strong connectivity",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Markowsky:1977:CCP,
author = "G. Markowsky",
title = "Categories of chain-complete posets",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "2",
pages = "125--135",
month = apr,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Computer Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
keywords = "categories; chain complete posets; formal languages;
isotone maps; posets; set theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hosono:1977:RPO,
author = "C. Hosono and M. Sato",
title = "The retracts in {P} omega do not form a continuous
lattice --- a solution to {Scott}'s problem",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "2",
pages = "137--142",
month = apr,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Dept. of Math., Kyoto Univ., Kyoto, Japan",
keywords = "continuous lattice; Pomega; retracts; topology",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Geller:1977:EDP,
author = "M. M. Geller and H. B. {Hunt, III} and T. G. Szymanski
and J. D. Ullman",
title = "Economy of description by parsers, {DPDA's}, and
{PDA's}",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "2",
pages = "143--153",
month = apr,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Univ. of Michigan, Ann Arbor, MI, USA",
keywords = "description; deterministic automata; deterministic
pushdown automata; formal languages; languages;
parsers; pushdown automata",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Francon:1977:AAT,
author = "J. Francon",
title = "On the analysis of algorithms for trees",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "2",
pages = "155--169",
month = apr,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Centre de Calcul du CNRS, Strasbourg, France",
keywords = "algorithm theory; algorithms; analysis; nodes; trees;
trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Stork:1977:PPA,
author = "H.-G. Stork",
title = "On the paging-complexity of periodic arrangements",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "2",
pages = "171--197",
month = apr,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6120
(File organisation)",
corpsource = "Inst. fur Informatik, Univ. Stuttgart, Stuttgart, West
Germany",
keywords = "complexity; file organisation; locality principle;
paging system; periodic arrangements; program
structure; reference strings",
pubcountry = "Netherlands",
treatment = "A Application; T Theoretical or Mathematical",
}
@Article{Maurer:1977:FEL,
author = "H. Maurer and Th. Ottmann and A. Salomaa",
title = "On the form equivalence of {L}-forms",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "2",
pages = "199--225",
month = apr,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. fur Angewandte Informatik und Formale
Beschreibungsverfahren, Univ. Karlsruhe, Karlsruhe,
West Germany",
keywords = "computability and decidability; decidable;
deterministic; form equivalence; formal languages;
grammar; grammars; L-forms",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ferrante:1977:EDP,
author = "J. Ferrante and J. R. Geiser",
title = "An efficient decision procedure for the theory of
rational order",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "2",
pages = "227--233",
month = apr,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Tufts Univ., Medford, MA, USA",
keywords = "decision procedure; efficient; number theory; rational
numbers; rational order; sentences",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Lehmann:1977:NSS,
author = "D. J. Lehmann",
title = "A note on {Schnorr}'s separatedness",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "2",
pages = "235--??",
month = apr,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
keywords = "digital arithmetic; monotone computations;
separatedness",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Papadimitriou:1977:ETS,
author = "C. H. Papadimitriou",
title = "The {Euclidean} traveling salesman problem is
{NP-complete}",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "3",
pages = "237--244",
month = jun,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1180 (Optimisation techniques)",
corpsource = "Center for Res. in Computing Technol., Harvard Univ.,
Cambridge, MA, USA",
keywords = "Euclidean; NP-complete; optimisation; travelling
salesman problem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Geller:1977:LGL,
author = "M. M. Geller and M. A. Harrison",
title = "On {LR(k}) grammars and languages",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "3",
pages = "245--276",
month = jun,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Computer Sci. Div., Univ. of California, Berkeley, CA,
USA",
keywords = "computability and decidability; decidability;
deterministic automata; deterministic pushdown
automata; equality problem; formal languages; grammars;
languages; LR(k) grammars",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Jones:1977:CSP,
author = "N. D. Jones and L. H. Landweber and Y. E. Lien",
title = "Complexity of some problems in {Petri} nets",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "3",
pages = "277--299",
month = jun,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dept. of Computer Sci., Univ. of Kansas, Lawrence, KS,
USA",
keywords = "complexity; computational complexity; controllability;
directed graphs; k-boundedness; liveness; Petri nets;
reachability",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Daley:1977:IOD,
author = "R. Daley",
title = "On the inference of optimal descriptions",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "3",
pages = "301--319",
month = jun,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Pittsburgh,
Pittsburgh, PA, USA",
keywords = "formal logic; inference; optimal descriptions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Olshansky:1977:DAC,
author = "T. Olshansky and A. Pnueli",
title = "A direct algorithm for checking equivalence of {LL(k})
grammars",
journal = j-THEOR-COMP-SCI,
volume = "4",
number = "3",
pages = "321--349",
month = jun,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Div., Tel Aviv Univ., Tel Aviv, Israel",
keywords = "branching; checking equivalence; computability and
decidability; decidable; direct algorithm; grammars;
LL(k) grammars",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Burkhard:1977:NPF,
author = "W. A. Burkhard",
title = "Non-uniform partial-match file designs",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "1",
pages = "1--23",
month = aug,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6120 (File organisation)",
corpsource = "Dept. of Appl. Phys. and Information Sci., Computer
Sci. Div., Univ. of California, San Diego, La Jolla,
CA, USA",
keywords = "associative access; average case performance; file
designs; file organisation; inversion retrieval; k
letter words; nonuniform partial match file designs;
queries; retrieval; worst case bounds",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kwong:1977:RAS,
author = "Y. S. Kwong",
title = "On reduction of asynchronous systems",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "1",
pages = "25--50",
month = aug,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., State Univ. of New York,
Albany, NY, USA",
keywords = "asynchronous systems; conceptual reduction;
instantaneous actions; interleaving; parallel
processing; programming theory; single occurrences",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Chottin:1977:SSC,
author = "L. Chottin",
title = "Syntactical study of certain language solutions of
operator equations",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "1",
pages = "51--84",
month = aug,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Univ. de Bordeaux, Talence, France",
keywords = "grammars; graph theory; operator equations; polynomial
systems; syntax; trees (mathematics)",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Engelfriet:1977:IIS,
author = "J. Engelfriet",
title = "Iterating iterated substitution",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "1",
pages = "85--100",
month = aug,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Appl. Math., Twente Univ. of Technol.,
Enschede, Netherlands",
keywords = "ETOL; formal languages; full hyper AFL; grammars;
iterating iterated substitution; regular languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Mandel:1977:FSM,
author = "A. Mandel and I. Simon",
title = "On finite semigroups of matrices",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "101--111",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4220 (Automata theory)",
corpsource = "Inst. de Matematica e Estatistica, Univ. de Sao Paulo,
Sao Paulo, Brazil",
keywords = "automata theory; automaton; finite semigroups; group
theory; matrices; matrix algebra",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Cremers:1977:FDD,
author = "A. B. Cremers and T. N. Hibbard",
title = "On the formal definition of dependencies between the
control and information structure of a data space",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "113--128",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6120
(File organisation)",
corpsource = "Abteilung Informatik, Univ. Dortmund, Dortmund, West
Germany",
keywords = "control structure; data space; data structures; data
types; dependencies; formal definition; information
structure; programming theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Latteux:1977:PRC,
author = "M. Latteux",
title = "Product in the rational cone produced by {D}\slash sub
1\slash *",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "129--134",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. de Lille, Villeneuve d'Ascq, France",
keywords = "cone; formal languages; product; rational",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Aiello:1977:PLS,
author = "L. Aiello and M. Aiello and R. W. Weyhrauch",
title = "{PASCAL} in {LCF}: semantics and examples of proof",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "135--177",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6140D
(High level languages)",
corpsource = "Istituto die Elaborazione dell'Informazione, CNR,
Pisa, Italy",
keywords = "axiomatization; correctness; LCF; PASCAL; programming
languages; programming theory; proof; proof checker;
semantics; syntax",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Galil:1977:CON,
author = "Z. Galil and N. Megiddo",
title = "Cyclic ordering is {NP-complete}",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "179--182",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Dept. of Math. Sci., Tel Aviv Univ., Tel Aviv,
Israel",
keywords = "cyclic ordering problem; elements; NP-complete; set;
set theory; triples",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Jacob:1977:ACC,
author = "G. Jacob",
title = "An algorithm for calculating the cardinal, finite or
infinite, of the semigroups of matrices",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "183--204",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4220 (Automata theory)",
corpsource = "Dept. d'Informatique, Univ. Lille I, Villeneuve
d'Ascq, France",
keywords = "cardinality; commutative field; finite automata;
finite automaton; finite set; K-automaton; matrices;
matrix semigroup",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Atkinson:1977:CGA,
author = "M. D. Atkinson",
title = "The complexity of group algebra computations",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "205--209",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4240 (Programming and algorithm
theory)",
corpsource = "Dept. of Computing Math., Univ. Coll., Cardiff, UK",
keywords = "bilinear forms; complexity; computational complexity;
cyclic group; fast finite Fourier transform; finite
group; group algebra computations; group theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Karhumaki:1977:RCN,
author = "J. Karhumaki",
title = "Remarks on commutative {N}-rational series",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "211--217",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
keywords = "commutative N-rational series; formal languages;
series (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Reutenauer:1977:QER,
author = "C. Reutenauer",
title = "On a question of {S. Eilenberg} (rational sequences)",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "2",
pages = "219--??",
month = oct,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Tue Jul 20 12:56:45 1999",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Inst. de Programmation, Univ. Pierre et Marie Curie,
Paris VI, France",
keywords = "number theory; rational coefficients; rational
sequences",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Plotkin:1977:LCP,
author = "G. D. Plotkin",
title = "{LCF} considered as a programming language",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "3",
pages = "223--255",
month = dec,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Artificial Intelligence, Univ. of Edinburgh,
Edinburgh, UK",
keywords = "denotational semantics; formal languages; LCF;
operational semantics; programming language",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Smyth:1977:EGD,
author = "M. B. Smyth",
title = "Effectively given domains",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "3",
pages = "257--274",
month = dec,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
keywords = "definition; effectively given domains; formal
languages; function space; inverse limits; powder
domain; product; recursive domain equations; set
theory; sum",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Elgot:1977:MFL,
author = "C. C. Elgot and L. Snyder",
title = "On the many facets of lists",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "3",
pages = "275--305",
month = dec,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6120
(File organisation)",
corpsource = "Math. Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
keywords = "algebraicized; data structures; LISP; lists",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ginsburg:1977:PAF,
author = "S. Ginsburg and E. H. Spanier",
title = "Pushdown acceptor forms",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "3",
pages = "307--320",
month = dec,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. of Southern California, Los Angeles, CA, USA",
keywords = "family of languages; grammars; interpretations;
pushdown acceptor",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Luckhardt:1977:FEC,
author = "H. Luckhardt",
title = "A fundamental effect in computations on real numbers",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "3",
pages = "321--324",
month = dec,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Math. Inst., Univ. Frankfurt/Main, Frankfurt/Main,
West Germany",
keywords = "computations; constructive extensional choices;
elementary constructions; fundamental effect; number
theory; real numbers; unavoidable intensionalities",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Choffrut:1977:RRC,
author = "C. Choffrut",
title = "Rational relations characterization of sequential and
subsequential functions",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "3",
pages = "325--337",
month = dec,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. de Math., Univ. Paris VII, Paris, France",
keywords = "characterization; formal languages; rational
relations; sequential functions; subsequential
functions",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Rozenberg:1977:BS,
author = "G. Rozenberg and M. Penttonen and A. Salomaa",
title = "Bibliography of {L} systems",
journal = j-THEOR-COMP-SCI,
volume = "5",
number = "3",
pages = "339--354",
month = dec,
year = "1977",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Antwerp, Antwerp, Belgium",
keywords = "formal languages; L systems",
pubcountry = "Netherlands",
treatment = "B Bibliography",
}
@Article{Cohen:1978:OCT,
author = "R. S. Cohen and A. Y. Gold",
title = "Omega-computations on {Turing} machines",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "1",
pages = "1--23",
month = feb,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., Technion, Israel Inst. of
Tech., Haifa, Israel",
keywords = "grammars; omega-grammars; omega-recognition model;
omega-sets; omega-tapes; omega-Turing acceptor models;
Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Lynch:1978:LSM,
author = "N. Lynch",
title = "Log space machines with multiple oracle tapes",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "1",
pages = "25--39",
month = feb,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "School of Information and Computer Sci., Georgia Inst.
of Technol., Atlanta, GA, USA",
keywords = "multiple oracle tapes; oracle Turing machine;
reducibilities; space bound; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Abelson:1978:TTL,
author = "H. Abelson",
title = "Towards a theory of local and global in computation",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "1",
pages = "41--67",
month = feb,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Electrical Engng. and Computer Sci., MIT,
Cambridge, MA, USA",
keywords = "complexity; computation;