%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.05", %%% date = "07 October 1999", %%% time = "12:44:44 MDT", %%% filename = "tcs1980.bib", %%% address = "Center for Scientific Computing %%% University of Utah %%% Department of Mathematics, 322 INSCC %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 585 1640, +1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "54356 11264 46065 431825", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at ieee.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "BibTeX, bibliography, Theoretical Computer %%% Science", %%% supported = "yes", %%% docstring = "This is a bibliography of publications in %%% the journal Theoretical Computer Science %%% (CODEN TCSCDI, ISSN 0304-3975), which %%% began publishing in 1975. %%% %%% This file covers the years 1980--1984; %%% 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.05, the year coverage looked %%% like this: %%% %%% 1980 ( 66) 1982 ( 87) 1984 (123) %%% 1981 ( 72) 1983 (108) %%% %%% Article: 456 %%% %%% Total entries: 456 %%% %%% This bibliography was prepared by merging %%% data from the TeX Users Group bibliography %%% archive, the BibNet Project archive, the OCLC %%% Contents1st database, the Compendex database, %%% and the IEEE INSPEC database. %%% %%% Numerous errors in the sources noted above %%% have been corrected. Spelling has been %%% verified with the UNIX spell and GNU ispell %%% programs using the exception dictionary %%% stored in the companion file with extension %%% .sok. %%% %%% BibTeX citation tags are uniformly chosen %%% as name:year:abbrev, where name is the %%% family name of the first author or editor, %%% year is a 4-digit number, and abbrev is a %%% 3-letter condensation of important title %%% words. Citation tags were automatically %%% generated by software developed for the %%% BibNet Project. %%% %%% In this bibliography, entries are sorted in %%% publication order within each journal, %%% using bibsort -byvolume. %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== @Preamble{"\hyphenation{ Bai-er He-ma-chan-dra Ko-ba-ya-shi Kri-zanc Lett-mann Mal-u-szyn-ski Mar-chet-ti Mar-u-o-ka Och-man-ski Pal-a-mi-des-si Piet-rzy-kow-ski Pros-ku-row-ski Pu-ru-sho-tha-man Ros-en-krantz Spor-tel-li Sturt-i-vant Ta-ka-da Vau-zeilles Win-kow-ski Win-skel to-po-log-ique }"} %======================================================================= % Acknowledgement abbreviations: @String{ack-nhfb = "Nelson H. F. Beebe, Center for Scientific Computing, University of Utah, Department of Mathematics, 322 INSCC, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 585 1640, +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@ieee.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %======================================================================= % Journal abbreviations: @String{j-THEOR-COMP-SCI = "Theoretical Computer Science"} %======================================================================= % Bibliography entries, sorted in publication order: @Article{Schnorr:1980:ACP, author = "C. P. Schnorr and J. P. {Van de Wiele}", title = "On the additive complexity of polynomials", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "1--18", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4130 (Interpolation and function approximation); C4240 (Programming and algorithm theory)", corpsource = "Fachbereich Math., Univ. Frankfurt, Frankfurt, West Germany", keywords = "additive complexity; algebraically independent coefficients; computational complexity; lower bounds; polynomials", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Brzozowski:1980:ERL, author = "J. A. Brzozowski and E. Leiss", title = "On equations for regular languages, finite automata, and sequential networks", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "19--35", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo, Ont., Canada", keywords = "Boolean automaton; Boolean functions; empty set; empty word; finite automata; formal languages; nondeterministic automaton; regular languages; sequential networks; underlying alphabet", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kurka:1980:APC, author = "P. Kurka", title = "Applicability of a production in a categorical grammar", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "37--44", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Center of Biomath., Acad. of Sci., Praha, Czechoslovakia", keywords = "categorical grammar; grammars; production; topological condition", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ehrenfeucht:1980:ETE, author = "A. Ehrenfeucht and G. Rozenberg", title = "Every two equivalent {D0L} systems have a regular true envelope", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "45--52", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder, CO, USA", keywords = "equivalent D0L systems; formal languages; regular true envelope", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hartmann:1980:MCS, author = "W. Hartmann and P. Schuster", title = "Multiplicative complexity of some rational functions", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "53--61", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4130 (Interpolation and function approximation); C4240 (Programming and algorithm theory)", corpsource = "Seminar fur Angewandte Math., Univ. Zurich, Zurich, Switzerland", keywords = "compositions; computational complexity; continued fractions; multiplicative complexity; polynomials; products; quotients; rational functions; sharp bounds; Strassen's theorem; substitution method", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Zaks:1980:LGO, author = "S. Zaks", title = "Lexicographic generation of ordered trees", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "63--82", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Univ. of Illinois, Urbana, IL, USA", keywords = "formal logic; generating algorithm; internal nodes; lexicographic generation; ordered trees; ranking function; regular binary trees; trees (mathematics); unranking procedure", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Schnorr:1980:BNC, author = "C. P. Schnorr", title = "A $3n$-lower bound on the network complexity of {Boolean} functions", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "83--92", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Fachbereich Math., Univ. Frankfurt, Frankfurt, West Germany", keywords = "3n lower bound; Boolean functions; computational complexity; network complexity", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Biskup:1980:IMD, author = "J. Biskup", title = "Inferences of multivalued dependencies in fixed and undetermined universes", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "93--105", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C6160D (Relational databases)", corpsource = "Lehrstuhl fur Angewandte Mathematik, Tech. Hochschule Aachen, Aachen, West Germany", keywords = "complementation rule; completeness; database management systems; database relations; DBMS; fixed universes; formal logic; inference rules; multivalued dependencies; subset rule; undetermined universes", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Prodinger:1980:ID, author = "H. Prodinger", title = "On the interpolation of {D0L-sequences}", journal = j-THEOR-COMP-SCI, volume = "10", number = "1", pages = "107--108", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Inst. fur Math. Logik und Formale Sprachen, Tech. Univ Wien, Wien, Austria", keywords = "D0L sequences; formal languages; interpolation", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Fortune:1980:DSH, author = "S. Fortune and J. Hopcroft and J. Wyllie", title = "The directed subgraph homeomorphism problem", journal = j-THEOR-COMP-SCI, volume = "10", number = "2", pages = "111--121", month = feb, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Cornell Univ., Ithaca, NY, USA", keywords = "directed acyclic graph; directed graphs; directed subgraph homeomorphism problem; NP completeness; pattern graphs; polynomial time algorithm", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Lieberherr:1980:PH, author = "K. Lieberherr", title = "{P}-optimal heuristics", journal = j-THEOR-COMP-SCI, volume = "10", number = "2", pages = "123--131", month = feb, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1180 (Optimisation techniques)", corpsource = "Dept. of Math., Florida State Univ., Tallahassee, FL, USA", keywords = "invariant problem; linear inequalities; optimal solution; optimisation; P-optimal heuristics; transformations", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Wiedmer:1980:CIO, author = "E. Wiedmer", title = "Computing with infinite objects", journal = j-THEOR-COMP-SCI, volume = "10", number = "2", pages = "133--155", month = feb, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Abteilung fuer Forschung und Studien, Hasler AG, Bern, Switzerland", keywords = "computability; computability and decidability; computable function; infinite length; infinite objects; parallel processes; real numbers; topology", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{deLuca:1980:SPV, author = "A. {de Luca} and A. Restivo", title = "On some properties of very pure codes", journal = j-THEOR-COMP-SCI, volume = "10", number = "2", pages = "157--170", month = feb, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B6120B (Codes)", corpsource = "Lab. di Cibernetica, CNR, Naples, Italy", keywords = "codes; maximality; synchronization; very pure codes", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Staples:1980:CGE, author = "J. Staples", title = "Computation on graph-like expressions", journal = j-THEOR-COMP-SCI, volume = "10", number = "2", pages = "171--185", month = feb, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Math. and Computer Sci., Queensland Inst. of Technol., Brisbane, Qld., Australia", keywords = "commutativity; computational steps; graph theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Havel:1980:BL, author = "I. M. Havel", title = "On branching and looping. {I}", journal = j-THEOR-COMP-SCI, volume = "10", number = "2", pages = "187--220", month = feb, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Acad. of Sci., Prague, Czechoslovakia", keywords = "branching; discrete processes; finite branching automata; formal languages; languages; looping", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kozen:1980:CBA, author = "D. Kozen", title = "Complexity of {Boolean} algebras", journal = j-THEOR-COMP-SCI, volume = "10", number = "3", pages = "221--247", month = mar, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "automata theory; Berman complexity class; Boolean algebra; Boolean algebras; computational complexity; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Cohen:1980:COT, author = "R. Cohen and A. Gold", title = "On the complexity of omega-type {Turing} acceptors", journal = j-THEOR-COMP-SCI, volume = "10", number = "3", pages = "249--272", month = mar, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Dept. of Computer Sci., Univ. of Toronto, Toronto, Ont., Canada", keywords = "complexity; Turing acceptors; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Havel:1980:BLI, author = "I. M. Havel", title = "On branching and looping. {II}", journal = j-THEOR-COMP-SCI, volume = "10", number = "3", pages = "273--295", month = mar, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Acad. of Sci., Prague, Czechoslovakia", keywords = "branching; finite automata; finite branching automation; looping", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Staples:1980:OEG, author = "J. Staples", title = "Optimal evaluation of graph-like expressions", journal = j-THEOR-COMP-SCI, volume = "10", number = "3", pages = "297--316", month = mar, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Math. and Computer Sci., Queensland Inst. of Technol., Brisbane, Qld., Australia", keywords = "evaluation algorithm; formal logic; graph like expressions; graph theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{King:1980:ITF, author = "K. N. King", title = "Iteration theorems for families of strict deterministic languages", journal = j-THEOR-COMP-SCI, volume = "10", number = "3", pages = "317--333", month = mar, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Electrical Engng. and Computer Sci., Univ. of California, Berkeley, CA, USA", keywords = "deterministic languages; formal languages; iteration theorems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Dobkin:1980:CLP, author = "D. P. Dobkin and S. P. Reiss", title = "The complexity of linear programming", journal = j-THEOR-COMP-SCI, volume = "11", number = "1", pages = "1--18", month = may, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1180 (Optimisation techniques); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer Sci., Univ. of Arizona, Tucson, AZ, USA", keywords = "complexity; computational complexity; convex hulls of polytopes; linear programming; LP completeness", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Staples:1980:SSR, author = "J. Staples", title = "Speeding up subtree replacement systems", journal = j-THEOR-COMP-SCI, volume = "11", number = "1", pages = "39--47", month = may, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Dept. of Math. and Computer Sci., Queensland Inst. of Technol., Brisbane, Qld., Australia", keywords = "correctness; graph like expressions; graph theory; optimal evaluation algorithms; subtree replacement systems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Berman:1980:CLT, author = "L. Berman", title = "The complexity of logical theories", journal = j-THEOR-COMP-SCI, volume = "11", number = "1", pages = "71--77", month = may, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Computer Sci., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "alternating TM; complexity; computational complexity; decision procedures; decision theory and analysis; Ehrenfencht games; encoding; formal logic; logical theories", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kucera:1980:CDT, author = "L. Kucera and J. Nesetril and A. Pultr", title = "Complexity of dimension three and some related edge-covering characteristics of graphs", journal = j-THEOR-COMP-SCI, volume = "11", number = "1", pages = "93--106", month = may, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", corpsource = "Charles Univ., Prague, Czechoslovakia", keywords = "computational complexity; dimension three; edge covering characteristics; graph theory; graphs; NP completeness; polynomial time", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hotz:1980:NIC, author = "G. Hotz", title = "A new invariant for context free languages", journal = j-THEOR-COMP-SCI, volume = "11", number = "1", pages = "107--116", month = may, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Fachbereich Math. und Informatik, Univ. des Saarlandes, Saarbrucken, West Germany", keywords = "context free grammars; context free languages; context-free grammars; context-free languages; grammar", language = "German", pubcountry = "Netherlands", treatment = "N New Development; T Theoretical or Mathematical", } @Article{Harary:1980:GTM, author = "F. Harary", title = "Graph theoretic models", journal = j-THEOR-COMP-SCI, volume = "11", number = "2", pages = "117--121", month = jun, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Dept. of Math., Univ. of Michigan, Ann Arbor, MI, USA", keywords = "graph theoretic models; graph theory", pubcountry = "Netherlands", treatment = "G General Review", } @Article{Borger:1980:RPP, author = "E. Borger and H. {Kleine Buning}", title = "The reachability problem for {Petri} nets and decision problems for {Skolem} arithmetic", journal = j-THEOR-COMP-SCI, volume = "11", number = "2", pages = "123--143", month = jun, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Tue Jul 20 12:57:21 1999", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Lehrstuhl Informatik II, Univ. Dortmund, Dortmund, West Germany", keywords = "binary disjunctions; decision problems; formal logic; graph theory; Horn formulae; monadic predicate symbols; Petri nets; prenex conjunctive normal form; quantifier free matrix; reachability problem; Skolem arithmetic", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Rosenberg:1980:UDE, author = "A. L. Rosenberg and L. J. Stockmeyer and L. Snyder", title = "Uniform data encodings", journal = j-THEOR-COMP-SCI, volume = "11", number = "2", pages = "145--165", month = jun, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C6120 (File organisation); C6130 (Data handling techniques)", corpsource = "Math. Sci. Dept., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "data encodings; data structure; data structures; edge dilation; edge labelled graphs; encoding; graph theory; nonpolynomial; vertices", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Beynon:1980:SFF, author = "W. M. Beynon", title = "On the structure of free finite state machines", journal = j-THEOR-COMP-SCI, volume = "11", number = "2", pages = "167--180", month = jun, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Dept. of Computer Sci., Univ. of Warwick, Coventry, UK", keywords = "Abelian groups; disjoint copies; finite automata; finite semigroups; free finite state machines; necessary and sufficient conditions; transition monoid machine; universal presentation", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Arnold:1980:MII, author = "A. Arnold and M. Nivat", title = "Metric interpretations of infinite trees and semantics of nondeterministic recursive programs", journal = j-THEOR-COMP-SCI, volume = "11", number = "2", pages = "181--205", month = jun, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Lab. d'Informatique, Univ. de Poitiers, Poitiers, France", keywords = "infinite computations; infinite trees; non deterministic recursive programs; programming theory; semantics; trees (mathematics)", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Bougaut:1980:EAP, author = "B. Bougaut", title = "An explicit algorithm for {PGCD} research in certain principal rings between groups of numbers", journal = j-THEOR-COMP-SCI, volume = "11", number = "2", pages = "207--220", month = jun, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Inst. Nat. des Sci. Appl., Rennes, France", keywords = "computation; division algorithm; Euclid algorithm; group theory; integers; number fields; rings", language = "French", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hennessy:1980:MSN, author = "M. C. B. Hennessy and E. A. Ashcroft", title = "A mathematical semantics for a nondeterministic typed lambda -calculus", journal = j-THEOR-COMP-SCI, volume = "11", number = "3", pages = "227--245", month = jul, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Univ. Federal de Pernambuco, Pernambuco, Brazil", keywords = "deterministic language; formal languages; lambda calculus; mathematical semantics; nondeterministic algorithms", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ehrig:1980:PCG, author = "H. Ehrig and B. K. Rosen", title = "Parallelism and concurrency of graph manipulations", journal = j-THEOR-COMP-SCI, volume = "11", number = "3", pages = "247--275", month = jul, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Fachbereich Informatik, Tech. Univ. Berlin, Berlin, West Germany", keywords = "Church Rosser theorem; concurrency; grammars; graph derivation sequence; graph grammar theory; graph manipulations; graph theory; parallelism; pullback lemmas; sequential independence", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Kozen:1980:ISC, author = "D. Kozen", title = "Indexings of subrecursive classes", journal = j-THEOR-COMP-SCI, volume = "11", number = "3", pages = "277--301", month = jul, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "combinatorial completeness; deciding halting; deciding membership; diagonalization; formal languages; Godel numbering; lambda calculus; programming language; Rice's theorem; subrecursive classes; subrecursive indexing", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Blum:1980:ANR, author = "N. Blum and K. Mehlhorn", title = "On the average number of rebalancing operations in weight-balanced trees", journal = j-THEOR-COMP-SCI, volume = "11", number = "3", pages = "303--320", month = jul, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Fachbereich 10, Univ. des Saarlandes, Saarbrucken, West Germany", keywords = "average number; double rotations; rebalancing operation; trees (mathematics); weight balanced trees", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Heintz:1980:LBP, author = "J. Heintz and M. Sieveking", title = "Lower bounds for polynomials with algebraic coefficients", journal = j-THEOR-COMP-SCI, volume = "11", number = "3", pages = "321--330", month = jul, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B0290F (Interpolation and function approximation); C4130 (Interpolation and function approximation)", corpsource = "Fachbereich Math., Johann-Wolfgang Goethe Univ., Frankfurt/Main, West Germany", keywords = "algebraic coefficients; complexity; computational complexity; linear equations; polynomials", pubcountry = "Netherlands", treatment = "P Practical", } @Article{vonzurGathen:1980:SPH, author = "J. {von zur Gathen} and V. Strassen", title = "Some polynomials that are hard to compute", journal = j-THEOR-COMP-SCI, volume = "11", number = "3", pages = "331--335", month = jul, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B0290F (Interpolation and function approximation); C4130 (Interpolation and function approximation); C4210 (Formal logic)", corpsource = "Seminar fur Angewandte Math., Univ. Zurich, Zurich, Switzerland", keywords = "computability and decidability; polynomials", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Netto:1980:TIM, author = "A. B. Netto", title = "There are infinitely many complete prefix codes of constant length $\ell (\ell\ge3)$", journal = j-THEOR-COMP-SCI, volume = "11", number = "3", pages = "337--339", month = jul, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4130 (Interpolation and function approximation); C4210 (Formal logic)", corpsource = "Inst. de Matematica e Estatistica, Univ. de Sao Paulo, Sao Paulo, Brazil", keywords = "constant length; polynomials; prefix codes; trees (mathematics)", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ben-Ari:1980:CTG, author = "M. Ben-Ari", title = "Comments on {`Tautology testing with a generalized matrix reduction method'}", journal = j-THEOR-COMP-SCI, volume = "11", number = "3", pages = "341--??", month = jul, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Math. Sci., Tel Aviv Univ., Ramat Aviv, Israel", keywords = "formal languages; generalized matrix reduction method; proof system; propositional calculus; tautology testing", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Jaffe:1980:EST, author = "J. M. Jaffe", title = "Efficient scheduling of tasks without full use of processor resources", journal = j-THEOR-COMP-SCI, volume = "12", number = "1", pages = "1--17", month = sep, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4200 (Computer theory); C6150J (Operating systems)", corpsource = "Lab. for Computer Sci., MIT, Cambridge, MA, USA", keywords = "computation theory; multiprocessing programs; nonpreemptive scheduling; operating systems (computers); polynomial time algorithms; processor resources; scheduling; tasks", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Saheb-Djahromi:1980:CMN, author = "N. Saheb-Djahromi", title = "{CPOs} of measures for nondeterminism", journal = j-THEOR-COMP-SCI, volume = "12", number = "1", pages = "19--37", month = sep, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1140Z (Other topics in statistics); C4240 (Programming and algorithm theory)", corpsource = "Faculty of Sci., Univ. of Tehran, Tehran, Iran", keywords = "complete partial order; CPO; nondeterminism; probability; probability distributions; programming theory; semantics", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Winkowski:1980:BCS, author = "J. Winkowski", title = "Behaviours of concurrent systems", journal = j-THEOR-COMP-SCI, volume = "12", number = "1", pages = "39--60", month = sep, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C5420 (Mainframes and minicomputers)", corpsource = "Inst. Podstaw Informatyki PAN, Warszawa, Poland", keywords = "concurrent systems; parallel processing; sequential processing", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Harel:1980:PCR, author = "D. Harel", title = "Proving the correctness of regular deterministic programs: a unifying survey using dynamic logic", journal = j-THEOR-COMP-SCI, volume = "12", number = "1", pages = "61--81", month = sep, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "algorithmic logic; correctness proving; dynamic logic; formal logic; programming logic; programming theory; regular deterministic programs", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ausiello:1980:TUA, author = "G. Ausiello and A. Marchetti-Spaccamela", title = "Toward a unified approach for the classification of {NP}-complete optimization problems", journal = j-THEOR-COMP-SCI, volume = "12", number = "1", pages = "83--96", month = sep, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Oct 24 12:51:05 1998", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C1180 (Optimisation techniques)", corpsource = "Istituto di Automatica, CNR, Roma, Italy", keywords = "classification; combinatorial mathematics; NP complete problems; optimisation; optimization; unified approach", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Monier:1980:ECT, author = "L. Monier", title = "Evaluation and comparison of two efficient probabilistic primality testing algorithms", journal = j-THEOR-COMP-SCI, volume = "12", number = "1", pages = "97--108", month = sep, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1140Z (Other topics in statistics); C4240 (Programming and algorithm theory); C5230 (Digital arithmetic methods)", corpsource = "Lab. de Recherche en Informatique, Univ. de Paris-Sud, Orsay, France", keywords = "computational complexity; number theory; probabilistic primality testing algorithms; probability", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Grant:1980:SMI, author = "P. W. Grant", title = "Some more independence results in complexity theory", journal = j-THEOR-COMP-SCI, volume = "12", number = "2", pages = "119--126", month = oct, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer Sci., Univ. Coll. of Swansea, Swansea, UK", keywords = "complexity theory; computational complexity; independence results", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ehrenfeucht:1980:AES, author = "A. Ehrenfeucht and G. Rozenberg", title = "On ambiguity in {E0L} systems", journal = j-THEOR-COMP-SCI, volume = "12", number = "2", pages = "127--134", month = oct, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder, CO, USA", keywords = "ambiguity; context free grammars; context free language; context-free grammars; context-free languages; E0L systems; negative prefix property", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Maurer:1980:SEF, author = "H. A. Maurer and A. Salomaa and D. Wood", title = "Synchronized {E0L} forms", journal = j-THEOR-COMP-SCI, volume = "12", number = "2", pages = "135--159", month = oct, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Inst. for Informationsverarbeitung, Tech. Univ. Graz, Graz, Austria", keywords = "ambiguity; E0L systems; formal languages; languages; synchronised E0L forms; syntax analysis", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Angluin:1980:CPP, author = "D. Angluin", title = "On counting problems and the polynomial-time hierarchy", journal = j-THEOR-COMP-SCI, volume = "12", number = "2", pages = "161--173", month = oct, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4130 (Interpolation and function approximation); C4220 (Automata theory); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer Sci., Edinburgh Univ., Edinburgh, UK", keywords = "computational complexity; polynomial time hierarchy; polynomials; probabilistic Turing machines; sets; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Cousineau:1980:ADC, author = "G. Cousineau", title = "An algebraic definition for control structures", journal = j-THEOR-COMP-SCI, volume = "12", number = "2", pages = "175--192", month = oct, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Lab. Informatique Th{\'e}orique et Programmation, Univ. Pierre et Marie Curie, Paris, France", keywords = "algebraic definition; computation tree; concatenation; control structures; explicit loops; infinite trees; rational trees; recursive definition; star operation; trees (mathematics)", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Beatty:1980:TIT, author = "J. C. Beatty", title = "Two iteration theorems for the {LL(k}) languages", journal = j-THEOR-COMP-SCI, volume = "12", number = "2", pages = "193--228", month = oct, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4100 (Numerical analysis); C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo, Ont., Canada", keywords = "derivation trees; formal languages; grammar; grammars; iteration theorems; iterative methods; LL(k) languages; trees (mathematics)", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Tiuryn:1980:UFP, author = "J. Tiuryn", title = "Unique fixed points vs. least fixed points", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "229--254", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4140 (Linear algebra); C4210 (Formal logic)", corpsource = "Lehrstuhl fur Informatik II, RWTH Aachen, Aachen, West Germany", keywords = "algebra; algebras; extensions; formal languages; least fixed points; programming languages; semantics; unique fixed point", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Dobkin:1980:DM, author = "D. Dobkin and J. I. Munro", title = "Determining the mode", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "255--263", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer Sci., Univ. of Arizona, Tucson, AZ, USA", keywords = "complexity; computational complexity; computing modes; multisets; sorting", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Joshi:1980:LCP, author = "A. K. Joshi and L. S. Levy and K. Yueh", title = "Local constraints in programming languages. {I}. Syntax", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "265--290", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer and Information Sci., Univ. of Pennsylvania, Philadelphia, PA, USA", keywords = "ALGOL 60; context free languages; context-free grammars; context-free languages; correctness proof; grammatical structure; local constraints; parsing algorithm; programming languages; syntax; tree", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Oppen:1980:CCC, author = "D. C. Oppen", title = "Complexity, convexity and combinations of theories", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "291--302", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Computer Sci. Dept., Stanford Univ., Stanford, CA, USA", keywords = "combinations; complexity; computability and decidability; computational complexity; convexity; decidable combinations; quantifier free theory; satisfiability problem; theorem proving; theories", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Valiant:1980:NCB, author = "L. G. Valiant", title = "Negation can be exponentially powerful", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "303--314", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4130 (Interpolation and function approximation)", corpsource = "Computer Sci. Dept., Edinburgh Univ., Edinburgh, UK", keywords = "efficiency; exponential gain; multivariate polynomials; negations; perfect matchings; planar graphs; polynomials", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Munro:1980:SSL, author = "J. I. Munro and M. S. Paterson", title = "Selection and sorting with limited storage", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "315--323", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C6120 (File organisation)", corpsource = "Dept. of Computer Sci., Univ. of Waterloo, Waterloo, Ont., Canada", keywords = "file; file organisation; internal storage; probabilistic methods; selection; sorting; storage", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Boe:1980:MCS, author = "J. M. Boe and A. {de Luca} and A. Restivo", title = "Minimal complete sets of words", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "325--332", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1260 (Information theory); C6130 (Data handling techniques)", corpsource = "Univ. des Sci. et Tech. du Languedoc, Montpellier, France", keywords = "codes; free monoid; information theory; minimal complete sets; words", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gill:1980:DST, author = "J. Gill and J. Hunt and J. Simon", title = "Deterministic simulation of tape-bounded probabilistic {Turing} machine transducers", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "333--338", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Dept. of Electrical Engng., Stanford Univ., Stanford, CA, USA", keywords = "deterministic simulation; probabilistic Turing machine transducers; tape bounded machines; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ehrenfeucht:1980:BDS, author = "A. Ehrenfeucht and G. Rozenberg", title = "On a bound for the {D0L} sequence equivalence problem", journal = j-THEOR-COMP-SCI, volume = "12", number = "3", pages = "339--342", month = nov, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder, CO, USA", keywords = "D0L sequence; equivalence problem; explicit bound; formal languages", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Wadge:1980:ETD, author = "W. W. Wadge", title = "An extensional treatment of dataflow deadlock", journal = j-THEOR-COMP-SCI, volume = "13", number = "1", pages = "3--15", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Computer Sci. Dept., Univ. of Warwick, Coventry, UK", keywords = "completeness; cycle sum test; dataflow deadlock; dependency graph; extensional treatment; program; programming theory; semantics", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Lynch:1980:DBI, author = "N. A. Lynch and M. J. Fischer", title = "On describing the behaviour and implementation of distributed systems", journal = j-THEOR-COMP-SCI, volume = "13", number = "1", pages = "17--43", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4200 (Computer theory)", corpsource = "Georgia Inst. of Technol., Atlanta, GA, USA", keywords = "computation theory; design specification; distributed processing; distributed systems; machinery; subsystems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Pnueli:1980:TSC, author = "A. Pnueli", title = "The temporal semantics of concurrent programs", journal = j-THEOR-COMP-SCI, volume = "13", number = "1", pages = "45--60", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Computer Sci. Div., Tel-Aviv Univ., Tel-Aviv, Israel", keywords = "concurrent programs; logic framework; programming theory; state sequences; Temporal Logic; temporal semantics", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Maggiolo-Schettini:1980:MSC, author = "A. Maggiolo-Schettini and H. Wedde and J. Winkowski", title = "Modeling a solution for a control problem in distributed systems by restrictions", journal = j-THEOR-COMP-SCI, volume = "13", number = "1", pages = "61--83", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Inst. di Sci. dell'Informazione, Univ. di Pisa, Pisa, Italy", keywords = "concurrency; constraint module; control problem; correctness; distributed processing; distributed systems; event structure; fairness; Loosely Coupled Systems; programming theory; restricted case graph; restrictions; slack phase techniques", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Nielsen:1980:PNE, author = "M. Nielsen and G. Plotkin and G. Winskel", title = "{Petri} nets, event structures and domains. {I}", journal = j-THEOR-COMP-SCI, volume = "13", number = "1", pages = "85--108", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Univ. of Aarhus, Aarhus, Denmark", keywords = "causal nets; concurrency; confusion; domain theory; domains; event structures; formal logic; languages; net theory; occurrence nets; Petri nets; transition nets; translations", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Genrich:1980:SMH, author = "H. J. Genrich and K. Lautenbach", title = "System modelling with high-level {Petri} nets", journal = j-THEOR-COMP-SCI, volume = "13", number = "1", pages = "109--136", month = jan, year = "1980", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4140 (Linear algebra); C4210 (Formal logic)", corpsource = "Inst. fur Informationssytemforschung, Gesellschaft fur Math. und Datenverarbeitung, St. Augustin, West Germany", keywords = "concurrent systems; distributed data base; formal logic; high-level Petri net; linear algebra; linear-algebraic techniques; Petri nets; predicate/transition-nets; resource management; system modelling; variable extension", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Straubing:1981:GSP, author = "H. Straubing", title = "A generalization of the Schutzenberger product of finite monoids", journal = j-THEOR-COMP-SCI, volume = "13", number = "2", pages = "137--150", month = feb, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Dept. of Math., Reed Coll., Portland, OR, USA", keywords = "concatenation product; dot depth hierarchy; finite monoids; free monoid; Schutzenberger product; set theory; star free sets", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Stoy:1981:CTP, author = "J. E. Stoy", title = "The congruence of two programming language definitions", journal = j-THEOR-COMP-SCI, volume = "13", number = "2", pages = "151--174", month = feb, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Oxford Univ. Computing Lab., Oxford, UK", keywords = "formal languages; programming language definitions", pubcountry = "Netherlands", } @Article{Harel:1981:TCN, author = "D. Harel", title = "On the total correctness of nondeterministic programs", journal = j-THEOR-COMP-SCI, volume = "13", number = "2", pages = "175--192", month = feb, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "arbitrary programming language; computation trees; Dijkstra; execution method; guarded commands; nondeterministic programs; programming languages; programming theory; total correctness", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gallier:1981:NFPa, author = "J. H. Gallier", title = "Nondeterministic flowchart programs with recursive procedures: semantics and correctness. {I}", journal = j-THEOR-COMP-SCI, volume = "13", number = "2", pages = "193--223", month = feb, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer and Information Sci., Univ. of Pennsylvania, Philadelphia, PA, USA", keywords = "correctness; execution tree; nondeterministic flowchart programs; programming theory; recursive procedures; semantics", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Goldfarb:1981:USU, author = "W. D. Goldfarb", title = "The undecidability of the second-order unification problem", journal = j-THEOR-COMP-SCI, volume = "13", number = "2", pages = "225--230", month = feb, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Philosophy, Harvard Univ., Cambridge, MA, USA", keywords = "formal logic; second order logic; undecidability; unification problem", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Thomas:1981:RS, author = "W. Thomas", title = "Remark on the star-height-problem", journal = j-THEOR-COMP-SCI, volume = "13", number = "2", pages = "231--237", month = feb, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Math. Inst., Freiburg, West Germany", keywords = "automata theory; general regular expressions; regular events; star height problem", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gallier:1981:NFPb, author = "J. H. Gallier", title = "Nondeterministic flowchart programs with recursive procedures: semantics and correctness. {II}", journal = j-THEOR-COMP-SCI, volume = "13", number = "3", pages = "239--270", month = mar, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer and Information Sci., Univ. of Pennsylvania, Philadelphia, PA, USA", keywords = "correctness; equivalence; extension; flowcharting; inductive assertion method; nondeterministic flowchart programs; programming theory; recursive procedures; second-order predicate calculus; semantics", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Engeler:1981:GGT, author = "E. Engeler", title = "Generalized {Galois} theory and its application to complexity", journal = j-THEOR-COMP-SCI, volume = "13", number = "3", pages = "271--293", month = mar, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Inst. fur Informatik, ETH-Zentrum, Zurich, Switzerland", keywords = "auxiliary procedures; complexity; computational complexity; Galois theory; polynomial equations; solution strategies; solvability", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gurari:1981:CEP, author = "E. M. Gurari and O. H. Ibarra", title = "The complexity of the equivalence problem for two characterizations of {Presburger} sets", journal = j-THEOR-COMP-SCI, volume = "13", number = "3", pages = "295--314", month = mar, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Dept. of Computer Sci., Univ. of Minnesota, Minneapolis, MN, USA", keywords = "automata theory; complexity; computational complexity; deterministic time complexity; equivalence problem; NP-complete; Presburger sets; reversal-bounded multicounter machines; semilinear sets", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{MeyerAufDerHeide:1981:CTV, author = "F. {Meyer Auf Der Heide}", title = "A comparison of two variations of a pebble game on graphs", journal = j-THEOR-COMP-SCI, volume = "13", number = "3", pages = "315--322", month = mar, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4220 (Automata theory); C4240 (Programming and algorithm theory)", corpsource = "Faculty of Math., Univ. of Bielefeld, Bielefeld, West Germany", keywords = "directed acyclic graph; directed graphs; distinguished vertex; pebble game; programming theory; storage requirement; straight line program; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Leiss:1981:SRR, author = "E. Leiss", title = "Succinct representation of regular languages by {Boolean} automata", journal = j-THEOR-COMP-SCI, volume = "13", number = "3", pages = "323--330", month = mar, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dept. of Computer Sci., Univ. of Kentucky, Lexington, KY, USA", keywords = "Boolean automata; Boolean function; Boolean functions; deterministic automata; finite automata; formal languages; regular languages", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Galil:1981:LSU, author = "Z. Galil and J. Seireras", title = "Linear-time string-matching using only a fixed number of local storage locations", journal = j-THEOR-COMP-SCI, volume = "13", number = "3", pages = "331--336", month = mar, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math. Sci., Tel-Aviv Univ., Tel-Aviv, Israel", keywords = "automata-theoretic terms; dynamic storage allocation; finite automata; FORTRAN; linear-time string-matching algorithm; local storage locations; programming theory; random-access machine; restricted writing alphabet; writing multihead finite automaton", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gati:1981:SEG, author = "G. Gati", title = "Some elements of a {Galois} theory of the structure and complexity of the tree automorphism problem", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "1--17", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Inst. fur Informatik, Eidgenossische Tech. Hochschule Zurich, Zurich, Switzerland", keywords = "complexity; computational complexity; Engeler's generalization; Galois group; Galois theory; problem difficulty; time complexity; tree automorphism problem", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{SchulteMonting:1981:MEE, author = "J. {Schulte Monting}", title = "Merging of 4 or 5 elements with $n$ elements", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "19--37", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C6130 (Data handling techniques)", corpsource = "Math. Inst., Univ. T{\"u}bingen, T{\"u}bingen, West Germany", keywords = "5-element chain; data handling; finite chain; minimum-comparison-merging; very tight bounds", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Nishitani:1981:FSS, author = "Y. Nishitani and N. Honda", title = "The Firing Squad Synchronization problem for graphs", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "39--61", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Res. Inst. of Electrical Communication, Tohoku Univ., Sendai, Japan", keywords = "finite automata; Firing Squad Synchronization problem; graphs; synchronization times", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Leiss:1981:GLE, author = "E. Leiss", title = "On generalized language equations", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "63--77", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dept. of Computer Sci., Univ. of Houston, Houston, TX, USA", keywords = "alphabet; Boolean automata; finite automata; fixed languages; formal languages; generalized language equations; language equations", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Rosenthal:1981:OAS, author = "A. Rosenthal", title = "Optimal algorithms for sensitivity analysis in associative multiplication problems", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "79--90", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer and Communication Sci., Univ. of Michigan, Ann Arbor, MI, USA", keywords = "graph theory; Huffman trees; optimal ordered binary search trees; optimal strategies; optimisation; programming theory; sensitivity analysis", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Long:1981:GVP, author = "T. J. Long", title = "On gamma -reducibility versus polynomial time many-one reducibility", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "91--101", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer and Information Sci., Ohio State Univ., Columbus, OH, USA", keywords = "computational complexity; deterministic polynomial time; nondeterministic polynomial time; polynomial time Turing reduction; reducibility; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Galil:1981:TEV, author = "Z. Galil", title = "On the theoretical efficiency of various network flow algorithms", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "103--111", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math. Sci., Tel-Aviv Univ., Tel-Aviv, Israel", keywords = "algorithm theory; combinatorial mathematics; combinatorial optimisation; maximal flow; network flow algorithms; optimisation; theoretical efficiency; time bounds; topology", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kozen:1981:EPC, author = "D. Kozen and R. Parikh", title = "An elementary proof of the completeness of {PDL}", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "113--118", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "completeness; formal logic; PDL; Propositional Dynamic Logic; Segerberg axioms", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Latteux:1981:CLS, author = "M. Latteux", title = "Concerning a lemma of substitution", journal = j-THEOR-COMP-SCI, volume = "14", number = "1", pages = "119--123", month = apr, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Lab. d'Informatique, Univ. des Sci. et Techniques de Lille I, Villeneuve d'Ascq, France", keywords = "bifaithful trio; disjoint alphabets; formal languages; full trios; Greibach syntactic lemma; substitutions", language = "French", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Jantzen:1981:PSO, author = "M. Jantzen", title = "The power of synchronizing operations on strings", journal = j-THEOR-COMP-SCI, volume = "14", number = "2", pages = "127--154", month = may, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Fachbereich Informatik, Univ. Hamburg, Hamburg, West Germany", keywords = "cancellation; computation sequence; computation theory; homomorphism; inverse shuffle; iterated shuffle; shuffle; strings; synchronizing operation", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Gallier:1981:DNF, author = "J. H. Gallier", title = "{DPDA's} in 'atomic normal form' and applications to equivalence problems", journal = j-THEOR-COMP-SCI, volume = "14", number = "2", pages = "155--186", month = may, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Dept. of Computer and Information Sci., Univ. of Pennsylvania, Philadelphia, PA, USA", keywords = "'Atomic Normal Form'; address language; deterministic automata; deterministic pushdown automata; equivalence", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Beauquier:1981:SS, author = "J. Beauquier", title = "Substitution of {semi-AFLs}", journal = j-THEOR-COMP-SCI, volume = "14", number = "2", pages = "187--193", month = may, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Lab. Informatique Th{\'e}orique et Programmation, Univ. de Picardie, Amiens, France", keywords = "abstract family language; computation theory; homomorphism; substitution operator", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Therien:1981:CFM, author = "D. Therien", title = "Classification of finite monoids: The language approach", journal = j-THEOR-COMP-SCI, volume = "14", number = "2", pages = "195--208", month = may, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "School of Computer Sci., McGill Univ., Montreal, Que., Canada", keywords = "algorithm theory; convergence variety; finite monoid", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Maruoka:1981:PDT, author = "A. Maruoka and M. Kimura and N. Shoji", title = "Pattern decomposition for tessellation automata", journal = j-THEOR-COMP-SCI, volume = "14", number = "3", pages = "211--226", month = jun, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Faculty of Engng., Tohoku Univ., Sendai, Japan", keywords = "automata theory; bijective mapping; monogenic cellular automata; neighborhood; pattern decomposition; positive integer; q-state; residue; states number; tessellation automata", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Bucher:1981:CDF, author = "W. Bucher and H. A. Maurer and K. Culik and D. Wotschke", title = "Concise description of finite languages", journal = j-THEOR-COMP-SCI, volume = "14", number = "3", pages = "227--246", month = jun, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Inst. fur Informationsverarbeitung, Tech. Univ. Graz, Graz, Austria", keywords = "computational complexity; context-free grammars; finite language; finite number; grammatical complexity; productions number; X complexity", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Stoklosa:1981:CA, author = "J. Stoklosa and W. Zakowski", title = "Computations of ( alpha,k)-machines", journal = j-THEOR-COMP-SCI, volume = "14", number = "3", pages = "247--265", month = jun, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Inst. of Control Engng., Tech. Univ. of Poznan, Poznan, Poland", keywords = "boundedness; cell number; computational complexity; convergence; cyclic computation; divergence; feedback function; k-machine; positive integer; sequence generator", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Rozenberg:1981:PTI, author = "G. Rozenberg and R. Verraedt", title = "On pure, terminal invariant and nonterminal invariant interpretations of {E0L} forms", journal = j-THEOR-COMP-SCI, volume = "14", number = "3", pages = "267--288", month = jun, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Inst. of Appl. Math and Computer Sci., Univ. of Leiden, Leiden, Netherlands", keywords = "expression oriented language; L forms theory; language level; nonterminal symbol; programming theory; pure interpretations; terminal symbol", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Moran:1981:GAA, author = "S. Moran", title = "General approximation algorithms for some arithmetical combinatorial problems", journal = j-THEOR-COMP-SCI, volume = "14", number = "3", pages = "289--303", month = jun, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1180 (Optimisation techniques); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer Sci., Univ. of Minnesota, Minneapolis, MN, USA", keywords = "approximation algorithm; computational complexity; hard optimization; maximal integer; minimal integer; nonlinear programming; polynomial; worst case relative error", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Callegarin:1981:AIP, author = "G. Callegarin and G. Pacini", title = "About the implementability and the power of equationally defined data abstractions", journal = j-THEOR-COMP-SCI, volume = "14", number = "3", pages = "305--315", month = jun, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Istituto di Sci. dell'Informazione, Univ. degli Studi di Pisa, Pisa, Italy", keywords = "data abstraction; equationally defined data; language embedding; least congruence; programming theory; semantics; word algebra", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Jensen:1981:CPN, author = "K. Jensen", title = "Coloured {Petri} nets and the invariant-method", journal = j-THEOR-COMP-SCI, volume = "14", number = "3", pages = "317--336", month = jun, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Computer Sci. Dept., Aarhus Univ., Aarhus, Denmark", keywords = "coloured Petri nets; colours set; common subnet; formal sum; invariant-method; predicate/transition-nets; programming theory; transition", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Bucher:1981:NPT, author = "W. Bucher", title = "A note on a problem in the theory of grammatical complexity", journal = j-THEOR-COMP-SCI, volume = "14", number = "3", pages = "337--344", month = jun, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Inst. fur Informationsverarbeitung, Tech. Univ. Graz, Graz, Austria", keywords = "bounds; computational complexity; context-free grammars; grammatical complexity; infinite context-free language; infinite linear language; words set", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Schmidt:1981:PPGa, author = "G. Schmidt", title = "Programs as partial graphs. {I}. Flow equivalence and correctness", journal = j-THEOR-COMP-SCI, volume = "15", number = "1", pages = "1--25", month = jul, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", corpsource = "Inst. fur Informatik, Tech. Univ. Munchen, Munchen, West Germany", keywords = "correctness; equivalence; graph theory; partial graph; program flow; program termination; programming theory; relational algebra; semantics; single program steps", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Book:1981:BQMa, author = "R. V. Book", title = "Bounded query machines: on {NP} and {PSPACE}", journal = j-THEOR-COMP-SCI, volume = "15", number = "1", pages = "27--39", month = jul, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1180 (Optimisation techniques); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math., Univ. of California, Santa Barbara, CA, USA", keywords = "bounded query machine; nondeterministic polynomial; nonlinear programming; oracle set; programming theory", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Book:1981:BQMb, author = "R. V. Book and C. Wrathall", title = "Bounded query machines: on {NP()} and {NPQUERY()}", journal = j-THEOR-COMP-SCI, volume = "15", number = "1", pages = "41--50", month = jul, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math., Univ. of California, Santa Barbara, CA, USA", keywords = "bounded query machine; NP operator; NPQUERY operator; programming theory; PSPACE operator", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Araki:1981:RFL, author = "T. Araki and T. Kagimasa and N. Tokura", title = "Relations of flow languages to {Petri} net languages", journal = j-THEOR-COMP-SCI, volume = "15", number = "1", pages = "51--75", month = jul, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Information and Computer Sci., Faculty of Engng. Sci., Osaka Univ., Toyonaka, Osaka, Japan", keywords = "correctness; equivalence; extended expression; flow languages; Petri net languages; programming theory; relational language", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Lazard:1981:SAE, author = "D. Lazard", title = "Solution of algebraic equations systems", journal = j-THEOR-COMP-SCI, volume = "15", number = "1", pages = "77--110", month = jul, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4140 (Linear algebra); C4240 (Programming and algorithm theory)", corpsource = "Dept. de Math., Univ. de Poitiers, Poitiers, France", keywords = "algebraic closure; algebraic equations; common zeros; computational complexity; conjugate zeros; ground field; linear algebra; multiplicities; multivariate polynomials; univariate equation", language = "French", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Heilbrunner:1981:PAA, author = "S. Heilbrunner", title = "A parsing automata approach to {LR} theory", journal = j-THEOR-COMP-SCI, volume = "15", number = "2", pages = "117--157", month = aug, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Hochschule der Bundeswehr Munchen, Munchen, West Germany", keywords = "automata theory; grammars; item grammars; LC grammar; LL grammar; LR theory; parsing automata; prefix parsers", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Schmidt:1981:PPGb, author = "G. Schmidt", title = "Programs as partial graphs. {II}. Recursion", journal = j-THEOR-COMP-SCI, volume = "15", number = "2", pages = "159--179", month = aug, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Inst. for Informatik, Tech. Univ. Munchen, Munchen, West Germany", keywords = "conditional branching; correctness; derivatives; equivalence; flow diagram programs; graph theory; Hitchcock-Park's theorem; partial graphs; programming theory; recursive programs; semantics; sequencing; termination; unified relational algebra", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Landweber:1981:SSN, author = "L. H. Landweber and R. J. Lipton and E. L. Robertson", title = "On the structure of sets in {NP} and other complexity classes", journal = j-THEOR-COMP-SCI, volume = "15", number = "2", pages = "181--200", month = aug, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Computer-Sci. Dept., Univ. of Wisconsin, Madison, WI, USA", keywords = "computational complexity; deterministic complexity; nondeterministic complexity; nonlinear programming; resource bounded complexity; sets structure", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Alder:1981:ACA, author = "A. Alder and V. Strassen", title = "On the algorithmic complexity of associative algebras", journal = j-THEOR-COMP-SCI, volume = "15", number = "2", pages = "201--211", month = aug, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4130 (Interpolation and function approximation); C4240 (Programming and algorithm theory)", corpsource = "Seminar fur Angewandte Math., Univ. Zurich, Zurich, Switzerland", keywords = "algorithmic complexity; associative algebras; computational complexity; finite dimensional algebra; function approximation; nonscalar division; nonscalar multiplication; rational function", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Germano:1981:SRC, author = "G. Germano and A. Maggiolo-Schettini", title = "Sequence recursiveness without cylindrification and limited register machines", journal = j-THEOR-COMP-SCI, volume = "15", number = "2", pages = "213--221", month = aug, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Istituto di Scienze dell'Informazione, Univ. di Pisa, Pisa, Italy", keywords = "cylindrification; input datum; output datum; programming theory; recursiveness; register machines; semantics; sequence", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Thatcher:1981:MAS, author = "J. W. Thatcher and E. G. Wagner and J. B. Wright", title = "More on advice on structuring compilers and proving them correct", journal = j-THEOR-COMP-SCI, volume = "15", number = "3", pages = "223--249", month = sep, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6150C (Compilers, interpreters and other processors)", corpsource = "Math. Sci. Dept., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "abstract syntax; compilers; correctness proving; example language; program compilers; programming theory; semantics; structuring compilers", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Paz:1981:NDP, author = "A. Paz and S. Moran", title = "Non deterministic polynomial optimization problems and their approximations", journal = j-THEOR-COMP-SCI, volume = "15", number = "3", pages = "251--277", month = sep, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1180 (Optimisation techniques)", corpsource = "Dept. of Computer Sci., Univ. of California, Berkeley, CA, USA", keywords = "approximability properties; approximation theory; nondeterministic polynomial optimization problems; NPOP; optimisation; polynomials", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Leggett:1981:OPP, author = "E. W. {Leggett, Jr.} and D. J. Moore", title = "Optimization problems and the polynomial hierarchy", journal = j-THEOR-COMP-SCI, volume = "15", number = "3", pages = "279--289", month = sep, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1180 (Optimisation techniques)", corpsource = "Clemson Univ., Clemson, SC, USA", keywords = "Chromatic Number Problem; Knapsack Packing Problem; Maximal Clique Problem; optimisation; optimisation problems; polynomial hierarchy; Symmetric Traveling Salesman Problem", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Katseff:1981:SRP, author = "H. P. Katseff and M. Sipser", title = "Several results in program size complexity", journal = j-THEOR-COMP-SCI, volume = "15", number = "3", pages = "291--309", month = sep, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Electronic Res. Lab., Univ. of California, Berkeley, CA, USA", keywords = "computational complexity; Kolmogorov's complexity measure; program size complexity; programming theory; size complexity", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Loui:1981:SBO, author = "M. C. Loui", title = "A space bound for one-tape multidimensional {Turing} machines", journal = j-THEOR-COMP-SCI, volume = "15", number = "3", pages = "311--320", month = sep, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Lab. for Computer Sci., MIT, Cambridge, MA, USA", keywords = "multidimensional Turing machines; one tape Turing machines; space bound; time complexity; Turing machines; worktape head", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Benzaken:1981:CGE, author = "C. Benzaken and S. Foldes", title = "Complexity of graph embeddability problems", journal = j-THEOR-COMP-SCI, volume = "15", number = "3", pages = "321--328", month = sep, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", corpsource = "Univ. Sci. et Medicale, Grenoble, France", keywords = "computational complexity; embeddability problems; graph embeddability; graph theory; time complexity", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Stratman:1981:ECT, author = "R. Stratman", title = "On the existence of closed terms in the type lambda calculus. {II}: transformations of unification problems", journal = j-THEOR-COMP-SCI, volume = "15", number = "3", pages = "329--338", month = sep, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Rutgers Univ., New Brunswick, NJ, USA", keywords = "computability and decidability; decidable unification problems; polynomial time decidable; unification problems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Weihrauch:1981:EMS, author = "K. Weihrauch and U. Schreiber", title = "Embedding metric spaces into cpos", journal = j-THEOR-COMP-SCI, volume = "16", number = "1", pages = "5--24", month = oct, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Fachbereich Math./Informatik, Fernuniv./Gesamthochschule Hagen, Hagen, West Germany", keywords = "computability; computability and decidability; cpo; Euclidean space; infinite trees; metric spaces; Polish topology; topology", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ehrenfeucht:1981:SCS, author = "A. Ehrenfeucht and G. Rozenberg", title = "On the subword complexity of square-free {D0L} languages", journal = j-THEOR-COMP-SCI, volume = "16", number = "1", pages = "25--32", month = oct, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Univ. of Colorado, Boulder, CO, USA", keywords = "computational complexity; D0L languages; formal languages; square free languages; subword complexity; subwords", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Takasu:1981:LBP, author = "S. Takasu and S. Kawabata", title = "A logical basis for programming methodology", journal = j-THEOR-COMP-SCI, volume = "16", number = "1", pages = "43--60", month = oct, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Res. Inst. for Math. Sci., Kyoto Univ., Kyoto, Japan", keywords = "assignment statements; FIND; formal proofs; IF-statements; logical basis; programming methodology; programming theory; WHILE- statements; WHILE-programs", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Jantzen:1981:SMS, author = "M. Jantzen", title = "On a special monoid with a single defining relation", journal = j-THEOR-COMP-SCI, volume = "16", number = "1", pages = "61--73", month = oct, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Fachbereich Informatik, Univ. Hamburg, Hamburg, West Germany", keywords = "congruence classes; context-free language; context-free languages; isomorphic proper subgroups; monoid; single defining relation", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Simon:1981:TPT, author = "J. Simon", title = "On tape-bounded probabilistic {Turing} machine acceptors", journal = j-THEOR-COMP-SCI, volume = "16", number = "1", pages = "75--91", month = oct, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Dept. Ciencia da Computa{\c{c}}ao, Univ. Estadual de Campinas, Sao Paulo, Brazil", keywords = "deterministic tape complexities; probabilistic tape complexities; probabilistic Turing machine; tape bounded Turing machine; Turing machine; Turing machine acceptor; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Main:1981:FUR, author = "M. G. Main and D. B. Benson", title = "Free upper regular bands", journal = j-THEOR-COMP-SCI, volume = "16", number = "1", pages = "93--98", month = oct, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1110 (Algebra); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer Sci., Washington State Univ., Pullman, WA, USA", keywords = "data types; group theory; lattice-ordered semigroup; programming theory; universal domains; upper regular bands", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Lieberherr:1981:UCD, author = "K. Lieberherr", title = "Uniform complexity and digital signatures", journal = j-THEOR-COMP-SCI, volume = "16", number = "1", pages = "99--110", month = oct, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Electrical Engng. and Computer Sci., Princeton Univ., Princeton, NJ, USA", keywords = "computational complexity; digital signatures; security of data; signature checking; signature production; uniform complexity", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Tao:1981:CPA, author = "Ren-ji Tao", title = "On the computational power of automata with time or space bounded by {Ackermann}'s or superexponential functions", journal = j-THEOR-COMP-SCI, volume = "16", number = "2", pages = "115--148", month = nov, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Inst. of Computing Technol., Acad. of Sinica, Beijing, China", keywords = "Ackermann's function; automata; automata theory; computational power; superexponential functions", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Pittle:1981:LGL, author = "J. Pittle", title = "On {LLP(k}) grammars and languages", journal = j-THEOR-COMP-SCI, volume = "16", number = "2", pages = "149--175", month = nov, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C6150C (Compilers, interpreters and other processors)", corpsource = "Charles Univ., Prague, Czechoslovakia", keywords = "compilers; deterministic grammar; formal languages; grammars; languages; LL(k) grammars; LLP(k) grammars; LR(k) grammars; parsing; program compilers", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Galbiati:1981:CBN, author = "G. Galbiati and M. J. Eischer", title = "On the complexity of $2$-output {Boolean} networks", journal = j-THEOR-COMP-SCI, volume = "16", number = "2", pages = "177--185", month = nov, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4230B (Combinatorial switching theory)", corpsource = "Inst of Mat., Univ. of Pavia, Pavia, Italy", keywords = "2-output Boolean networks; and-gates; Boolean functions; combinational complexity; complexity; monotone networks; not-gates; optimal realizations; or-gates", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Raiha:1981:SCS, author = "K.-J. Raiha and E. Ukkonen", title = "The shortest common supersequence problem over binary alphabet is {NP-complete}", journal = j-THEOR-COMP-SCI, volume = "16", number = "2", pages = "187--198", month = nov, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C1180 (Optimisation techniques); C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dept. of Computer Sci., Univ. of Helsinki, Helsinki, Finland", keywords = "automata theory; binary alphabet; finite strings; formal languages; NP-complete; optimisation; shortest common supersequence problem", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Csirmaz:1981:PPV, author = "L. Csirmaz", title = "Programs and program verifications in a general setting", journal = j-THEOR-COMP-SCI, volume = "16", number = "2", pages = "199--210", month = nov, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Math. Inst., Hungarian Acad. of Sci., Budapest, Hungary", keywords = "completeness; Floyd-Hoare derivability; halting configurations; Peano models; program testing; program verifications; programming theory; standard programs", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Nguyen:1981:DPL, author = "V. L. Nguyen and J. L. Lassez", title = "A dual problem to least fixed points", journal = j-THEOR-COMP-SCI, volume = "16", number = "2", pages = "211--221", month = nov, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Computer Sci., Univ. of Melbourne, Parkville, Vic., Australia", keywords = "continuous functions; continuous lattices; dual problem; duality (mathematics); least fixed points; maximal ascending sequences; minimal continuous functions; programming theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Book:1981:TCP, author = "R. V. Book and C. P. O'Dunlaing", title = "Testing for the {Church-Rosser} property", journal = j-THEOR-COMP-SCI, volume = "16", number = "2", pages = "223--229", month = nov, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math., Univ. of California, Santa Barbara, CA, USA", keywords = "algorithm theory; Church-Rosser property; finite automata; finite Thue system; grammars; polynomial time algorithm; program optimisers; theorem proves; trees", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Carter:1981:NEC, author = "I. L. Carter and R. Eagin", title = "A note on the existence of continuous functionals", journal = j-THEOR-COMP-SCI, volume = "16", number = "2", pages = "231--235", month = nov, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B0290F (Interpolation and function approximation); B0290K (Nonlinear and functional equations); C4130 (Interpolation and function approximation); C4150 (Nonlinear and functional equations)", corpsource = "Computer Sci. Dept., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", keywords = "continuous functionals; functional equations; index set; interpolating function; interpolation; partial functions", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kleijn:1981:CRS, author = "H. C. M. Kleijn and G. Rozenberg", title = "Context-free restrictions on selective rewriting", journal = j-THEOR-COMP-SCI, volume = "16", number = "3", pages = "237--269", month = dec, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Inst. of Appl. Math. and Computer Sci., Univ. of Leiden, Leiden, Netherlands", keywords = "context-free grammar; context-free grammars; formal language theory; selective rewriting", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Lam:1981:GCS, author = "K. Lam and M. K. Siu and C. T. Yu", title = "A generalized counter scheme", journal = j-THEOR-COMP-SCI, volume = "16", number = "3", pages = "271--278", month = dec, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Statistics, Hong Kong Univ., Hong Kong", keywords = "generalized counter scheme; programming theory; transposition heuristic", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Burkhard:1981:ICT, author = "W. A. Burkhard and M. L. Fredman and D. J. Kleitman", title = "Inherent complexity trade-offs for range query problems", journal = j-THEOR-COMP-SCI, volume = "16", number = "3", pages = "279--290", month = dec, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6120 (File organisation)", corpsource = "Dept. of Electrical Engng. and Computer Sci., Univ. of California, San Diego, La Jolla, CA, USA", keywords = "computational complexity; data structures; range query problems", pubcountry = "Netherlands", treatment = "A Application; T Theoretical or Mathematical", } @Article{Albert:1981:LHR, author = "J. Albert and L. Wegner", title = "Languages with homomorphic replacements", journal = j-THEOR-COMP-SCI, volume = "16", number = "3", pages = "291--305", month = dec, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Inst. fur Angewandte Informatik und Formulae Beschreibungsverfahren, Univ. Karlsruhe, Karlsruhe, West Germany", keywords = "context-free languages; H-systems; homomorphic replacements; language generators; van Wijngaarden grammars", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gupta:1981:RAM, author = "U. I. Gupta and D. T. Lee and J. W. Pruitt and C. K. Wong", title = "Record allocation for minimizing seek delay", journal = j-THEOR-COMP-SCI, volume = "16", number = "3", pages = "307--319", month = dec, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C6120 (File organisation)", corpsource = "Dept. of Electrical Engng. and Computer Sci., Northwestern Univ., Evanston, IL, USA", keywords = "file organisation; linear storage device; performance bounds; seek delay", pubcountry = "Netherlands", treatment = "A Application", } @Article{Berman:1981:PDL, author = "F. Berman and M. Paterson", title = "Propositional Dynamic Logic is weaker without tests", journal = j-THEOR-COMP-SCI, volume = "16", number = "3", pages = "321--328", month = dec, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Purdue Univ., West Lafayette, IN, USA", keywords = "branching; formal logic; iteration; program operators; test-free propositional dynamic logic", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Edelsbrunner:1981:SSG, author = "H. Edelsbrunner and H. A. Maurer", title = "A space-optimal solution of general region location", journal = j-THEOR-COMP-SCI, volume = "16", number = "3", pages = "329--336", month = dec, year = "1981", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Inst. fur Informationsverarbeitung, Tech. Univ. of Graz., Graz, Austria", keywords = "algorithm theory; general region location; linear space; logarithmic time", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Blattner:1982:PGF, author = "M. Blattner and S. Ginsburg", title = "Position-restricted grammar forms and grammars", journal = j-THEOR-COMP-SCI, volume = "17", number = "1", pages = "1--27", month = jan, year = "1982", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Math. Sci. Dept., Rice Univ., Houston, TX, USA", keywords = "context-free grammars; context-free language; context-free languages; grammar forms; grammars; interpretation grammars; position restricted grammar; terminal word", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Welzl:1982:CD, author = "E. Welzl", title = "Color-families are dense", journal = j-THEOR-COMP-SCI, volume = "17", number = "1", pages = "29--41", month = jan, year = "1982", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Inst. fur Informationsverarbeitung, Tech. Univ. Graz, Graz, Austria", keywords = "grammar forms; graph colouring", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ekkonen:1982:SPE, author = "E. Ekkonen", title = "Structure preserving elimination of null productions from context-free grammars", journal = j-THEOR-COMP-SCI, volume = "17", number = "1", pages = "43--54", month = jan, year = "1982", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:36:07 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Computer Sci., Univ. of Helsinki, Helsinki, Finland", keywords = "context-free grammars; Greibach normal form; homomorphic images; null production", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gurari:1982:SSU, author = "E. M. Gurari and O. H. Ibarra", title = "Some simplified undecidable and {NP-hard} problems for simple programs", journal = j-THEOR-COMP-SCI, volume = "17", number = "1", pages = "55--73", month = jan, year = "1982", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov