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