%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.08",
%%% date = "31 October 2000",
%%% time = "12:34:18 MDT",
%%% filename = "tcs1990.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 = "49163 33420 136452 1407867",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at computer.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 1990--1994;
%%% companion files tcs19xx.bib each cover
%%% other pentads.
%%%
%%% The journal has World-Wide Web home sites
%%% at several locations:
%%%
%%% Title pages:
%%% http://www.elsevier.nl/locate/issn/03043975 (Europe)
%%% http://www.elsevier.com/locate/issn/03043975 (North America)
%%% http://www.elsevier.co.jp/locate/issn/03043975 (Japan)
%%% http://www.sciencedirect.com/science/journal/03043975
%%%
%%% Tables of contents:
%%% http://www.elsevier.nl/locate/tcs
%%% http://www.elsevier.nl/locate/estoc/03043975 (Europe)
%%% http://www.elsevier.com/locate/estoc/03043975 (North America)
%%% http://www.elsevier.co.jp/locate/estoc/03043975 (Japan)
%%%
%%% Elsevier Science alert page:
%%% http://www.elsevier.nl/mcs/tcs/Menu.html (Europe)
%%%
%%% The tables of contents sites begin coverage
%%% with Volume 91, Number 1, 1992, and have full
%%% text of articles from Volume 190, Number 1,
%%% 1998.
%%%
%%% At version 1.08, the year coverage looked
%%% like this:
%%%
%%% 1990 ( 147) 1994 ( 287) 1998 ( 1)
%%% 1991 ( 251) 1995 ( 1) 1999 ( 0)
%%% 1992 ( 256) 1996 ( 0) 2000 ( 1)
%%% 1993 ( 259) 1997 ( 1)
%%%
%%% Article: 1204
%%%
%%% Total entries: 1204
%%%
%%% 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,
%%% the IEEE INSPEC database, and the journal Web
%%% pages.
%%%
%%% 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@computer.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{Wagner:1990:APP,
author = "E. G. Wagner",
title = "Algebras, polynomials and programs",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "3--34",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dept. of Math. Sci., IBM Thomas J. Watson Res. Center,
Yorktown Heights, NY, USA",
keywords = "algebraic applications; arbitrary algebras; computer
science; elementary category theory; formal languages;
iteration; Lawvere algebraic theories; polynomials;
programming languages; programming theory; recursion;
set theory; substitution; universal algebra",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bainbridge:1990:FP,
author = "E. S. Bainbridge and P. J. Freyd and A. Scedrov and P.
J. Scott",
title = "Functorial polymorphism",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "35--64",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Ottawa Univ., Ont., Canada",
keywords = "calculus of generalized natural transformations;
computational linguistics; formal languages;
parametricity; partial equivalence relations; PERs;
polymorphic lambda calculus; polymorphism; Reynolds
invariance condition; Reynolds parametricity condition;
semantic analog; semantic approximations; universal
type abstraction; universal types",
pubcountry = "Netherlands",
treatment = "B Bibliography; T Theoretical or Mathematical",
}
@Article{Barr:1990:FPC,
author = "M. Barr",
title = "Fixed points in {Cartesian} closed categories",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "65--72",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dept. of Math. and Stat., McGill Univ., Montreal,
Que., Canada",
keywords = "cartesian closed categories; domain theory; formal
logic; internally omega-complete partial order; least
fixed point; natural numbers object; omega-continuous
endomorphism; semantic models; set theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bloom:1990:NGT,
author = "S. L. Bloom",
title = "A note on guarded theories",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "73--83",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dept. of Comput. Sci., Stevens Inst. of Technol.,
Hoboken, NJ, USA",
keywords = "algebraic theory; formal logic; guarded theories;
guards; maximal families; partial correctness; set
theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Mulry:1990:CFP,
author = "P. S. Mulry",
title = "Categorical fixed point semantics",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "85--97",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Colgate Univ., Hamilton, NY, USA",
keywords = "categorical fixed point results; computational
linguistics; formal languages; natural numbers;
semantic categories; set theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Nielson:1990:FCM,
author = "H. R. Nielson and F. Nielson",
title = "Functional completeness of the mixed $\lambda$-calculus
and combinatory logic",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "99--126",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., Aarhus Univ., Denmark",
keywords = "binding times; combinator-based abstract machines;
combinatory logic; compile-time; formal logic;
functional languages; mixed lambda-calculus; run-time
computations",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Pasztor:1990:RPD,
author = "A. Pasztor",
title = "Recursive programs and denotational semantics in
absolute logics of programs",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "127--150",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Sch. of Comput. Sci., Florida Int. Univ., Miami, FL,
USA",
keywords = "2-sorted first order logic; absolute; absolute logics
of programs; absolute versions; complete inference
system; denotational semantics; formal logic; logics;
program verification; program verification methods;
programming theory; recursive programs; semantics; set
theoretic property; weak second order logic",
pubcountry = "Netherlands",
treatment = "B Bibliography; T Theoretical or Mathematical",
}
@Article{Bottinger:1990:STD,
author = "C. Bottinger",
title = "On {Scott}'s thesis for domains of information and
well-quasi-orderings",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "151--158",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Fachbereich 6-Math., Univ. GHS Essen, West Germany",
keywords = "canonical process; computational linguistics; CPOs;
formal languages; sufficient condition;
well-quasi-orderings",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Wells:1990:GCS,
author = "C. Wells",
title = "A generalization of the concept of sketch",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "1",
pages = "159--178",
day = "15",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C6110B (Software engineering
techniques)",
corpsource = "Dept. of Math. and Stat., Case Western Reserve Univ.,
Cleveland, OH, USA",
keywords = "cartesian closed category; categorial construction;
data structures; entities; formal specification;
function space objects; functional programming;
functional programming languages; list objects; locos;
power objects; reflexive objects; set theory; sketch;
specification; topos",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Tiuryn:1990:FPF,
author = "J. Tiuryn and D. B. Benson",
title = "Fixed points in free process algebras. {II}",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "2",
pages = "179--192",
day = "26",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Comput. Sci., Washington State Univ.,
Pullman, WA, USA",
keywords = "delta-semilinear polynomials; free process algebras;
left simple polynomials; polynomials; rewriting
systems; right multipliers; sufficient conditions;
tau-semilinear polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Longo:1990:CCF,
author = "G. Longo and E. Moggi",
title = "A category-theoretic characterization of functional
completeness",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "2",
pages = "193--211",
day = "26",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dipartimento di Inf., Pisa Univ., Italy",
keywords = "abstract Godel-number; algebraic functions;
application; cartesian closed categories;
category-theoretic characterization; combinatory logic;
formal languages; formal logic; functional
completeness; group theory; lambda-calculus models;
partial recursive functionals; principal morphisms;
programming language; type-free language",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Senizergues:1990:CDC,
author = "G. Senizergues",
title = "A characterisation of deterministic context-free
languages by means of right-congruences",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "2",
pages = "213--232",
day = "26",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "LITP, Paris, France",
keywords = "context-free languages; controlled rewriting systems;
deterministic context-free languages; regular semi-Thue
systems; rewriting system; rewriting systems;
right-congruence; right-congruences",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Jung:1990:CCC,
author = "A. Jung",
title = "{Cartesian} closed categories of algebraic {CPOs}",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "2",
pages = "233--250",
day = "26",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Fachbereich Math., Tech. Hochschule Darmstadt, West
Germany",
keywords = "algebraic CPOs; algebraic function space; complete
lattice; continuous functions; countably based
algebraic CPOs; formal logic; graph theory; L-domain;
largest cartesian closed full subcategory; least
element; natural extension; number theory; profinite
domains",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Gambosi:1990:LPP,
author = "G. Gambosi and J. Nesetril and M. Talamo",
title = "On locally presented posets",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "2",
pages = "251--260",
day = "26",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Istituto di Analisi dei Sistemi ed Inf., CNR, Rome,
Italy",
keywords = "Boolean dimension; computational complexity; dags;
Dushnik-Miller dimension; graph theory; locally
presented posets; planar dags; time complexity;
transitive closure",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Terlutte:1990:CRT,
author = "A. Terlutte",
title = "Cyclic rational transductions and polynomials of
rational functions",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "2",
pages = "261--271",
day = "26",
month = jan,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. des Sci. et Tech. de Lille, Villeneuve D'Ascq,
France",
keywords = "cyclic rational transductions; finite image; formal
languages; polynomially bounded rational transductions;
polynomials; rational functions; rational
transductions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrenfeucht:1990:TCB,
author = "A. Ehrenfeucht and G. Rozenberg",
title = "Theory of $2$-structures. {I}. Clans, basic
subclasses, and morphisms",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "3",
pages = "277--303",
day = "15",
month = feb,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Dept. of Comput. Sci., Colorado Univ., Boulder, CO,
USA",
keywords = "2-structures theory; basic subclasses; clans; graph;
graph theory; morphisms; relational structure; sorts;
trees; trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrenfeucht:1990:TIR,
author = "A. Ehrenfeucht and G. Rozenberg",
title = "Theory of $2$-structures. {II.} Representation through
labeled tree families",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "3",
pages = "305--342",
day = "15",
month = feb,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Dept. of Comput. Sci., Colorado Univ., Boulder, CO,
USA",
keywords = "2-structures theory; graph theory; hierarchical
representations; inner node; labeled tree families;
trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrenfeucht:1990:PH,
author = "A. Ehrenfeucht and G. Rozenberg",
title = "Primitivity is hereditary for $2$-structures",
journal = j-THEOR-COMP-SCI,
volume = "70",
number = "3",
pages = "343--358",
day = "15",
month = feb,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Dept. of Comput. Sci., Colorado Univ., Boulder, CO,
USA",
keywords = "2-structures; graph theory; hereditary; primitivity;
trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Aggarwal:1990:CCP,
author = "A. Aggarwal and A. K. Chandra and M. Snir",
title = "Communication complexity of {PRAMs}",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "1",
pages = "3--28",
day = "13",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C5320G
(Semiconductor storage)",
corpsource = "IBM, Thomas J. Watson Res. Center, Yorktown Heights,
NY, USA",
keywords = "arithmetic; binary tree; communication complexity;
computational complexity; computational requirements;
local memory; LPRAM; random-access storage; semirings;
trees (mathematics)",
pubcountry = "Netherlands",
treatment = "P Practical; T Theoretical or Mathematical",
}
@Article{Culik:1990:NTP,
author = "K. {Culik, II}",
title = "New techniques for proving the decidability of
equivalence problems",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "1",
pages = "29--45",
day = "13",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., South Carolina Univ., Columbia,
SC, USA",
keywords = "D0L equivalence problem; decidability; Ehrenfeucht
conjecture; languages; proving; relations",
pubcountry = "Netherlands",
treatment = "B Bibliography; T Theoretical or Mathematical",
}
@Article{Gruska:1990:SSP,
author = "J. Gruska",
title = "Synthesis, structure and power of systolic
computations",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "1",
pages = "47--77",
day = "13",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C5220 (Computer architecture)",
corpsource = "Inst. of Tech. Cybern., Slovak Acad. of Sci.,
Bratislava, Czechoslovakia",
keywords = "linear array computations; models; parallel
architectures; power; simulations; structure;
synthesis; systolic architectures; systolic
computations; transformations; tree",
pubcountry = "Netherlands",
treatment = "B Bibliography; P Practical; T Theoretical or
Mathematical",
}
@Article{Hartmanis:1990:NDS,
author = "J. Hartmanis",
title = "New developments in structural complexity theory",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "1",
pages = "79--93",
day = "13",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Cornell Univ., Ithaca, NY,
USA",
keywords = "computational complexity; structural complexity
theory; working hypotheses",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kruskal:1990:CTE,
author = "C. P. Kruskal and L. Rudolph and M. Snir",
title = "A complexity theory of efficient parallel algorithms",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "1",
pages = "95--132",
day = "13",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Inst. for Adv. Comput. Studies, Maryland Univ.,
College Park, MD, USA",
keywords = "complexity theory; computational complexity; EP;
parallel algorithms; parallel computation; robustness;
running time; simulating machine",
pubcountry = "Netherlands",
treatment = "B Bibliography; T Theoretical or Mathematical",
}
@Article{Thiagarajan:1990:SBA,
author = "P. S. Thiagarajan",
title = "Some behavioural aspects of net theory",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "1",
pages = "133--153",
day = "13",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Inst. of Math. Sci., Madras, India",
keywords = "behavioural aspects; behavioural descriptions;
causality; concurrency; conflict; distributed systems;
elementary net systems; net theory; Petri nets; system
model",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Weijland:1990:SLP,
author = "W. P. Weijland",
title = "Semantics for logic programs without occur check",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "1",
pages = "155--174",
day = "13",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6110 (Systems analysis and programming); C6140D
(High level languages)",
corpsource = "Centre for Math. and Comput. Sci., Amsterdam,
Netherlands",
keywords = "completeness; CSLD- resolution; logic programming;
logic programs; PROLOG; Prolog; semantics;
SLD-resolution; soundness",
pubcountry = "Netherlands",
treatment = "P Practical; T Theoretical or Mathematical",
}
@Article{Anonymous:1990:IFW,
author = "Anonymous",
title = "{INFORMATIKA 88. 2nd French-Soviet Workshop on
Methods of Compilation and Program Construction}",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "2",
pages = "??--??",
day = "30",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C6150C (Compilers,
interpreters and other processors)",
conflocation = "Nice, France; 23-25 Feb. 1988",
conftitle = "INFORMATIKA 88. 2nd French-Soviet Workshop on Methods
of Compilation and Program Construction",
keywords = "algorithm; alternative structure compilation;
attribute models; automatic program synthesis;
compilation; computational; constructive system; cut;
denotational semantics; formal languages; functional
equivalence; mixed computation; operational; plasma
pattern; program compilers; program schemes; Prolog",
pubcountry = "Netherlands",
treatment = "P Practical; T Theoretical or Mathematical",
}
@Article{Arcangeli:1990:PPP,
author = "J.-P. Arcangeli and C. Pomian",
title = "Principles of plasma pattern and alternative structure
compilation",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "2",
pages = "177--191",
day = "30",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6150C (Compilers, interpreters and other
processors)",
conflocation = "Nice, France; 23-25 Feb. 1988",
conftitle = "INFORMATIKA 88. 2nd French-Soviet Workshop on Methods
of Compilation and Program Construction",
corpsource = "Lab. Langages et Syst. Inf., Univ. Paul Sabatier,
Toulouse, France",
keywords = "alternative structure compilation; backtracking;
formal model; message parsing; pattern codes; pattern
matching; plasma pattern; program compilers; simple
jumps; single pass compiler; syntax",
pubcountry = "Netherlands",
treatment = "P Practical",
}
@Article{Billaud:1990:SOD,
author = "M. Billaud",
title = "Simple operational and denotational semantics for
{Prolog} with cut",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "2",
pages = "193--208",
day = "30",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6110 (Systems analysis and programming); C6140D
(High level languages); C6150C (Compilers, interpreters
and other processors)",
conflocation = "Nice, France; 23-25 Feb. 1988",
conftitle = "INFORMATIKA 88. 2nd French-Soviet Workshop on Methods
of Compilation and Program Construction",
corpsource = "Dept. Inf., Bordeaux I Univ., Talence, France",
keywords = "behaviour; control structures; cut operator;
denotational semantics; equivalence rules; if-then-else
operator; logic programming; operational semantics;
program interpreters; PROLOG; Prolog dialects; Prolog
programs; reference interpreter; rewriting system;
stream-generating functions",
pubcountry = "Netherlands",
treatment = "P Practical",
}
@Article{Bulyonkov:1990:MCC,
author = "M. A. Bulyonkov",
title = "Mixed computation and compilation: new approaches to
old problems",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "2",
pages = "209--226",
day = "30",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6150C (Compilers, interpreters and other
processors)",
conflocation = "Nice, France; 23-25 Feb. 1988",
conftitle = "INFORMATIKA 88. 2nd French-Soviet Workshop on Methods
of Compilation and Program Construction",
corpsource = "Comput. Center, Acad. of Sci., Novosibirsk, Ukrainian
SSR, USSR",
keywords = "abstract interpretation; compilation; incremental
computation; metaprogramming; mixed computation;
partial evaluator; polyvariancy; program compilers;
program manipulations; sequential decomposition;
survey; user control",
pubcountry = "Netherlands",
treatment = "P Practical",
}
@Article{Galmiche:1990:CSA,
author = "D. Galmiche",
title = "Constructive system for automatic program synthesis",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "2",
pages = "227--239",
day = "30",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C6150C (Compilers,
interpreters and other processors)",
conflocation = "Nice, France; 23-25 Feb. 1988",
conftitle = "INFORMATIKA 88. 2nd French-Soviet Workshop on Methods
of Compilation and Program Construction",
corpsource = "Centre de Recherche en Inf. de Nancy, Vandoeuvre les
Nancy, France",
keywords = "automatic program synthesis; automatized program
synthesis; constants; constructive system; grammars;
higher-order calculus; intuitionistic type theory;
lambda-expressions; logical theory; program
compilers; programmation; programming proofs; typed
lambda-calculus; types",
pubcountry = "Netherlands",
treatment = "P Practical; T Theoretical or Mathematical",
}
@Article{Penjam:1990:CAM,
author = "J. Penjam",
title = "Computational and attribute models of formal
languages",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "2",
pages = "241--264",
day = "30",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
conflocation = "Nice, France; 23-25 Feb. 1988",
conftitle = "INFORMATIKA 88. 2nd French-Soviet Workshop on Methods
of Compilation and Program Construction",
corpsource = "Inst. of Cybern., Estonian Acad. of Sci., Tallinn,
Estonian SSR, USSR",
keywords = "algorithms; attribute evaluation programs; attribute
grammars; attribute models; compiler specification;
computational models; formal languages; NUT-system;
program specification; programming languages;
semantically equivalent computational models;
semantics; structural synthesis",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Sabelfeld:1990:ADF,
author = "V. K. Sabelfeld",
title = "An algorithm deciding functional equivalence in a new
class of program schemes",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "2",
pages = "265--279",
day = "30",
month = mar,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
conflocation = "Nice, France; 23-25 Feb. 1988",
conftitle = "INFORMATIKA 88. 2nd French-Soviet Workshop on Methods
of Compilation and Program Construction",
corpsource = "Comput. Center, Acad. of Sci., Novosibirsk, USSR",
keywords = "algorithm; automata theory; decidability; equivalence
classes; formal languages; free interpretation;
functional equivalence; predicate; program
optimization; program schemes; program verification;
through schemes; undecidable problem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Senizergues:1990:SDP,
author = "G. Senizergues",
title = "Some decision problems about controlled rewriting
systems",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "3",
pages = "281--346",
day = "10",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Lab. of Comput. Sci., Bordeaux I Univ., Talence,
France",
keywords = "c-systems; class equivalence problem; class inclusion
problem; confluence problem; controlled rewriting
systems; decidability; decidable; decision problems;
deterministic context-free languages; equivalence
classes; equivalence problem; finite semi-Thue systems;
finitely generated congruences; partial confluence
problem; recursively equivalent; refinement problem;
rewriting systems; syntactic congruence; undecidable;
word problem",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrig:1990:CDT,
author = "H. Ehrig and F. Parisi-Presicce and P. Boehm and C.
Rieckhoff and C. Dimitrovici and M. Grosse-Rhode",
title = "Combining data type and recursive process
specifications using projection algebras",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "3",
pages = "347--380",
day = "10",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra)",
corpsource = "Tech. Univ. Berlin, Inst. fur Software und Theor.
Inf., West Germany",
keywords = "algebra; algebraic semantics; algebraic specification;
complete process algebras; data type process
specifications; metric approach; nonterminating
processes; projection algebras; projection spaces;
recursive process specifications; recursively defined
processes",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Dulucq:1990:FSS,
author = "S. Dulucq and D. Gouyou-Beauchamps",
title = "On the factors of the {Sturmian} sequences",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "3",
pages = "381--400",
day = "10",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1120 (Analysis); C4150 (Nonlinear and functional
equations); C4210 (Formal logic)",
corpsource = "UER Math. et Inf., Bordeaux I Univ., Talence, France",
keywords = "alphabet; Euler function; formal languages; functional
equation; functional equations; generating function;
language; line; slope; Sturmian sequences; word",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Gibbons:1990:OEO,
author = "A. Gibbons and W. Rytter",
title = "Optimally edge-colouring outerplanar graphs is in
{NC}",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "3",
pages = "401--411",
day = "10",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Warwick Univ., Coventry, UK",
keywords = "computational complexity; graph colouring; optimal
edge colouring; outerplanar graphs; P-RAM; parallel
random access machine; polylogarithmic time; write
conflicts",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Manes:1990:TCI,
author = "E. G. Manes",
title = "A transformational characterization of if-then-else",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "3",
pages = "413--417",
day = "10",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Math. and Stat., Massachusetts Univ.,
Amherst, MA, USA",
keywords = "if-then-else; partial functions; programming theory;
sets; transformational characterization",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Chrobak:1990:DSU,
author = "M. Chrobak and T. Szymacha and A. Krawczyk",
title = "A data structure useful for finding {Hamiltonian}
cycles",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "3",
pages = "419--424",
day = "10",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory); C6120 (File
organisation)",
corpsource = "Inst. of Inf., Warsaw Univ., Poland",
keywords = "algorithm; balanced trees; complexity; computational
complexity; data structure; data structures;
Hamiltonian cycles; reversals; reversible AVL-tree;
sequence maintenance; trees (mathematics)",
pubcountry = "Netherlands",
treatment = "P Practical; T Theoretical or Mathematical",
}
@Article{Skandalis:1990:NOR,
author = "K. Skandalis",
title = "Nonrecursiveness of the operations on real numbers",
journal = j-THEOR-COMP-SCI,
volume = "71",
number = "3",
pages = "425--429",
day = "10",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Dept. of Math., Crete Univ., Greece",
keywords = "nonrecursiveness; number theory; real numbers",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Sakarovitch:1990:F,
author = "J. Sakarovitch",
title = "Foreword",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "1",
pages = "1--??",
day = "25",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Fri Nov 21 19:16:33 MST 1997",
acknowledgement = ack-nhfb,
}
@Article{Budach:1990:TIC,
author = "L. Budach",
title = "Topological invariants of classification problems",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "1",
pages = "3--26",
day = "25",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic); C4240 (Programming and algorithm theory); C4250
(Database theory)",
corpsource = "Humboldt-Univ., Sektion Math., Berlin, East Germany",
keywords = "Betti numbers; classification problems; complexity;
computational complexity; database theory;
Euler-Poincare characteristic; formal logic; invariant
structures; questionnaires; set theory; topological
invariants",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hashiguchi:1990:ILT,
author = "K. Hashiguchi",
title = "Improved limitedness theorems on finite automata with
distance functions",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "1",
pages = "27--38",
day = "25",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Inf. and Comput. Sci., Toyohashi Univ. of
Technol., Japan",
keywords = "distance functions; finite automata; limitedness
theorems; sufficient condition; words",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
xxtitle = "Improved limitedness theorems of finite automata with
distance functions",
}
@Article{Carpi:1990:NWR,
author = "A. Carpi and A. {de Luca}",
title = "Non-repetitive words relative to a rewriting system",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "1",
pages = "39--53",
day = "25",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dipartimento di Matematica ed Applicazioni, Napoli
Univ., Italy",
keywords = "context-free languages; context-free systems;
decidability; decision problems; nonrepetitive words;
rewriting system; rewriting systems; semi-commutations;
square-free word; symmetric rewriting systems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Restivo:1990:CLC,
author = "A. Restivo",
title = "Codes and local constraints",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "1",
pages = "55--64",
day = "25",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "B6120B (Codes); C4210 (Formal logic); C4220
(Automata theory); C4240 (Programming and algorithm
theory)",
corpsource = "Dipartimento di Matematica e Applicazioni, Palermo
Univ., Italy",
keywords = "automata; automata theory; codes; completeness;
encoding; engineering applications; extremal
properties; forbidden words; formal languages;
languages; local constraints; maximality",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Simon:1990:FFF,
author = "I. Simon",
title = "Factorization forests of finite height",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "1",
pages = "65--94",
day = "25",
month = apr,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Instituto de Matematica e Estatistica, Sao Paulo
Univ., Brazil",
keywords = "bounded gap Ramsey-type property; factorization
forests; finite height; finite semigroup; formal
languages; free semigroup; group theory; morphism;
Ramseyan factorization forest; vertex set",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Anonymous:1990:CCA,
author = "Anonymous",
title = "{CAAP} '88 --- 13th Colloque sur les Arbres en
Alg{\`e}bre et en Programmation. ({French})
[{Colloquium} on Trees in Algebra and Programming]",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "??--??",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic); C4240 (Programming and algorithm theory)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
keywords = "A/sup 2/CCS; algebra; algorithm theory; atomic actions
for CCS; AVL trees; combinatory differential fields;
complexity; Dactl; data structures; directed
hypergraphs; dynamic algorithms; equational completion;
formal logic; functional languages; Hennessy-Milner
Logic; logic programming; narrowing strategies;
order-sorted algebras; parallelism; path length; proof
systems; recursion; rewrite based algebraic
specifications; rewriting systems; satisfiability;
specification languages; term rewrite languages; trees
(mathematics)",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Dauchet:1990:E,
author = "M. Dauchet and J. L. Remy",
title = "Editorial",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "95--??",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Fri Nov 21 19:16:33 MST 1997",
acknowledgement = ack-nhfb,
}
@Article{Ausiello:1990:DMD,
author = "G. Ausiello and U. Nanni and G. F. Italiano",
title = "Dynamic maintenance of directed hypergraphs",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "97--117",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory); C4250 (Database
theory); C6120 (File organisation)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "Dipartimento di Inf. e Sistemistica, Rome Univ.,
Italy",
keywords = "computation theory; data structure; data structures;
directed graphs; directed hypergraphs; hyperarcs",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Engeler:1990:CDF,
author = "E. Engeler",
title = "Combinatory differential fields",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "119--131",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "Eidgenossische Tech. Hochschule-Zentrum, Zurich,
Switzerland",
keywords = "algebra; closed-form solvability; combinatory
equations; combinatory field; differential fields;
Liouville-Ritt-Risch theory; problem solving",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Echahed:1990:CNS,
author = "R. Echahed",
title = "On completeness of narrowing strategies",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "133--146",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "LIFIA/IMAG, Inst. Nat. Polytech., Grenoble, France",
keywords = "algebraic specifications; completeness; E-unification;
E-unifiers; formal specification; functional languages;
functional programming; high level languages; LPG; many
sorted algebras; narrowing occurrence selection
strategy; narrowing strategies; reduction relations;
relational languages; rewriting systems; specification
languages; syntactical criteria; term rewriting
systems; unification",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Francon:1990:ADA,
author = "J. Francon and B. Randrianarimanana and R. Schott",
title = "Analysis of dynamic algorithms in {Knuth}'s model",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "147--167",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6120
(File organisation)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "Dept. Inf., Univ. Louis Pasteur, Strasbourg, France",
keywords = "algorithm theory; continued fractions; data
structures; deletions; dictionaries; dynamic
algorithms; dynamically varying data structures;
insertions; integrated costs; limiting distributions;
linear lists; negative query; orthogonal polynomials;
priority queues; statistical analysis; statistical
model",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Gnaedig:1990:ECO,
author = "I. Gnaedig and C. Kirchner and H. Kirchner",
title = "Equational completion in order-sorted algebras",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "169--202",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "LORIA, Vandoeuvre-les-Nancy, France",
keywords = "algebra; completion procedures; equational term
rewriting systems; formal logic; logic programming;
order-sorted algebras; order-sorted equational logic;
proof orderings; rewriting systems",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Gorrieri:1990:AA,
author = "R. Gorrieri and S. Marchetti and U. Montanari",
title = "{$A^2 CCS$}: atomic actions for {$CCS$}",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "203--223",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "Dipartimento di Inf., Pisa Univ., Italy",
keywords = "A/sup 2/CCS; atomic actions; calculus for
Communicating Systems; CCS; compositional transition
systems; formal languages; prefix operation;
specification languages; underlined action symbol",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Kennaway:1990:ITR,
author = "R. Kennaway",
title = "Implementing term rewrite languages in {Dactl}",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "225--249",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sun Oct 25 13:16:00 1998",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "Sch. of Inf. Syst., East Anglia Univ., Norwich, UK",
keywords = "Dactl; evaluation strategy; functional language;
functional programming; graph rewriting; low-level
language; parallel machines; rewriting systems",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Klein:1990:TUB,
author = "R. Klein and D. Wood",
title = "A tight upper bound for the path length of {AVL}
trees",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "251--264",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "Inst. f{\"u}r Inf., Freiburg Univ., West Germany",
keywords = "AVL trees; brother trees; comparison cost;
computational complexity; path length; search problems;
tight upper bound; trees (mathematics)",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Larsen:1990:PSS,
author = "K. G. Larsen",
title = "Proof systems for satisfiability in {Hennessy-Milner
Logic} with recursion",
journal = j-THEOR-COMP-SCI,
volume = "72",
number = "2-3",
pages = "265--288",
day = "23",
month = may,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
conflocation = "Nancy, France; 21-25 March 1988",
conftitle = "CAAP '88 --- 13th Colloque sur les Arbres en Algebre
et en Programmation (Colloquium on Trees in Algebra and
Programming)",
corpsource = "Aalborg Univ. Centre, Denmark",
keywords = "complete proof systems; concurrent programming;
decision procedure; finite-state process; formal logic;
Hennessy-Milner logic with recursion; introduction
rule; observational equivalence; parallel programming;
PROLOG; recursive functions; recursively specified
formula; satisfiability; specification; theorem
proving",
pubcountry = "Netherlands",
sponsororg = "AFCET; BCS; GI",
treatment = "T Theoretical or Mathematical",
}
@Article{Jacopini:1990:RPC,
author = "G. Jacopini and G. Sontacchi",
title = "Reversible parallel computation: an evolving
space-model",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "1",
pages = "1--46",
day = "08",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Dipartimento di Matematica, Roma Univ., Italia,
Italy",
keywords = "algorithm theory; colored spaces; compressibility of
information; computation theory; computer science;
computing functions; Euclidean spaces; finite automata;
microscopic reversibility; parallel computation;
parallel processing; space-model; transmission; Turing
non-polynomial functions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kroger:1990:IAT,
author = "F. Kroger",
title = "On the interpretability of arithmetic in temporal
logic",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "1",
pages = "47--60",
day = "08",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. fur Inf., Ludwig-Maximilians-Univ. Munchen, West
Germany",
keywords = "arithmetic; categorical axiomatizations; first-order
theory; formal logic; incompleteness results;
interpretability; temporal logic",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Lavault:1990:EAM,
author = "C. Lavault",
title = "Exact average message complexity values for
distributed election on bidirectional rings of
processors",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "1",
pages = "61--79",
day = "08",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4230B (Combinatorial switching theory); C4240
(Programming and algorithm theory)",
corpsource = "INRIA, le Chesnay, France",
keywords = "bidirectional rings; combinatorial enumeration
methods; computational complexity; distributed election
algorithm; distributed leader; distributed processing;
distributed system; message complexity values;
multiprocessor interconnection networks; rings of
processors",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Varricchio:1990:FFM,
author = "S. Varricchio",
title = "Factorizations of free monoids and unavoidable
regularities",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "1",
pages = "81--89",
day = "08",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Rome Univ., Italy",
keywords = "Burnside problem; combinatorics; factorizations;
finite alphabet; formal languages; free monoids;
searching; unavoidable regularities",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Jerrum:1990:FUG,
author = "M. Jerrum and A. Sinclair",
title = "Fast uniform generation of regular graphs",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "1",
pages = "91--100",
day = "08",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Edinburgh Univ., UK",
keywords = "computational complexity; degree sequences; graph
theory; labelled graph; n-vertex sequences; polynomial
time; rapidly convergent stochastic process; regular
graphs; regular sequences; uniform generation",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Huwig:1990:NIC,
author = "H. Huwig and A. Poigne",
title = "A note on inconsistencies caused by fixpoints in a
{Cartesian} closed category",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "1",
pages = "101--112",
day = "08",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Abt. Inf., Dortmund Univ., West Germany",
keywords = "Cartesian closed category; category theory; computer
science; coproducts; domain theory; fixpoints;
inconsistencies; programming; programming theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ganzinger:1990:F,
author = "H. Ganzinger",
title = "Foreword",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "2",
pages = "119--??",
day = "22",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Fri Nov 21 19:16:33 MST 1997",
acknowledgement = ack-nhfb,
}
@Article{Aiken:1990:TCP,
author = "A. Aiken",
title = "A theory of compaction-based parallelization",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "2",
pages = "121--154",
day = "22",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6110
(Systems analysis and programming)",
corpsource = "IBM Almaden Res. Center, San Jose, CA, USA",
keywords = "compaction-based parallelization; doacross; formal
system; infinite sequences; limits; measure;
multiprocessor machines; parallel algorithms; parallel
programming; program improvement; software pipelining;
transformational system; transformations; vector
machines; vectorization; VLIW machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Fuh:1990:TIS,
author = "You-Chin C. Fuh and P. Mishra",
title = "Type inference with subtypes",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "2",
pages = "155--175",
day = "22",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1230 (Artificial intelligence); C4240 (Programming
and algorithm theory)",
corpsource = "Dept. of Comput. Sci., State Univ. of New York, Stony
Brook, NY, USA",
keywords = "classical unification algorithm; inference mechanisms;
MATCH; polymorphic type inference; principal type
property; principal types; programming theory; proof of
correctness; structured theory; subtypes; syntactic
completeness; type transformation; type-checker",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Giegerich:1990:CSI,
author = "R. Giegerich",
title = "Code selection by inversion of order-sorted derivors",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "2",
pages = "177--211",
day = "22",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6140D
(High level languages)",
corpsource = "Tech. Fak., Bielefeld Univ., West Germany",
keywords = "code selection problem; code selector specification;
completeness; expressive power; formal criteria;
hierarchic derivor; high level languages; intermediate
languages; inversion; nonsyntactic subtasks;
order-sorted derivors; order-sorted term algebras;
pattern matching; programming theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Horwitz:1990:ARQ,
author = "S. Horwitz",
title = "Adding relational query facilities to software
development environments",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "2",
pages = "213--230",
day = "22",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C4250
(Database theory); C6115 (Programming support); C6140D
(High level languages); C6160D (Relational DBMS)",
corpsource = "Dept. of Comput. Sci., Wisconsin-Univ., Madison, WI,
USA",
keywords = "database theory; implicit relations; nonrelational
data structures; nonstandard relational operations;
programming environments; programming theory; query
evaluation; query languages; relational databases;
relational query facilities; relationally-attributed
grammars; software development environments; transitive
closure",
pubcountry = "Netherlands",
treatment = "P Practical; T Theoretical or Mathematical",
}
@Article{Wadler:1990:DTP,
author = "P. Wadler",
title = "Deforestation: transforming programs to eliminate
trees",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "2",
pages = "231--248",
day = "22",
month = jun,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory); C6150C (Compilers,
interpreters and other processors)",
corpsource = "Dept. of Comput. Sci., Glasgow Univ., UK",
keywords = "algorithm; deforestation; eliminate; intermediate
trees; optimizing compiler; program compilers; program
transformation; programming theory; syntactic form;
trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Beigel:1990:BRC,
author = "R. Beigel",
title = "Bi-immunity results for cheatable sets",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "3",
pages = "249--263",
day = "22",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Johns Hopkins Univ., Baltimore,
MD, USA",
keywords = "bi-immunity; cheatable sets; computational complexity;
parallel programming; parallel queries; polynomial-time
algorithm; recursive set; set theory; time complexity
classes",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Chen:1990:DBO,
author = "Jian-er Chen",
title = "The difference between one tape and two tapes: with
respect to reversal complexity",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "3",
pages = "265--278",
day = "22",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Math., Columbia Univ., New York, NY, USA",
keywords = "1-tape; 2-tape; complexity measure; computational
complexity; reversal complexity; Turing machine models;
Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hoffmann:1990:RNG,
author = "J. Hoffmann and M. G. Main",
title = "Results on {NLC} grammars with one-letter terminal
alphabets",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "3",
pages = "279--294",
day = "22",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Dept. of Comput. Sci., Colorado Univ., Boulder, CO,
USA",
keywords = "grammars; graph languages; graph theory; language
generating mechanism; NLC grammars; node label
controlled graph grammars; restricted connection
relation; terminal alphabets",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kim:1990:CDR,
author = "Changwook Kim",
title = "Complexity and decidability for restricted classes of
picture languages",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "3",
pages = "295--311",
day = "22",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Sch. of Electr. Eng. and Comput. Sci., Oklahoma Univ.,
Norman, OK, USA",
keywords = "complexity; computational complexity; containment;
decidability; equivalence; formal languages; picture
languages; stripe picture languages; three-way picture
languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Robson:1990:STB,
author = "J. M. Robson",
title = "Strong time bounds: non-computable bounds and a
hierarchy theorem",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "3",
pages = "313--317",
day = "22",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Comput. Sci., Australian Nat. Univ.,
Canberra, ACT, Australia",
keywords = "computability; computational complexity; hierarchy
theorem; non-computable bounds; RAM program; time
bounds",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bertossi:1990:SMW,
author = "A. A. Bertossi and F. Luccio and E. Lodi and L.
Pagli",
title = "String matching with weighted errors",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "3",
pages = "319--328",
day = "22",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dipartimento di Inf., Pisa Univ., Italy",
keywords = "computational complexity; parallel algorithms;
parallel time; PRAM model; sequential time; string
matching problem; weighted differences; weighted
errors",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Head:1990:SSM,
author = "T. Head",
title = "The set of strings mapped into a submonoid by iterates
of a morphism",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "3",
pages = "329--333",
day = "22",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math. Sci., State Univ. of New York,
Binghamton, NY, USA",
keywords = "constructable regular language; endomorphism; formal
languages; morphisms; strings; submonoid",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Schmitt:1990:HAI,
author = "W. Schmitt",
title = "{Hopf} algebras and identities in free partially
commutative monoids",
journal = j-THEOR-COMP-SCI,
volume = "73",
number = "3",
pages = "335--340",
day = "22",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Univ. of Southern California, Los
Angeles, CA, USA",
keywords = "algebra of polynomials; commutative monoids; formal
languages; Hopf algebras; partially commutative
alphabet; partially commutative words; polynomials",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Diekert:1990:WPT,
author = "V. Diekert",
title = "Word problems over traces which are solvable in linear
time",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "1",
pages = "3--18",
day = "30",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. fur Inf., Tech. Univ. Munchen, West Germany",
keywords = "blocks; cones; confluence; decidability; decidable
word problem; finite complete replacement systems; free
partially commutative monoids; global condition; linear
time; noetherian trace replacement system; semi Thue
systems; trace replacement systems; vector replacement
systems; weight-reducing",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Fussell:1990:SAP,
author = "D. Fussell and R. Thurimella",
title = "Successive approximation in parallel graph
algorithms",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "1",
pages = "19--35",
day = "30",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4130 (Interpolation and function approximation);
C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comp. Sci., Texas Univ., Austin, TX, USA",
keywords = "approximation theory; mesh of trees network model;
neighboring vertices; open ear decomposition algorithm;
parallel algorithms; parallel graph algorithms;
parallel planarity testing; successive algorithm;
triconnectivity",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Gavilanes-Franco:1990:FOL,
author = "A. Gavilanes-Franco and F. Lucio-Carrasco",
title = "A first order logic for partial functions",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "1",
pages = "37--69",
day = "30",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. de Inf. y Autom., Fac. de Matematicas, Univ.
Complutense de Madrid, Spain",
keywords = "calculi; completeness; first order logic; formal
reasoning; many-valued logics; model theory; partial
functions; program effects; semantical motivation;
soundness; three valued logic",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Jancar:1990:DTL,
author = "P. Jancar",
title = "Decidability of a temporal logic problem for {Petri}
nets",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "1",
pages = "71--93",
day = "30",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Min. Inst., Czechoslovak Acad. of Sci., Ostrava,
Czechoslovakia",
keywords = "decidability; decision algorithm; infinite weakly fair
occurrence sequence; open problem; Petri nets; temporal
logic",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Preparata:1990:DPP,
author = "F. P. Preparata and R. Tamassia",
title = "Dynamic planar point location with optimal query
time",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "1",
pages = "95--114",
day = "30",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4190 (Other numerical methods)",
corpsource = "Coordinated Sci. Lab., Illinois Univ., Urbana, IL,
USA",
keywords = "computational geometry; convex planar subdivision;
depletion; dynamic planar point location; insertion;
optimal query time; trapezoid method",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Szepietowski:1990:IDN,
author = "A. Szepietowski",
title = "If deterministic and nondeterministic space
complexities are equal for log log n, then they are
also equal for log n",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "1",
pages = "115--119",
day = "30",
month = jul,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Math., Tech. Univ. of Gdansk, Poland",
keywords = "computational complexity; deterministic space
complexity; nondeterministic space complexities",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Gastin:1990:AMD,
author = "P. Gastin",
title = "An asynchronous model for distributed systems",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "2",
pages = "121--162",
day = "21",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "LITP, Paris 6 Univ., France",
keywords = "asynchronous model; bases; concatenation; concurrency;
CSP; dependency; distributed model; distributed
processing; distributed systems; ESTELLE; finitary
part; formal languages; free partially commutative
monoid; infinitary free monoid; infinite product;
isomorphic; language theory; length; prefix order;
semantics; upper bound",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Gecseg:1990:ARP,
author = "F. Gecseg and H. Jurgensen",
title = "Automata represented by products of soliton automata",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "2",
pages = "163--181",
day = "21",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C5280 (Other digital
techniques)",
corpsource = "Jozsef Attila Tudomanyegyetem Bolyai Intezete, Szeged,
Hungary",
keywords = "automata theory; biocomputers; homomorphic
representations; isomorphic representations; logic;
mathematical model; molecular switching elements;
simulation power; soliton automata; soliton switching;
soliton valves; solitons; transition semigroups",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Oommen:1990:DOE,
author = "B. J. Oommen and E. R. Hansen and J. I. Munro",
title = "Deterministic optimal and expedient move-to-rear list
organizing strategies",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "2",
pages = "183--197",
day = "21",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1140Z (Other and miscellaneous); C4240 (Programming
and algorithm theory); C6130 (Data handling
techniques)",
corpsource = "Sch. of Comput. Sci., Carleton Univ., Ottawa, Ont.,
Canada",
keywords = "absorbing; access probabilities; constant space;
counter-intuitive; descending order; deterministic;
expedient; linear space; list processing; Markovian
representation; move-to-rear list organizing; optimal;
probability; programming theory; self-organizing;
sorting",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Okulicka:1990:PC,
author = "F. Okulicka",
title = "On priority in {COSY}",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "2",
pages = "199--216",
day = "21",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)C4240 (Programming
and algorithm theory); C6150J (Operating systems)",
corpsource = "Inst. of Math., Warsaw Univ. of Technol., Poland",
keywords = "concurrency control; COSY path expressions;
decomposition theorem; formal semantics; Petri nets;
priority path; priority relation; programming theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hartmanis:1990:RMS,
author = "J. Hartmanis and L. A. Hemachandra",
title = "Robust machine saccept easy sets",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "2",
pages = "217--225",
day = "21",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Comput. Sci., Cornell Univ., Ithaca, NY,
USA",
keywords = "computational property; easy sets; languages;
nondeterministic oracle access; relativizations;
robustly categorical machines; robustly complementary
machines; robustly Sigma *-accepting machines; robustly
Sigma *-spanning machines; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bezem:1990:CRR,
author = "M. Bezem",
title = "Completeness of resolution revisited",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "2",
pages = "227--237",
day = "21",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Centre for Math. and Comput. Sci., Amsterdam,
Netherlands",
keywords = "cardinality; clauses; completeness proofs; ground
clauses; ground resolution; infinite sets; language;
redundancies; set theory; Zorn Lemma",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Huttel:1990:SCB,
author = "H. Huttel",
title = "{SnS} can be modally characterized",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "2",
pages = "239--248",
day = "21",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Lab. for Found. of Comput. Sci., Edinburgh Univ., UK",
keywords = "equivalence; equivalence classes; formal languages;
formal logic; label set; Milner; modal mu-calculus;
Rabin recognizable tree languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kummer:1990:EPP,
author = "M. Kummer",
title = "An easy priority-free proof of a theorem of
Friedberg",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "2",
pages = "249--251",
day = "21",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics)",
corpsource = "Fakultat fur Inf., Karlsruhe Univ., West Germany",
keywords = "enumeration; Friedberg; partial recursive one-place
functions; priority-free proof; set; set theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Zhang:1990:PNM,
author = "Jingzhong Zhang and Lu Yang and M. Deng",
title = "The parallel numerical method of mechanical theorem
proving",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "3",
pages = "253--271",
day = "28",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4190 (Other numerical methods); C4210 (Formal
logic)",
corpsource = "Inst. of Math. Sci., Acad. Sinica, Chengdu, China",
keywords = "algebraic identity; complexity; geometry theorems;
mechanical theorem proving; multi-instance numerical
verification; nontrivial geometric theorems; parallel
algorithms; parallel numerical method; theorem
proving",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Casas:1990:ASC,
author = "R. Casas and M.-I. Fernandez-Camacho and J.-M.
Steyaert",
title = "Algebraic simplification in computer algebra: an
analysis of bottom-up algorithms",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "3",
pages = "273--298",
day = "28",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1110 (Algebra); C4240 (Programming and algorithm
theory)",
corpsource = "Fac. de Inf., Univ. Politecnica de Catalunya,
Barcelona, Spain",
keywords = "algebra; algebraic expressions; algebraic
simplification; average size; average time complexity;
bottom-up algorithms; computational complexity;
computer algebra; logical expressions; simplification
algorithms; space gain; worst-case behaviour",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{He:1990:EAE,
author = "Xin He",
title = "An efficient algorithm for edge coloring planar graphs
with Delta colors",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "3",
pages = "299--312",
day = "28",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., State Univ. of New York,
Buffalo, NY, USA",
keywords = "computational complexity; edge coloring; efficient
algorithm; graph colouring; maximum degree; planar
graphs; vertices",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Babai:1990:LBC,
author = "L. Babai and P. Pudlak and V. Rodl and E. Szemeredi",
title = "Lower bounds to the complexity of symmetry {Boolean}
functions",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "3",
pages = "313--323",
day = "28",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "E{\"o}tv{\"o}s Univ., Budapest, Hungary",
keywords = "Boolean functions; bounded widths; branching programs;
complexity; computational complexity; lower bounds;
symmetry Boolean functions; unbounded widths",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hertrampf:1990:RAM,
author = "U. Hertrampf",
title = "Relations among mod-classes",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "3",
pages = "325--328",
day = "28",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Inst. for Inf., Wurzburg Univ., West Germany",
keywords = "closed under union; deterministic polynomial time
computation; mod-classes; oracle answer; prime
divisors; relations; residue class modulo; subclasses;
Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Romeuf:1990:PAS,
author = "J.-F. Romeuf",
title = "A polynomial algorithm for solving systems of two
linear {Diophantine} equations",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "3",
pages = "329--340",
day = "28",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4140 (Linear algebra); C4240 (Programming and
algorithm theory)",
corpsource = "Lab. d'Inf., Rouen Univ., Mont-Saint-Aignan, France",
keywords = "absolute values; complexity; computational complexity;
linear algebra; linear diophantine equations; max;
minimal length solution; polynomial algorithm; rational
expression; upper bounds; variables",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Anselmo:1990:ZCT,
author = "M. Anselmo",
title = "On zigzag codes and their decidability",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "3",
pages = "341--354",
day = "28",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "B6120B (Codes); C4210 (Formal logic); C4220
(Automata theory); C6130 (Data handling techniques)",
corpsource = "Lab. de'Inf. Theor. et Programmation, Paris Univ.,
France",
keywords = "automata theory; codes; crossing sequences;
decidability; nonambiguous; regular language; two-way
automata; zigzag codes; zigzag factorizations",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Szymanski:1990:CAR,
author = "J. Szymanski",
title = "On the complexity of algorithms on recursive trees",
journal = j-THEOR-COMP-SCI,
volume = "74",
number = "3",
pages = "355--361",
day = "28",
month = aug,
year = "1990",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:24:22 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Inst. of Math., Tech. Univ., Poznan, Poland",
keywords = "computational complexity; degree path lengths; mean
path lengths; recursive tree a