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