%%% -*-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", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. de Math. et Inf., Poitiers Univ., France", keywords = "formal languages; rational omega-languages; syntactic congruence", pubcountry = "Netherlands A17", treatment = "T Theoretical or Mathematical", } @Article{Bunder:1985:EKC, author = "M. W. Bunder", title = "An extension of {Klop}'s counterexample to the {Church-Rosser} property to lambda-calculus with other ordered pair combinators", journal = j-THEOR-COMP-SCI, volume = "39", number = "2-3", pages = "337--342", 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); C4230B (Combinatorial switching theory)", corpsource = "Dept. of Math., Wollongong Univ., NSW, Australia", keywords = "Church-Rosser property; combinatorial mathematics; combinatory logic; Klop counterexample; ordered pair combinators", pubcountry = "Netherlands A18", treatment = "T Theoretical or Mathematical", } @Article{Karhumaki:1985:TC, author = "J. Karhumaki", title = "On three-element codes", journal = j-THEOR-COMP-SCI, volume = "40", number = "1", pages = "3--11", month = sep, year = "1985", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", acknowledgement = ack-nhfb, classification = "B6120B (Codes); C4210 (Formal logic)", corpsource = "Dept. of Math., Turku Univ., Finland", keywords = "bounded delay; codes; formal language theory; formal languages; three-element codes; unique maximal element", pubcountry = "Netherlands A01", treatment = "T Theoretical or Mathematical", } @Article{Restivo:1985:RLB, author = "A. Restivo and C. Reutenauer", title = "Rational languages and the {Burnside} problem", journal = j-THEOR-COMP-SCI, volume = "40", number = "1", pages = "13--30", month = sep, year = "1985", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Istituto di Matematica, Palermo Univ., Italy", keywords = "bounded languages; Burnside problem; commutativity; formal languages; pumping; rational languages; rational power series; regularity conditions; square-free words; syntactic monoid", pubcountry = "Netherlands A02", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Blumer:1985:SAR, author = "A. Blumer and J. Blumer and D. Haussler and A. Ehrenfeucht and Chen and M. T. and J. Seiferas", title = "The smallest automation recognizing the subwords of a text", journal = j-THEOR-COMP-SCI, volume = "40", number = "1", pages = "31--55", month = sep, 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. and Comput. Sci., Denver Univ., CO, USA", keywords = "finite automata; linear time; partial deterministic finite automaton; smallest automation; text subwords", pubcountry = "Netherlands A03", treatment = "T Theoretical or Mathematical", } @Article{Schoning:1985:RAD, author = "U. Schoning", title = "Robust algorithms: a different approach to oracles", journal = j-THEOR-COMP-SCI, volume = "40", number = "1", pages = "57--66", month = sep, 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 Inf., Stuttgart Univ., West Germany", keywords = "computational complexity; deterministic polynomial time algorithms; NP-complete problems; oracle machine; probabilistic classes; robust algorithms", pubcountry = "Netherlands A04", treatment = "T Theoretical or Mathematical", } @Article{Paige:1985:LTS, author = "R. Paige and R. E. Tarjan and R. Bonic", title = "A linear time solution to the single function coarsest partition problem", journal = j-THEOR-COMP-SCI, volume = "40", number = "1", pages = "67--84", month = sep, year = "1985", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", acknowledgement = ack-nhfb, classification = "C1180 (Optimisation techniques); C4220 (Automata theory)", corpsource = "Dept. of Comput. Sci., Rutgers Univ., New Brunswick, NJ, USA", keywords = "automated manufacturing; finite automata; finite state automata; linear time solution; minimisation; single function coarsest partition problem; state minimization; woven fabric", pubcountry = "Netherlands A05", treatment = "T Theoretical or Mathematical", } @Article{Bauer:1985:NRS, author = "G. Bauer", title = "n-level rewriting systems", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "85--99", month = "????", 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., Kaiserslautern Univ., West Germany", keywords = "finite complete rewriting system; monoid; n-level rewriting systems; programming theory", pubcountry = "Netherlands A01", treatment = "T Theoretical or Mathematical", } @Article{Book:1985:VTA, author = "R. V. Book and F. Otto", title = "On the verifiability of two-party algebraic protocols", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "101--130", month = "????", year = "1985", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", acknowledgement = ack-nhfb, classification = "B6210L (Computer communications); C5620 (Computer networks and techniques); C6130 (Data handling techniques)", corpsource = "Dept. of Math., California Univ., Santa Barbara, CA, USA", keywords = "communication protocols; cryptography; protocols; public-key cryptosystems; two-party algebraic protocols; verifiability", pubcountry = "Netherlands A02", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Bucher:1985:TRG, author = "W. Bucher and A. Ehrenfeucht and D. Haussler", title = "On total regulators generated by derivation relations", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "131--148", month = "????", 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. for Inf. Process., Tech. Univ. of Graz, Austria", keywords = "context-free languages; derivation relations; formal languages; regular language; total regulators; well-quasi-order", pubcountry = "Netherlands A03", treatment = "T Theoretical or Mathematical", } @Article{Aalbersberg:1985:CSP, author = "I. J. J. Aalbersberg and G. Rozenberg", title = "{CTS} systems and {Petri} nets", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "149--162", month = "????", 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 = "Inst. of Appl. Math. and Comput. Sci., Leiden Univ., Netherlands", keywords = "automaton models; concurrent processes; context-free grammar selector'; context-free grammars; coordinated table selective substitution systems; CTS systems; directed graphs; grammar; Petri nets; unifying framework", pubcountry = "Netherlands A04", treatment = "T Theoretical or Mathematical", } @Article{Ayers:1985:DAS, author = "K. Ayers", title = "Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "163--174", month = "????", 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 = "Boise State Univ., ID, USA", keywords = "automata theory; closure properties; context-sensitive languages; grammars; lambda -linearly bounded deque automata; ordered grammar; pushdown automaton; semilinear bounded languages", pubcountry = "Netherlands A05", treatment = "T Theoretical or Mathematical", } @Article{Kobayashi:1985:SON, author = "K. Kobayashi", title = "On the structure of one-tape nondeterministic {Turing} machine time hierarchy", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "175--193", month = "????", 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 Inf. Sci., Tokyo Inst. of Technol., Japan", keywords = "computational complexity; crossing sequences; Kolmogorov complexity; one-tape nondeterministic Turing machine time hierarchy; Turing machines", pubcountry = "Netherlands A06", treatment = "T Theoretical or Mathematical", } @Article{Huang:1985:IFS, author = "Ming-Deh A. Huang and K. J. Lieberherr", title = "Implications of forbidden structures for extremal algorithmic problems", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "195--210", month = "????", 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)", corpsource = "Dept. of Electr. Eng. and Comput. Sci., Princeton Univ., NJ, USA", keywords = "approximation theory; extremal algorithmic problems; forbidden structures; linear time; maximisation; P-optimal approximation algorithms; P-optimal thresholds; RAM; satisfiability problems", pubcountry = "Netherlands A07", treatment = "T Theoretical or Mathematical", } @Article{Mascari:1985:WNA, author = "G. Mascari and M. {Venturini Zilli}", title = "While-programs with nondeterministic assignments and the logic {ALNA}", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "211--235", month = "????", 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 = "Istituto per le Applicazioni del Calcolo 'Mauro Picone', CNR, Roma, Italy", keywords = "Algorithmic Logic for while-programs with Nondeterministic Assignments; computation trees; logic ALNA; nondeterministic assignments; programming theory; semantical properties; trees (mathematics); unbounded countable nondeterminism; while-programs", pubcountry = "Netherlands A08", treatment = "T Theoretical or Mathematical", } @Article{Balcazar:1985:BQM, author = "J. L. Balcazar and R. V. Book and U. Schoning", title = "On bounded query machines", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "237--243", month = "????", 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 = "Fac. d'Inf., Univ. Politecnica de Barcelona, Spain", keywords = "bounded query machines; computational complexity", pubcountry = "Netherlands A09", treatment = "T Theoretical or Mathematical", } @Article{Kanaoka:1985:HDS, author = "T. Kanaoka and S. Tomita", title = "Homogeneous decomposition of stochastic systems", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "245--255", month = "????", 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 Eng., Yamaguchi Univ., Ube, Japan", keywords = "automata theory; decomposition theory; homogeneous decomposition; homogeneous whirl decomposition; nonpseudostochastic; state splitting; stochastic systems; transition matrices", pubcountry = "Netherlands A10", treatment = "T Theoretical or Mathematical", } @Article{Abdali:1985:TCR, author = "S. K. Abdali and B. D. Saunders", title = "Transitive closure and related semiring properties via eliminants", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "257--274", month = "????", 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. and Eng., Univ. of Pet. and Min., Dhahran, Saudi Arabia", keywords = "algebraic structures; axiomatic formulation; closed semirings; closure algorithms; computer science; correctness; eliminants; finite automata; graph-theoretical path problems; linear equations; matrix closure; operations research; regular expressions; semiring properties; transitive closure", pubcountry = "Netherlands A11", treatment = "T Theoretical or Mathematical", } @Article{Fogelman-Soulie:1985:PSC, author = "F. Fogelman-Soulie", title = "Parallel and sequential computation on {Boolean} networks", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "275--300", month = "????", 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. de Dynamique des Reseaux, Paris, France", keywords = "asymptotic behavior; automata theory; Boolean functions; Boolean networks; computing elements; discrete iterations; large assemblies; limit cycles; model; parallel computation; sequential computation; spatial characterization; spatial structure", pubcountry = "Netherlands A12", treatment = "T Theoretical or Mathematical", } @Article{Ginzburg:1985:RSS, author = "A. Ginzburg and M. Yoeli", title = "Reducibility of synchronization structures", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "301--314", month = "????", 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); C6110 (Systems analysis and programming)", corpsource = "Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel", keywords = "control structures; homomorphism; necessary and sufficient conditions; posets; programming theory; reducibility; structured programming; synchronisation; synchronization structures", pubcountry = "Netherlands A13", treatment = "T Theoretical or Mathematical", } @Article{Urbanek:1985:GNF, author = "F. J. Urbanek", title = "On {Greibach} normal form construction", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "315--317", month = "????", year = "1985", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Mon Oct 26 07:53:09 1998", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Inst. fur Algebra und Diskrete Math., Tech. Univ., Wien, Austria", keywords = "Chomsky normal form grammar; context-free grammars; derivation-oriented reasoning; Greibach normal form; Greibach normal form construction", pubcountry = "Netherlands A14", treatment = "T Theoretical or Mathematical", } @Article{Kaminski:1985:LBP, author = "M. Kaminski", title = "A lower bound for polynomial multiplication", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "319--322", month = "????", 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)", corpsource = "Dept. of Comput. Sci., Waterloo Univ., Ont., Canada", keywords = "lower bound; polynomial multiplication; polynomials; two third degree polynomials", pubcountry = "Netherlands A15", treatment = "T Theoretical or Mathematical", } @Article{Krishnamoorthy:1985:RPO, author = "M. S. Krishnamoorthy and P. Narendran", title = "On recursive path ordering", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "323--328", month = "????", year = "1985", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", acknowledgement = ack-nhfb, classification = "C4200 (Computer theory)", corpsource = "Dept. of Comput. Sci., Rensselaer Polytech. Inst., Troy, NY, USA", keywords = "computation theory; function symbols; NP-complete; partial order; recursive path ordering; well-founded partial order", pubcountry = "Netherlands A16", treatment = "T Theoretical or Mathematical", } @Article{Gonthier:1985:ACP, author = "G. Gonthier", title = "Algebraic calculi of processes and net expressions", journal = j-THEOR-COMP-SCI, volume = "40", number = "2-3", pages = "329--337", month = "????", year = "1985", CODEN = "TCSCDI", ISSN = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", acknowledgement = ack-nhfb, classification = "B0210 (Algebra); B0250 (Combinatorial mathematics); C1110 (Algebra); C1160 (Combinatorial mathematics)", corpsource = "CMA-ENSMP Sophia-Antipolis, Valbonne, France", keywords = "algebra; algebraic calculi; flow algebra; graph theory; MEIJE algebra; net expressions", pubcountry = "Netherlands A17", treatment = "T Theoretical or Mathematical", } @Article{Paun:1985:VRC, author = "G. P{\u{a}}un", title = "A variant of random context grammars: semi-conditional grammars", journal = j-THEOR-COMP-SCI, volume = "41", number = "1", pages = "1--17", month = "????", 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., Bucuresti, Romania", keywords = "context-free grammar; context-free grammars; context-sensitive languages; generative capacity; random context grammars; recursively enumerable languages; semiconditional grammars", pubcountry = "Netherlands A01", treatment = "T Theoretical or Mathematical", } @Article{Goles:1985:DPA, author = "E. Goles", title = "Dynamics of positive automata networks", journal = j-THEOR-COMP-SCI, volume = "41", number = "1", pages = "19--32", month = "????", 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. Matematicas, Chile Univ., Santiago, Chile", keywords = "automata theory; cycle length; dynamic behaviour; Lyapunov function; Lyapunov methods; majority networks; positive automata networks; threshold networks; transient length", pubcountry = "Netherlands A02", treatment = "X Experimental", } @Article{Cazanescu:1985:CT, author = "V. E. Cazanescu", title = "On context-free trees", journal = j-THEOR-COMP-SCI, volume = "41", number = "1", pages = "33--50", month = "????", 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 = "Dept. of Math., Bucharest Univ., Romania", keywords = "context-free grammars; context-free languages; context-free trees; generalised iterative algebraic theor