%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.08",
%%% date = "08 February 2014",
%%% time = "16:54:03 MST",
%%% filename = "tcs1975.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 = "52274 5481 22185 222432",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at ieee.org (Internet)",
%%% codetable = "ISO/ASCII",
%%% keywords = "BibTeX, bibliography, Theoretical Computer
%%% Science",
%%% license = "public domain",
%%% supported = "yes",
%%% docstring = "This is a bibliography of publications in
%%% the journal Theoretical Computer Science
%%% (CODEN TCSCDI, ISSN 0304-3975 (print),
%%% 1879-2294 (electronic)), 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.08, 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,
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@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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Univ. Math. Inst., Tubingen, West Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
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",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IRIA-Lab., Rocquencourt, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder,
CO, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Div. of Math. Sci., Univ. of Iowa, Iowa City, IA,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Lab. di Cibernetica, CNR, Arco Felice, Napoli, Italy",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Univ. of Washington, Seattle, WA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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:CNC,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4290 (Other computer
theory)",
corpsource = "Dept. of Machine Intelligence, Univ. of Edinburgh,
Edinburgh, UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4230 (Switching theory)",
corpsource = "Dept. of Math., Univ. of California, Riverside, CA,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
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",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Univ. of Massachusetts, Amherst, MA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Utrecht, Utrecht,
Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Tue Jul 20 10:47:23 1999",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., Yale Univ., New Haven, CT,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "B0210 (Algebra); C1110 (Algebra)",
corpsource = "Univ. Louis Pasteur, Strasbourg, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Bell Labs., Murray Hill, NJ, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of System Sci., Univ. of California, Los
Angeles, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Fachbereich Math., Univ. Frankfurt, Frankfurt, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of System Sci., Univ. of California, Los
Angeles, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder,
CO, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C6120 (File organisation); C7250 (Information
storage and retrieval)",
corpsource = "Inst. of Math., Polish Acad. of Sci., Warsaw, Poland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C6130 (Data handling techniques)",
corpsource = "Dept. of Math., MIT, Cambridge, MA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Math., Tech. Univ. of Brno, Brno,
Czechoslovakia",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Tech. Univ. Twente, Enschede, Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Computer Sci. Program, Univ. of Southern California,
Los Angeles, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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:ITC,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights,
NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Math. Centrum, Amsterdam, Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
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",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Project MAC, MIT, Cambridge, MA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IRIA-Lab., Rocquencourt, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., State Univ. of New York,
Amherst, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Forshungsinst. fur Math., ETH, Zurich, Switzerland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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:RPR,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Pennsylvania State Univ., University Park, PA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Math. Centre, Amsterdam, Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Computer Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "UER de Math., Univ. de Picardie, Amiens, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Computing Center, Novosibirsk, USSR",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4230 (Switching theory)",
corpsource = "Jozef Stefan Inst., Ljubljana, Yugoslavia",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., Univ. of Minnesota,
Minneapolis, MN, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "closure properties; finite automata; finite automaton
with multiplication; positive rational number;
register",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Springsteel:1976:PAL,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. of Montana, Missoula, MT, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4140 (Linear
algebra); C4290 (Other computer theory)",
corpsource = "Fachbereich Math., Univ. Frankfurt, Frankfurt, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Istituto di Sci. dell'Informazione, Torino, Italy",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "calculus; characterization; hereditarily finite
permutators; inverse; lambda calculus; normal forms;
permutators",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Even:1976:CN,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Dept. Computer Sci., Technion, Haifa, Israel",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Istituto di Sci. dell'Informazione, Univ. di Torino,
Torino, Italy",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Center for Res. in Computing Technol., Harvard Univ.,
Cambridge, MA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4230 (Switching theory)",
corpsource = "Cornell Univ., Ithaca, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4230 (Switching theory)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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:PTH,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4290 (Other computer theory)",
corpsource = "Math. Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4290 (Other computer theory)",
corpsource = "Dept. of Computer Sci., Yale Univ., New Haven, CT,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4210 (Formal logic)",
corpsource = "Pennsylvania State Univ., University Park, PA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Univ. des Saarlandes, Saarbrucken, West Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Abteilung Informatik, Univ. Dortmund, Dortmund, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo,
Ont., Canada",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Information and Computer Sci., Osaka Univ.,
Toyonaka, Osaka, Japan",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4290 (Other computer theory)",
corpsource = "Computer Sci. Dept., Univ. of Kansas, Lawrence, KS,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "completeness; complexity; computational complexity;
deterministic polynomial time",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Jensen:1976:MOO,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1230 (Artificial intelligence); C4210 (Formal
logic)",
corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo,
Ont., Canada",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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:FMI,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C6120 (File organisation)",
corpsource = "Computation Centre, Polish Acad. of Sci., Warsaw,
Poland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., Cornell Univ., Ithaca, NY,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Math. Inst., Univ. of Utrecht, Utrecht, Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Univ. de Paris VII, Paris, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Sektion Math., Humboldt Univ., Berlin, East Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Inst. of Math., Univ. of Tubingen, Tubingen, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algebraic geometry; computational complexity;
multiplications/divisions; polynomials; Strassen's
degree bound; symmetric polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Szymanski:1976:CBR,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Electrical Engng. and Computer Sci.,
Princeton Univ., Princeton, NJ, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "bounded right context grammar; context free grammar;
context-free grammars",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ruohonen:1976:ZZR,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Math. Dept., Univ. of Turku, Turku, Finland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1180 (Optimisation techniques)",
corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights,
NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Electrical Engng. and Computer Sci.,
Princeton Univ., Princeton, NJ, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Computer Sci. Dept., Stanford Univ., Stanford, CA,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., Yale Univ., New Haven, CT,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Dept., Indiana Univ., Bloomington, IN,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Lab. for Computer Sci., MIT, Cambridge, MA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Dept., Edinburgh Univ., Edinburgh, UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Dept., IBM Thomas J. Watson Res. Centre,
Yorktown Heights, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4230D (Sequential switching theory)",
corpsource = "Univ. de Paris VII, Rocquencourt, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra)",
corpsource = "Dept. d'Informatique, Univ. de Paris-Sud, Orsay,
France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Information and Computer Sci., Faculty of
Engng. Sci., Osaka Univ., Toyonaka, Osaka, Japan",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computability and decidability; decidable; Petri net;
reachability sets; strong connectivity",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Markowsky:1977:CCC,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Computer Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Dept. of Math., Kyoto Univ., Kyoto, Japan",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Univ. of Michigan, Ann Arbor, MI, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Centre de Calcul du CNRS, Strasbourg, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algorithm theory; algorithms; analysis; nodes; trees;
trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Stork:1977:PCP,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6120
(File organisation)",
corpsource = "Inst. fur Informatik, Univ. Stuttgart, Stuttgart, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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:FEF,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. fur Angewandte Informatik und Formale
Beschreibungsverfahren, Univ. Karlsruhe, Karlsruhe,
West Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Tufts Univ., Medford, MA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1180 (Optimisation techniques)",
corpsource = "Center for Res. in Computing Technol., Harvard Univ.,
Cambridge, MA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "Euclidean; NP-complete; optimisation; travelling
salesman problem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Geller:1977:LKG,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Computer Sci. Div., Univ. of California, Berkeley, CA,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dept. of Computer Sci., Univ. of Kansas, Lawrence, KS,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Pittsburgh,
Pittsburgh, PA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Div., Tel Aviv Univ., Tel Aviv, Israel",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "branching; checking equivalence; computability and
decidability; decidable; direct algorithm; grammars;
LL(k) grammars",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Burkhard:1977:NUP,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
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",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., State Univ. of New York,
Albany, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Univ. de Bordeaux, Talence, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Appl. Math., Twente Univ. of Technol.,
Enschede, Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4220 (Automata theory)",
corpsource = "Inst. de Matematica e Estatistica, Univ. de Sao Paulo,
Sao Paulo, Brazil",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6120
(File organisation)",
corpsource = "Abteilung Informatik, Univ. Dortmund, Dortmund, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. de Lille, Villeneuve d'Ascq, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6140D
(High level languages)",
corpsource = "Istituto die Elaborazione dell'Informazione, CNR,
Pisa, Italy",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Dept. of Math. Sci., Tel Aviv Univ., Tel Aviv,
Israel",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4220 (Automata theory)",
corpsource = "Dept. d'Informatique, Univ. Lille I, Villeneuve
d'Ascq, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4240 (Programming and algorithm
theory)",
corpsource = "Dept. of Computing Math., Univ. Coll., Cardiff, UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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:RCR,
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Tue Jul 20 12:56:45 1999",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Inst. de Programmation, Univ. Pierre et Marie Curie,
Paris VI, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Artificial Intelligence, Univ. of Edinburgh,
Edinburgh, UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry,
UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
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",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. of Southern California, Los Angeles, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Math. Inst., Univ. Frankfurt/Main, Frankfurt/Main,
West Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. de Math., Univ. Paris VII, Paris, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Antwerp, Antwerp, Belgium",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Computer Sci., Technion, Israel Inst. of
Tech., Haifa, Israel",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "School of Information and Computer Sci., Georgia Inst.
of Technol., Atlanta, GA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
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 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Electrical Engng. and Computer Sci., MIT,
Cambridge, MA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "complexity; computation; computational complexity;
connectivity predicate; covering multiplicity; global;
local; partial computations",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Culik:1978:TSC,
author = "K. {Culik, II} and H. A. Maurer and Th. Ottmann",
title = "On two-symbol complete {E0L} Forms",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "1",
pages = "69--92",
month = feb,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo,
Ont., Canada",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "E0L Forms; formal languages; nonterminal; normal
forms; trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Johnson:1978:DHP,
author = "D. S. Johnson and F. P. Preparata",
title = "The densest hemisphere problem",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "1",
pages = "93--107",
month = feb,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Bell Labs., Murray Hill, NJ, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computational complexity; densest hemisphere problem;
Euclidean space; graph theory; NP complete problems;
polynomial time algorithm",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Manna:1978:CFF,
author = "Z. Manna and A. Shamir",
title = "The convergence of functions to fixed points of
recursive definitions",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "2",
pages = "109--141",
month = apr,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Artificial Intelligence Lab., Stanford Univ.,
Stanford, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "convergence; fixed points; functions; programming
theory; recursive definitions; recursive functions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Culik:1978:IFE,
author = "K. {Culik, II} and H. A. Maurer and Th. Ottmann and K.
Ruohonen and A. Salomaa",
title = "Isomorphism, form equivalence and sequence equivalence
of {DP0L} forms",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "2",
pages = "143--173",
month = apr,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo,
Ont., Canada",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "DP0L forms; form equivalence; grammars; isomorphic;
sequence equivalence",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Greibach:1978:OWF,
author = "S. A. Greibach",
title = "One way finite visit automata",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "2",
pages = "175--221",
month = apr,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of System Sci., Univ. of California, Los
Angeles, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "finite automata; finite visit automata;
nondeterministic; nonerasing stack automata; one way;
one working tape; preset Turing machine; Turing
machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Rackoff:1978:CBP,
author = "C. Rackoff",
title = "The covering and boundedness problems for vector
addition systems",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "2",
pages = "223--231",
month = apr,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., Univ. of Toronto, Toronto,
Ont., Canada",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "boundedness; computability and decidability;
computational complexity; covering; decision
procedures; vector addition systems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bennison:1978:SLP,
author = "V. L. Bennison and R. I. Soare",
title = "Some lowness properties and computational complexity
sequences",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "3",
pages = "233--254",
month = jun,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Math. Sci., State Univ. of New York,
Binghamton, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computational complexity; computational complexity
sequences; lowness properties; partial recursive
functions; recursive functions; recursively enumerable
sets; single fastest program",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Courcelle:1978:RTLa,
author = "B. Courcelle",
title = "A representation of trees by languages. {I}",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "3",
pages = "255--279",
month = jun,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IRIA, Domaine de Voluceau, Rocquencourt, Le Chesnay,
France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algebraic trees; context-free grammars; formal
languages; prefix free grammars; recursive program
schemes; schematic tree grammars; strict deterministic
grammars; trees; trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Knuth:1978:ELS,
author = "D. E. Knuth and A. Schonhage",
title = "The expected linearity of a simple equivalence
algorithm",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "3",
pages = "281--315",
month = jun,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Comp. Sci. Dept., Stanford Univ., Stanford, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algorithm theory; disjoint equivalence classes;
expected linearity; graph theory; random graphs; simple
equivalence algorithm",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bollman:1978:SDP,
author = "D. Bollman and M. Laplaza",
title = "Some decision problems for polynomial mappings",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "3",
pages = "317--325",
month = jun,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Math., Univ. of Puerto Rico, Mayaguez, Puerto
Rico",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "bijectivity; computability and decidability;
computational complexity; diophantine functions;
injectivity; partial recursive functions; polynomial
mappings; proper subclass; recursive functions;
surjectivity; undecidability results",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrenfeucht:1978:ELC,
author = "A. Ehrenfeucht and G. Rozenberg",
title = "{E0L} languages are not codings or {FP0L} languages",
journal = j-THEOR-COMP-SCI,
volume = "6",
number = "3",
pages = "327--341",
month = jun,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder,
CO, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "0L systems; codings; E0L languages; formal languages;
FP0L languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{deGroote:1978:VOAa,
author = "H. F. {de Groote}",
title = "On varieties of optimal algorithms for the computation
of bilinear mappings. {I}. The isotropy group of a
bilinear mapping",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "1",
pages = "1--24",
month = aug,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra)",
corpsource = "Math. Inst., Univ. Tubingen, Tubingen, West Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algorithm varieties; bilinear mapping; computation;
isotropy group; matrix algebra; optimal algorithms",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Courcelle:1978:RTLb,
author = "B. Courcelle",
title = "A representation of trees by languages. {II}",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "1",
pages = "25--55",
month = aug,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IRIA, Domaine de Voluceau, Rocquencourt, Le Chesnay,
France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "deterministic push down automata; deterministic tree
grammars; equivalence problems; formal languages;
recursive program schemes; trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Wright:1978:UAI,
author = "J. B. Wright and E. G. Wagner and J. W. Thatcher",
title = "A uniform approach to inductive posets and inductive
closure",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "1",
pages = "57--77",
month = aug,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Math. Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "formal logic; inductive closure; inductive posets",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{vanEmdeBoas:1978:SAM,
author = "P. {van Emde Boas}",
title = "Some applications of the {McCreight-Meyer} algorithm
in abstract complexity theory",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "1",
pages = "79--98",
month = aug,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1140C (Queueing theory); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Math., Univ. of Amsterdam, Amsterdam,
Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "abstract complexity theory; closure operator;
computational complexity; Honesty theorem; McCreight
Meyer algorithm; Naming theorem; priority queue;
queueing theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Verbeek:1978:DRC,
author = "R. Verbeek and K. Weihrauch",
title = "Data representation and computational complexity",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "1",
pages = "99--116",
month = aug,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Inst. fur Informatik, Univ. Bonn, Bonn, West Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computational complexity; data representation",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Mignotte:1978:IIC,
author = "M. Mignotte",
title = "Intersection of images of certain recurrent linear
series",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "1",
pages = "117--121",
month = aug,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4210 (Formal logic)",
corpsource = "Univ. Louis Pasteur, Strasbourg, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "formal languages; images intersection; language
theory; Lindenmayer systems; recurrent linear series;
series (mathematics)",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{deGroote:1978:VOAb,
author = "H. F. {de Groote}",
title = "On varieties of optimal algorithms for the computation
of bilinear mappings. {II}. Optimal algorithms for
2*2-matrix multiplication",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "2",
pages = "127--148",
month = oct,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4140 (Linear algebra)",
corpsource = "Math. Inst., Univ. Tubingen, Tubingen, West Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computation of bilinear mappings; matrix algebra;
matrix multiplication; optimal algorithms;
optimisation; varieties",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kobayashi:1978:MFT,
author = "K. Kobayashi",
title = "On the minimal firing time of the firing squad
synchronization problem for polyautomata networks",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "2",
pages = "149--167",
month = oct,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Information Sci., Tokyo Inst. of Technol.,
Tokyo, Japan",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "finite automata; finite automaton; firing squad
synchronisation problem; minimal firing time;
polyautomata networks",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrenfeucht:1978:EHS,
author = "A. Ehrenfeucht and G. Rozenberg",
title = "Elementary homomorphisms and a solution of the {D0L}
sequence equivalence problem",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "2",
pages = "169--183",
month = oct,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder,
CO, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computability and decidability; D0L sequence
equivalence problem; decidable; elementary D0L systems;
formal languages; homomorphisms",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Book:1978:LSR,
author = "R. V. Book and C. Wrathall",
title = "On languages specified by relative acceptance",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "2",
pages = "185--195",
month = oct,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Math. and Computer Sci. Program, Univ. of
California, Santa Barbara, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "EXRUD(A); formal languages; languages;
nondeterministic oracle machines; polynomial time;
relative acceptance; specified; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Perrot:1978:VLO,
author = "J.-F. Perrot",
title = "Varieties of languages and operations",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "2",
pages = "197--210",
month = oct,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. de Programmation, Univ. Paris, Paris, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "concatenation; formal languages; Kleene's star
operation; rational languages; shuffle product;
varieties",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Pin:1978:SMW,
author = "J. E. Pin",
title = "On the syntactic monoid of {L}* where {L} is a finite
language",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "2",
pages = "211--215",
month = oct,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "CNRS, Paris, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "finite language; formal languages; full finite prefix
code; rational languages; star operation; syntactic
monoid",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Muller:1978:FIT,
author = "D. E. Muller and F. P. Preparata",
title = "Finding the intersection of two convex polyhedra",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "2",
pages = "217--236",
month = oct,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Coordinated Sci. Lab., Univ. of Illinois, Urbana, IL,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "convex hull; geometric duals; intersection; three
dimensional space; topology; two convex polyhedra",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{deGroote:1978:VOAc,
author = "H. F. {de Groote}",
title = "On varieties of optimal algorithms for the computation
of bilinear mappings. {III}. Optimal algorithms for the
computation of $xy$ and $yx$ where $x,y$ in
{$M_2(K)$}",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "3",
pages = "239--249",
month = dec,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C1180 (Optimisation techniques);
C4240 (Programming and algorithm theory)",
corpsource = "Math. Inst., Univ. Tubingen, Tubingen, West Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algorithm theory; bilinear mappings; equivalence
classes; field K; matrix algebra; optimal algorithms;
optimisation",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Schnorr:1978:ILB,
author = "C. P. Schnorr",
title = "Improved lower bounds on the number of
multiplications\slash divisions which are necessary to
evaluate polynomials",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "3",
pages = "251--261",
month = dec,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4140 (Linear algebra); C5230 (Digital arithmetic
methods)",
corpsource = "Fachbereich Math., Univ. Frankfurt, Frankfurt, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "digital arithmetic; evaluation;
multiplications/divisions; polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Skyum:1978:GEF,
author = "S. Skyum",
title = "On good {ET0L} forms",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "3",
pages = "263--272",
month = dec,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Aarhus, Aarhus,
Denmark",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "ET0L forms; formal languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hartmanis:1978:LTI,
author = "J. Hartmanis",
title = "On log-tape isomorphisms of complete sets",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "3",
pages = "273--286",
month = dec,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Computer Sci., Cornell Univ., Ithaca, NY,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "complete sets; computational complexity; CSL; formal
languages; isomorphisms; log n-tape computable
reductions; log tape isomorphisms; NL; NP; polynomial
time computable reductions; PTAPE; single letter
alphabet",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ibarra:1978:TWS,
author = "O. H. Ibarra",
title = "On two-way sequential transductions of full
{semi-AFLs}",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "3",
pages = "287--309",
month = dec,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Minnesota,
Minneapolis, MN, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "finite substitutions; formal languages; grammars;
homomorphisms; languages; parallel rewriting systems;
semi AFL; sequential transductions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Greibach:1978:RBP,
author = "S. A. Greibach",
title = "Remarks on blind and partially blind one-way
multicounter machines",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "3",
pages = "311--324",
month = dec,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory); C5230
(Digital arithmetic methods)",
corpsource = "Dept. of System Sci., Univ. of California, Los
Angeles, CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "automata theory; digital arithmetic; Dyck set; formal
languages; languages; least intersection closed
semiAFL; nondeterministic machines; partially blind
multicounter machines; Petri net languages;
quasirealtime",
pubcountry = "Netherlands",
}
@Article{Kleiman:1978:ECS,
author = "M. Kleiman and N. Pippenger",
title = "An explicit construction of short monotone formulae
for the monotone symmetric functions",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "3",
pages = "325--332",
month = dec,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4210 (Formal logic)",
corpsource = "Math. Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "Boolean functions; combinatorial logic; combinatorial
mathematics; conjunction; disjunction; formal logic;
functions; monotone symmetric functions; short monotone
formulae",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Friedman:1978:NNS,
author = "E. P. Friedman",
title = "A note on non-singular deterministic pushdown
automata",
journal = j-THEOR-COMP-SCI,
volume = "7",
number = "3",
pages = "333--339",
month = dec,
year = "1978",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Computer Sci. Dept., Univ. of California, Los Angeles,
CA, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "automata theory; deterministic pushdown automata;
Valiant's equivalence decision procedure",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Soisalon-Soininen:1979:CPL,
author = "E. Soisalon-Soininen",
title = "On the covering problem for left-recursive grammars",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "1",
pages = "1--11",
month = feb,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Helsinki, Helsinki,
Finland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "covering problem; grammars; left recursion",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Wand:1979:FPC,
author = "M. Wand",
title = "Fixed-point constructions in order-enriched
categories",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "1",
pages = "13--30",
month = feb,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic); C6120 (File organisation)",
corpsource = "Computer Sci. Dept., Indiana Univ., Bloomington, IN,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "categories; continuous lattice; data structures; fixed
point construction; partial ordering; set theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bibel:1979:TTG,
author = "W. Bibel",
title = "Tautology testing with a generalised matrix reduction
method",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "1",
pages = "31--44",
month = feb,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1230 (Artificial intelligence); C4210 (Formal
logic)",
corpsource = "Inst. fur Informatik, Tech. Univ., Munchen, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "formal logic; generalised matrix reduction; matrix
algebra; Presburger arithmetic; propositional logic;
tautology; testing; theorem proving",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Preparata:1979:FIH,
author = "F. P. Preparata and D. E. Muller",
title = "Finding the intersection of n half-spaces in time
{O}(n log n)",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "1",
pages = "45--55",
month = feb,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Coordinated Sci. Lab., Univ. of Illinois, Urbana, IL,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algorithm; half spaces; intersection; three
dimensional space; time; topology",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Johansen:1979:GFN,
author = "P. Johansen",
title = "The generating function of the number of subpatterns
of a {D0L} sequence",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "1",
pages = "57--68",
month = feb,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Datalogisk Inst., Kobenhavns Univ., Kobenhavn,
Denmark",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algorithm theory; D0L sequence; formal languages;
generating function; number of subpatterns",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hashiguchi:1979:DPO,
author = "K. Hashiguchi",
title = "A decision procedure for the order of regular events",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "1",
pages = "69--72",
month = feb,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Res. Inst. of Electrical Communication, Tohoku Univ.,
Sendai, Japan",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "decision procedure; finite alphabet; formal languages;
order; regular events",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Apt:1979:RAE,
author = "K. R. Apt and J. A. Bergstra and L. G. L. T.
Meertens",
title = "Recursive assertions are not enough-or are they?",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "1",
pages = "73--87",
month = feb,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Math. Centre, Amsterdam, Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "complete; programming theory; recursive assertions;
while programs",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Majster:1979:DTA,
author = "M. E. Majster",
title = "Data types, abstract data types and their
specification problem",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "1",
pages = "89--127",
month = feb,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C6120 (File organisation)",
corpsource = "Inst. fur Informatik, Tech. Univ., Munchen, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "abstract data types; algebraic properties; data
structures; data type; specification",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hopcroft:1979:RPD,
author = "J. Hopcroft and J.-J. Pansiot",
title = "On the reachability problem for $5$-dimensional vector
addition systems",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "135--159",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Dept., Cornell Univ., Ithaca, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computability and decidability; computable semilinear
sets; containment; decidable; equivalence;
reachability; vector addition systems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Prodinger:1979:LOR,
author = "H. Prodinger and F. J. Urbanek",
title = "Language operators related to Init",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "161--175",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. fur Math. Logik und Formale Sprachen, Tech.
Univ. Wien, Wien, Austria",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "Anf; formal languages; Init; language operator",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Baker:1979:SST,
author = "T. P. Baker and A. L. Selman",
title = "A second step toward the polynomial hierarchy",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "177--187",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Dept., Univ. of Iowa, Iowa City, IA,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "formal language; formal languages; polynomial
hierarchy; recursive oracle",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Valiant:1979:CCP,
author = "L. G. Valiant",
title = "The complexity of computing the permanent",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "189--201",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4140 (Linear algebra); C4290 (Other computer
theory)",
corpsource = "Computer Sci. Dept., Univ. of Edinburgh, Edinburgh,
UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "arithmetic; complexity; computational complexity;
counting problems; matrices; matrix algebra;
nondeterministic polynomial time computations;
permanent function",
pubcountry = "Netherlands",
}
@Article{Pudlak:1979:CMH,
author = "P. Pudlak and F. N. Springsteel",
title = "Complexity in mechanized hypothesis formation",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "203--225",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Math. Inst., Czechoslovak Acad. of Sci., Prague,
Czechoslovakia",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algorithmic complexity; computability; computability
and decidability; computational complexity; formal
logic; GUHA; mechanized hypothesis formation; sampled
data",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hajek:1979:AHC,
author = "P. Hajek",
title = "Arithmetical hierarchy and complexity of computation",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "227--237",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Math. Inst., CSAV, Prague, Czechoslovakia",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "arithmetical hierarchy; complete; computational
complexity; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hartmanis:1979:RBD,
author = "J. Hartmanis",
title = "Relations between diagonalization, proof systems, and
complexity gaps",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "239--253",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Computer Sci. Dept., Cornell Univ., Ithaca, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "complexity gaps; computational complexity;
diagonalization; proof systems; time bounded
computations; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Morgenstern:1979:EWT,
author = "J. Morgenstern",
title = "An extension of {Winograd}'s theorem",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "255--259",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. de Math., Univ. de Nice, Parc Valrose, Nice,
France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computational complexity; extension; Winograd's
theorem",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Arnold:1979:NPT,
author = "A. Arnold and M. Latteux",
title = "A new proof of two theorems about rational
transductions",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "2",
pages = "261--263",
month = apr,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. de Lille I, Villeneuve d'Ascq, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "decomposition; formal languages; language theory;
rational transductions; theorems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bohm:1979:DAI,
author = "C. Bohm and M. Dezani-Ciancaglini and P. Peretti and
S. R. D. Rocca",
title = "A discrimination algorithm inside
$\lambda$-$\beta$-calculus",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "3",
pages = "271--291",
month = jun,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Istituto Matematico G. Castelnuovo, Univ. di Rome,
Rome, Italy",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "discrimination algorithm; finite set; formal logic;
lambda beta calculus; normal combinators",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Beauquier:1979:AGS,
author = "J. Beauquier",
title = "Algebraic generation and systems of iterative pairs",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "3",
pages = "293--323",
month = jun,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. de Programmation, Paris, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "context free languages; context-free languages; image
language; iterative pairs; rational transduction;
source language; transfer theorem",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Elgot:1979:SMC,
author = "C. C. Elgot and J. C. Shepherdson",
title = "A semantically meaningful characterization of
reducible flowchart schemes",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "3",
pages = "325--357",
month = jun,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Math. Sci. Dept., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "flowgraph; formal logic; homomorphism; programming
theory; reducible flowchart schemes; semantically
meaningful characterization",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Winograd:1979:MAE,
author = "S. Winograd",
title = "On multiplication in algebraic extension fields",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "3",
pages = "359--377",
month = jun,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4140 (Linear algebra)",
corpsource = "IBM T.J. Watson Res. Center, Yorktown Heights, NY,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algebraic extension fields; Chinese remainder theorem;
irreducible polynomial; multiplication; polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Dolev:1979:CPG,
author = "D. Dolev",
title = "Commutation properties and generating sets
characterize slices of various synchronization
primitives",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "3",
pages = "379--391",
month = jun,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Appl. Math., Weizmann Inst. of Sci., Rehovot,
Israel",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "commutation property; integer vectors; Petri nets;
programming theory; synchronization primitives; vector
replacement systems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hindley:1979:DTH,
author = "R. Hindley",
title = "The discrimination theorem holds for combinatory weak
reduction",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "3",
pages = "393--394",
month = jun,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. Coll. of Swansea, Swansea, UK",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "combinatory weak reduction; discrimination theorem;
formal logic",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Autebert:1979:NCD,
author = "J.-M. Autebert",
title = "A note on the cylinder of deterministic languages",
journal = j-THEOR-COMP-SCI,
volume = "8",
number = "3",
pages = "395--399",
month = jun,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. de Programmation, Univ. Paris VI, Paris,
France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "context free languages; context-free languages;
deterministic language family; embedded cylinders",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Plaisted:1979:FVT,
author = "D. A. Plaisted",
title = "Fast verification, testing, and generation of large
primes",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "1--16",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C5230 (Digital arithmetic methods)",
corpsource = "Dept. of Computer Sci., Univ. of Illinois, Urbana, IL,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algorithm; fast verification; generation; large
primes; number theory; primality; short certificates;
stochastic method; testing",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Duval:1979:RBG,
author = "J.-P. Duval",
title = "Relationship between global periodicity and
repetitions of words",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "17--26",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4290 (Other computer theory)",
corpsource = "Lab. d'Informatique, Faculte des Sci., Univ. de Rouen,
Mont Saint Aignan, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computational linguistics; global periodicity;
repetitions; word",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bergstra:1979:CRS,
author = "J. Bergstra and J. W. Klop",
title = "{Church--Rosser} strategies in the lambda calculus",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "27--38",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Math. Inst., Wassenaarseweg, Leiden, Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "Church Rosser strategies; lambda calculus; one step
reduction method; trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Guessarian:1979:PTA,
author = "I. Guessarian",
title = "Program transformations and algebraic semantics",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "39--65",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "UER de Math., Univ. de Paris, Paris, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algebraic semantics; optimization algorithm;
programming theory; recursive program schemes;
transformations",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Statman:1979:IPL,
author = "R. Statman",
title = "Intuitionistic propositional logic is polynomial-space
complete",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "67--72",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Philosophy, Univ. of Michigan, Ann Arbor, MI,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "formal logic; intuitionistic propositional logic;
polynomial space",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Statman:1979:TCE,
author = "R. Statman",
title = "The typed $\lambda$-calculus is not elementary
recursive",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "73--81",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Philosophy, Univ. of Michigan, Ann Arbor, MI,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "elementary recursive; formal logic; lambda calculus",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Wegener:1979:SFW,
author = "I. Wegener",
title = "Switching functions whose monotone complexity is
nearly quadratic",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "83--97",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4230 (Switching theory); C4240 (Programming and
algorithm theory)",
corpsource = "Fakultat fur Math., Univ. Bielefeld, Bielefeld, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "complexity; computational complexity; monotone
switching functions; nearly quadratic; switching
functions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Flajolet:1979:NRR,
author = "P. Flajolet and J. C. Raoult and J. Vuillemin",
title = "The number of registers required for evaluating
arithmetic expressions",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "99--125",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Iria-Lab., Rocquencourt, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "arithmetic expressions; binary trees; distribution;
enumeration results; evaluating; parameter; registers;
trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Wechsung:1979:RBS,
author = "G. Wechsung and A. Brandstadt",
title = "A relation between space, return and dual return
complexities",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "127--140",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Sektion Math., Friedrich-Schiller-Univ. Jena, Jena,
East Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "auxiliary pushdown tape; complexities; complexity
classes; computational complexity; dual return;
identity function; nondeterministic Turing machines;
resource functions; return; space; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Christol:1979:ARP,
author = "G. Christol",
title = "Almost $k$-recognisable periodic sets",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "141--145",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Univ. Paris, Paris, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "automata; automata theory; k basis integral numbers;
periodic sets",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Wegener:1979:CCS,
author = "I. Wegener",
title = "A counterexample to a conjecture of {Schnorr}
referring to monotone networks",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "1",
pages = "147--150",
month = jul,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4130 (Interpolation and function approximation);
C4230 (Switching theory)",
corpsource = "Fakultat fur Math., Univ. Bielefeld, Bielefeld, West
Germany",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "Boolean functions; monotone computations; monotone
networks; polynomials; rational polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Tang:1979:CPP,
author = "A. Tang",
title = "Chain properties in {P} omega",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "153--172",
month = aug,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. EECS, Princeton Univ., Princeton, NJ, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "chain properties; data types; formal languages;
partially ordered sets; Pomega; programming languages;
set theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Harrison:1979:EGT,
author = "M. A. Harrison and I. M. Havel and A. Yehudai",
title = "On equivalence of grammars through transformation
trees",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "173--205",
month = aug,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Computer Sci. Div., Univ. of California, Berkeley, CA,
USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computability and decidability; context free
languages; context-free grammars; decidability;
equivalence problem; grammars; transformation trees",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Karhumaki:1979:CDS,
author = "J. Karhumaki",
title = "On commutative {DT0L} systems",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "207--220",
month = aug,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Turku, Turku, Finland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "commutative DT0L systems; composite numbers;
computability and decidability; formal languages;
languages; length sets; undecidability results; word",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Perrin:1979:ERF,
author = "D. Perrin",
title = "The ergodic representation of finite automata",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "221--241",
month = aug,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. de Math., Univ. de Haute Normandie, Mont
Saint-Aignan, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "ergodic representation; finite automata; finite
languages; formal languages; Schutzenberger matrix
representation",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ashcroft:1979:GSF,
author = "E. A. Ashcroft and F. E. Fich",
title = "A generalized setting for fixpoint theory",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "243--256",
month = aug,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo,
Ont., Canada",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "fixpoint theory; formal languages; mathematical
semantics; programming languages; recursive definitions
of functions; unique minimal solutions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bloom:1979:AGT,
author = "S. L. Bloom and R. Tendell",
title = "Algebraic and graph theoretic characterizations of
structured flowchart schemes",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "265--286",
month = oct,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C6110 (Systems
analysis and programming)",
corpsource = "Dept. of Pure and Appl. Math., Stevens Inst. of
Technol., Hoboken, NJ, USA",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "algebraic characterisations; Dijkstra schemes; Elgot's
CACI; flowcharting; graph theoretic characterizations;
graph theory; reducible schemes; structured flowchart",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Nijholt:1979:SCG,
author = "A. Nijholt",
title = "Simple chain grammars and languages",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "287--309",
month = oct,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Vrije Univ., Amsterdam, Netherlands",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "chain grammars; deterministic pushdown transducer;
grammars; languages; LL(1) grammars; LR(0) grammars;
parser",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Inoue:1979:OWS,
author = "K. Inoue and I. Takanami and A. Nakamura and T. Ae",
title = "One-way simple multihead finite automata",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "311--328",
month = oct,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Electronics, Yamaguchi Univ., Ube, Japan",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "accepting powers; closure properties; finite automata;
languages; multihead finite automata; Turing
computations",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Aubin:1979:MSIa,
author = "R. Aubin",
title = "Mechanizing structural induction. {I}. Formal system",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "329--346",
month = oct,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Computer Sci., Concordia Univ., Montreal,
Que., Canada",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "automating mildly complex proofs; induction rule;
lexicographic ordering; program proving; programming
theory; structural induction; typed language",
pubcountry = "Netherlands",
treatment = "P Practical",
}
@Article{Aubin:1979:MSIb,
author = "R. Aubin",
title = "Mechanizing structural induction. {II}. Strategies",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "347--362",
month = oct,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C1230 (Artificial intelligence); C4240 (Programming
and algorithm theory)",
corpsource = "Dept. of Computer Sci., Concordia Univ., Montreal,
Que., Canada",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "fast simplification algorithm; formal language;
hypotheses; induction strategy; mildly complex proofs;
number theory; programming theory; structural
induction; theorem proving",
pubcountry = "Netherlands",
treatment = "P Practical",
}
@Article{Reutenauer:1979:ASC,
author = "C. Reutenauer",
title = "On the associated series to certain {Lindenmayer}
systems",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "363--375",
month = oct,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. de Programmation, Univ. Pierre et Marie Curie,
Paris, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "D0L languages; DT0L languages; formal languages;
Lindenmayer systems",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ruohonen:1979:SDP,
author = "K. Ruohonen",
title = "On some decidability problems for {HD0L} systems with
nonsingular {Parikh} matrices",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "377--384",
month = oct,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Math. Dept., Univ. of Turku, Turku, Finland",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "computability and decidability; decidability problems;
effective findability; equivalence problem; formal
languages; generating morphisms; HD0L systems;
nonsingular Parikh matrices; zeros",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Rodriguez:1979:FCL,
author = "F. Rodriguez",
title = "Families of closed languages by open brackets",
journal = j-THEOR-COMP-SCI,
volume = "9",
number = "2",
pages = "385--398",
month = oct,
year = "1979",
CODEN = "TCSCDI",
ISSN = "0304-3975 (print), 1879-2294 (electronic)",
ISSN-L = "0304-3975",
bibdate = "Sat Nov 22 13:36:07 MST 1997",
bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1975.bib",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. Paul. Sabatier, Toulouse, France",
fjournal = "Theoretical Computer Science",
journal-URL = "http://www.sciencedirect.com/science/journal/03043975/",
keywords = "automata languages; closed languages; formal
languages; open brackets; unary operator",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}