%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "1.06",
%%% date = "05 November 2003",
%%% time = "09:20:43 MST",
%%% filename = "tcs1985.bib",
%%% address = "Center for Scientific Computing
%%% University of Utah
%%% Department of Mathematics, 110 LCB
%%% 155 S 1400 E RM 233
%%% Salt Lake City, UT 84112-0090
%%% USA",
%%% telephone = "+1 801 581 5254",
%%% FAX = "+1 801 581 4148",
%%% URL = "http://www.math.utah.edu/~beebe",
%%% checksum = "64846 17661 74067 702888",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at computer.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 1985--1989;
%%% 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.06, the year coverage looked
%%% like this:
%%%
%%% 1985 ( 152) 1992 ( 0) 1999 ( 0)
%%% 1986 ( 124) 1993 ( 0) 2000 ( 0)
%%% 1987 ( 110) 1994 ( 0) 2001 ( 0)
%%% 1988 ( 119) 1995 ( 0) 2002 ( 0)
%%% 1989 ( 134) 1996 ( 0) 2003 ( 1)
%%%
%%% Article: 634
%%% Proceedings: 6
%%%
%%% Total entries: 640
%%%
%%% 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, 110 LCB,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
%%% ====================================================================
%%% Journal abbreviations:
@String{j-THEOR-COMP-SCI = "Theoretical Computer Science"}
%%% ====================================================================
%%% Publisher abbreviations:
@String{pub-NH = "North-Hol{\-}land"}
@String{pub-NH:adr = "Amsterdam, The Netherlands"}
%%% ====================================================================
%%% Bibliography entries, sorted in publication order:
@Article{Lange:1985:RWS,
author = "K.-J. Lange and E. Welzl",
title = "Recurrent words and simultaneous growth in {T0L}
systems",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "1",
pages = "1--15",
month = jan,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Fachbereich Inf., Hamburg Univ., West Germany",
keywords = "context-free grammars; context-free languages;
decidability results; Markov DT0L systems; PSPACE-hard;
recurrent words; simultaneous growth; T0L systems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Stern:1985:CSC,
author = "J. Stern",
title = "Characterizations of some classes of regular events",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "1",
pages = "17--42",
month = jan,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Math., Caen Univ., France",
keywords = "automata theory; characterizations; minimal automaton;
piecewise testable events; regular events",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Bloom:1985:LCO,
author = "S. L. Bloom and D. R. Troeger",
title = "A logical characterization of observation
equivalence",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "1",
pages = "43--53",
month = jan,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Pure and Appl. Math., Stevens Inst. of
Technol., Hoboken, NJ, USA",
keywords = "finitary formal language; formal languages; logical
characterization; observation equivalence;
omega-conjunctions; quantification; regular trace
language; S-TL; synchronisation; synchronization trees;
trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Edelsbrunner:1985:FTS,
author = "H. Edelsbrunner",
title = "Finding transversals for sets of simple geometric
figures",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "1",
pages = "55--69",
month = jan,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Inst. for Inf. Processing, Tech. Univ. of Graz,
Austria",
keywords = "computational complexity; computer graphics; convex
hull problems; geometric figures; geometric transforms;
transversals",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Metivier:1985:CLR,
author = "Y. Metivier",
title = "Calculation of the length of rewriting chains in free
monoide",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "1",
pages = "71--87",
month = jan,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "UER de Math. et Inf., Bordeaux Univ., Talence,
France",
keywords = "complexity measure; computational complexity; free
monoide; rewriting chains",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Benoit:1985:AT,
author = "C. Benoit",
title = "Axiomatisation of tests",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "1",
pages = "89--107",
month = jan,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Lab. de Marcoussis, Centre de Recherches de la
Compagnie G{\'e}n{\'e}rale d'Electricit{\'e},
Marcoussis, France",
keywords = "axiomatisation; equational theories; formal languages;
function symbol; nonordered algebras",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kapur:1985:MMS,
author = "D. Kapur and M. S. Krishnamoorthy and R. McNaughton
and Narendran and P.",
title = "An {$O(\bmod {T} \bmod ^3)$} algorithm for testing the
{Church-Rosser} property of {Thue} systems",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "1",
pages = "109--114",
month = jan,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "General Electric Co., Res. and Dev. Center,
Schenectady, NY, USA",
keywords = "Church-Rosser property; computational complexity;
linear string-matching algorithm; reduction algorithm;
Thue systems; trees (mathematics)",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
xxnote = "Check math in title??",
}
@Article{Pecuchet:1985:TFA,
author = "J.-P. Pecuchet",
title = "Two-way finite automata and finite words",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "1",
pages = "115--122",
month = jan,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Lab. d'Inf., Fac. des Sci., Mont-Saint-Aigman,
France",
keywords = "finite automata; finite words; formal languages; omega
-language; regular automata; two-way finite automata",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Fribourg:1985:SOT,
author = "L. Fribourg",
title = "A superposition oriented theorem prover",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "129--164",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1230 (Artificial intelligence); C4210 (Formal
logic)",
corpsource = "LITP, Paris, France",
keywords = "binary resolution; clausal superposition; equational
clauses; formal logic; formalism of clauses; inference
rules; locking resolution procedures; resolution;
rewriting; strong restriction; strongly restricted
paramodulation; subsumption; superposition oriented
theorem prover; term simplification; theorem proving",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ausiello:1985:EAV,
author = "G. Ausiello and A. d'Atri and M. Moscarini",
title = "On the existence of acyclic views in a database
scheme",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "165--177",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C4250
(Database theory)",
corpsource = "Dipartimento di Inf. e Sistemistica, Roma Univ.,
Italy",
keywords = "acyclic database schemes; acyclic views;
alpha-acyclicity; Berge-acyclicity; computational
complexity; database theory; gamma-acyclicity;
NP-completeness; relational database theory; relational
databases",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Cori:1985:RSS,
author = "R. Cori and Y. Metivier",
title = "Recognizable subsets of some partially {Abelian}
monoids",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "179--189",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "Bordeaux I Univ., UER de math. et Inf., Talence,
France",
keywords = "connected graph; finite alphabet; formal logic; free
partially abelian monoid; graph theory; noncommuting
pairs; recognisable subsets; set theory",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Memmi:1985:IFN,
author = "G. Memmi and A. Finkel",
title = "An introduction to {FIFO} nets-monogeneous nets: a
subclass of {FIFO} nets",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "191--214",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory); C4240
(Programming and algorithm theory)",
corpsource = "Ecole Nat. Sup{\'e}rieure des Telecommun., Paris,
France",
keywords = "alphabetical FIFO nets; bounded monogeneous nets;
coloured-Petri-net simulation; context-free languages;
coverability graph; decidability; graph theory;
monogeneous FIFO nets; parallel computation model;
parallel processing; programming theory; regular
languages; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kobayashi:1985:PTC,
author = "K. Kobayashi",
title = "On proving time constructibility of functions",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "215--225",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Inf. Sci., Tokyo Inst. of Technol., Japan",
keywords = "deterministic automata; deterministic multitape Turing
machines; functions; sufficient condition; time
constructibility; Turing machines",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Narendran:1985:CRC,
author = "P. Narendran and F. Otto",
title = "Complexity results on the conjugacy problem for
monoids",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "227--243",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Gen Elect. Co., Res. and Dev. Center, Schenectady, NY,
USA",
keywords = "alphabet; computational complexity; conjugacy problem;
decidability; finite almost-confluent Thue system;
finite Church-Rosser Thue system; formal languages;
infinite Church-Rosser Thue system; monoids;
presentations; recursive functions; recursive Thue
systems; recursively enumerable degree",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Plaisted:1985:CDP,
author = "D. A. Plaisted",
title = "Complete divisibility problems for slowly utilized
oracles",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "245--260",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Illinois Univ., Urbana, IL,
USA",
keywords = "complete divisibility problems; computational
complexity; integers; intractability; NP-completeness;
polynomials; root; slowly utilized oracles; sparse
polynomial; unrelativized complexity",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hirose:1985:HCR,
author = "S. Hirose and S. Okawa and M. Yoneda",
title = "A homomorphic characterization of recursively
enumerable languages",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "261--269",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Kanagawa Univ., Yokohama, Japan",
keywords = "Dyck language; formal languages; homomorphic
characterization; homomorphic image; intersection;
minimal linear language; recursive functions;
recursively enumerable languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Pin:1985:AMR,
author = "J.-E. Pin and J. Sakarovitch",
title = "An application of the matrix representation of
transductions",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "271--293",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Paris VI. Univ., France",
keywords = "automata theory; control operations; Dyck-reduction;
formal language theory; formal languages; free-group;
language recognition; matrix representation; monoids;
T0L-systems; transductions",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Head:1985:CPH,
author = "T. Head and J. Wilkinson",
title = "Code properties and homomorphisms of {D0L} systems",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "295--312",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1260 (Information theory); C4210 (Formal logic)",
corpsource = "Dept. of Math. Sci., Alaska Univ., Fairbanks, AK,
USA",
keywords = "alphabet; biprefix codes; codes; commutative
equivalent; context-free languages; D0L systems;
derivative; erasure; finite set; finite symbols;
homomorphic image; homomorphisms; infix codes; linearly
bounded D0L languages; outfix codes; polynomially
bounded D0L languages; prefix codes; singleton; suffix
codes",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Leiss:1985:CTU,
author = "E. Leiss",
title = "On classes of tractable unrestricted regular
expressions",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "313--327",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory); C4240
(Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Houston Univ., TX, USA",
keywords = "Boolean automata; Boolean functions; closure;
computational complexity; context-free languages;
equivalence classes; equivalence problem; finite
automata; intractable complexity; nontrivial
subclasses; reduced automaton; tractable complexity;
tractable unrestricted regular expressions",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Oyamaguchi:1985:DTE,
author = "M. Oyamaguchi",
title = "On the data type extension problem for algebraic
specifications",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "329--336",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6120
(File organisation)",
corpsource = "Fac. of Eng., Mie Univ., Tsu-shi, Japan",
keywords = "abstract data type; algebraic specifications; data
structures; data type extension problem; decidability;
final algebra semantics; programming theory; terminal
algebra semantics",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Kapur:1985:FTS,
author = "D. Kapur and P. Narendran",
title = "A finite {Thue} system with decidable word problem and
without equivalent finite canonical system",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "337--344",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Comput. Sci. Branch, Gen. Electr. Corp. Res. and Dev.,
Schenectady, NY, USA",
keywords = "Church-Rosser property; decidability; decidable word
problem; equivalent finite canonical system; finite
Thue system; formal languages; semiThue systems;
single-axiom Thue system; term rewriting systems",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Sain:1985:SPC,
author = "I. Sain",
title = "A simple proof for the completeness of {Floyd}'s
method",
journal = j-THEOR-COMP-SCI,
volume = "35",
number = "2-3",
pages = "345--348",
month = feb,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Math. Inst., Hungarian Acad. of Sci., Budapest,
Hungary",
keywords = "completeness; continuous traces semantics; Floyd's
method; program semantics; programming theory;
unprovable programs",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Broy:1985:HUN,
author = "M. Broy",
title = "On the {Herbrand-Kleene} universe for nondeterministic
computations",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "1--19",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6150J (Operating systems)",
corpsource = "Passau Univ., West Germany",
keywords = "arbitrary signature; commuting diagram; function
symbols; Herbrand-Kleene universe; infinite tree;
interpretation; multiprocessing programs;
nondeterministic choice operator; nondeterministic
computations; power domain approach; recursive
equation; set-valued function; trees (mathematics)",
pubcountry = "Netherlands",
treatment = "P Practical; T Theoretical or Mathematical",
}
@Article{Engelfriet:1985:DOE,
author = "J. Engelfriet",
title = "Determinacy to (observation equivalence=trace
equivalence)",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "21--25",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Twente Univ. of Technol.,
Enschede, Netherlands",
keywords = "determinacy; nondeterministic behaviour; observation
equivalence; parallel process; programming theory;
trace equivalence",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Janicki:1985:TSS,
author = "R. Janicki",
title = "Transforming sequential systems into concurrent
systems",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "27--58",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Inst. of Electron. Syst., Aalborg Univ., Denmark",
keywords = "abstract resources; cigarette smokers; concurrent
systems; dining philosophers; functionally equivalent
system; multiprocessing systems; necessary and
sufficient conditions; path expressions; programming
theory; readers; sequential systems transformation;
specification; vending machine; writers",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Blum:1985:ONS,
author = "N. Blum",
title = "An {$\Omega(n^4/3)$} lower bound on the monotone
network complexity of the $n^{th}$ degree convolution",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "59--69",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Inst. fur Angewandte Math. und Inf., Univ. des
Saarlandes, Saarbrucken, West Germany",
keywords = "Boolean functions; computational complexity; lower
bound; monotone network complexity; n/sup th/ degree
convolution",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Tiomkin:1985:PDL,
author = "M. L. Tiomkin and J. A. Makowsky",
title = "Propositional dynamic logic with local assignments",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "71--87",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Technion-Israel Inst. of Technol., Haifa, Israel",
keywords = "finitely branching; formal logic; local assignments;
looping; predicate variables; program terms;
propositional dynamic logic; propositional variables;
truth values",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Igarashi:1985:PLR,
author = "Y. Igarashi",
title = "A pumping lemma for real-time deterministic
context-free languages",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "89--97",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Comput. Sci., Gunma Univ., Kiryu, Japan",
keywords = "context-free languages; deterministic automata;
pumping lemma; real-time deterministic context-free
languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{DeFelice:1985:CFC,
author = "C. {De Felice}",
title = "Construction of factorisation codes",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "99--108",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1260 (Information theory)",
corpsource = "LITP, Paris VIII, Univ., France",
keywords = "codes; factorisation codes; finite maximal codes;
finite subset",
language = "French",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Hirose:1985:CSH,
author = "S. Hirose and M. Yoneda",
title = "On the {Chomsky} and {Stanley}'s homomorphic
characterization of context-free languages",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "109--112",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Kanagawa Univ., Yokohama, Japan",
keywords = "context-free languages; Dyck language; homomorphic
characterization; homomorphism",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Ruohonen:1985:EMS,
author = "K. Ruohonen",
title = "On equality of multiplicity sets of regular
languages",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "113--117",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Inst. of Math., Tampere Univ. of Technol., Finland",
keywords = "equality; equivalence problem; formal languages;
multiplicity sets; regular languages",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Scarpellini:1985:CBN,
author = "B. Scarpellini",
title = "Complex {Boolean} networks obtained by
diagonalization",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "119--125",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Basel Univ., Switzerland",
keywords = "Boolean functions; boolean functions; complex Boolean
networks; diagonalization",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Winskel:1985:PM,
author = "G. Winskel",
title = "On powerdomains and modality",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "1",
pages = "127--137",
month = mar,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Comput. Lab., Cambridge Univ., UK",
keywords = "Hoare power domain; modal assertions; modality;
nondeterministic computations; nondeterministic
program; partial correctness; Plotkin power domain;
powerdomains; programming theory; Smyth power domain",
pubcountry = "Netherlands",
treatment = "T Theoretical or Mathematical",
}
@Article{Fenton:1985:GMT,
author = "N. E. Fenton and R. W. Whitty and A. A. Kaposi",
title = "A generalised mathematical theory of structured
programming",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "145--171",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory); C6110 (Systems
analysis and programming)",
corpsource = "Math. Inst., Oxford Univ., Oxford, UK",
keywords = "classification; D-structuredness; flowgraphs; formal
methods; generalised mathematical theory; graph theory;
program control structures; programming theory;
structured programming",
pubcountry = "Netherlands A01",
treatment = "T Theoretical or Mathematical",
}
@Article{Sudborough:1985:CDC,
author = "I. H. Sudborough and E. Welzl",
title = "Complexity and decidability for chain code picture
languages",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "173--202",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Electr. Eng., Northwestern Univ., Evanston,
IL, USA",
keywords = "chain code picture languages; codes; complexity;
computational complexity; decidability; formal
languages; membership problem; NP-complete; picture
description; picture processing; regular languages",
pubcountry = "Netherlands A02",
treatment = "T Theoretical or Mathematical",
}
@Article{Demel:1985:FAC,
author = "J. Demel and M. Demlova and V. Koubek",
title = "Fast algorithms constructing minimal subalgebras,
congruences, and ideals in a finite algebra",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "203--216",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Faculty of Civil Eng., Prague Tech. Univ.,
Czechoslovakia",
keywords = "algebra; congruences; fast algorithms; finite algebra;
finite automata; graph theory; ideals; minimal
nontrivial congruences; minimal subalgebras; running
times; sequential automata",
pubcountry = "Netherlands A03",
treatment = "T Theoretical or Mathematical",
}
@Article{Kaminski:1985:COL,
author = "M. Kaminski",
title = "A classification of omega-regular languages",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "217--229",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Comput. Sci., Waterloo Univ., Ont., Canada",
keywords = "classification; finite automata; formal languages;
invariant property; omega-regular languages",
pubcountry = "Netherlands A04",
treatment = "T Theoretical or Mathematical",
}
@Article{Allender:1985:ILB,
author = "E. Allender and M. M. Klawe",
title = "Improved lower bounds for the cycle detection
problem",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "231--237",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Sch. of Inf. and Comput. Sci., Georgia Inst. of
Technol., Atlanta, GA, USA",
keywords = "cycle detection problem; Floyd's algorithm; lower
bounds; memory locations; programming theory",
pubcountry = "Netherlands A05",
treatment = "T Theoretical or Mathematical",
}
@Article{Fagin:1985:BPC,
author = "R. Fagin and M. M. Klawe and N. J. Pippenger and L.
Stockmeyer",
title = "Bounded-depth, polynomial-size circuits for symmetric
functions",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "239--250",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "IBM Res. Lab., San Jose, CA, USA",
keywords = "Boolean functions; Boolean variables; bounded depth
circuits; polynomial-size circuits; symmetric Boolean
functions; symmetric functions",
pubcountry = "Netherlands A06",
treatment = "T Theoretical or Mathematical",
}
@Article{FarinasDelCerro:1985:DLD,
author = "L. {Farinas Del Cerro} and E. Orlowska",
title = "{DAL-a} logic for data analysis",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "251--264",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Langages et Syst. Inf., Univ. Paul Sabatier, Toulouse,
France",
keywords = "data analysis logic; deductive system; formal logic;
logic language; logic tools; proof procedures",
pubcountry = "Netherlands A07",
treatment = "T Theoretical or Mathematical",
}
@Article{Jerrum:1985:CFM,
author = "M. R. Jerrum",
title = "The complexity of finding minimum-length generator
sequences",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "265--289",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Edinburgh Univ., UK",
keywords = "computational complexity; cyclicly adjacent
transpositions; generator set cardinality;
minimum-length generator sequences; permutation group;
polynomial time; polynomials; PSPACE-complete; single
target permutation",
pubcountry = "Netherlands A08",
treatment = "T Theoretical or Mathematical",
}
@Article{Matsuno:1985:ASM,
author = "H. Matsuno and K. Inoue and H. Taniguchi and I.
Takanami",
title = "Alternating simple multihead finite automata",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "291--308",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Electron., Yamaguchi Junior Coll., Hofu,
Japan",
keywords = "alternating simple multihead finite automaton;
ASPMHFAs; Boolean operations; closure properties;
complexity measure; computational complexity; finite
automata; ordinary alternating multihead finite
automata; SPMHFAs",
pubcountry = "Netherlands A09",
treatment = "T Theoretical or Mathematical",
}
@Article{Keller-Gehrig:1985:FAC,
author = "W. Keller-Gehrig",
title = "Fast algorithms for the characteristic polynomial",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "309--317",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4130 (Interpolation and function approximation);
C4240 (Programming and algorithm theory)",
keywords = "characteristic polynomial; computational complexity;
fast algorithms; matrix multiplication; polynomials",
pubcountry = "Netherlands A10",
treatment = "T Theoretical or Mathematical",
}
@Article{Diks:1985:EBT,
author = "K. Diks",
title = "Embeddings of binary trees in lines",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "319--331",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Inst. Inf., Warszawa Univ., Poland",
keywords = "binary trees embedding; dilation-cost; graph theory;
n-vertex binary tree; trees (mathematics)",
pubcountry = "Netherlands A11",
treatment = "T Theoretical or Mathematical",
}
@Article{Alt:1985:MEN,
author = "H. Alt",
title = "Multiplication is the easiest nontrivial arithmetic
function",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "333--339",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., Pennsylvania State Univ.,
University Park, PA, USA",
keywords = "Boolean circuit; Boolean functions; Boolean
operations; fixed point multiplication; nontrivial
arithmetic function",
pubcountry = "Netherlands A12",
treatment = "T Theoretical or Mathematical",
}
@Article{Rytter:1985:CRM,
author = "W. Rytter and M. Chrobak",
title = "A characterization of reversal-bounded multipushdown
machine languages",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "341--344",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Inst. of Inf., Warsaw Univ., Poland",
keywords = "automata theory; characterization; DLOG; formal
languages; reversal-bounded multipushdown machine
languages; Turing machines",
pubcountry = "Netherlands A13",
treatment = "T Theoretical or Mathematical",
}
@Article{Farr:1985:CCH,
author = "G. Farr and C. McDiarmid",
title = "The complexity of counting homeomorphs",
journal = j-THEOR-COMP-SCI,
volume = "36",
number = "2-3",
pages = "345--348",
month = apr,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4240
(Programming and algorithm theory)",
corpsource = "Math. Inst., Oxford, UK",
keywords = "complexity; computational complexity; counting
homeomorphs; finite nontrivial family of graphs; graph
theory; minimal nonplanar subgraphs; subgraphs",
pubcountry = "Netherlands A14",
treatment = "T Theoretical or Mathematical",
}
@Article{Ko:1985:SNC,
author = "K. Ko",
title = "On some natural complete operators",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "1",
pages = "1--30",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Dept. of Comput. Sci., Houston Univ., TX, USA",
keywords = "completeness; computational complexity; deterministic
oracle Turing machine; integer functions; natural
complete operators; nondeterministic oracle Turing
machine; NP operator; polynomial time; polynomials;
Turing machines",
pubcountry = "Netherlands A01",
treatment = "T Theoretical or Mathematical",
}
@Article{Rozenberg:1985:CSS,
author = "G. Rozenberg",
title = "On coordinated selective substitutions: towards a
unified theory of grammars and machines",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "1",
pages = "31--50",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Inst. of Appl. Math. and Comput. Sci., Leiden Univ.,
Netherlands",
keywords = "automata theory; coordinated selective substitutions;
formal language theory; formal languages; grammars;
machines; unified theory",
pubcountry = "Netherlands A02",
treatment = "T Theoretical or Mathematical",
}
@Article{Muller:1985:TEP,
author = "D. E. Muller and P. E. Schupp",
title = "The theory of ends, pushdown automata, and
second-order logic",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "1",
pages = "51--75",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic); C4220 (Automata theory)",
corpsource = "Dept. of Math., Comput. Sci. Illinois Univ., Urbana,
IL, USA",
keywords = "automata theory; Cayley graphs; cellular automata;
context free groups; edge-labeled graphs; ends theory;
formal logic; graph theory; infinite binary tree;
monadic second-order theory; pushdown automata; Rabin's
theorem; second-order logic theory; tiling systems;
trees (mathematics); two dimensional grid",
pubcountry = "Netherlands A03",
treatment = "T Theoretical or Mathematical",
}
@Article{Bergstra:1985:ACP,
author = "J. A. Bergstra and J. W. Klop",
title = "Algebra of communicating processes with abstraction",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "1",
pages = "77--121",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C1260
(Information theory)",
corpsource = "Centre for Math. and Comput. Sci., Amsterdam,
Netherlands",
keywords = "abstraction; algebra; axiom system; communicating
processes; conservativity; consistency; expansion
theorem; finite acyclic process graphs; graph theory;
information theory; Milner's tau -laws; model;
recursive path orderings; rewriting terms; syntactic
properties",
pubcountry = "Netherlands A04",
treatment = "T Theoretical or Mathematical",
}
@Article{Gallier:1985:RTR,
author = "J. H. Gallier and R. V. Book",
title = "Reductions in tree replacement systems",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "2",
pages = "123--150",
month = nov,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic); C4220 (Automata theory)",
corpsource = "Dept. of Comput. and Inf. Sci., Moore Sch. of Electr.
Eng., Pennsylvania Univ., Philadelphia, PA, USA",
keywords = "Church-Rosser monadic reduction systems; Church-Rosser
tree replacement systems; congruence class;
deterministic automata; deterministic bottom-up tree
pushdown automation; finite Church-Rosser reduction
systems; formal languages; grammars; linear time
decidability; monadic Thue systems; norm; tree reducing
machine; tree rewriting system; trees (mathematics)",
pubcountry = "Netherlands A01",
treatment = "T Theoretical or Mathematical",
}
@Article{Bouge:1985:CTP,
author = "L. Bouge",
title = "A contribution to the theory of program testing",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "2",
pages = "151--181",
month = nov,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "LITP, UER de Math., Paris Univ., France",
keywords = "abstract formalism; acceptability; bias; effective
automatic test generation; equivalence relation;
preorder; program proving; program testing; program
testing theory; programming theory; quality assessment;
reliability; test battery; test context; test
optimisation; validity",
pubcountry = "Netherlands A02",
treatment = "T Theoretical or Mathematical",
}
@Article{Culik:1985:TTT,
author = "K. {Culik, II} and I. Fris",
title = "Topological transformations as a tool in the design of
systolic networks",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "2",
pages = "183--216",
month = nov,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Dept. of Comput. Sci., Waterloo Univ., Ont., Canada",
keywords = "automata theory; computational network; correctness
proving; distributed sorting; equivalence; Leiserson
and Saxe; parallel processing; parallel synchronised
processors; retiming lemma; space-time diagrams;
systolic conversion theorem; systolic network; systolic
ring; topological transformations; unrollings",
pubcountry = "Netherlands A03",
treatment = "T Theoretical or Mathematical",
}
@Article{Gonczarowski:1985:AST,
author = "J. Gonczarowski and M. K. Warmuth",
title = "Applications of scheduling theory to formal language
theory",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "2",
pages = "217--243",
month = nov,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1290 (Applications of systems theory); C4210
(Formal logic); C4240 (Programming and algorithm
theory)",
corpsource = "Inst. of Math. and Computer Sci., Hebrew Univ. of
Jerusalem, Israel",
keywords = "computational complexity; context-free grammars;
context-free languages; context-free rewriting;
derivation forest; dynamic programming membership
algorithms; EOL rewriting; formal language theory;
NP-hard membership; parallel nonterminal-rewriting;
scheduling; scheduling theory",
pubcountry = "Netherlands A04",
treatment = "T Theoretical or Mathematical",
}
@Article{deSimone:1985:HSD,
author = "R. {de Simone}",
title = "Higher-level synchronising devices in {MEIJE-SCCS}",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "3",
pages = "245--267",
month = dec,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Centre de Math. Appl., INRIA, Valbonne, France",
keywords = "actions monoids; expressiveness study; higher level
nonprimitive operators; MEIJE-SCCS; original SCCS
calculus; parallel processing; parallelism; programming
theory; semantic conditional rules; synchronisation;
synchronising operators; transition systems",
pubcountry = "Netherlands A01",
treatment = "T Theoretical or Mathematical",
}
@Article{Tarlecki:1985:EFM,
author = "A. Tarlecki",
title = "On the existence of free models in abstract algebraic
institutions",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "3",
pages = "269--304",
month = dec,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., Edinburgh Univ., UK",
keywords = "abstract algebraic institutions; abstract data types;
algebra; algebraic specification languages; arbitrary
theory morphism; data structures; forgetful functors;
formal logic; free constructions; free functors; free
models; left adjoints; logical system; partial
algebras; reachable initial models; specification
languages; specifications writing; submodel; theory
morphism",
pubcountry = "Netherlands A02",
treatment = "T Theoretical or Mathematical",
}
@Article{Darondeau:1985:AFA,
author = "P. Darondeau",
title = "About fair asynchrony",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "3",
pages = "305--336",
month = dec,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4240 (Programming and
algorithm theory)",
corpsource = "IRISA, Rennes, France",
keywords = "abstract model; asynchronous agents; CCS like
language; classical algebraic domains; fair asynchrony;
fairness; formal languages; implementation preorder;
infinitary languages; observable properties; parallel
processing; parallelism; programming theory; semantic
modelling; synchronisation",
pubcountry = "Netherlands A03",
treatment = "T Theoretical or Mathematical",
}
@Article{Ehrenfeucht:1985:AGF,
author = "A. Ehrenfeucht and H. C. M. Kleijn and G. Rozenberg",
title = "Adding global forbidding context to context-free
grammars",
journal = j-THEOR-COMP-SCI,
volume = "37",
number = "3",
pages = "357--360",
month = dec,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., Colorado Univ., Boulder, CO,
USA",
keywords = "context free languages; context-free grammars;
context-free languages; fixed alphabet; global
forbidding context; IS grammar; one sequential
grammars; selective substitution grammar theory",
pubcountry = "Netherlands A04",
treatment = "T Theoretical or Mathematical",
}
@Article{Fle:1985:MSI,
author = "M. P. Fle and G. Roucairol",
title = "Maximal serializability of iterated transactions",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "1--16",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4250 (Database theory)",
corpsource = "Lab. de Recherche en Inf., Univ. de Paris-Sud, Orsay,
France",
keywords = "concurrent transactions; conflicting accesses; correct
behaviours; database consistency; database theory;
dining philosophers; finite automata; finite automaton;
iterated transactions; maximal serialisability;
multiprocessing programs; synchronisation;
synchronization",
pubcountry = "Netherlands A01",
treatment = "T Theoretical or Mathematical",
}
@Article{Weihrauch:1985:TRT,
author = "K. Weihrauch",
title = "Type 2 recursion theory",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "17--33",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., Fernuniv., Hagen, West
Germany",
keywords = "computability; computably open subsets; continuous
functions; recursive functions; recursively enumerable
subsets; topological version; type 2 recursion theory",
pubcountry = "Netherlands A02",
treatment = "T Theoretical or Mathematical",
}
@Article{Kreitz:1985:TR,
author = "C. Kreitz and K. Weihrauch",
title = "Theory of representations",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "35--53",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic)",
corpsource = "LG Theor. Inf., Fernuniv., Hagen, West Germany",
keywords = "computability; effectivity theory; recursion
theoretical properties; recursive functions; separable
T/sub 0/-space; set theory; topological properties;
topology; type 2 computability; unique admissible
representation",
pubcountry = "Netherlands A03",
treatment = "T Theoretical or Mathematical",
}
@Article{Wegener:1985:CSF,
author = "I. Wegener",
title = "On the complexity of slice functions",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "55--68",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "B1265B (Logic circuits); C1160 (Combinatorial
mathematics); C4210 (Formal logic); C4230B
(Combinatorial switching theory)C4240 (Programming and
algorithm theory)",
corpsource = "Johann Wolfgang Goethe-Univ., Frankfurt, West
Germany",
keywords = "arbitrary complete bases; Boolean convolution; Boolean
functions; canonical slice functions; circuit
combination complexity; clique function; combinatorial
circuits; combinatorial switching; computational
complexity; conjunction; disjunction; monotone circuit
complexity; Nechiporuk Boolean sums; set circuits; set
intersection; set theory; set union",
pubcountry = "Netherlands A04",
treatment = "T Theoretical or Mathematical",
}
@Article{Snir:1985:LBP,
author = "M. Snir",
title = "Lower bounds on probabilistic linear decision trees",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "69--82",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1140E (Game theory); C1160 (Combinatorial
mathematics); C4240 (Programming and algorithm
theory)",
corpsource = "Dept. of Comput. Sci., Hebrew Univ. of Jerusalem,
Israel",
keywords = "computational complexity; decision theory; lower
bounds; probabilistic linear decision trees; random
processes; randomising algorithm; trees (mathematics)",
pubcountry = "Netherlands A05",
treatment = "T Theoretical or Mathematical",
}
@Article{Ramanan:1985:PRK,
author = "P. V. Ramanan and C. L. Liu",
title = "Permutation representation of $k$-ary trees",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "83--98",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic); C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Illinois Univ., Urbana, IL,
USA",
keywords = "data structures; k-ary tree traversals; k-ary trees;
lexicographic order; permutation representation;
sorting; trees (mathematics)",
pubcountry = "Netherlands A06",
treatment = "T Theoretical or Mathematical",
}
@Article{Beeri:1985:FSJ,
author = "C. Beeri and M. Y. Vardi",
title = "Formal systems for join dependencies",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "99--116",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4250 (Database theory)",
corpsource = "Dept. of Comput. Sci., Hebrew Univ. of Jerusalem,
Israel",
keywords = "database theory; extended join dependencies; formal
system; generalised join dependencies; Gentzen-style
system; implication problem; relational database
theory; relational databases; tuple generating
dependencies; unbounded inference rules",
pubcountry = "Netherlands A07",
treatment = "T Theoretical or Mathematical",
}
@Article{Leconte:1985:CPM,
author = "M. Leconte",
title = "A characterization of power-free morphisms",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "117--122",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Paris VII Univ., France",
keywords = "cube-free image; decidability; formal languages;
power-free morphisms; power-free words; square-free
morphism",
pubcountry = "Netherlands A08",
treatment = "T Theoretical or Mathematical",
}
@Article{Van:1985:CSG,
author = "D. L. Van",
title = "Code-compatible sets and a generalisation of the
{Sardinas-Patterson} theorem",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "123--132",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); B6120B (Codes);
C1160 (Combinatorial mathematics); C4210 (Formal
logic); C4290 (Other computer theory)",
corpsource = "Inst. of Math., Hanoi, Viet Nam",
keywords = "code-compatible sets; codes; generalised
Sardinas-Patterson theorem; infinitary code; monoid;
set theory",
pubcountry = "Netherlands A09",
treatment = "T Theoretical or Mathematical",
}
@Article{Leiss:1985:SRR,
author = "E. Leiss",
title = "Succinct representation of regular languages by
{Boolean} automata. {II}",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "133--136",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory)",
corpsource = "Dept. of Comput. Sci., Houston Univ., TX, USA",
keywords = "Boolean automata; Boolean function; Boolean functions;
complementation; context-free languages; deterministic
automata; finite automata; language equations;
precisely attainable lower bound; reduced automaton;
regular languages; sequential networks; succinct
representation; transition function",
pubcountry = "Netherlands A10",
treatment = "T Theoretical or Mathematical",
}
@Article{Finkel:1985:GTH,
author = "A. Finkel",
title = "A generalisation of the theorems of {Higman} and of
{Simon} to infinite words",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "1",
pages = "137--142",
month = may,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Mon Oct 26 07:53:28 1998",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Univ. de Paris-Sud, Orsay, France",
keywords = "be a subword of; finite alphabet; finite words; formal
languages; generalised Higman's theorem; generalised
Simon's theorem; increasing subsequence; infinite
sequence; infinite words; quasi-order",
pubcountry = "Netherlands A11",
treatment = "T Theoretical or Mathematical",
}
@Article{Schmidt:1985:RSC,
author = "D. Schmidt",
title = "The recursion-theoretic structure of complexity
classes",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "143--156",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Inst. fur Informat. I, Karlsruhe Univ., West Germany",
keywords = "complexity classes; computational complexity;
diagonalization theorems; recursion-theoretic
structure",
pubcountry = "Netherlands A01",
treatment = "T Theoretical or Mathematical",
}
@Article{Watanabe:1985:OPT,
author = "O. Watanabe",
title = "On one-one polynomial time equivalence relations",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "157--165",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4130 (Interpolation and function approximation);
C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Inf. Sci., Tokyo Inst. of Technol., Japan",
keywords = "complexity classes; computational complexity;
EXPTIM-P; EXPTIME complete sets; one-one polynomial
time equivalence relations; polynomials",
pubcountry = "Netherlands A02",
treatment = "T Theoretical or Mathematical",
}
@Article{Imori:1985:PCS,
author = "M. Imori and H. Yamada",
title = "Periodic character sequences where identifying two
characters strictly reduces the period",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "167--192",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Fac. of Sci., Tokyo Univ., Japan",
keywords = "cellular automata; finite automata; homomorphic map;
periodic character sequences; primitive period",
pubcountry = "Netherlands A03",
treatment = "T Theoretical or Mathematical",
}
@Article{Burkhard:1985:ICC,
author = "H. D. Burkhard",
title = "An investigation of controls for concurrent systems
based on abstract control languages",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "193--122",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory); C6150J
(Operating systems)",
corpsource = "Sektion Math., Humboldt Univ., Berlin, East Germany",
keywords = "abstract control languages; concurrent systems;
deadlock avoidance; fairness; liveness; multiprocessing
programs; programming theory",
pubcountry = "Netherlands A04",
treatment = "T Theoretical or Mathematical",
}
@Article{Jantzen:1985:ERE,
author = "M. Jantzen",
title = "Extending regular expressions with iterated shuffle",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "223--247",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Fachbereich Informat., Hamburg Univ., West Germany",
keywords = "algebraic language theory; finite expression; iterated
shuffle; Kleene star; multicounter machine; NSPACE;
product; programming theory; regular expressions
extending; union",
pubcountry = "Netherlands A05",
treatment = "T Theoretical or Mathematical",
}
@Article{Asano:1985:ASH,
author = "T. Asano",
title = "An approach to the subgraph homeomorphism problem",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "249--267",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Dept. of Math. Eng. and Instrum. Phys., Tokyo Univ.,
Japan",
keywords = "fixed pattern graph; graph theory; Kuratowski graphs;
NP- complete; polynomial time; subgraph homeomorphism
problem; Thomsen graph",
pubcountry = "Netherlands A06",
treatment = "T Theoretical or Mathematical",
}
@Article{Mishra:1985:HVA,
author = "B. Mishra and E. Clarke",
title = "Hierarchical verification of asynchronous circuits
using temporal logic",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "269--291",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., Carnegie-Mellon Univ.,
Pittsburgh, PA, USA",
keywords = "asynchronous circuits; branching time temporal logic;
correctness; formal logic; hierarchical verification;
nondeterminism; temporal logic",
pubcountry = "Netherlands A07",
treatment = "T Theoretical or Mathematical",
}
@Article{Gonzalez:1985:CMM,
author = "T. F. Gonzalez",
title = "Clustering to minimize the maximum intercluster
distance",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "293--306",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Programs in Comput. Sci., Texas Univ., Richardson, TX,
USA",
keywords = "algorithm theory; approximation algorithm; clustering;
graph theory; maximum intercluster distance;
minimisation; objective function value; triangular
inequality",
pubcountry = "Netherlands A08",
treatment = "T Theoretical or Mathematical",
}
@Article{Harel:1985:PLR,
author = "D. Harel and D. Peleg",
title = "Process logic with regular formulas",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "307--322",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Appl. Math., Weizmann Inst. of Sci., Rehovot,
Israel",
keywords = "extension RPL; formal logic; Kleene's regular
operators; process logic; program behaviour; regular
formulas",
pubcountry = "Netherlands A09",
treatment = "T Theoretical or Mathematical",
}
@Article{Rosenkrantz:1985:TGC,
author = "D. J. Rosenkrantz and H. B. {Hunt, III}",
title = "Testing for grammatical coverings",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "323--341",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., State Univ. of New York,
Albany, NY, USA",
keywords = "computational problem; context-free grammars;
deterministic polynomial time algorithms; grammar
homomorphism; grammar isomorphism; grammatical
coverings testing; interpretation; mappings;
NP-complete; Reynolds covering; weak Reynolds
covering",
pubcountry = "Netherlands A10",
treatment = "T Theoretical or Mathematical",
}
@Article{Linial:1985:DHH,
author = "N. Linial and M. Tarsi",
title = "Deciding hypergraph $2$-colourability by
{H}-resolution",
journal = j-THEOR-COMP-SCI,
volume = "38",
number = "2-3",
pages = "343--347",
month = jun,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0250 (Combinatorial mathematics); C1160
(Combinatorial mathematics)",
corpsource = "Inst. of Math. and Comput. Sci., Hebrew Univ.,
Jerusalem, Israel",
keywords = "Boolean formulas; computational problem; graph
colouring; H-resolution; hypergraph 2-colourability
deciding; propositional calculus; satisfiability
problem",
pubcountry = "Netherlands A11",
treatment = "T Theoretical or Mathematical",
}
@Article{Anonymous:1985:TCF,
author = "Anonymous",
title = "{Third Conference on Foundations of Software Technology
and Theoretical Computer Science}",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "1",
pages = "??--??",
month = jul,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C6110 (Systems analysis and
programming)",
conflocation = "Bangalore, India; 12-14 Dec. 1983",
conftitle = "Third Conference on Foundations of Software Technology
and Theoretical Computer Science",
keywords = "cancellation properties; communicating processes;
context-free grammars; linear equations; logic
programming; logic programs; modulator proofs;
observational equivalence; optimal fixed points;
polynomials; proof-theoretic characterisation; software
engineering; software technology; stability; trace
semantics",
pubcountry = "Netherlands",
sponsororg = "Nat. Centre Software Dev. and Comput. Tech",
}
@Article{Frougny:1985:CGC,
author = "C. Frougny",
title = "Context-free grammars with cancellation properties",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "1",
pages = "3--13",
month = jul,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
conflocation = "Bangalore, India; 12-14 Dec. 1983",
conftitle = "Third Conference on Foundations of Software Technology
and Theoretical Computer Science",
corpsource = "LITP and UER de Math., Univ. Paris V, France",
keywords = "cancellation properties; context-free grammar;
context-free grammars; free monoid; general algebraic
construction; Hotz monoid; Rees quotient; syntactic
monoid",
pubcountry = "Netherlands A01",
sponsororg = "Nat. Centre Software Dev. and Comput. Tech",
treatment = "T Theoretical or Mathematical",
}
@Article{Lassez:1985:OFL,
author = "J.-L. Lassez and M. J. Maher",
title = "Optimal fixedpoints of logic programs",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "1",
pages = "15--25",
month = jul,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C6110 (Systems analysis and programming)",
conflocation = "Bangalore, India; 12-14 Dec. 1983",
conftitle = "Third Conference on Foundations of Software Technology
and Theoretical Computer Science",
corpsource = "Dept. of Comput. Sci., Melbourne Univ., Parkville,
Vic., Australia",
keywords = "least fixedpoint semantics; logic programming; logic
programs; optimal fixed points; recursive programming",
pubcountry = "Netherlands A02",
sponsororg = "Nat. Centre Software Dev. and Comput. Tech",
treatment = "T Theoretical or Mathematical",
}
@Article{Stirling:1985:PCO,
author = "C. Stirling",
title = "A proof-theoretic characterization of observational
equivalence",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "1",
pages = "27--45",
month = jul,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
conflocation = "Bangalore, India; 12-14 Dec. 1983",
conftitle = "Third Conference on Foundations of Software Technology
and Theoretical Computer Science",
corpsource = "Dept. of Comput. Sci., Edinburgh Univ., UK",
keywords = "formal languages; modal language; modal proof systems;
nondeterministic languages; observational equivalence;
proof-theoretic characterization",
pubcountry = "Netherlands A03",
sponsororg = "Nat. Centre Software Dev. and Comput. Tech",
treatment = "T Theoretical or Mathematical",
}
@Article{Back:1985:STS,
author = "R. J. R. Back and H. Mannila",
title = "On the suitability of trace semantics for modular
proofs of communicating processes",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "1",
pages = "47--68",
month = jul,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4290 (Other computer theory)",
conflocation = "Bangalore, India; 12-14 Dec. 1983",
conftitle = "Third Conference on Foundations of Software Technology
and Theoretical Computer Science",
corpsource = "Dept. of Inf. Processing, Abo Akademi, Finland",
keywords = "abstraction; communicating processes; distributed
processing; modular proofs; partial correctness;
semantic model; suitability; trace model; trace
semantics",
pubcountry = "Netherlands A04",
sponsororg = "Nat. Centre Software Dev. and Comput. Tech",
treatment = "T Theoretical or Mathematical",
}
@Article{Kannan:1985:SSL,
author = "R. Kannan",
title = "Solving systems of linear equations over polynomials",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "1",
pages = "69--88",
month = jul,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "B0290F (Interpolation and function approximation);
C4130 (Interpolation and function approximation)",
conflocation = "Bangalore, India; 12-14 Dec. 1983",
conftitle = "Third Conference on Foundations of Software Technology
and Theoretical Computer Science",
corpsource = "Dept. of Comput. Sci., Carnegie-Mellon Univ.,
Pittsburgh, PA, USA",
keywords = "Hermite form; linear equations; matrix; matrix
algebra; polynomials; triangular canonical form",
pubcountry = "Netherlands A05",
sponsororg = "Nat. Centre Software Dev. and Comput. Tech",
treatment = "T Theoretical or Mathematical",
}
@Article{Ibarra:1985:ERT,
author = "O. H. Ibarra and M. A. Palis and J. H. Chang",
title = "On efficient recognition of transductions and
relations",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "89--106",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic); C4220 (Automata theory); C4240
(Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Minnesota Univ., Minneapolis,
MN, USA",
keywords = "automata theory; computational complexity;
context-free language recognition; context-free
languages; counter machines; depth-first search;
dynamic programming; k-tape one-way nondeterministic
pushdown acceptors; language recognition; pushdown
machines; relations; transductions; translation;
unit-cost random access machine",
pubcountry = "Netherlands A01",
treatment = "T Theoretical or Mathematical",
}
@Article{Priese:1985:FDM,
author = "L. Priese",
title = "On a fast decomposition method in some models of
concurrent computations",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "107--121",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Fachbereich Math. und Inf., Univ. Gesamthochschule
Paderborn, West Germany",
keywords = "asynchronous control modules; automata theory;
computational complexity; concurrent automation;
concurrent computations; data flow machines; fast
decomposition method; network-type models;
output-lines; parallel computations; parallel
processing; Petri nets; sequential machines;
speed-independent modules",
pubcountry = "Netherlands A02",
treatment = "T Theoretical or Mathematical",
}
@Article{Kapur:1985:CPS,
author = "D. Kapur and P. Narendran and M. S. Krishnamoorthy and
McNaughton and R.",
title = "The {Church-Rosser} property and special {Thue}
systems",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "123--133",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Comput. Sci. Branch, G.E. Res. and Dev. Center,
Schenectady, NY, USA",
keywords = "Church-Rosser property; computational complexity;
empty string; Thue systems",
pubcountry = "Netherlands A03",
treatment = "T Theoretical or Mathematical",
}
@Article{Bohm:1985:AST,
author = "C. Bohm and A. Berarducci",
title = "Automatic synthesis of typed Lambda -programs on term
algebras",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "135--153",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dipartimento di Matematica, Roma Univ., Italy",
keywords = "automatic synthesis; automatic uniform synthesis
paradigms; completeness theorem; computational
complexity; iterative functions; iteratively defined
functions; programming language; programming theory;
second-order types lambda calculus; term algebras;
tree-structures; typed Lambda -programs",
pubcountry = "Netherlands A04",
treatment = "T Theoretical or Mathematical",
}
@Article{Parigot:1985:LAP,
author = "M. Parigot and E. Pelz",
title = "A logical approach of {Petri} net languages",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "155--169",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C1160 (Combinatorial mathematics); C4210 (Formal
logic); C4220 (Automata theory)",
corpsource = "UER de Math. et Inf., Paris VII Univ., France",
keywords = "Buchi-like theorem; deadlock languages; directed
graphs; finite automata; formal languages; logical
approach; logical formulas; Petri net languages;
regular expressions",
pubcountry = "Netherlands A05",
treatment = "T Theoretical or Mathematical",
}
@Article{Spehner:1985:ESE,
author = "J.-C. Spehner",
title = "Entire systems of equations on a finite alphabet and
{Ehrenfeucht}'s conjecture",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "171--188",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory)",
corpsource = "Inst. des Sci., Exactes et Appl., Univ. de Haute
Alsace, Mulhouse, France",
keywords = "automata theory; Ehrenfeucht conjecture; entire
systems of equations; finite alphabet; generalized
automaton; morphism; morphisms; shuffle automation",
language = "French",
pubcountry = "Netherlands A06",
treatment = "T Theoretical or Mathematical",
}
@Article{RodriguezArtalejo:1985:SQA,
author = "M. {Rodriguez Artalejo}",
title = "Some questions about expressiveness and relative
completeness in {Hoare}'s logic",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "189--206",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. de Ecuaciones Funcionales, Univ. Complutense,
Madrid, Spain",
keywords = "completeness; expressiveness; formal logic; Hoare
logic; strong relative incompleteness; true partial
correctness assertion; unwind property;
while-programs",
pubcountry = "Netherlands A07",
treatment = "T Theoretical or Mathematical",
}
@Article{Mahaney:1985:RAP,
author = "S. R. Mahaney and P. Young",
title = "Reductions among polynomial isomorphism types",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "207--224",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4130 (Interpolation and function approximation);
C4240 (Programming and algorithm theory)",
corpsource = "AT and T Bell Labs., Murray Hill, NJ, USA",
keywords = "classical recursive function theory; computational
complexity; Karp-reducible; many-one degree;
NP-complete sets; polynomial isomorphism types;
polynomially invertible reductions; polynomials;
size-increasing",
pubcountry = "Netherlands A08",
treatment = "T Theoretical or Mathematical",
}
@Article{Joseph:1985:SRW,
author = "D. Joseph and P. Young",
title = "Some remarks on witness functions for nonpolynomial
and noncomplete sets in {NP}",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "225--237",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4130 (Interpolation and function approximation);
C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Wisconsin Univ., Madison, WI,
USA",
keywords = "computational complexity; coNP; k-creative set;
noncomplete sets; nonpolynomial sets; NP; polynomially
computable function; polynomials; witness functions",
pubcountry = "Netherlands A09",
treatment = "T Theoretical or Mathematical",
}
@Article{Hull:1985:NSP,
author = "R. Hull",
title = "Non-finite specifiability of projections of functional
dependency families",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "239--265",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4250 (Database theory); C6160D (Relational
databases)",
corpsource = "Dept. of Comput. Sci., Univ. of Southern California,
Los Angeles, CA, USA",
keywords = "database theory; functional dependency families;
implicational dependency family; nonfinite
specifiability; projections; relational database
instances; relational databases",
pubcountry = "Netherlands A10",
treatment = "T Theoretical or Mathematical",
}
@Article{Vogel:1985:TAM,
author = "J. Vogel and K. Wagner",
title = "Two-way automata with more than one storage medium",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "267--280",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4220 (Automata theory); C4240 (Programming and
algorithm theory)",
corpsource = "Sektion Math., Friedrich-Schiller Univ., Jena, East
Germany",
keywords = "automata theory; checking stacks; computational
complexity; computational power; nonerasing stack;
pushdown store; space complexity classes; storage
medium; two-way automata",
pubcountry = "Netherlands A11",
treatment = "T Theoretical or Mathematical",
}
@Article{Siromoney:1985:IWO,
author = "R. Siromoney and V. R. Dare",
title = "On infinite words obtained by selective substitution
grammars",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "281--295",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Math., Madras Christian Coll., India",
keywords = "closure properties; decidability; grammars; infinite
words; limit language families; limiting processes;
selective substitution grammars",
pubcountry = "Netherlands A12",
treatment = "T Theoretical or Mathematical",
}
@Article{Haken:1985:IR,
author = "A. Haken",
title = "The intractability of resolution",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "297--308",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4240 (Programming and algorithm theory)",
corpsource = "Dept. of Comput. Sci., Toronto Univ., Ont., Canada",
keywords = "computational complexity; infinitely many disjunctive
normal form propositional calculus tautologies;
intractability; pigeonhole principle; polynomial;
resolution",
pubcountry = "Netherlands A13",
treatment = "T Theoretical or Mathematical",
}
@Article{Ginsburg:1985:CTS,
author = "S. Ginsburg and E. H. Spanier",
title = "On completing tables to satisfy functional
dependencies",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "309--317",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4250 (Database theory); C6160D (Relational
databases)",
corpsource = "Dept. of Comput. Sci., Univ. of Southern California,
Los Angeles, CA, USA",
keywords = "completely-specified table; database theory;
functional dependencies; partially-specified table;
relational databases; sufficiency conditions",
pubcountry = "Netherlands A14",
treatment = "T Theoretical or Mathematical",
}
@Article{Book:1985:SNP,
author = "R. V. Book and F. Otto",
title = "On the security of name-stamp protocols",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "319--325",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C5620 (Computer networks and techniques); C6130
(Data handling techniques)",
corpsource = "Dept. of Math., California Univ., Santa Barbara, CA,
USA",
keywords = "cryptography; name-stamp protocols; p-parity cascade
protocols; protocols; security; two-party cascade
protocols",
pubcountry = "Netherlands A15",
treatment = "T Theoretical or Mathematical",
}
@Article{Leiss:1985:SSE,
author = "E. L. Leiss",
title = "On solving star equations",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "327--332",
month = aug,
year = "1985",
CODEN = "TCSCDI",
ISSN = "0304-3975",
bibdate = "Sat Nov 22 13:29:49 MST 1997",
acknowledgement = ack-nhfb,
classification = "C4210 (Formal logic)",
corpsource = "Dept. of Comput. Sci., Houston Univ., TX, USA",
keywords = "constant language; formal languages; language
equation; mapping; operations union; star equation;
uniqueness; unrestricted star",
pubcountry = "Netherlands A16",
treatment = "T Theoretical or Mathematical",
}
@Article{Arnold:1985:SCR,
author = "A. Arnold",
title = "A syntactic congruence for rational omega-languages",
journal = j-THEOR-COMP-SCI,
volume = "39",
number = "2-3",
pages = "333--335",
month = aug,
year = "1985",
CODEN = "TCSCDI",