,\ell>1$}", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "17--56", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "IBM Thomas J. Watson Research Cent", affiliationaddress = "Yorktown Heights, NY, USA", classification = "723; 921; C4240 (Programming and algorithm theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; classification; Coefficients of Polynomials; computational complexity; Computer Programming; Mathematical Techniques--Polynomials; Minimal Bilinear Algorithms; minimal bilinear algorithms; Noncommutative Algorithms; polynomials; Polynomials Products", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Borodin:1988:TBS, author = "Allan Borodin and Faith E. Fich and Friedhelm {Meyer auf der Heide} and Eli Upfal and Avi Wigderson", title = "A tradeoff between search and update time for the implicit dictionary problem", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "57--68", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Toronto", affiliationaddress = "Toronto, Ont, Can", classification = "723; C6120 (File organisation); C6160 (Database management systems (DBMS))", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. Sci., Toronto Univ., Ont., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Data Processing--Data Structures; data structures; Data Types; database management systems; Database Searching; Database Systems; Database Update; Implicit Dictionary Problem; implicit dictionary problem; search time; update time", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Brandenburg:1988:ISQ, author = "Franz J. Brandenburg", title = "On the intersection of stacks and queues", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "69--80", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Passau", affiliationaddress = "Passau, West Ger", classification = "721; C4210 (Formal logic); C4220 (Automata theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Fakultat f{\"u}r Math. und Inf., Passau Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; automata theory; Context Free Language; context-free languages; families of languages; Formal Languages; formal languages; intersection; Intersections of Language Families; Nondeterministic Real Time Machines; nondeterministic real-time machines; one-reset tape; one-reversal restrictions; pushdown stack; Pushdown Stacks; Queues; queues; regular languages; retrieval restriction; stacks; symmetry", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Choffrut:1988:CRF, author = "C. Choffrut and M. P. Sch{\"u}tz\-en\-berger", title = "Counting with rational functions", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "81--101", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Rouen", affiliationaddress = "Mont-St.-Aignan, Fr", classification = "721; C4220 (Automata theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Fac. des Sci., Rowen Univ., Mont-Saint-Aignan, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; automata theory; Counting Functions; free cyclic monoid; Free Cyclic Monoids; free monoid; Free Monoids; integer; Lipschitz Condition; Lipschitz condition; Lipschitz Functions; Rational Functions; rational functions counting", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{DeFelice:1988:FBS, author = "Clelia {De Felice}", title = "Finite biprefix sets of paths in a graph", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "103--128", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ di Napoli", affiliationaddress = "Naples, Italy", classification = "723; 921; B0250 (Combinatorial mathematics); B6120B (Codes); C1160 (Combinatorial mathematics); C1260 (Information theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dipartimento di Matematica e Appl., Napoli Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Cesari-Sch{\"u}tzenberger Algorithm; Codes of Paths in a Graph; Codes, Symbolic; Computer Programming--Algorithms; Finite Biprefix Sets; Graph Theory; Integration of Codes; Mathematical Techniques; codes; combinatorial theory; decoding; double-infinite paths; finite biprefix sets; graph; graph theory; integration; maximal biprefix codes of words", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Hartmanis:1988:CCM, author = "Juris Hartmanis and Lane A. Hemachandra", title = "Complexity classes without machines: On complete languages for {UP}", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "129--142", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Cornell Univ", affiliationaddress = "Ithaca, NY, USA", classification = "721; 723; C4210 (Formal logic); C4240 (Programming and algorithm theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Complete Languages; complete languages; Complexity Classes; complexity classes; computational complexity; Computer Metatheory; counting; Counting Class up; counting classes; Formal Languages; formal languages; intersection classes; np Languages; probabilistic classes; UP", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Kirschenhofer:1988:FRD, author = "Peter Kirschenhofer and Helmut Prodinger", title = "Further results on digital search trees", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "143--154", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Technische Univ Wien", affiliationaddress = "Vienna, Austria", classification = "723; 921; C1160 (Combinatorial mathematics); C6120 (File organisation)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Inst. f{\"u}r Algebra and Diskrete Math., Tech. Univ. Wien, Vienna, Austria", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Binary Tries; Calculus of Finite Differences; Computer Programming--Algorithms; cost of insertion; Data Processing; Data Structures; data structures; Database Searching; Database Systems; Digital Search Trees; digital search trees; distribution results; finite differences; Insertion Costs; Mathematical Techniques--Trees; Patricia Tries; Patricia tries; trees (mathematics)", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Kraus:1988:KBT, author = "Sarit Kraus and Daniel Lehmann", title = "Knowledge, belief and time", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "155--174", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Hebrew Univ", affiliationaddress = "Jerusalem, Isr", classification = "723; 922; C4210 (Formal logic)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. Sci., Hebrew Univ., Jerusalem, Israel", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Artificial Intelligence; Belief; belief; Cognitive Systems; completeness result; decision procedure described; Decision Procedures; Decision Theory and Analysis; formal logic; Knowledge; knowledge; logical system; Logical Systems; persistence; Systems Science and Cybernetics; Time", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Lange:1988:DNR, author = "Klaus-J{\"o}rn Lange", title = "Decompositions of nondeterministic reductions", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "175--181", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Hamburg", affiliationaddress = "Hamburg, West Ger", classification = "721; C4210 (Formal logic); C4220 (Automata theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Fachbereich Inf., Univ. Hamburg, West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; automata theory; Conjuctive Turing Reducibility; decompositions; formal language operations; Formal Languages; formal languages; Logarithmic Oracle Hierarchy; logarithmic space bound; Many-One Reducibility; Nondeterministic Reductions; nondeterministic reductions; Nonerasing Homomorphisms; nonerasing homomorphisms; polynomial time bound; Turing Reducibility", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Lisper:1988:SEC, author = "Bjorn Lisper", title = "Synthesis and equivalence of concurrent systems", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "183--199", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Royal Inst of Technology", affiliationaddress = "Stockholm, Swed", classification = "722; 723; 921; C4130 (Interpolation and function approximation); C4190 (Other numerical methods); C4290 (Other computer theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "NADA, R. Inst. of Technol., Stockholm, Sweden", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "cell action structure; communication structure; Communication Structures; computational networks; Computer Programming--Algorithms; Computer Systems, Digital; concurrent systems; equivalence; fast Fourier transforms; FFT algorithm; fft Algorithms; framework for synthesis; Local Memory; local memory; Mathematical Techniques--Algebra; Mathematical Transformations--Fast Fourier Transforms; Parallel Processing; parallel processing; polynomials; specification; Synchronous Concurrent Systems; target hardware", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Metivier:1988:RSF, author = "Y. Metivier", title = "On recognizable subsets of free partially commutative monoids", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "201--208", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Bordeaux I", affiliationaddress = "Talence, Fr", classification = "721; 921; C1160 (Combinatorial mathematics); C4220 (Automata theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Bordeaux I Univ., Talence, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "automata theory; Automata Theory; connected noncommutation graph; Free Partially Abelian Monoids; free partially commutative monoids; Free Partially Commutative Monoids; graph theory; iterative factor; Mathematical Techniques--Graph Theory; Noncommutation Graph; recognizable subsets; Recognizable Subsets", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Monien:1988:MCN, author = "B. Monien and I. H. Sudborough", title = "{Min Cut} is {NP}-complete for edge weighted trees", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "209--229", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Paderborn", affiliationaddress = "Paderborn, West Ger", classification = "723; 921; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Fachbereich Math. und Inf., Paderborn Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Complexity; Computer Metatheory; Edge Weighted Trees; edge weighted trees; graph theory; Mathematical Techniques; Min Cut Linear Arrangement Problem; NP-complete; np-completeness; planar graphs; polynomial size edge weights; progressive black white pebble demand; search number; topological bandwidth; Trees; trees (mathematics); vertex separation", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Pecuchet:1988:ESP, author = "Jean-Pierre Pecuchet", title = "Etude syntaxique des parties reconnaissables de mots infinis. ({French}) [{Syntactic} study of rational omega-languages of infinite words]", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "231--248", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "CNRS", affiliationaddress = "Mont-St.-Aignan, Fr", classification = "721; C4210 (Formal logic); C4220 (Automata theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "CNRS LITP, Lab. d'Inf. de Rouen, Mont-Saint-Aignan, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "automata; automata theory; Automata Theory; Decidability; formal languages; Formal Languages; infinite words; locally testable languages; Locally Testable Languages; piecewise testable languages; Piecewise Testable Languages; Rational Omega Languages; rational omega-languages; semigroups; Semigroups; Syntax", language = "French", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Reed:1988:TMC, author = "G. M. Reed and A. W. Roscoe", title = "A timed model for communicating sequential processes", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "249--261", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Oxford Univ", affiliationaddress = "Oxford, Engl", classification = "723; C4240 (Programming and algorithm theory); C6140 (Programming languages)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Oxford Univ., UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Communicating Sequential Processes; communicating sequential processes; Computer Programming Languages; Computer Systems, Digital--Parallel Processing; concealment; csp; CSP; distributed computing; Models; nondeterministic choice; parallel composition; Parallel Languages; programming languages; programming theory; Real Time Models; recursion; semantic models; sequential composition; specification; time-critical processes; timed model; timed stability model; timing assumptions; verification", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Rosier:1988:CDF, author = "Louis E. Rosier and Hsu-Chun Yen", title = "On the complexity of deciding fair termination of probabilistic concurrent finite-state programs", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "263--324", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Texas at Austin", affiliationaddress = "Austin, TX, USA", classification = "721; 723; 921; C4220 (Automata theory); C4240 (Programming and algorithm theory)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. Sci., Texas Univ., Austin, TX, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "alternating logspace hierarchy; Automata Theory--Finite Automata; Complexity; complexity of deciding; computational complexity; Computer Metatheory--Programming Theory; Computer Programming; EXPTIME-complete; Fair Termination; fair termination; finite automata; Lower Bounds; Mathematical Techniques--Graph Theory; Probabilistic Concurrent Finite-State Programs; probabilistic concurrent finite-state programs; programming theory; PSPACE-complete; PTIME; Theory; Turing Machines; Upper Bounds", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Simon:1988:IAT, author = "Klaus Simon", title = "An improved algorithm for transitive closure on acyclic digraphs", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "325--346", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ des Saarlandes", affiliationaddress = "Saarbruecken, West Ger", classification = "723; 921; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Angewandte Math. und Inf., Univ. des Saarlandes, Saarbrucken, West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Acyclic Digraphs; acyclic digraphs; algorithm; Algorithms; Chain Decomposition; chain decomposition; Computer Programming; directed graphs; Mathematical Techniques--Graph Theory; Topological Sorting; Transitive Closure; transitive closure; transitive reduction; Worst Case Space; Worst Case Time; worst-case runtime", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Stirling:1988:GOG, author = "Colin Stirling", title = "A generalization of {Owicki-Gries}'s {Hoare} logic for a concurrent while language", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "347--359", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Edinburgh", affiliationaddress = "Edinburgh, Scotl", classification = "723; C4210 (Formal logic)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. Sci., Edinburgh Univ., UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Programming Languages; Computer Systems, Digital--Parallel Processing; Concurrent While Language; concurrent while language; first-order formulas; formal languages; formal logic; Hoare asserted programs; Hoare Logic; Hoare logic; Operational Semantics; operational semantics; potential computations; sets of invariants; syntax-directed generalization; Theory", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Straubing:1988:SLD, author = "Howard Straubing", title = "Semigroups and languages of dot-depth two", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "361--378", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Boston Coll", affiliationaddress = "Chestnut Hill, MA, USA", classification = "721; C4210 (Formal logic)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. Sci., Boston Coll., Chestnut Hill, MA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Dot Depth; dot-depth two; Formal Languages; formal languages; languages; mathematical logic; Mathematical Logics; Semigroup Theory; semigroups; Star Free Languages; star-free language", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Varman:1988:EPA, author = "Peter Varman and Kshitij Doshi", title = "An efficient parallel algorithm for updating minimum spanning trees", journal = j-THEOR-COMP-SCI, volume = "58", number = "1-3", pages = "379--397", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Rice Univ", affiliationaddress = "Houston, TX, USA", classification = "723; 921; C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory); C5320G (Semiconductor storage)", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conflocation = "Rennes, France; 15-19 July 1986", conftitle = "Thirteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Electr. and Comput. Eng., George R. Brown Sch. of Eng., Rice Univ., Houston, TX, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; Computer Programming; Concurrent Read Exclusive Write; concurrent-read-exclusive-write parallel random access machine; graph theory; Mathematical Techniques--Trees; Minimum Spanning Trees; n-vertex graph; parallel algorithm; Parallel Algorithms; parallel algorithms; Parallel Random Access Machines (prams); random-access storage; Tree Updates; trees (mathematics); updating minimum spanning trees", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput. Sci", treatment = "T Theoretical or Mathematical", } @Article{Bosco:1988:NVS, author = "Pier Giorgio Bosco and Elio Giovannetti and Corrado Moiso", title = "Narrowing vs. {SLD}-resolution", journal = j-THEOR-COMP-SCI, volume = "59", number = "1--2", pages = "3--23", month = jul, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Cent Studi e Lab Telecomunicazioni", affiliationaddress = "Turin, Italy", classification = "723; C4210 (Formal logic); C4240 (Programming and algorithm theory)", conference = "International Joint Conference on Theory and Practice of Software Development --- TAPSOFT '87", conflocation = "Pisa, Italy; 23-27 March 1987", conftitle = "International Joint Conference on Theory and Practice of Software Development", corpsource = "Lab. Telecommun., Turin, Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; Computer Metatheory--Programming Theory; Computer Programming; Computer Programming Languages--Theory; E Unification Algorithms; E-unification; flattening; formal logic; Functional Programming; functional programming; Logic Programming; logic programming; narrowing; Narrowing Sequences; narrowing sequences; programming theory; resolution sequences; semantic unification; Semantic Unification Algorithms; sld Resolution; SLD-resolution", meetingaddress = "Pisa, Italy", meetingdate = "Mar 23--27 1987", meetingdate2 = "03/23--27/87", pubcountry = "Netherlands", sponsor = "Univ di Pisa, Pisa, Italy; IEI-CNR; CNUCE-CNR; EATS; AICA", treatment = "T Theoretical or Mathematical", } @Article{Boudol:1988:CA, author = "G. Boudol and I. Castellani", title = "Concurrency and atomicity", journal = j-THEOR-COMP-SCI, volume = "59", number = "1--2", pages = "25--84", month = jul, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "INRIA Sophia-Antipolis", affiliationaddress = "Valbonne, Fr", classification = "723; C4210 (Formal logic); C4240 (Programming and algorithm theory)", conference = "International Joint Conference on Theory and Practice of Software Development --- TAPSOFT '87", conflocation = "Pisa, Italy; 23-27 March 1987", conftitle = "International Joint Conference on Theory and Practice of Software Development", corpsource = "INRIA Sophia-Antipolis, Valbonne, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "abstraction mechanism; atomic actions; Atomic Actions; atomicity; bisimulation; calculus of concurrent processes; Calculus of Concurrent Processes; Computer Metatheory; Computer Programming Languages--Theory; Computer Programming--Theory; concurrency; finite computation; formal languages; Labeled Posets; labelled poset; labelled transition relation; Operational Semantics; parallel programming; programming theory; Programming Theory; semantics; Semantics of Concurrency; sequential nondeterminism; single event; synchronization", meetingaddress = "Pisa, Italy", meetingdate = "Mar 23--27 1987", meetingdate2 = "03/23--27/87", pubcountry = "Netherlands", sponsor = "Univ di Pisa, Pisa, Italy; IEI-CNR; CNUCE-CNR; EATS; AICA", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Breazu-Tannen:1988:EMP, author = "Val Breazu-Tannen and Thierry Coquand", title = "Extensional models for polymorphism", journal = j-THEOR-COMP-SCI, volume = "59", number = "1--2", pages = "85--114", month = jul, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Pennsylvania", affiliationaddress = "Philadelphia, PA, USA", classification = "723; C4210 (Formal logic); C4240 (Programming and algorithm theory)", conference = "International Joint Conference on Theory and Practice of Software Development --- TAPSOFT '87", conflocation = "Pisa, Italy; 23-27 March 1987", conftitle = "International Joint Conference on Theory and Practice of Software Development", corpsource = "Dept. of Comput. and Inf. Sci., Pennsylvania Univ., Philadelphia, PA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "booleans; Computer Metatheory; Computer Programming Languages; Data Types; Extensional Models; extensional models; formal languages; functional languages; Girard-Reynolds polymorphic lambda calculus; object oriented languages; Object Oriented Programming Languages; polymorphic extensional collapse; polymorphic integers; Polymorphic Lambda Calculus; Polymorphism; polymorphism; programming theory; Theory", meetingaddress = "Pisa, Italy", meetingdate = "Mar 23--27 1987", meetingdate2 = "03/23--27/87", pubcountry = "Netherlands", sponsor = "Univ di Pisa, Pisa, Italy; IEI-CNR; CNUCE-CNR; EATS; AICA", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Browne:1988:CFK, author = "M. C. Browne and E. M. Clarke and O. Gr{\"u}mberg", title = "Characterizing finite {Kripke} structures in {Propositional Temporal Logic}", journal = j-THEOR-COMP-SCI, volume = "59", number = "1--2", pages = "115--131", month = jul, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Carnegie Mellon Univ", affiliationaddress = "Pittsburgh, PA, USA", classification = "723; C4210 (Formal logic)", conference = "International Joint Conference on Theory and Practice of Software Development --- TAPSOFT '87", conflocation = "Pisa, Italy; 23-27 March 1987", conftitle = "International Joint Conference on Theory and Practice of Software Development", corpsource = "Dept. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "bisimulation; Branching Time Logic; Branching Time Operators; branching-time operators; Computer Metatheory; Computer Programming--Algorithms; CTL formula; equivalence; equivalence with respect to stuttering; Finite Kripke Structures; finite Kripke structures; Formal Logic; formal logic; infinite behaviors; linear-time operators; modulo stuttering; nexttime operator; polynomial algorithm; Propositional Temporal Logic; propositional temporal logic; synthesis procedures", meetingaddress = "Pisa, Italy", meetingdate = "Mar 23--27 1987", meetingdate2 = "03/23--27/87", pubcountry = "Netherlands", sponsor = "Univ di Pisa, Pisa, Italy; IEI-CNR; CNUCE-CNR; EATS; AICA", treatment = "T Theoretical or Mathematical", } @Article{Drabent:1988:IAM, author = "Wlodzimierz Drabent and Jan Maluszynski", title = "Inductive assertion method for logic programs", journal = j-THEOR-COMP-SCI, volume = "59", number = "1--2", pages = "133--155", month = jul, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Polish Acad of Sciences", affiliationaddress = "Warsaw, Pol", classification = "723; C4240 (Programming and algorithm theory)", conference = "International Joint Conference on Theory and Practice of Software Development --- TAPSOFT '87", conflocation = "Pisa, Italy; 23-27 March 1987", conftitle = "International Joint Conference on Theory and Practice of Software Development", corpsource = "Inst. of Comput. Sci., Polish Acad. of Sci., Warszawa, Poland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "arbitrary search strategy; Computer Metatheory--Programming Theory; Computer Programming; Declarative Semantics; declarative semantics; extra-logical built-in procedures; Inductive Assertion; inductive assertion method; informal reasoning; logic programming; Logic Programs; logic programs; OR-parallelism; Partial Correctness; partial correctness; procedure calls; programming theory; Prolog backtracking; Prolog Computation Rule; Prolog computation rule; theorem proving; Theory", meetingaddress = "Pisa, Italy", meetingdate = "Mar 23--27 1987", meetingdate2 = "03/23--27/87", pubcountry = "Netherlands", sponsor = "Univ di Pisa, Pisa, Italy; IEI-CNR; CNUCE-CNR; EATS; AICA", treatment = "T Theoretical or Mathematical", } @Article{Lafont:1988:LAM, author = "Y. Lafont", title = "The linear abstract machine", journal = j-THEOR-COMP-SCI, volume = "59", number = "1--2", pages = "157--180", month = jul, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Imperial Coll", affiliationaddress = "London, Engl", classification = "723; C4220 (Automata theory); C4240 (Programming and algorithm theory); C6110 (Systems analysis and programming)", conference = "International Joint Conference on Theory and Practice of Software Development --- TAPSOFT '87", conflocation = "Pisa, Italy; 23-27 March 1987", conftitle = "International Joint Conference on Theory and Practice of Software Development", corpsource = "Dept. of Comput., Imperial Coll., London, UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "automata theory; clean semantics; Computer Metatheory--Programming Theory; Computer Programming; functional programming; Functional Programming; implementation technique; lazy evaluation; Lazy Evaluation; linear abstract machine; Linear Abstract Machine; linear logic; programming; programming theory; Semantics of Side Effects; side effects; Theory", meetingaddress = "Pisa, Italy", meetingdate = "Mar 23--27 1987", meetingdate2 = "03/23--27/87", pubcountry = "Netherlands", sponsor = "Univ di Pisa, Pisa, Italy; IEI-CNR; CNUCE-CNR; EATS; AICA", treatment = "T Theoretical or Mathematical", } @Article{RonchiDellaRocca:1988:PTS, author = "Simona {Ronchi Della Rocca}", title = "Principal type scheme and unification for intersection type discipline", journal = j-THEOR-COMP-SCI, volume = "59", number = "1--2", pages = "181--209", month = jul, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ di Torino", affiliationaddress = "Turin, Italy", classification = "723; C4210 (Formal logic)", conference = "International Joint Conference on Theory and Practice of Software Development --- TAPSOFT '87", conflocation = "Pisa, Italy; 23-27 March 1987", conftitle = "International Joint Conference on Theory and Practice of Software Development", corpsource = "Dipartimento de Inf. Torino Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; Computer Programming Languages; formal logic; functionality theory; Intersection Type Discipline; intersection type discipline; lambda -calculus; Lambda Calculus; lambda calculus; Principal Type Scheme; principal type scheme; Theory; type schemes; Unification; unification", meetingaddress = "Pisa, Italy", meetingdate = "Mar 23--27 1987", meetingdate2 = "03/23--27/87", pubcountry = "Netherlands", sponsor = "Univ di Pisa, Pisa, Italy; IEI-CNR; CNUCE-CNR; EATS; AICA", treatment = "T Theoretical or Mathematical", } @Article{Hesselink:1988:IRU, author = "Wim H. Hesselink", title = "Interpretations of recursion under unbounded nondeterminacy", journal = j-THEOR-COMP-SCI, volume = "59", number = "3", pages = "211--234", month = aug, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Groningen Univ", affiliationaddress = "Groningen, Neth", classification = "723; C6120 (File organisation); C6140 (Programming languages)", corpsource = "Dept. of Math. and Comput. Sci., Groningen Univ., Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "alternatives; arbitrary atomic statements; composition; Computer Metatheory; Computer Programming Languages; data structures; Egli-Milner Ordering; Egli-Milner ordering; mutual recursion; preparator functions; programming languages; Recursion; recursion interpretation; Semantics; Theory; Unbounded Nondeterminacy; unbounded nondeterminacy; Weakest Liberal Precondition; weakest precondition; Weakest Precondition", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Hesselink:1988:DFM, author = "Wim H. Hesselink", title = "Deadlock and fairness in morphisms of transition systems", journal = j-THEOR-COMP-SCI, volume = "59", number = "3", pages = "235--257", month = aug, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Groningen Univ", affiliationaddress = "Groningen, Neth", classification = "723; C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math. and Comput. Sci., Groningen Univ., Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "bisimilar processes; Computer Metatheory; Computer Programming Languages; deadlock; execution sequence; Fair Communicating Merge; fairness; image sequence; morphisms; Morphisms; programming theory; Theory; Transition Systems; transition systems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hodel:1988:ODE, author = "A. Scottedward Hodel and Michael C. Loui", title = "Optimal dynamic embedding of {$X$}-trees into arrays", journal = j-THEOR-COMP-SCI, volume = "59", number = "3", pages = "259--276", month = aug, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Illinois at Urbana-Champaign", affiliationaddress = "Urbana, IL, USA", classification = "721; 723; 921; C1160 (Combinatorial mathematics); C6120 (File organisation)", corpsource = "Dept. of Electr. and Comput. Eng., Illinois Univ., Urbana-Champaign, IL, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Arrays; Automata Theory; d-dimensional array; Data Processing; data structures; File Organization; multihead bounded activity machine; Optimal Dynamic Embedding; optimal dynamic embedding; Optimization; Space Complexity; storage medium; trees (mathematics); X-Trees; X-trees", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Kalorkoti:1988:TIM, author = "K. Kalorkoti", title = "The trace invariant and matrix inversion", journal = j-THEOR-COMP-SCI, volume = "59", number = "3", pages = "277--286", month = aug, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Edinburgh", affiliationaddress = "Edinburgh, Scotl", classification = "723; 921; C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., Edinburgh Univ., UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; Computational Complexity; computational complexity; Computer Programming; Computer Systems, Digital--Parallel Processing; Mathematical Techniques--Matrix Algebra; matrix inversion; matrix multiplication; nonscalar complexity measure; Parallel Algorithms; parallel computations; straight-line model; Trace Invariant; trace invariant", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Schmidt-Schauss:1988:ICU, author = "Manfred Schmidt-Schauss", title = "Implication of clauses is undecidable", journal = j-THEOR-COMP-SCI, volume = "59", number = "3", pages = "287--296", month = aug, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Kaiserslautern", affiliationaddress = "Kaiserslautern, West Ger", classification = "723; C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., Kaiserslautern Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Artificial Intelligence; Automated Deduction Systems; Automatic Theorem Proving; clause sets; clauses implication; Computer Metatheory; decidability; decision problem; finitely generated stable transitive relations; Implication of Clauses; Undecidability; undecidable", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Rytter:1988:EPC, author = "Wojciech Rytter", title = "On efficient parallel computations for some dynamic programming problems", journal = j-THEOR-COMP-SCI, volume = "59", number = "3", pages = "297--307", month = aug, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Warsaw Univ", affiliationaddress = "Warsaw, Pol", classification = "921; C1160 (Combinatorial mathematics); C1180 (Optimisation techniques); C4240 (Programming and algorithm theory); C5320G (Semiconductor storage)", corpsource = "Inst. of Inf., Warsaw Univ., Poland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Binary Tree Search; Computer Programming--Algorithms; Computer Systems, Digital--Parallel Processing; CREW P-RAM; cube-connected computer; dynamic programming; dynamic programming problems; Mathematical Programming, Dynamic; Matrix Multiplication; optimal binary search tree; optimal order; optimal triangulation of polygons; Parallel Algorithms; parallel algorithms; parallel computations; parallel random-access machine; parsing; perfect shuffle computer; Polygon Triangularization; random-access storage; straight-line programs; trees (mathematics)", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Engelfriet:1988:NBN, author = "Joost Engelfriet and George Leih", title = "Nonterminal bounded {NLC} graph grammars", journal = j-THEOR-COMP-SCI, volume = "59", number = "3", pages = "309--315", month = aug, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Leiden", affiliationaddress = "Leiden, Neth", classification = "721; C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., Leiden Univ., Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; formal languages; Grammars; grammars; graph languages; graph theory; linear graph grammar; nce Graph Grammars; neighbourhood controlled embedding; nlc Graph Grammars; node label controlled graph grammars; nonterminal bounded; Nonterminal Bounded Grammars", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Stoughton:1988:SR, author = "Allen Stoughton", title = "Substitution revisited", journal = j-THEOR-COMP-SCI, volume = "59", number = "3", pages = "317--325", month = aug, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Sussex", affiliationaddress = "Brighton, Engl", classification = "723; C4210 (Formal logic)", corpsource = "Sch. of Math. and Phys. Sci., Sussex Univ., Brighton, UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Alpha Congruence; Computer Metatheory; Computer Programming Languages; Denotational Semantics; formal languages; formal logic; induction-free proofs; lambda calculus; Lambda Calculus; Simultaneous Substitution; simultaneous substitution; structural induction; Substitution Lemma; Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Aalbersberg:1988:TT, author = "I. J. Aalbersberg and G. Rozenberg", title = "Theory of traces", journal = j-THEOR-COMP-SCI, volume = "60", number = "1", pages = "1--82", month = mar, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., Leiden Univ., Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "behavior; concurrent systems; directed graphs; formal string language theory; labeled acyclic directed graphs; labeled partial orders; mathematical description; nonsequential nature of causality; parallel programming; partial commutativity; Petri nets; programming theory; sequential nature of observations; system behavior; theory of traces", pubcountry = "Netherlands A01", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Tiuryn:1988:SRB, author = "J. Tiuryn and P. Urzyczyn", title = "Some relationships between logics of programs and complexity theory", journal = j-THEOR-COMP-SCI, volume = "60", number = "1", pages = "83--108", month = mar, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Inst. of Math., Warsaw Univ., Poland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "arrays; comparative schematology; complexity theory; computational complexity; computational power; flow-diagrams; formal logic; logics; programming theory; recursive procedures", pubcountry = "Netherlands A02", treatment = "T Theoretical or Mathematical", } @Article{America:1988:DES, author = "P. America and J. {De Bakker}", title = "Designing equivalent semantic models for process creation", journal = j-THEOR-COMP-SCI, volume = "60", number = "2", pages = "109--176", month = sep, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Philips Res. Labs., Eindhoven, Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "denotational semantic; formal languages; languages; metric structures; operational semantics; parallel object-oriented languages; POOL; process creation; semantic models", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Roscoe:1988:LOP, author = "A. W. Roscoe and C. A. R. Hoare", title = "The laws of occam programming", journal = j-THEOR-COMP-SCI, volume = "60", number = "2", pages = "177--229", month = sep, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6140D (High level languages)", corpsource = "Comput. Lab., Oxford Univ., UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "algebraic laws; high level languages; normal form; occam; occam programming; programming theory; semantics; WHILE- free programs", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Eilam-Tzoreff:1988:MPS, author = "Tali Eilam-Tzoreff and Uzi Vishkin", title = "Matching patterns in strings subject to multi-linear transformations", journal = j-THEOR-COMP-SCI, volume = "60", number = "3", pages = "231--254", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Tel Aviv Univ", affiliationaddress = "Tel Aviv, Isr", classification = "723; C4200 (Computer theory)", corpsource = "Dept. of Comput. Sci., Sch. of Math. Sci., Tel Aviv Univ., Israel", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; computation theory; Computer Metatheory; Computer Programming; Minimum Distance Problems; multi-linear transformations; Multilinear Transformations; pattern matching; Pattern Matching; pattern recognition; strings; Strings of Real Numbers", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Duval:1988:GSC, author = "Jean-Pierre Duval", title = "{G}{\'e}n{\'e}ration d'une section des classes de conjugaison et arbre des mots de {Lyndon} de longueur born{\'e}e. ({French}) [{Generation} of a section of conjugation classes and tree of {Lyndon} words of limited length]", journal = j-THEOR-COMP-SCI, volume = "60", number = "3", pages = "255--283", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Rouen", affiliationaddress = "Mont-St.-Aignan, Fr", classification = "723; C4210 (Formal logic)", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; Computer Programming--Algorithms; conjugation class; Conjugation Classes; formal languages; lexicographical ordering; Lexicographical Ordering; linear time; Lyndon word; Lyndon Words; ordered alphabet; primitive word", language = "French", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Carpi:1988:SUA, author = "Arturo Carpi", title = "On synchronizing unambiguous automata", journal = j-THEOR-COMP-SCI, volume = "60", number = "3", pages = "285--296", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ di Napoli", affiliationaddress = "Naples, Italy", classification = "721; C4220 (Automata theory)", corpsource = "Dipartimento di Matematica e Applicazioni, Naples Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; automata theory; polynomial upper bound; Polynomial Upper Bounds; Shortest Word of Minimal Rank; synchronizing; Synchronizing Pairs; Synchronizing Unambiguous Automata; transition monoid; unambiguous automata; Unambiguous Relations", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Beeson:1988:TCS, author = "Michael J. Beeson", title = "Towards a computation system based on set theory", journal = j-THEOR-COMP-SCI, volume = "60", number = "3", pages = "297--340", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "San Jose State Univ", affiliationaddress = "San Jose, CA, USA", classification = "723; 921; C1160 (Combinatorial mathematics); C4200 (Computer theory)", corpsource = "Dept. of Math. and Comput. Sci., San Jose State Univ., CA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "axiomatic theory; computation system; Computation Systems; computation theory; Computer Metatheory; Computer Programming Languages; Data Processing--Data Structures; data structures; denotational semantics; Lambda Calculus; Mathematical Techniques--Set Theory; polymorphic set theory; recursion-theoretic model; recursive operations; set theory; set-theoretic model; Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Spehner:1988:RFL, author = "Jean-Claude Spehner", title = "La reconnaissance des facteurs d'un langage fini dans un texte en temps lin{\'e}aire. ({French}) [{The} recognition of the factors of a finite language in a text in linear time]", journal = j-THEOR-COMP-SCI, volume = "60", number = "3", pages = "341--381", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Haute Alsace", affiliationaddress = "Mulhouse, Fr", classification = "721; 723; C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dept. de Math. et Informatique, Fac. des Sci. et Tech., Univ. de Haute Alsace, Mulhouse, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "automata theory; Automata Theory; Computer Programming--Algorithms; Factor Transducers; family of identifiers; finite language; Finite Languages; formal languages; Formal Languages; Language Factors; partial automaton; transducer", language = "French", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Shallit:1988:GAS, author = "J. Shallit", title = "A generalization of automatic sequences", journal = j-THEOR-COMP-SCI, volume = "61", number = "1", pages = "1--16", month = oct, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Dept. of Math. and Comput. Sci., Dartmouth Coll., Hanover, NH, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "algebraic equation; automatic sequences; finite automata; finite automation; generalization; infinite Fibonacci word; k-uniform homomorphisms; uniform tag sequences", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Domosi:1988:CCP, author = "P. Domosi and Z. Esik", title = "Critical classes for the $\alpha_0$-product", journal = j-THEOR-COMP-SCI, volume = "61", number = "1", pages = "17--24", month = oct, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Inst. of Math., Lajos Kossuth Univ., Debrecen, Hungary", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "alpha /sub 0/-product; automata; automata theory; completeness; counters; Krohn-Rhodes Decomposition Theorem; necessary conditions; two-state reset automaton", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Meznik:1988:SIR, author = "I. Meznik", title = "On a subclass of infinity -regular languages", journal = j-THEOR-COMP-SCI, volume = "61", number = "1", pages = "25--32", month = oct, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Math., Turku Univ., Finland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "deterministic version; finite sequences; formal languages; G- machines; G-languages; infinite sequences; infinity -regular languages; subclass", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{He:1988:NOP, author = "Xin He", title = "A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs", journal = j-THEOR-COMP-SCI, volume = "61", number = "1", pages = "33--47", month = oct, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. and Inf. Sci., Ohio State Univ., Columbus, OH, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "graph theory; maximal independent set; nearly optimal parallel algorithm; parallel algorithms; planar graphs; PRAM; subroutine", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Seger:1988:OTS, author = "C.-J. Seger and J. A. Brzozowski", title = "An optimistic ternary simulation of gate races", journal = j-THEOR-COMP-SCI, volume = "61", number = "1", pages = "49--66", month = oct, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "B1265B (Logic circuits); C5210B (Computer-aided logic design)C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., Waterloo Univ., Ont., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "almost-equal-delay race model; critical races; digital networks; gate races; hazards; logic CAD; optimistic ternary simulation; ternary logic; ternary model; timing problems", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{vandenBroek:1988:CTG, author = "P. M. {van den Broek}", title = "Comparison of two graph-rewrite systems", journal = j-THEOR-COMP-SCI, volume = "61", number = "1", pages = "67--81", month = oct, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Inf., Twente Univ., Enschede, Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "common domain; graph-rewrite systems; rewriting systems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Thatte:1988:IFO, author = "S. Thatte", title = "Implementing first-order rewriting with constructor systems", journal = j-THEOR-COMP-SCI, volume = "61", number = "1", pages = "83--92", month = oct, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Electr. Eng. and Comput. Sci., Michigan Univ., Ann Arbor, MI, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "arbitrary call-by-value confluent systems; canonical systems; constructor systems; defining characteristics; first-order rewriting; rewriting systems; semiregular systems; translation", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Cori:1988:AA, author = "R. Cori and E. Sopena and M. Latteux and Y. Roos", title = "2-asynchronous automata", journal = j-THEOR-COMP-SCI, volume = "61", number = "1", pages = "93--102", month = oct, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Lab. de Math. et Inf., Bordeaux I Univ., Talence, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "2-asynchronous automata; communication problem; concurrent processes; finite automata; mailboxes", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Book:1988:SGC, author = "Ronald V. Book and Ding-Zhu Du", title = "The structure of generalized complexity cores", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "103--119", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of California", affiliationaddress = "Santa Barbara, CA, USA", classification = "723; C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math., California Univ., Santa Barbara, CA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "C-levelable; computational complexity; Computer Metatheory; countable class; finite union; finite variation; Generalized Complexity Cores; generalized complexity cores; Proper Hard Cores; Recursive Sets; Sets of Strings; Structural Properties; structure", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Dahlhaus:1988:PCP, author = "Elias Dahlhaus and Marek Karpinski", title = "Parallel construction of perfect matchings and {Hamiltonian} cycles on dense graphs", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "121--136", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Bonn", affiliationaddress = "Bonn, West Ger", classification = "723; 921; C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory); C5320G (Semiconductor storage)", corpsource = "Dept. of Comput. Sci., Bonn Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; communications; Computer Programming; Computer Systems, Digital--Parallel Processing; Concurrent Read-Exclusive Write; CREW-PRAM; dense graph combinatorics; dense graphs; Dense Graphs; distributed algorithms; graph theory; Hamiltonian cycles; Hamiltonian Cycles; Mathematical Techniques--Graph Theory; parallel algorithms; Parallel Algorithms; parallel algorithms; parallel construction; Parallel Random Access Machines; perfect matchings; Perfect Matchings; random-access storage; routing", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Moriya:1988:ACA, author = "Tetsuo Moriya and Hideki Yamasaki", title = "Accepting conditions for automata on $\omega$-languages", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "137--147", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Kokushikan Univ", affiliationaddress = "Tokyo, Jpn", classification = "721; C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Center for Inf. Sci., Kokushikan Univ., Tokyo, Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Accepting Conditions; Automata Theory; conditions acceptance; finite automata; Finite Automata; finite automata; formal languages; Inclusion Relations; Nondeterministic Finite Automata; omega-languages; Omega-Languages; Omega-Regular Languages", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{King:1988:AMF, author = "K. N. King", title = "Alternating multihead finite automata", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "149--174", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Georgia State Univ", affiliationaddress = "Atlanta, GA, USA", classification = "721; C4220 (Automata theory)", corpsource = "Dept. of Math. and Comput. Sci., Georgia State Univ., Atlanta, GA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "alternating multihead finite automata; Alternating Multihead Finite Automata; alternating Turing machine model; Alternating Turing Machine Model; Automata Theory; Deterministic Multihead Finite Automata; finite automata; Finite Automata; languages; Nondeterministic Multihead Finite Automata; Pushdown Automata; upper bounds", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{DiBattista:1988:APR, author = "Giuseppe {Di Battista} and Roberto Tamassia", title = "Algorithms for plane representations of acyclic digraphs", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "175--198", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Rome 'La Sapienza'", affiliationaddress = "Rome, Italy", classification = "723; 921; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Dipartimento di Inf. e Sistemistica, Rome Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Acyclic Digraphs; acyclic digraphs; Algorithms; Computer Programming; Digraphs of Lattices; directed graphs; family trees; Graph Algorithms; Grid Drawings; grid drawings; Hasse diagrams; hierarchical structures; ISA hierarchies; knowledge representation diagrams; Mathematical Techniques--Graph Theory; organization charts; PERT networks; plane representations; straight drawings; Straight Drawings; subroutine-call graphs; time complexity; trees (mathematics); Visibility Representations; visibility representations", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gischer:1988:ETP, author = "Jay L. Gischer", title = "The equational theory of pomsets", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "199--224", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Coll of William \& Mary", affiliationaddress = "Williamsburg, VA, USA", classification = "723; C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., Coll. of William and Mary, Williamsburg, VA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "algebraic properties; Axiomatic Properties; axiomatic properties; closure operations; Computer Metatheory; Computer Systems, Digital--Parallel Processing; concatenation; equational theory; Equational Theory of Pomsets; generalization of strings; Ideals of Pomsets; model of concurrency; parallel composition; Partial Orders; pomsets; programming theory; Semantics of Parallel Programs; Sets of Pomsets; theory of languages; union", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Alexi:1988:EVP, author = "Werner Alexi", title = "Extraction and verification of programs by analysis of formal proofs", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "225--258", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "723; C4240 (Programming and algorithm theory); C6150G (Diagnostic, testing, debugging and evaluating systems)", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "analysis of formal proofs; Computer Metatheory--Programming Theory; Computer Programming; constructions of objects; Correctness; correctness; Formal Proofs; graphs; mathematical tool; program statements; Program Synthesis Algorithm; Program Verification; program verification; programming theory; programs extraction; programs verification; symbols; termination; Termination; Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gargov:1988:DLC, author = "George Gargov and Solomon Passy", title = "Determinism and looping in combinatory {PDL}", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "259--277", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Sofia Univ", affiliationaddress = "Sofia, Bulg", classification = "723; C4240 (Programming and algorithm theory); C6110 (Systems analysis and programming)", corpsource = "Fac. of Math., Sofia Univ., Bulgaria", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "atomic formulae; combinatory PDL; Combinatory pdl; Computer Metatheory--Programming Theory; Computer Programming; CPDL; decidability; Determinism; finite-model property results; Infinite Repeating Construct; logic programming; Looping; programming theory; propositional dynamic logic; Propositional Modal Logics of Programs; propositional modal logics of programs; Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Staiger:1988:SEU, author = "Ludwig Staiger", title = "{Ein Satz {\"u}ber die Entropie von Untermonoiden}. ({German}) [{A} theorem on the entropy of submonoids]", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "279--282", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Akad der Wissenschaften", affiliationaddress = "Berlin, West Ger", classification = "721; C4210 (Formal logic)", corpsource = "Karl-Weierstrass-Inst. fur Math., Akad. der Wissenschaften, Berlin, East Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; entropy of submonoids; Entropy of Submonoids; Finite Alphabets; formal languages; Formal Languages; language; radius of convergence; structure generating function; theorem", language = "German", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kretschmer:1988:CPR, author = "Thomas Kretschmer", title = "A closure property of regular languages", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "283--287", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ des Saarlandes", affiliationaddress = "Saarbruecken, West Ger", classification = "721; C4210 (Formal logic)", corpsource = "Univ. des Saarlandes Fachbereich Inf., Saarbrucken, West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Closure Property; closure property; formal languages; Formal Languages; Inverse Image; inverse image; Powerset; regular languages; Regular Languages; semigroup homomorphism; Semigroup Homomorphism", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Arnold:1988:LDF, author = "Andre Arnold", title = "Logical definability of fixed points", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "289--297", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Bordeaux I", affiliationaddress = "Talence, Fr", classification = "721; 921; C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Lab. d'Inf., Bordeaux Univ., Talence, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "automata; automata theory; Automata Theory; decidability; Fixed Points; least fixed points; Logical Definability; Mathematical Techniques--Trees; Monotonic Functions; monotonic functions; Tree Automata; trees", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Belaga:1988:BMR, author = "Edward G. Belaga", title = "Bilinear mincing rank", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "299--306", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "CNRS", affiliationaddress = "Strasbourg, Fr", classification = "921; C4240 (Programming and algorithm theory)", corpsource = "IRMA-CNRS Univ. Louis Pasteur, Strasbourg, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Bilinear Circuit-Size Complexity; bilinear circuit-size complexity; bilinear form; Bilinear Form; Bilinear Mincing Rank; bilinear mincing rank; characteristic zero; computational complexity; lower bound; Lower Bounds; Mathematical Techniques", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Megiddo:1988:FMD, author = "Nimrod Megiddo and Uzi Vishkin", title = "On finding a minimum dominating set in a tournament", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "307--316", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "IBM", affiliationaddress = "San Jose, CA, USA", classification = "723; 921; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "IBM Almaden Res. Center, San Jose, CA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; Boolean Formulas; boolean formulas; Computer Programming; conjunctive normal form; directed graph; directed graphs; Mathematical Techniques--Set Theory; Minimum Dominating Set; minimum dominating set; polynomial-time algorithm; Polynomial-Time Algorithm; polynomial-time algorithm; Satisfiability Problem; satisfiability problem; tournament; Tournament", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kennaway:1988:GR, author = "R. Kennaway", title = "On 'On graph rewritings'", journal = j-THEOR-COMP-SCI, volume = "61", number = "2--3", pages = "317--320", month = nov, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Sch. of Inf. Syst., East Anglia Univ., Norwich, UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "graph rewritings; graph theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Abiteboul:1988:RHD, author = "Serge Abiteboul and R. Hull", title = "Restructuring hierarchical database objects", journal = j-THEOR-COMP-SCI, volume = "62", number = "1--2", pages = "3--38", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "INRIA", affiliationaddress = "Le Chesnay, Fr", classification = "723; C4250 (Database theory); C6160 (Database management systems (DBMS))", conference = "Selected Papers presented at the First International Conference on Database Theory", corpsource = "INRIA, Le Chesnay, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Complex Objects; Data Processing--Data Structures; data structures; database management systems; Database Systems; database systems; database theory; Hierarchical Data Structures; hierarchical database objects; Hierarchical Database Objects; hierarchical structures; Office Automation; Office Information Systems; Rewrite Operations; rewrite rules; structural transformations; Theory", meetingaddress = "Rome, Italy", meetingdate = "Sep 1986", meetingdate2 = "09/86", pubcountry = "Netherlands", sponsor = "European Assoc for Theoretical Computer Science", treatment = "T Theoretical or Mathematical", } @Article{Atzeni:1988:SCI, author = "Paolo Atzeni and D. Stott Parker", title = "Set containment inference and syllogisms", journal = j-THEOR-COMP-SCI, volume = "62", number = "1--2", pages = "39--65", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "CNR", affiliationaddress = "Rome, Italy", classification = "723; C4210 (Formal logic); C6170 (Expert systems)", conference = "Selected Papers presented at the First International Conference on Database Theory", corpsource = "IASI-CNR, Roma, Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory--Formal Logic; consistency; containment statements; Database Systems; formal languages; formal logic; inference; intractability; knowledge representation; Knowledge Representation; negative information; Set Containment Inference; Syllogisms; syllogisms; Theory; Type Hierarchies; Type Inclusion Inference", meetingaddress = "Rome, Italy", meetingdate = "Sep 1986", meetingdate2 = "09/86", pubcountry = "Netherlands", sponsor = "European Assoc for Theoretical Computer Science", treatment = "T Theoretical or Mathematical", } @Article{Chan:1988:DAB, author = "Edward P. F. Chan and Hector J. Hernandez", title = "On the desirability of $\gamma$-acyclic {BCNF} database schemes", journal = j-THEOR-COMP-SCI, volume = "62", number = "1--2", pages = "67--104", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Alberta", affiliationaddress = "Edmonton, Alberta, Can", classification = "723; C4250 (Database theory)", conference = "Selected Papers presented at the First International Conference on Database Theory", corpsource = "Dept. of Comput. Sci., Alberta Univ., Edmonton, Alta., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Bounded Database Schemes; Boyce-Codd Normal Form Database Schemes; Computer Programming--Algorithms; connection-trap-free; Database Systems; database theory; desirability; functional dependencies; Functional Dependencies; gamma -acyclic BCNE database schemes; Query Processing; query processing; Relational; representative instance; semantics; Updates; updates; X- total projection", meetingaddress = "Rome, Italy", meetingdate = "Sep 1986", meetingdate2 = "09/86", pubcountry = "Netherlands", sponsor = "European Assoc for Theoretical Computer Science", treatment = "T Theoretical or Mathematical", } @Article{Lakshmanan:1988:SFM, author = "V. S. Lakshmanan", title = "Split-freedom and {MVD}-intersection: {A} new characterization of multivalued dependencies having conflict-free covers", journal = j-THEOR-COMP-SCI, volume = "62", number = "1--2", pages = "105--122", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Indian Inst of Science", affiliationaddress = "Bangalore, India", classification = "723; C4250 (Database theory); C6160D (Relational DBMS)", conference = "Selected Papers presented at the First International Conference on Database Theory", corpsource = "Dept. of Comput. Sci. and Autom., Indian Inst. of Sci., Bangalore, India", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Programming--Algorithms; conflict-free covers; Database Systems; database theory; multivalued dependencies; Multivalued Dependencies; MVD-intersection; Polynomial Time Algorithms; Relational; relational databases; Split Free Sets; split-free sets", meetingaddress = "Rome, Italy", meetingdate = "Sep 1986", meetingdate2 = "09/86", pubcountry = "Netherlands", sponsor = "European Assoc for Theoretical Computer Science", treatment = "T Theoretical or Mathematical", } @Article{Lynch:1988:ITN, author = "Nancy Lynch and Michael Merritt", title = "Introduction to the theory of nested transactions", journal = j-THEOR-COMP-SCI, volume = "62", number = "1--2", pages = "123--185", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "MIT", affiliationaddress = "Cambridge, MA, USA", classification = "721; 723; C4220 (Automata theory); C4240 (Programming and algorithm theory)", conference = "Selected Papers presented at the First International Conference on Database Theory", corpsource = "MIT, Cambridge, MA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; automata theory; Computer Programming--Algorithms; Concurrency; concurrency; concurrency control; correctness; Database Systems; locking algorithm; Locking Algorithms; nested transactions; Nested Transactions; Resiliency; resiliency properties; Theory; transaction processing", meetingaddress = "Rome, Italy", meetingdate = "Sep 1986", meetingdate2 = "09/86", pubcountry = "Netherlands", sponsor = "European Assoc for Theoretical Computer Science", treatment = "T Theoretical or Mathematical", } @Article{Sacca:1988:GCM, author = "Domenico Sacca and Carlo Zaniolo", title = "The generalized counting method for recursive logic queries", journal = j-THEOR-COMP-SCI, volume = "62", number = "1--2", pages = "187--220", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ della Calabria", affiliationaddress = "Rende, Italy", classification = "723; C4250 (Database theory); C6160 (Database management systems (DBMS)); C6170 (Expert systems)", conference = "Selected Papers presented at the First International Conference on Database Theory", corpsource = "Dipartimento di Sistemi, Univ. della Calabria, Rende, Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Artificial Intelligence; backward chaining; binding-passing behavior; Database Systems; database theory; Fixpoint Computations; forward chaining; Forward Chaining; function symbols; Generalized Counting Method; generalized counting method; Horn Clauses; Horn clauses queries; Logic Programming; logic programming; query languages; recursive logic queries; Recursive Logic Queries; safety; termination; Theory", meetingaddress = "Rome, Italy", meetingdate = "Sep 1986", meetingdate2 = "09/86", pubcountry = "Netherlands", sponsor = "European Assoc for Theoretical Computer Science", treatment = "P Practical", } @Article{vanGucht:1988:IFM, author = "Dirk {van Gucht}", title = "Interaction-free multivalued dependency sets", journal = j-THEOR-COMP-SCI, volume = "62", number = "1--2", pages = "221--233", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Indiana Univ", affiliationaddress = "Bloomington, IN, USA", classification = "723; 921; C4250 (Database theory)", conference = "Selected Papers presented at the First International Conference on Database Theory", corpsource = "Dept. of Comput. Sci., Indiana Univ., Bloomington, IN, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Acyclic Join Dependencies; acyclic join dependency; conflict-free MVD set; database design problems; Database Systems; database theory; dependency theory; Interaction Free Multivalued Dependency Sets; interaction-free MVD set; join dependencies; Mathematical Techniques--Set Theory; Multivalued Dependencies; set theory; syntactic characterization; Theory", meetingaddress = "Rome, Italy", meetingdate = "Sep 1986", meetingdate2 = "09/86", pubcountry = "Netherlands", sponsor = "European Assoc for Theoretical Computer Science", treatment = "T Theoretical or Mathematical", } @Article{Geffert:1988:RRE, author = "Viliam Geffert", title = "A representation of a recursively enumerable languages by two homomorphisms and a quotient", journal = j-THEOR-COMP-SCI, volume = "62", number = "3", pages = "235--249", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of P. J. Safarik", affiliationaddress = "Kosice, Czech", classification = "721; 921; C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., Univ. of P. J. Safarik, Kosice, Czechoslovakia", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Formal Languages; formal languages; Homomorphisms; homomorphisms; Mathematical Techniques--Set Theory; quotient; Quotient Operation; Recursively Enumerable Languages; recursively enumerable languages; Right Overflow Languages", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", xxtitle = "Representation of a recursively enumerable languages by two homomorphisms and a quotient", xxtitle = "A presentation of a recursively enumerable languages by two homomorphisms and a quotient", } @Article{Rao:1988:ACA, author = "Nageswara S. V. Rao and S. S. Iyengar and R. L. Kashyap", title = "An average-case analysis of {MAT} and inverted file", journal = j-THEOR-COMP-SCI, volume = "62", number = "3", pages = "251--266", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Louisiana State Univ", affiliationaddress = "Baton Rouge, LA, USA", classification = "723; 903; 921; 922; C6120 (File organisation); C6160 (Database management systems (DBMS))", corpsource = "Dept. of Comput. Sci., Louisiana State Univ., Baton Rouge, LA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "average-case analysis; Data Processing; data space; data structures; database management systems; Database Systems; file organisation; File Organization; Information Science--Information Retrieval; inverted file; Inverted Files; MAT; Mathematical Techniques--Trees; multiple attribute tree; Multiple Attribute Trees; Partial Match Queries; partial-match queries; Probability; trees (mathematics); uniform probabilistic model; Worst Case Complexity; worst-case complexities", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Salomaa:1988:PRC, author = "Kai Salomaa", title = "A pumping result for $2$-context-free languages", journal = j-THEOR-COMP-SCI, volume = "62", number = "3", pages = "267--287", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Turku", affiliationaddress = "Turku, Finl", classification = "721; C4210 (Formal logic)", corpsource = "Dept. of Math., Turku Univ., Finland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "2-Context-Free Languages; 2-context-free languages; Automata Theory; Context Free Languages; context-free grammars; context-free languages; K-Context-Free Languages; k-parallel derivations; Pattern Selectors; Pumping Properties; pumping result; Scheduling--Theory; Selector Languages", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Zeugmann:1988:PRO, author = "Thomas Zeugmann", title = "On the Power of Recursive Optimizers", journal = j-THEOR-COMP-SCI, volume = "62", number = "3", pages = "289--310", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; ftp://ftp.math.utah.edu/pub/bibnet/authors/z/zeugmann-thomas-u.bib; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Humboldt Univ Berlin", affiliationaddress = "Berlin, East Ger", classification = "723; C4210 (Formal logic)", corpsource = "Dept. of Math., Humboldt Univ., Berlin, East Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "arbitrary program; Computer Metatheory; Computer Programming--Theory; Existence Problem; fastest programs; Inductive Inference; power; Program Synthesis; Programming Theory; recursive functions; recursive optimizers; Recursive Optimizers", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Buss:1988:RPG, author = "Samuel R. Buss and Gyorgy Turan", title = "Resolution proofs on generalized pigeonhole principles", journal = j-THEOR-COMP-SCI, volume = "62", number = "3", pages = "311--317", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of California", affiliationaddress = "San Diego, CA, USA", classification = "723; C4200 (Computer theory)", corpsource = "Dept. of Math., California Univ., San Diego, CA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "computation theory; Computer Metatheory; constant-formula-depth Frege proof systems; encoding; exponential lower bound; Exponential Lower Bounds; Frege Proof Systems; Generalized Pigeonhole Principles; generalized pigeonhole principles; propositional formulas; Propositional Formulas; resolution proofs; Resolution Proofs", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", xxtitle = "Resolution proofs of generalized pigeonhole principles", } @Article{Meinel:1988:PNP, author = "Christoph Meinel", title = "The power of nondeterminism in polynomial-size bounded-width branching programs", journal = j-THEOR-COMP-SCI, volume = "62", number = "3", pages = "319--325", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Akad der Wissenschaften", affiliationaddress = "Berlin, East Ger", classification = "721; 723; C4240 (Programming and algorithm theory)", corpsource = "Karl-Weierstrass-Inst. fur Math., Akad. der Wissenschaften, Berlin, East Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory--Turing Machines; computational complexity; computational tool; Computer Metatheory; Computer Programming--Theory; Nondeterministic Branching Programs; Polynomial Size; polynomial-size bounded-width branching programs; power of nondeterminism; programming theory; Programming Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Schmidt:1989:APT, author = "Ursula Schmidt", title = "Avoidable patterns on two letters", journal = j-THEOR-COMP-SCI, volume = "63", number = "1", pages = "1--17", month = jan, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Freiburg", affiliationaddress = "Freiburg, West Ger", classification = "723; C1250 (Pattern recognition)", corpsource = "Inst. fur Inf., Freiburg Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Avoidable Patterns; avoidable patterns; Computer Metatheory; Computer Programming Languages--Theory; minimal alphabet; Minimal Alphabets; pattern recognition; Thue--Morse; Two Letter Alphabets", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Livesey:1989:SFB, author = "M. Livesey", title = "Stable families of behavioural equivalences", journal = j-THEOR-COMP-SCI, volume = "63", number = "1", pages = "19--41", month = jan, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of St. Andrews", affiliationaddress = "St. Andrews, Scotl", classification = "723; C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., St. Andrews Univ., UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Behavioral Equivalences; behavioural equivalences; Computer Metatheory; Computer Programming--Theory; preorders; programming theory; Programming Theory; quotient system; Stability of Equivalences; stable families; Stable Family of Preorders; transition system; Transition Systems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ambos-Spies:1989:RCH, author = "Klaus Ambos-Spies", title = "On the relative complexity of hard problems for complexity classes without complete problems", journal = j-THEOR-COMP-SCI, volume = "63", number = "1", pages = "43--61", month = jan, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Oldenburg", affiliationaddress = "Oldenburg, West Ger", classification = "723; 921; C4240 (Programming and algorithm theory)", corpsource = "Fachbereich Inf., Oldenburg Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "complexity classes; computational complexity; Computational Complexity; Computer Metatheory; hard problems; Mathematical Techniques--Set Theory; natural closure properties; np Completeness; Partial Ordering; Polynomial Time Reducibility; polynomial time reducibility notions; recursive sequence; Recursive Sets; recursive sets; relative complexity", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ginsburg:1989:COH, author = "Seymour Ginsburg and Chang-jie Tang", title = "Cohesion of object histories", journal = j-THEOR-COMP-SCI, volume = "63", number = "1", pages = "63--90", month = jan, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Southern California", affiliationaddress = "Los Angeles, CA, USA", classification = "723; 921; C4250 (Database theory); C6160D (Relational DBMS)", corpsource = "Dept. of Comput. Sci., Univ. of Southern California, Los Angeles, CA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "algebraically-oriented; cohesion; Database Systems; database theory; Distributed; event-driven model; Historical Data; historical data for objects; Mathematical Techniques--Set Theory; Object Histories; object histories; record-based; relational databases", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Johnson:1989:UFD, author = "J. Howard Johnson", title = "A unified framework for disambiguating finite transductions", journal = j-THEOR-COMP-SCI, volume = "63", number = "1", pages = "91--111", month = jan, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Waterloo", affiliationaddress = "Waterloo, Ont, Can", classification = "723; 903; C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., Waterloo Univ., Ont., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; correctness proofs; disambiguating finite transductions; finite state transduction; Finite Transductions; formal languages; genealogical minimum; Information Retrieval Systems--Online Searching; Language Processing; Lexical Analysis; lexicographic minimum; multiple output values; natural languages; Text Processing; unified framework", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Hagiya:1989:GPP, author = "Masami Hagiya", title = "Generalization from partial parametrization in higher-order type theory", journal = j-THEOR-COMP-SCI, volume = "63", number = "2", pages = "113--139", month = feb, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Kyoto Univ", affiliationaddress = "Kyoto, Jpn", classification = "723; C4240 (Programming and algorithm theory); C6120 (File organisation)", corpsource = "Res. Inst. for Math. Sci., Kyoto Univ., Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; Computer Programming--Theory; constructive type theory; data structures; formulae-as-types notion; generalizing a program; Higher Order Type Theory; higher-order type theory; largest sum segment problem; longest up segment problem; Partial Parametrization; partial parametrization; programming theory; Programming Theory", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Birget:1989:CIT, author = "Jean-Camille Birget", title = "Concatenation of inputs in a two-way automaton", journal = j-THEOR-COMP-SCI, volume = "63", number = "2", pages = "141--156", month = feb, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Nebraska", affiliationaddress = "Lincoln, NE, USA", classification = "721; C4220 (Automata theory)", corpsource = "Dept. of Comput. Sci., Nebraska Univ., Lincoln, NE, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; concatenation; Concatenation of Inputs; crossing sequence; Finite Automata; finite automata; Input Strings; partial functions; quadruple; Two Way Finite Automata; two-way automaton", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{deFelice:1989:CFF, author = "Clelia {de Felice}", title = "Construction of a family of finite maximal codes", journal = j-THEOR-COMP-SCI, volume = "63", number = "2", pages = "157--184", month = feb, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Paris", affiliationaddress = "Paris, Fr", classification = "723; B6120B (Codes); C1260 (Information theory)", corpsource = "Paris VII Univ., France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "algorithm; codes; Codes, Symbolic; Computer Programming--Algorithms; Construction; Factorization; finite maximal code; Finite Maximal Codes; finite maximal codes; Two Letter Alphabets; Variable Length Codes", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Pelc:1989:SKE, author = "Andrzej Pelc", title = "Searching with known error probability", journal = j-THEOR-COMP-SCI, volume = "63", number = "2", pages = "185--202", month = feb, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ du Quebec a Hull", affiliationaddress = "Hull, Que, Can", classification = "723; 922; C1260 (Information theory)", corpsource = "Dept. d'Inf., Quebec Univ., Hull, Que., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; comparison queries; Computer Programming; Continuous Search; discrete bounded; Discrete Bounded Search; Discrete Unbounded Search; Error Probability; information theory; Interactive Searching; interactive searching; probability; Probability; Reliability; Search Algorithms; searching algorithm", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hromkovic:1989:TLR, author = "Juraj Hromkovic", title = "Tradeoffs for language recognition on alternating machines", journal = j-THEOR-COMP-SCI, volume = "63", number = "2", pages = "203--221", month = feb, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Comenius Univ", affiliationaddress = "Bratislava, Czech", classification = "721; 723; C4220 (Automata theory)", corpsource = "Dept. of Theor. Cybernet. and Math. Inf., Comenius Univ., Bratislava, Czechoslovakia", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "alternating machine; Alternating Machines; Automata Theory; complexity measure; Complexity Measures; Computational Complexity; Computer Metatheory; Computer Systems, Digital; finite automata; input tape; Language Recognition; nondeterministic machines; optimal lower bounds; parallel computing model; Parallel Random Access Machines; read-only heads", pubcountry = "Netherlands", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Saito:1989:SBE, author = "Takashi Saito and Hidenosuke Nishio", title = "Structural and behavioral equivalence relations in automata networks", journal = j-THEOR-COMP-SCI, volume = "63", number = "2", pages = "223--237", month = feb, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Kyoto Univ", affiliationaddress = "Kyoto, Jpn", classification = "721; 921; C1160 (Combinatorial mathematics); C4220 (Automata theory)", corpsource = "Dept. of Biophys., Kyoto Univ., Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Networks; automata networks; Automata Theory; Behavioral Equivalence; behavioural equivalence relations; Directed Graphs; directed graphs; edge-label; finite automata; Finite Automata; finite automaton; Mathematical Techniques--Graph Theory; Structural Equivalence; structural equivalence; vertex-labeled directed graph", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", xxtitle = "Structural and behavioural equivalence relations in automata networks", } @Article{Du:1989:ISC, author = "Ding-Zhu Du and Ronald V. Book", title = "On inefficient special cases of {NP}-complete problems", journal = j-THEOR-COMP-SCI, volume = "63", number = "3", pages = "239--252", month = mar, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Acad Sinica", affiliationaddress = "Beijing, China", classification = "723; 921; C4240 (Programming and algorithm theory)", corpsource = "Inst. of Appl. Math., Acad. Sinica., Beijing, China", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "computability; computational complexity; Computer Metatheory; inefficient special cases; intractable set; Intractable Sets; Mathematical Techniques--Set Theory; np Complete Problems; NP-complete problems; polynomial complexity core", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gardarin:1989:TLP, author = "Georges Gardarin and Irene Guessarian and Christophe {de Maindreville}", title = "Translation of logic programs into functional fixpoint equations", journal = j-THEOR-COMP-SCI, volume = "63", number = "3", pages = "253--274", month = mar, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Paris VI", affiliationaddress = "Le Chesnay, Fr", classification = "723; 921; C4240 (Programming and algorithm theory); C6150C (Compilers, interpreters and other processors)", corpsource = "LITP, Paris VI Univ., Le Chesnay, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "binary rules; Computer Metatheory; Computer Programming--Theory; cyclic rules; Database Systems--Theory; DATALOG; function symbols; Functional Fixpoint Equations; functional fixpoint equations; functional programming; Horn Clause Programs; logic programming; logic programs; Logic Programs; MAGIC; magic function method; Magic Function Method; Mathematical Techniques--Graph Theory; optimized relational algebra programs; PROBLEM predicates; program compilers; Programming Theory; programming theory; Query Compilation; recursive function free Horn clause programs; reviews; rule redundancy elimination", pubcountry = "Netherlands", treatment = "G General Review; T Theoretical or Mathematical", } @Article{Benson:1989:FPF, author = "David B. Benson and Jerzy Tiuryn", title = "Fixed points in free process algebras, part {I}", journal = j-THEOR-COMP-SCI, volume = "63", number = "3", pages = "275--294", month = mar, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Washington State Univ", affiliationaddress = "Pullman, WA, USA", classification = "723; 921; C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., Washington State Univ., Pullman, WA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; distributive lattice; fixed point solutions; formal languages; Free Process Algebras; free process algebras; iterative equation; Iterative Equations; iterative methods; linear left simple polynomials; Linear Polynomials; Mathematical Techniques; polynomials; Polynomials; silent action; sum operator", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Lingas:1989:SIB, author = "Andrzej Lingas", title = "Subgraph isomorphism for biconnected outerplanar graphs in cubic time", journal = j-THEOR-COMP-SCI, volume = "63", number = "3", pages = "295--302", month = mar, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Link{\"o}ping Univ", affiliationaddress = "Link{\"o}ping, Swed", classification = "921; C1160 (Combinatorial mathematics); C1180 (Optimisation techniques); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. and Inf. Sci., Linkoping Univ., Sweden", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "algorithm theory; Biconnected Outerplanar Graphs; biconnected outerplanar graphs; Computer Programming--Algorithms; cubic time; dynamic programming; dynamic programming algorithm; graph theory; Mathematical Programming, Dynamic; Mathematical Techniques--Graph Theory; Subgraph Isomorphism", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Bloom:1989:ELC, author = "Stephen L. Bloom and Zoltan Esik", title = "Equational logic of circular data type specification", journal = j-THEOR-COMP-SCI, volume = "63", number = "3", pages = "303--331", month = mar, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Stevens Inst of Technology", affiliationaddress = "Hoboken, NJ, USA", classification = "723; C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., Stevens Inst. of Technol., Hoboken, NJ, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Circular Data Type Specification; circular data type specification; Computer Metatheory; Computer Programming--Theory; data structures; disjoint union; Equational Logic; equational properties; fixed points; flowchart algorithms; Flowchart Algorithms; formal logic; Iteration Theories; iteration theories; iterative methods; Programming Theory; programming theory; singleton set; stacks; strong behaviours", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{deLuca:1989:SCP, author = "Aldo {de Luca} and Stefano Varricchio", title = "Some combinatorial properties of the {Thue--Morse} sequence and a problem in semigroups", journal = j-THEOR-COMP-SCI, volume = "63", number = "3", pages = "333--348", month = mar, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ di Roma La Sapienza", affiliationaddress = "Rome, Italy", classification = "723; C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Dipartimento di Matematica, Roma Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "combinatorial properties; Computer Metatheory; formal languages; group theory; Semigroups; semigroups; Special Factors; Thue--Morse Sequence; Thue--Morse sequence; two-letter alphabet", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Stoss:1989:RRF, author = "Hans-J{\"o}rg Stoss", title = "On the representation of rational functions of bounded complexity", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "1--13", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Konstanz", affiliationaddress = "Konstanz, West Ger", classification = "723; 921; C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math., Konstanz Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "bounded complexity; Complexity Bounds; complexity measure; computational complexity; Computer Metatheory; Lower Bounds; Mathematical Techniques--Algebra; Rational Functions; rational functions representation; Representation Theorem", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Stoss:1989:LBC, author = "Hans-J{\"o}rg Stoss", title = "Lower bounds for the complexity of polynomials", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "15--23", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Konstanz", affiliationaddress = "Konstanz, West Ger", classification = "723; 921; B0290F (Interpolation and function approximation); C4130 (Interpolation and function approximation)", corpsource = "Dept. of Math., Konstanz Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "arbitrary field; Complexity Bounds; complexity of polynomials; Computer Metatheory; divisors; Lower Bounds; lower bounds; Mathematical Techniques--Polynomials; polynomials; Representation Theorem", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Jojczyk:1989:IBP, author = "K. Jojczyk and J. Konieczny and T. Kuzak", title = "On interleaving behaviour of {PT-nets}", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "25--38", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Jagiellonian Univ", affiliationaddress = "Cracow, Pol", classification = "721; 723; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Dept. of Comput. Sci., Jagiellonian Univ., Krakow, Poland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory--Formal Languages; Computer Metatheory; interleaving behaviour; Petri nets; Petri Nets; Place/Transition nets; Place/Transition Nets; predicate expression; Predicate Expressions (Prex); prex; PT-nets; Sequence of Predicates; synchronization", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Tomita:1989:DBA, author = "Etsuji Tomita and Kazushi Seino", title = "A direct branching algorithm for checking the equivalence of two deterministic pushdown transducers, one of which is real-time strict", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "39--53", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Electro-Communications", affiliationaddress = "Chofu, Jpn", classification = "721; 723; C4220 (Automata theory)", corpsource = "Dept. of Commun. Eng., Univ. of Electro-Commun., Tokyo, Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Computer Programming--Algorithms; deterministic automata; Deterministic Pushdown Automata; Deterministic Pushdown Transducers; deterministic pushdown transducers; direct branching algorithm; Direct Branching Algorithm; equivalence; real-time strict", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Sato:1989:CBC, author = "Hiroyuki Sato", title = "{E-CCC}: between {CCC} and {TOPOS}", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "55--66", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Tokyo", affiliationaddress = "Tokyo, Jpn", classification = "723; C4200 (Computer theory)", corpsource = "Dept. of Inf. Sci., Tokyo Univ., Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Cartesian Closed Category; cartesian closed category; CCC; computation theory; Computer Metatheory; E-CCC; extended abstract data type theory; Lambda Calculus; Topos; TOPOS; typed lambda - calculus", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hung:1989:SCP, author = "Dang Van Hung and Elod Knuth", title = "Semi-commutations and {Petri} nets", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "67--81", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Mon Oct 26 07:54:00 1998", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Hungarian Acad of Sciences", affiliationaddress = "Budapest, Hung", classification = "723; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Comput. and Autom. Inst., Hungarian Acad. of Sci., Budapest, Hungary", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Asynchronous Cooperative Processes; Computer Metatheory; Computer Systems, Digital--Distributed; generalization; partial commutation; Partial Commutations; Petri Nets; Petri nets; Semicommutations; semicommutations; traces", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", xxauthor = "Dang {van Hung} and Elod Knuth", } @Article{Shamir:1989:CAN, author = "Eli Shamir and Assaf Schuster", title = "Communication aspects of networks based on geometric incidence relations", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "83--96", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Hebrew Univ", affiliationaddress = "Jerusalem, Isr", classification = "722; 723; 921; C4230 (Switching theory); C4240 (Programming and algorithm theory)", corpsource = "Leibniz Center for Res. in Comput. Sci., Hebrew Univ., Jerusalem, Israel", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "communication properties; Computer Programming--Algorithms; Computer Systems, Digital; geometric incidence relations; Geometric Incidence Relations; Interconnection Networks; lower bound; Mathematical Techniques--Graph Theory; multiprocessor interconnection networks; natural routing scheme; network theory; optimal complexity; Parallel Algorithms; parallel algorithms; Parallel Processing; parallel-routing algorithm; projective space; Routing Algorithms", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hindley:1989:BCL, author = "J. Roger Hindley", title = "{B}{CK}-combinators and linear \$lambda@-terms have types", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "97--105", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Coll", affiliationaddress = "Swansea, Wales", classification = "723; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Div. of Math., Univ. Coll. Swansea, UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "bck Combinators; BCK-combinators; combinatorial mathematics; Computer Metatheory; Lambda Terms; linear lambda -terms; nonstratification; primitive linear logic; Type Assignment", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Galil:1989:SDP, author = "Zvi Galil and Raffaele Giancarlo", title = "Speeding up dynamic programming with applications to molecular biology", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "107--118", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Columbia Univ", affiliationaddress = "New York, NY, USA", classification = "723; 921; B0260 (Optimisation techniques); C1180 (Optimisation techniques); C7330 (Biology and medicine)", corpsource = "Dept. of Comput. Sci., Columbia Univ., NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Programming--Algorithms; Concave Problems; Convex Problems; DNA; DNA sequences; Dual Problems; dynamic programming; geology; Inverse Quadrangle Inequality; Mathematical Programming, Dynamic; medical computing; molecular biology; Quadrangle Inequality; speech recognition", pubcountry = "Netherlands", treatment = "A Application; P Practical; T Theoretical or Mathematical", } @Article{Protasi:1989:NAO, author = "Marco Protasi and Maurizio Talamo", title = "On the number of arithmetical operations for finding {Fibonacci} numbers", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "119--124", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ di Roma Tor Vergata", affiliationaddress = "Rome, Italy", classification = "723; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Dipartimento di Matematica, Roma Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; algorithms; arithmetical operations; Arithmetical Operations; average case; Computational Complexity; Computer Metatheory; Computer Programming; Fibonacci Numbers; finding Fibonacci numbers; number theory; worst case", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Korach:1989:OLB, author = "E. Korach and S. Moran and S. Zaks", title = "Optimal lower bounds for some distributed algorithms for a complete network of processors", journal = j-THEOR-COMP-SCI, volume = "64", number = "1", pages = "125--132", month = apr, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Technion - Israel Inst of Technology", affiliationaddress = "Haifa, Isr", classification = "723; 921; C4230 (Switching theory)", corpsource = "Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; complete network of processors; Complete Networks; Computer Programming; Computer Systems, Digital--Distributed; distributed algorithms; Distributed Algorithms; distributed processing; Global Algorithms; Hamiltonian circuit; leader; Lower Bounds; Matching Algorithms; Mathematical Techniques--Graph Theory; maximal matching; multiprocessor interconnection networks; optimal lower bounds; spanning tree; synchronous networks", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kruskal:1989:TPM, author = "Clyde P. Kruskal and Larry Rudolph and Marc Snir", title = "Techniques for parallel manipulation of sparse matrices", journal = j-THEOR-COMP-SCI, volume = "64", number = "2", pages = "135--157", day = "7", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Maryland", affiliationaddress = "College Park, MD, USA", classification = "722; 723; 921; C4140 (Linear algebra); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., Inst. for Adv. Comput. Studies, Maryland Univ., College Park, MD, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "column permutation; computational complexity; Computer Systems, Digital; Gaussian Elimination; Gaussian elimination; Mathematical Techniques--Matrix Algebra; Matrix Addition; matrix addition; matrix algebra; Matrix Multiplication; matrix multiplication; matrix transpose; matrix vector multiplication; Matrix Vector Multiplication; mimd Computers; MIMD computers; parallel algorithms; parallel manipulation; Parallel Processing; raw permutation; sparse matrices; Sparse Matrices", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Robert:1989:OSA, author = "Yves Robert and Denis Trystram", title = "Optimal scheduling algorithms for parallel {Gaussian} elimination", journal = j-THEOR-COMP-SCI, volume = "64", number = "2", pages = "159--173", day = "7", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "CNRS", affiliationaddress = "Grenoble, Fr", classification = "723; 921; C1160 (Combinatorial mathematics); C4140 (Linear algebra); C4240 (Programming and algorithm theory)", corpsource = "Lab. TIM3, INPG, CNRS, Grenoble, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algorithms; Asymptotically Optimal Algorithms; asymptotically optimal algorithms; computational complexity; Computer Programming; Computer Systems, Digital--Parallel Processing; Gaussian Elimination; graph theory; linear algebra; Mathematical Techniques--Graph Theory; Optimal Scheduling Algorithms; optimisation; Parallel Algorithms; parallel algorithms; parallel Gaussian elimination; parallelism; Scheduling; scheduling; scheduling algorithms; shared memory system; simd/mimd Computers", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Lyon:1989:DFP, author = "Gordon Lyon", title = "Design factors for parallel processing benchmarks", journal = j-THEOR-COMP-SCI, volume = "64", number = "2", pages = "175--189", day = "7", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Natl Inst of Standards \& Technology", affiliationaddress = "Gaithersburg, MD, USA", classification = "722; 723; C5440 (Multiprocessor systems and techniques); C5470 (Performance evaluation and testing)", corpsource = "Nat. Comput. Syst. Lab., Nat. Inst. of Stand. and Technol., Gaithersburg, MD, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "application benchmarks; architectural clusters; Computer Systems, Digital; Computers, Digital--Performance; economic compatibility; mimd Computers; parallel architectures; parallel machines; Parallel Processing; parallel processing benchmarks; Parallel Processing Benchmarks; performance evaluation; Process Communication", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Bermond:1989:ICE, author = "J. C. Bermond and J. M. Fourneau", title = "Independent connections: An easy characterization of baseline-equivalent multistage interconnection networks", journal = j-THEOR-COMP-SCI, volume = "64", number = "2", pages = "191--201", day = "7", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "CNRS", affiliationaddress = "Paris, Fr", classification = "723; C1160 (Combinatorial mathematics); C4230 (Switching theory); C5220 (Computer architecture)", corpsource = "Univ. Paris Sud, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Banyan Networks; Banyan networks; Baseline network; baseline-equivalent multistage interconnection networks; binary string; bit directed routing; Computer Networks; Computer Systems, Digital--Parallel Processing; graph characterization; graph theory; Independent Connections; independent connections; index digit; multiprocessor interconnection networks; Multistage Interconnection Networks; network topology; parallel architectures; PIPID permutation; pipid Permutation; switching cells; switching theory; topological properties", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Akyildiz:1989:ESO, author = "I. F. Akyildiz and H. {von Brand}", title = "Exact solutions for open, closed and mixed queueing networks with rejection blocking", journal = j-THEOR-COMP-SCI, volume = "64", number = "2", pages = "203--219", day = "7", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Georgia Inst of Technology", affiliationaddress = "Atlanta, GA, USA", classification = "723; 922; B0240C (Queueing theory)C4230 (Switching theory); B6150 (Communication system theory); C1140C (Queueing theory)", corpsource = "Sch. of Inf. and Comput. Sci., Georgia Inst. of Technol., Atlanta, GA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "blocking network; Blocking Networks; class membership; closed queueing networks; Computer Systems, Digital--Performance; equilibrium state probabilities; exponential distribution; mixed queueing networks; multiple job classes; open queueing networks; Probability; probability; product form; Queueing Networks; queueing theory; Queueing Theory; rejection blocking; Rejection Blocking; reversible routing; scheduling; service requirement distributions; switching theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Stark:1989:CTS, author = "Eugene W. Stark", title = "Concurrent transition systems", journal = j-THEOR-COMP-SCI, volume = "64", number = "3", pages = "221--269", day = "29", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "State Univ of New York at Stony Brook", affiliationaddress = "Stony Brook, NY, USA", classification = "722; 723; C4220 (Automata theory); C4240 (Programming and algorithm theory)", corpsource = "State Univ. of New York, Stony Brook, NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "abstractions; automata theory; computation category; computation diagram; Computer Metatheory; Computer Systems, Digital; Concurrent Computation; concurrent computation; concurrent transition systems; Concurrent Transition Systems; Dataflow Models; dataflow-like model; Distributed; fair computation sequence; feedback; fixed-point principle; functional input/output behavior; machines; maximal ideals; nondeterministic transition systems; Observable Equivalence; observable equivalence; parallel product; parallel programming; programming theory; residual operations; sequential machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Therien:1989:PAM, author = "Denis Therien", title = "Programs over aperiodic monoids", journal = j-THEOR-COMP-SCI, volume = "64", number = "3", pages = "271--280", day = "29", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "McGill Univ", affiliationaddress = "Montreal, Que, Can", classification = "721; 723; C4220 (Automata theory); C4240 (Programming and algorithm theory)", corpsource = "Sch. of Comput. Sci., Mcgill Univ., Montreal, Que., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Aperiodic Monoids; aperiodic monoids; Automata Theory--Finite Automata; Boolean Circuits; boolean circuits; Computer Metatheory; Computer Programming--Theory; Computer Systems, Digital--Parallel Processing; finite automata; finite monoid; Finite Monoids; finite state automata; modulo p; parallel computing; parallel programming; program; programming theory; Programming Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Mazurkiewicz:1989:CSI, author = "Antoni Mazurkiewicz and Edward Ochmanski and Wojciech Penczek", title = "Concurrent systems and inevitability", journal = j-THEOR-COMP-SCI, volume = "64", number = "3", pages = "281--304", day = "29", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Polish Acad of Sciences", affiliationaddress = "Warsaw, Pol", classification = "722; 723; C4220 (Automata theory)", corpsource = "Inst. of Comput. Sci., Polish Acad. of Sci., Warszawa, Poland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "automata theory; Computer Metatheory; Computer Systems, Digital; Concurrent Systems; concurrent systems; Distributed; fair executable sequences; inevitability; Inevitability Property; partial order framework; Partially Ordered Sets; partially ordered sets of states; system states", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Howell:1989:PCF, author = "Rodney R. Howell and Louis E. Rosier", title = "Problems concerning fairness and temporal logic for conflict-free {Petri} nets", journal = j-THEOR-COMP-SCI, volume = "64", number = "3", pages = "305--329", day = "29", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Texas at Austin", affiliationaddress = "Austin, TX, USA", classification = "723; C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., Texas Univ., Austin, TX, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "complexity; Computer Metatheory; Computer Programming--Theory; conflict-free Petri nets; Conflict-Free Petri Nets; decidability; Fair Nontermination Problem; fair nontermination problem; fairness; finite state systems; formal logic; model checking problem; NLOGSPACE; NP; parallel programming; Petri nets; Programming Theory; programming theory; PTIME; Temporal Logic; temporal logic; undecidable", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Alon:1989:NTB, author = "Noga Alon and Uri Zwick", title = "On {Neciporuk}'s theorem for branching programs", journal = j-THEOR-COMP-SCI, volume = "64", number = "3", pages = "331--342", day = "29", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Tel-Aviv Univ", affiliationaddress = "Tel-Aviv, Isr", classification = "723; C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math. and Comput. Sci., Sackler Fac. of Exact Sci., Tel-Aviv Univ., Israel", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Boolean Functions; Boolean functions; branching programs; Branching Programs; Computer Metatheory; Computer Programming--Theory; explicit formulae; lower bounds; monotone non-decreasing functions; Neciporuk theorem; Neciporuk's Theorem; Programming Theory; programming theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{KleineBuning:1989:PVA, author = "Hans {Kleine B{\"u}ning} and Theodor Lettmann and Ernst W. Mayr", title = "Projections of vector addition system reachability sets are semilinear", journal = j-THEOR-COMP-SCI, volume = "64", number = "3", pages = "343--350", day = "29", month = may, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Karlsruhe", affiliationaddress = "Karlsruhe, West Ger", classification = "723; C4240 (Programming and algorithm theory)", corpsource = "Karlsruhe Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; Computer Programming--Algorithms; decidability; decidable; inclusion problem; one-dimensional projection; programming theory; Reachability Sets; vector addition system reachability sets; Vector Addition Systems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Enjalbert:1989:MRC, author = "Patrice Enjalbert and Luis {Farinas del Cerro}", title = "Modal resolution in clausal form", journal = j-THEOR-COMP-SCI, volume = "65", number = "1", pages = "1--33", day = "15", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Caen", affiliationaddress = "Caen, Fr", classification = "723; C1230 (Artificial intelligence); C6110 (Systems analysis and programming)", corpsource = "Lab. d'Informatique, Caen Univ., France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automated Deduction Methods; automated deduction methods; clausal form; Completeness Proof; completeness proof technique; Computer Metatheory; Computer Programming--Algorithms; Deletion Strategy; deletion strategy; Formal Logic; logic programming; Modal Logic; modal logic; modal resolution; Modal Resolution; Robinson resolution method; Subsumption Relation; subsumption relation; tableau method", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Abadi:1989:PTP, author = "Martin Abadi", title = "The power of temporal proofs", journal = j-THEOR-COMP-SCI, volume = "65", number = "1", pages = "35--83", day = "15", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Stanford Univ", affiliationaddress = "Stanford, CA, USA", classification = "723; C6110 (Systems analysis and programming)", corpsource = "Dept. of Comput. Sci., Stanford Univ., CA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Auxiliary Predicates; completeness results; Computer Metatheory; concurrent programs; Formal Logic; hardware devices; nonstandard soundness; parallel programming; power; reasoning; Temporal Logic; temporal proofs; Temporal Proofs", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Thatte:1989:FAL, author = "Satish R. Thatte", title = "Full abstraction and limiting completeness in equational languages", journal = j-THEOR-COMP-SCI, volume = "65", number = "1", pages = "85--119", day = "15", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Michigan", affiliationaddress = "Ann Arbor, MI, USA", classification = "723; C4210 (Formal logic)", corpsource = "Dept. of Electr. Eng. and Comput. Sci., Michigan Univ., Ann Arbor, MI, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "coherent computable models; Computer Metatheory; Computer Programming Languages; design principle; Equational Languages; equational languages; formal languages; full abstraction; Full Abstraction; fully abstract model; information systems; limiting completeness; Limiting Completeness; regular systems; Semantics; Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Anonymous:1989:CAC, author = "Anonymous", title = "{Conference on Arithmetics and Coding Systems}", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "??--??", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C1260 (Information theory); C4240 (Programming and algorithm theory)", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "arithmetic sequences; arithmetics; beta -expansions; classification; coding systems; combinatorial mathematics; computational complexity; diagonal continued fraction; encoding; ergodic properties; finitely generated sofic systems; formal logic; fractal functions; Fredholm determinant; fuller identities; geometry; infinite words; labelled subtrees; linear subword complexity; piecewise linear transformation; q-adic spectral analysis; randomly labelled tree; rational functions; rational probability measures; real-time constructed sequences; sequence; skew products; statistic; symbolic dynamics; Weyl sums", pubcountry = "Netherlands", } @Article{Allouche:1989:SRF, author = "Jean-Paul Allouche", title = "On a sequence of rational functions", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "123--130", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "CNRS", affiliationaddress = "Talence, Fr", classification = "721; 723; 921; C4220 (Automata theory)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Dept. of Math. et Inf., Bordeaux Univ., Talence, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory--Finite Automata; Computer Metatheory; finite automata; finite automaton; Iterative Problems; Mathematical Techniques; Number Theory; Rational Functions; rational functions; sequence; Sequences", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Blanchard:1989:BES, author = "F. Blanchard", title = "\$beta@-expansions and symbolic dynamics", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "131--141", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Paris", affiliationaddress = "Paris, Fr", classification = "721; 723; 921; C4210 (Formal logic)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Lab. de Probabilities, Paris 6 Univ., France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory--Formal Languages; beta -expansion; Beta Expansions; Beta Shifts; Computer Metatheory; formal languages; formal logic; integer coefficients; language theory; Mathematical Techniques; negative powers; Number Theory; Symbolic Dynamics; symbolic dynamics", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Bleuzen-Guernalec:1989:PCR, author = "Noelle Bleuzen-Guernalec", title = "On a possible classification of real-time constructed sequences", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "143--148", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Faculte des Sciences de Luminy", affiliationaddress = "Marseille, Fr", classification = "721; 723; 921; C1260 (Information theory); C4240 (Programming and algorithm theory)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Dept. de Math., Fac. des Sci. de Luminy, Marseille, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; complexity; computational complexity; Computer Metatheory; encoding; finite alphabet; Finite Alphabets; fixed-point generation; Infinite Sequences; infinite sequences; iterative productibility; Mathematical Techniques--Number Theory; possible classification; real-time constructed sequences; Realtime Producible Sequences", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Dekking:1989:POL, author = "F. M. Dekking", title = "On the probability of occurrence of labelled subtrees of a randomly labelled tree", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "149--152", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Delft Univ of Technology", affiliationaddress = "Delft, Neth", classification = "723; 921; 922; B0240 (Probability and statistics); B0250 (Combinatorial mathematics); C1140 (Probability and statistics); C1160 (Combinatorial mathematics)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Dept. of Math., Delft Univ. of Technol., Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Binary Trees; Computer Metatheory; Labeled Subtrees; labelled subtrees; Mathematical Techniques; Probability; probability; probability of occurrence; proofs; proposition; Randomly Labeled Trees; randomly labelled tree; theorem; Trees; trees (mathematics)", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Dumont:1989:SNR, author = "J.-M. Dumont and Alain Thomas", title = "Syst{\'e}mes de num\-{\'e}\-ra\-tion et fonction fractales relatifs aux substitutions. ({French}) [{Systems} of numeration and fractal functions relative to substitutions]", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "153--169", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Dumont, Jean-Marie", affiliationaddress = "Faculte des Sciences de Luminy, Marseille, Fr", classification = "723; 921; B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Dept. de Math., Fac. des Sci. de Luminy, Marseille, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "asymptotic formula; Computer Metatheory; finite alphabet; Fractal Functions; fractal functions; integers; Mathematical Techniques; Number Theory; number theory; numeration systems; real numbers; Self-Affine Functions; self-affine functions; Substitutions; substitutions", language = "French", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hansel:1989:RPM, author = "G. Hansel and D. Perrin", title = "Rational probability measures", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "171--188", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Rouen", affiliationaddress = "Mont-Saint-Aignan, Fr", classification = "721; 723; 922; C1140 (Probability and statistics); C1260 (Information theory); C4220 (Automata theory)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "LITP, Rouen Univ., Mount-Saint-Aignan, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; automata theory; Bernoulli measure; Codes, Symbolic--Encoding; coding; encoding; Finite Automata; finite automata; free submonoid; Multiplicative Measures; Probability; probability; Probability Measures on Words; probability theory; Rational Probability Measures; rational probability measures; Tower Construction", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hellekalek:1989:WSS, author = "P. Hellekalek and G. Larcher", title = "On {Weyl} sums and skew products over irrational rotations", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "189--196", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Salzburg", affiliationaddress = "Salzburg, Austria", classification = "723; 921; A0520 (Statistical mechanics)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Inst. f{\"u}r Math., Salzburg Univ., Austria", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "boundness; Computer Metatheory; ergodicity; Irrational Rotations; irrational rotations; limit points; Lipschitz-continuous derivative; Mathematical Techniques; Number Theory; skew product; Skew Products; statistical mechanics; Well Sums; Weyl sums", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kraaikamp:1989:SEP, author = "Cor Kraaikamp", title = "Statistic and ergodic properties of {Minkowski}'s diagonal continued fraction", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "197--212", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Amsterdam Univ", affiliationaddress = "Amsterdam, Neth", classification = "723; 921; 922; A0520 (Statistical mechanics)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Inst. of Math., Amsterdam Univ., Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; Continued Fraction Expansions; DCF; Ergodic Properties; ergodic properties; Mathematical Techniques; Minkowski's Diagonal Continued Fraction; Minkowski's diagonal continued fraction; Number Theory; S Expansions; statistic properties; statistical mechanics", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{MendesFrance:1989:GEI, author = "M. {Mendes France} and A. J. {van der Poorten}", title = "From geometry to {Euler} identities", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "213--220", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Bordeaux 1", affiliationaddress = "Talence, Fr", classification = "723; 921; C4190 (Other numerical methods)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "UER Math. et Inf., Bordeaux Univ., Talence, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "computational geometry; Computer Metatheory; Euler Identities; fuller identities; geometry; Geometry; Mathematical Techniques; Number Theory; Rational Functions; two-dimensional dynamical systems", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Mignosi:1989:IWL, author = "Filippo Mignosi", title = "Infinite words with linear subword complexity", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "221--242", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Palermo", affiliationaddress = "Palermo, Italy", classification = "721; 921; C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Dept. of Comput. Sci., Palermo Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; bounded partial quotients; combinational properties; combinatorial mathematics; computational complexity; continued fraction expansion; Formal Languages; Infinite Words; infinite words; Linear Subword Complexity; linear subword complexity; Mathematical Techniques--Combinatorial Mathematics; permutation property; real number; Sturmian Infinite Words", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Mori:1989:FDP, author = "Makoto Mori", title = "On the {Fredholm} determinant of a piecewise linear transformation", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "243--248", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "National Defence Acad", affiliationaddress = "Yokosuka, Jpn", classification = "723; 921; B0290H (Linear algebra); C4140 (Linear algebra)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Dept. of Math., Nat. Defence Acad., Kanagawa, Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; eigenvalues and eigenfunctions; finite-dimensional matrix; Fredholm Determinant; Fredholm determinant; integral equations; Mathematical Transformations; Perron--Frobenius operator; piecewise linear transformation; Piecewise Linear Transformations; piecewise-linear techniques; renewal equation; Signed Symbolic Dynamics; signed symbolic dynamics; zeta function; Zeta Functions", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Mosse:1989:QAS, author = "Brigitte Mosse", title = "{Q}-Adic spectral analysis of some arithmetic sequences", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "249--263", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "CNRS", affiliationaddress = "Marseille, Fr", classification = "723; 921; B6140 (Signal processing and detection); C1260 (Information theory)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "CNRS, UFR de Math., Univ. de Provence, Marseille, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Arithmetic Sequences; arithmetic sequences; Computer Metatheory; Mathematical Techniques; metric group action; Multiplicative Sequences; multiplicative sequences; Number Theory; q-adic spectral analysis; spectral analysis; Spectrum Analysis; Walsh Correlations; Walsh functions; Walsh Spectral Measures; Walsh spectral measures", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Restivo:1989:FGS, author = "Antonio Restivo", title = "Finitely generated sofic systems", journal = j-THEOR-COMP-SCI, volume = "65", number = "2", pages = "265--270", day = "28", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ di Palermo", affiliationaddress = "Palermo, Italy", classification = "723; 921; C4210 (Formal logic)", conference = "Conference on Arithmetics and Coding Systems", conflocation = "Marseille-Luminy, France; 9-13 June 1989", conftitle = "Conference on Arithmetics and Coding Systems", corpsource = "Dipartimento di Matematica ed Applicazioni, Palermo Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory--Computability and Decidability; Codes, Symbolic; Computer Metatheory; Decidability; decidability; decidable; Finite Sequences; finitely generated sofic systems; Mathematical Techniques--Number Theory; transitive sofic system; Transitive Sofic Systems", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Yokouchi:1989:CRT, author = "Hirofumi Yokouchi", title = "{Church--Rosser} theorem for a rewriting system on categorical combinators", journal = j-THEOR-COMP-SCI, volume = "65", number = "3", pages = "271--290", day = "17", month = jul, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "IBM", affiliationaddress = "Tokyo, Jpn", classification = "723; C4210 (Formal logic)", corpsource = "Tokyo Res. Lab., IBM Res., Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Categorical Combinators; CCL hierarchy; Church--Rosser Theorem; Church--Rosser theorem; Computer Metatheory; Computer Programming Languages; reduction strategy; Rewriting System; rewriting system; rewriting systems; Theory; type-free categorical combinations", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hardin:1989:CRP, author = "Therese Hardin", title = "Confluence results for the pure strong categorical logic {CCL} \$lambda@-calculi as subsystems of {CCL}", journal = j-THEOR-COMP-SCI, volume = "65", number = "3", pages = "291--342", day = "17", month = jul, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "INRIA", affiliationaddress = "Le Chesnay, Fr", classification = "723; C4210 (Formal logic)", corpsource = "Project FORMEL, INRIA, Le Chesnay, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "beta - derivations; CCL; Computer Metatheory; Computer Programming Languages; Confluence; formal logic; interpretation method; Lambda Calculus; projection rules; pure strong categorical logic; rewriting systems; Rewriting Systems; Strong Categorical Combinatory Logic; Theory; untyped Lambda-calculi", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Shepherdson:1989:SCS, author = "J. C. Shepherdson", title = "A sound and complete semantics for a version of negation as failure", journal = j-THEOR-COMP-SCI, volume = "65", number = "3", pages = "343--371", day = "17", month = jul, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Bristol", affiliationaddress = "Bristol, Engl", classification = "723; C4210 (Formal logic)", corpsource = "Dept. of Math., Bristol Univ., UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "3- valued logic; completeness; Computer Metatheory; consequence relation; declarative semantics; formal logic; Intuitionistic Logic; intuitionistic logic; Logic Programming; negation as failure; Negation as Failure; Programming Theory; Semantics; SLDNF-resolution; soundness; Three Valued Logic", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Lehmkuhl:1989:OAA, author = "T. Lehmkuhl and T. Lickteig", title = "On the order of approximation in approximative triadic decompositions of tensors", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "1--14", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Math. Inst., Tubingen Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "algebraic border rank; algebraically closed ground fields; approximative triadic decompositions; computational complexity; equivalence; order of approximation; real closed fields; tensors; topological border rank; upper bound", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Dunne:1989:MSN, author = "P. E. Dunne", title = "On monotone simulations of nonmonotone networks", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "15--25", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., Liverpool Univ., UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "Boolean functions; monotone simulations; nonmonotone networks", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Piperno:1989:APC, author = "A. Piperno", title = "Abstraction problems in combinatory logic: a compositive approach", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "27--43", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Dipartimento di Matematica, Rome Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "abstraction problems; cardinality; combinatorial mathematics; combinatory logic; compact code; compositive approach; formal logic; functional languages; lambda -terms; translation", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Kari:1989:OCP, author = "J. Kari", title = "Observations concerning a public-key cryptosystem based on iterated morphisms", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "45--53", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "B6120B (Codes); C6130 (Data handling techniques)", corpsource = "Dept. of Math., Turku Univ., Finland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "cryptography; cryptotext; decryption key; iterated morphisms; NP-hard problem; plaintext; public-key cryptosystem; substitutions", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Xin:1989:EAD, author = "Zhang Luo Xin", title = "An efficient algorithm to decide whether a monoid presented by a regular {Church--Rosser Thue} system is a group", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "55--63", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Math., Lanzhou Univ., China", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "algorithm; cardinality; decidability; decidable; group; monoid; regular Church--Rosser Thue system", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{opdenAkker:1989:LGL, author = "R. {op den Akker}", title = "On {LC(0)} grammars and languages", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "65--85", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., Twente Univ., Enschede, Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "deterministic languages; formal languages; grammars; languages; left-corner grammars; LL(1) languages; LR(0) languages; LR(k) grammars", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Urquhart:1989:CGS, author = "A. Urquhart", title = "The complexity of {Gentzen} systems for propositional logic", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "87--97", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Philos., Toronto Univ., Ont., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "biconditional; complexity; computational complexity; exponentially long proofs; formal logic; Gentzen systems; polynomial size proofs; propositional logic; valid sequents", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Statman:1989:SSC, author = "R. Statman", title = "On sets of solutions to combinator equations", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "99--104", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C1250 (Pattern recognition)", corpsource = "Dept. of Math., Carnegie-Mellon Univ., Pittsburgh, PA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "beta -conversion; combinator equations; combinatorial mathematics; pattern matching; pattern recognition; sets of solutions", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Pelc:1989:WAC, author = "A. Pelc", title = "Weakly adaptive comparison searching", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "105--111", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. d'Inf., Quebec Univ., Que., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "comparison queries; complexity; computational complexity; discrete search; error bound; weakly adaptive comparison searching; worst-case optimal algorithm", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Mundici:1989:FCM, author = "D. Mundici", title = "Functions computed by monotone {Boolean} formulas with no repeated variables", journal = j-THEOR-COMP-SCI, volume = "66", number = "1", pages = "113--114", day = "2", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dipartimento Sci. Inf., Milan Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "Boolean functions; matroid theory; monotone Boolean formulas; necessary condition; prime clause; prime implicant; singleton", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Diekert:1989:KBC, author = "Volker Diekert", title = "On the {Knuth--Bendix} completion for concurrent processes", journal = j-THEOR-COMP-SCI, volume = "66", number = "2", pages = "117--136", day = "20", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Technische Univ Muenchen", affiliationaddress = "Munich, West Ger", classification = "721; 723; C4210 (Formal logic); C4240 (Programming and algorithm theory)", conference = "14th International Colloquium on Automata, Languages and Programming", conflocation = "Karlsruhe, West Germany; 13-17 July 1987", conftitle = "Fourteenth International Colloquium on Automata, Languages and Programming", corpsource = "Inst. f{\"u}r Informatik, Tech. Univ. Munchen, West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; computability; computable; Computer Systems, Digital--Parallel Processing; Concurrent Processes; concurrent processes; critical pairs; finite trace replacement; formal languages; Free Partially Communicative Monoids; group theory; Knuth--Bendix Completion; Knuth--Bendix completion procedure; monoids; parallel algorithms; replacement systems; semi-Thue systems; vector replacement systems", meetingaddress = "Karlsruhe, West Ger", meetingdate = "Jun 1987", meetingdate2 = "06/87", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput.Sci", treatment = "T Theoretical or Mathematical", } @Article{Dietzfelbinger:1989:LBS, author = "Martin Dietzfelbinger", title = "Lower bounds for sorting of sums", journal = j-THEOR-COMP-SCI, volume = "66", number = "2", pages = "137--155", day = "20", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Dortmund", affiliationaddress = "Dortmund, West Ger", classification = "723; 921; C4240 (Programming and algorithm theory); C6130 (Data handling techniques)", conference = "14th International Colloquium on Automata, Languages and Programming", conflocation = "Karlsruhe, West Germany; 13-17 July 1987", conftitle = "Fourteenth International Colloquium on Automata, Languages and Programming", corpsource = "Lehrstuhl Informatik II, Dortmund Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "comparison tree; complexity of sorting; Computational Complexity; computational complexity; Computer Systems Programming; lower bound; Lower Bounds; Mathematical Techniques--Trees; optimal; Sorting; sorting; Sorting of Sums; sums", meetingaddress = "Karlsruhe, West Ger", meetingdate = "Jun 1987", meetingdate2 = "06/87", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput.Sci", treatment = "T Theoretical or Mathematical", } @Article{Edelsbrunner:1989:TNC, author = "Herbert Edelsbrunner and Guenter Rote and Ermo Welzl", title = "Testing the necklace condition for shortest tours and optimal factors in the plane", journal = j-THEOR-COMP-SCI, volume = "66", number = "2", pages = "157--180", day = "20", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Illinois at Urbana-Champaign", affiliationaddress = "Urbana, IL, USA", classification = "723; 921; C1160 (Combinatorial mathematics); C1290 (Applications of systems theory); C4240 (Programming and algorithm theory)", conference = "14th International Colloquium on Automata, Languages and Programming", conflocation = "Karlsruhe, West Germany; 13-17 July 1987", conftitle = "Fourteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "combinatorial analysis; complexity results; computational complexity; Computer Programming--Algorithms; graph theory; intersection graphs; Mathematical Programming; Necklace Condition; necklace condition; operations research; Optimal Factors; optimal factors; Shortest Tours; shortest tours; Traveling Salesman Problem; traveling salesman tour", meetingaddress = "Karlsruhe, West Ger", meetingdate = "Jun 1987", meetingdate2 = "06/87", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput.Sci", treatment = "T Theoretical or Mathematical", } @Article{Levcopoulos:1989:HOB, author = "Christos Levcopoulos and Andrzej Lingas and Jorg-R. R. Sack", title = "Heuristics for optimum binary search trees and minimum weight triangulation problems", journal = j-THEOR-COMP-SCI, volume = "66", number = "2", pages = "181--203", day = "20", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Link{\"o}ping Univ", affiliationaddress = "Link{\"o}ping, Swed", classification = "723; 921; C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", conference = "14th International Colloquium on Automata, Languages and Programming", conflocation = "Karlsruhe, West Germany; 13-17 July 1987", conftitle = "Fourteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. and Inf. Sci., Linkoping Univ., Sweden", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Amortization Argument; binary search trees; Computer Programming--Algorithms; Data Processing; Data Structures; duality; greedy heuristics; linear-time heuristic; Mathematical Techniques--Trees; Minimum Weight Triangulation; minimum weight triangulation; Optimum Binary Search Trees; optimum binary search trees; search problems; search trees; trees (mathematics)", meetingaddress = "Karlsruhe, West Ger", meetingdate = "Jun 1987", meetingdate2 = "06/87", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput.Sci", treatment = "T Theoretical or Mathematical", } @Article{NaitAbdallah:1989:LAA, author = "M. A. {Nait Abdallah}", title = "A logico-algebraic approach to the model theory of knowledge", journal = j-THEOR-COMP-SCI, volume = "66", number = "2", pages = "205--232", day = "20", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Western Ontario", affiliationaddress = "London, Ont, Can", classification = "723; 921; C1230 (Artificial intelligence); C4210 (Formal logic); C4240 (Programming and algorithm theory)", conference = "14th International Colloquium on Automata, Languages and Programming", conflocation = "Karlsruhe, West Germany; 13-17 July 1987", conftitle = "Fourteenth International Colloquium on Automata, Languages and Programming", corpsource = "Dept. of Comput. Sci., Univ. of Western Ontario, London, Ont., Canada", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Algebraic Semantics; algebraic semantics; Computer Metatheory; Computer Programming; first-order logic programming; formal languages; knowledge engineering; Logic Programming; logic programming; logic programming framework; logico-algebraic approach; Mathematical Techniques--Algebra; Model Theory of Knowledge; model theory of knowledge", meetingaddress = "Karlsruhe, West Ger", meetingdate = "Jun 1987", meetingdate2 = "06/87", pubcountry = "Netherlands", sponsororg = "Eur. Assoc. Theor. Comput.Sci", treatment = "T Theoretical or Mathematical", } @Article{Weil:1989:IMD, author = "P. Weil", title = "Inverse monoids of dot-depth two", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "233--245", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "LITP, Paris, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "dot-depth two; formal languages; inverse generators; inverse monoids; necessary condition; star-free regular language; syntactic monoid", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Yamasaki:1989:LTR, author = "H. Yamasaki", title = "Language-theoretical representations of $Gw$-languages", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "247--254", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dept. of Math., Hitotsubashi Univ., Tokyo, Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "finite automata; formal languages; Gw-languages; language theoretical representations; prefix-free finite languages; prefix-free regular languages", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Angluin:1989:TS, author = "D. Angluin and W. I. Gasarch and C. H. Smith", title = "Training sequences", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "255--272", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1230 (Artificial intelligence)", corpsource = "Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "finite sequence; inference mechanisms; learning systems; recursion theoretic framework; recursive functions; simultaneous inference of programs; training sequences", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Ito:1989:DTD, author = "A. Ito and K. Inoue and I. Takanami", title = "Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180 degrees-rotation", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "273--287", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Yamaguchi Univ., Ube, Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "2D deterministic online tesselation acceptor; finite automata; two-way two-dimensional alternating finite automaton", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Jacopini:1989:GIF, author = "G. Jacopini and P. Mentrasti", title = "Generation of invertible functions", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "289--297", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dipartimento di Matematica, Rome Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "formal logic; functional composition; functional iteration; invertible one-variable partial recursive functions; reversible iteration; Turing machines; Turning machine", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Makowsky:1989:WSO, author = "J. A. Makowsky and I. Sain", title = "Weak second order characterizations of various program verification systems", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "299--321", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6150G (Diagnostic, testing, debugging and evaluating systems)", corpsource = "Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "comprehension axiom; Floyd-Hoare Logic; logic programming; nonstandard logics of programs; program verification; program verification systems; weak second order characterisations", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Mezghiche:1989:PCB, author = "M. Mezghiche", title = "On pseudo-c beta normal form in combinatory logic", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "323--331", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Inst. Nat. d'Inf., Tizi-Ouzou, Algeria", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "CL-term; combinatorial mathematics; combinatory logic; formal logic; lambda beta -normal form; pseudo-c beta normal form", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Tiomkin:1989:PTV, author = "M. Tiomkin", title = "Probabilistic termination versus fair termination", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "333--340", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6150G (Diagnostic, testing, debugging and evaluating systems)", corpsource = "Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "complexity; concurrent programs; fair termination; probabilistic termination; program verification; recursive ordinals", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Honkala:1989:NCR, author = "J. Honkala", title = "A necessary condition for the rationality of the zeta function of a regular language", journal = j-THEOR-COMP-SCI, volume = "66", number = "3", pages = "341--347", day = "26", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dept. of Math., Turku Univ., Finland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "cyclic languages; formal languages; generating function; necessary condition; rationality; regular language; zeta function", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Swart:1989:IS, author = "Charles Swart and Dana Richards", title = "On the inference of strategies", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "5--18", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Oregon State Univ", affiliationaddress = "Corvallis, OR, USA", classification = "721; 921; 922; C1140E (Game theory); C4220 (Automata theory)", corpsource = "Dept. of Comput. Sci., Oregon State Univ., Corvallis, OR, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; automata theory; counter machine; Counter Machine Strategies; decidability; finite-state strategies; game theory; Game Theory; graph traversal techniques; Graph Traversal Techniques; inference mechanisms; Inference of Strategies; inference of strategies; infinite tournaments; Mathematical Techniques--Graph Theory; optimal defense; Prisoner's Dilemma; Probability; Turing machine; Turing Machine Strategies; Turing machines; two-person games", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Otto:1989:DCF, author = "Friedrich Otto", title = "On deciding confluence of finite string-rewriting systems modulo partial commutativity", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "19--35", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "State Univ of New York", affiliationaddress = "Albany, NY, USA", classification = "721; 723; C4210 (Formal logic)", corpsource = "Dept. of Comput. Sci., State Univ. of New York, Albany, NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Computer Metatheory; Confluence; confluence; Congruence; congruence; decidability; decidable; finite string-rewriting systems; Formal Languages; partial commutativity relation; partially commutative alphabets; Partially Commutative Monoids; rewriting systems; String Rewriting Systems; string-rewriting systems; term-rewriting systems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Martin:1989:GAM, author = "Ursula Martin", title = "A geometrical approach to multiset orderings", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "37--54", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of London", affiliationaddress = "London, Engl", classification = "921; C4290 (Other computer theory)", corpsource = "Dept. of Comput. Sci., R. Holloway and Bedford New Coll., London Univ., Egham, UK", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "computational geometry; Dominance Ordering; dominance ordering; geometrical approach; Mathematical Techniques; multiset ordering; Multiset Orderings; multiset orderings; multisets; set theory; Set Theory; Tame Orderings", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Clausen:1989:FGF, author = "Michael Clausen", title = "Fast generalized {Fourier} transforms", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "55--63", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ Karlsruhe", affiliationaddress = "Karlsruhe, West Ger", classification = "921; C4190 (Other numerical methods); C4240 (Programming and algorithm theory)", corpsource = "Fakultat fur Informatik, Karlsruhe Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "computational complexity; fast Fourier transforms; Fast Generalized Fourier Transforms; finite group; Finite Groups; Fourier transforms; Fourier Transforms; group theory; Linear Complexity; linear complexity; Mathematical Transformations; subgroups; Symmetric Groups; trivial upper bound; Wedderburn Transform; Wedderburn transform", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Beauquier:1989:MAF, author = "Daniele Beauquier", title = "Minimal automation for a factorial, transitive, and rational language", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "65--73", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ de Paris", affiliationaddress = "Paris, Fr", classification = "721; 723; C4210 (Formal logic); C4220 (Automata theory)", corpsource = "LITP, Paris VII Univ., France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Computer Programming--Algorithms; deterministic automata; deterministic automaton; equivalence relation; factorial, transitive, and rational language; formal languages; Formal Languages; FTR-language; intrinsic definition; Minimal Automata; minimal irreducible deterministic automaton; Rational Languages; syntactic monoid", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", xxtitle = "Minimal automaton for a factorial, transitive, and rational language", } @Article{Moriya:1989:GCA, author = "Etsuro Moriya", title = "A grammatical characterization of alternating pushdown automata", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "75--85", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Tokyo Woman's Christian Univ", affiliationaddress = "Tokyo, Jpn", classification = "721; C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dept. of Math., Tokyo Woman's Christian Univ., Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "alternating context-free languages; alternating pushdown automata; Alternating Pushdown Automata; Automata Theory; automata theory; class of languages; Context Free Grammars; Context Free Languages; context-free grammar; context-free grammars; context-free languages", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Marongiu:1989:CBT, author = "G. Marongiu and S. Tulipani", title = "On a conjecture of {Bergstra} and {Tucker}", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "87--97", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Univ of Bologna", affiliationaddress = "Bologna, Italy", classification = "723; C4240 (Programming and algorithm theory)", corpsource = "Dept. of Math., Bologna Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "abstract data type; Abstract Data Types; algebra semantics; computability; Computer Metatheory; Computer Programming Languages; data structures; data type; nontrivial case; proof techniques; semicomputable data type; Semicomputable Data Types; Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Inoue:1989:LSH, author = "Katsushi Inoue and Itsuo Takanami and Juraj Hromkovic", title = "Leaf-size hierarchy of two-dimensional alternating {Turing} machines", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "99--110", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Yamaguchi Univ", affiliationaddress = "Ube, Jpn", classification = "721; C4220 (Automata theory)", corpsource = "Dept. of Electron., Yamaguchi Univ., Ube, Japan", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "alternating; Alternating Turing Machines; Automata Theory; complexity classes; complexity measure; Complexity Measures; computational complexity; leaf-size bounded computations; leaf-size hierarchy; Turing Machines; Turing machines; two-dimensional", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Pardubska:1989:NMM, author = "Dana Pardubska and Ivana Stefanekova", title = "Nondeterministic multicounter machines and complementation", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "111--113", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Comenius Univ", affiliationaddress = "Bratislava, Czech", classification = "721; 921; C4210 (Formal logic); C4220 (Automata theory)", corpsource = "Dept. of Theor. Cybernetics, Comenius Univ., Bratislava, Czechoslovakia", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; automata theory; complementation; family of languages; Formal Languages; formal languages; Mathematical Techniques--Polynomials; multicounter machines; Nondeterministic Multicounter Machines; nondeterministic multicounter machines; polynomial function; Polynomial Functions", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Cosnard:1989:CSX, author = "M. Cosnard and J. Duprat and A. Ferreira", title = "Complexity of selection in {X} + {Y}", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "115--120", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "ENS", affiliationaddress = "Lyon, Fr", classification = "723; 921; C4240 (Programming and algorithm theory)", corpsource = "LIP-IMAG, ENS-Lyon, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "algorithm; Algorithms; complexity; Complexity of Selection; computational complexity; Computer Programming; lower bound; Mathematical Techniques--Matrix Algebra; matrices; searching; sorting", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Petuaud:1989:ETS, author = "Catherine Petuaud", title = "Entropie topologique des syst{\`e}mes specifi{\'e}s. ({French}) [{Topological} entropy of specified systems]", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "121--128", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Lycee Hoche", affiliationaddress = "Versailles, Fr", classification = "721; C4210 (Formal logic)", corpsource = "Lycee Hoche, Versailles, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Automata Theory; finite alphabet; formal languages; Formal Languages; sofic systems; specification property; Specification Property; topological entropies; Topological Entropy", language = "French", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{PinoPerez:1989:DRE, author = "Ramon {Pino Perez}", title = "Decidability of the restriction equational theory in the partial lambda calculus", journal = j-THEOR-COMP-SCI, volume = "67", number = "1", pages = "129--139", day = "5", month = sep, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, affiliation = "Liens", affiliationaddress = "Paris, Fr", classification = "723; C4210 (Formal logic)", corpsource = "Liens, Paris, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory--Programming Theory; Computer Programming; Decidability; decidability; decidable; equational theory; Partial Lambda Calculus; partial lambda calculus; partiality; Restriction Equational Theory; Theory", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Madlener:1989:ADP, author = "K. Madlener and F. Otto", title = "About the descriptive power of certain classes of finite string-rewriting systems", journal = j-THEOR-COMP-SCI, volume = "67", number = "2--3", pages = "143--172", day = "3", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", conflocation = "Bordeaux, France; 25-27 May 1987", conftitle = "Second International Conference on Rewriting Techniques and Applications 'RTA-87'", corpsource = "Fachbereich Inf., Kaiserslautern Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "algebraic characterizations; classes; complexity; computational complexity; decidability; decision problems; descriptive power; finite canonical string-rewriting systems; groups; monoids; rewriting systems; undecidable", pubcountry = "Netherlands", sponsororg = "Univ. Bordeaux 1; Univ. Nancy 1; City of Bordeaux; Greco Math. Inf.; Greco Programmation", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Bachmair:1989:CRM, author = "L. Bachmair and N. Dershowitz", title = "Completion for rewriting modulo a congruence", journal = j-THEOR-COMP-SCI, volume = "67", number = "2--3", pages = "173--201", day = "3", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1230 (Artificial intelligence); C4210 (Formal logic)", conflocation = "Bordeaux, France; 25-27 May 1987", conftitle = "Second International Conference on Rewriting Techniques and Applications 'RTA-87'", corpsource = "Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "completion modulo a congruence; correctness proving; equational inference system; equational theory; inference mechanisms; Jouannaud-Kirchner procedure; Peterson-Stickel; rewrite system; rewriting; rewriting systems; theorem proving; unique normal forms", pubcountry = "Netherlands", sponsororg = "Univ. Bordeaux 1; Univ. Nancy 1; City of Bordeaux; Greco Math. Inf.; Greco Programmation", treatment = "T Theoretical or Mathematical", } @Article{Gallier:1989:CST, author = "J. H. Gallier and W. Snyder", title = "Complete sets of transformations for general {E}-unification", journal = j-THEOR-COMP-SCI, volume = "67", number = "2--3", pages = "203--260", day = "3", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C1230 (Artificial intelligence); C4210 (Formal logic)", conflocation = "Bordeaux, France; 25-27 May 1987", conftitle = "Second International Conference on Rewriting Techniques and Applications 'RTA-87'", corpsource = "Dept. of Comput. and Inf. Sci., Pennsylvania Univ., Philadelphia, PA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "arbitrary equational theories; complete; complete set; completeness; critical pairs; equational proofs; general E-unification; narrowing; prove; rewriting systems; set theory; sound; surreduction; systems of terms; theorem proving; transformations; trees; trees (mathematics); unfailing completion", pubcountry = "Netherlands", sponsororg = "Univ. Bordeaux 1; Univ. Nancy 1; City of Bordeaux; Greco Math. Inf.; Greco Programmation", treatment = "T Theoretical or Mathematical", } @Article{Choppy:1989:CAT, author = "C. Choppy and S. Kaplan and M. Soria", title = "Complexity analysis of term-rewriting systems", journal = j-THEOR-COMP-SCI, volume = "67", number = "2--3", pages = "261--282", day = "3", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", conflocation = "Bordeaux, France; 25-27 May 1987", conftitle = "Second International Conference on Rewriting Techniques and Applications 'RTA-87'", corpsource = "Lab. de Recherche en Inf., CNRS, Univ. de Paris-Sud, Orsay, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "algebraic specification; asymptotic evaluation; complexity analysis; computational complexity; cost series; enumerative series; operator complexity; regular rewriting systems; rewriting systems; term-rewriting systems", pubcountry = "Netherlands", sponsororg = "Univ. Bordeaux 1; Univ. Nancy 1; City of Bordeaux; Greco Math. Inf.; Greco Programmation", treatment = "T Theoretical or Mathematical", } @Article{Baeten:1989:TRS, author = "J. C. M. Baeten and J. A. Bergstra and J. W. Klop and W. P. Weijland", title = "Term-rewriting systems with rule priorities", journal = j-THEOR-COMP-SCI, volume = "67", number = "2--3", pages = "283--301", day = "3", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", conflocation = "Bordeaux, France; 25-27 May 1987", conftitle = "Second International Conference on Rewriting Techniques and Applications 'RTA-87'", corpsource = "Amsterdam Univ., Netherlands", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "bounded systems; class; partial ordering; rewriting systems; rule priorities; semantics; term-rewriting systems", pubcountry = "Netherlands", sponsororg = "Univ. Bordeaux 1; Univ. Nancy 1; City of Bordeaux; Greco Math. Inf.; Greco Programmation", treatment = "T Theoretical or Mathematical", } @Article{Kirchner:1989:SIS, author = "H. Kirchner", title = "Schematization of infinite sets of rewrite rules generated by divergent completion processes", journal = j-THEOR-COMP-SCI, volume = "67", number = "2--3", pages = "303--332", day = "3", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", conflocation = "Bordeaux, France; 25-27 May 1987", conftitle = "Second International Conference on Rewriting Techniques and Applications 'RTA-87'", corpsource = "Loria and Crin, Vandoeuvre-les-Nancy, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "complete; decidability; divergent completion processes; equation; equational theory; infinite sets; rewrite rules; rewriting systems; rules; satisfiability; schematization; set theory; sound; validity", pubcountry = "Netherlands", sponsororg = "Univ. Bordeaux 1; Univ. Nancy 1; City of Bordeaux; Greco Math. Inf.; Greco Programmation", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Kirschenhofer:1989:BPP, author = "P. Kirschenhofer and H. Prodinger and W. Szpankowski", title = "On the balance property of {Patricia} trees: external path length viewpoint", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "1--17", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4130 (Interpolation and function approximation); C4210 (Formal logic)", corpsource = "Inst fur Algebra and Diskrete Math., Tech. Univ. Wien, Austria", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "approximation theory; asymptotic approximations; balance property; exact approximations; external path length; Patricia trees; probability; trees (mathematics)", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Chang:1989:ESS, author = "J. H. Chang and O. H. Ibarra and M. A. Palis", title = "Efficient simulations of simple models of parallel computation by time-bounded {ATMs} and space-bounded {TMs}", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "19--36", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "alternating Turing machines; boolean circuits; computational complexity; finite automata; finite-state machines; interconnected networks; one-way conglomerates; parallel computation; simple models; simulations; space-bounded TMs; time-bounded ATMs; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Droste:1989:ESD, author = "M. Droste", title = "Event structures and domains", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "37--47", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C6120 (File organisation)", corpsource = "Essen Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "algebraic complete partial order; computational processes; concrete data structures; data structures; denotational semantics; event domain; event structures", pubcountry = "Netherlands", treatment = "P Practical", } @Article{Hofer:1989:LIR, author = "G. Hofer", title = "Left ideals and reachability in machines", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "49--56", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Dept. of Math., Linz Univ., Austria", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "automata theory; automation; input set; leftideals; mappings; near-rings; state set; syntactic near-rings; zero-symmetric part", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gambosi:1989:WCA, author = "G. Gambosi and G. F. Italiano and M. Talamo", title = "Worst-case analysis of the set-union problem with extended backtracking", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "57--70", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6120 (File organisation)", corpsource = "Inst. di Analisi dei Sistemi ed Informatica-CNR, Rome, Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "computational complexity; data structure; data structures; extended backtracking; set-union problem; space complexity; time complexity; worst case analysis", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Huckenbeck:1989:EGT, author = "U. Huckenbeck", title = "{Euclidian} geometry in terms of automata theory", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "71--87", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4220 (Automata theory)", corpsource = "Lehrstuhl fur Informatik I, Wurzburg Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "abstract automata; automata theory; elementary geometric problems; Euclidian operations; jumps; oracle sets", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Karloff:1989:NAB, author = "H. J. Karloff", title = "An {NC} algorithm for {Brooks}' theorem", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "89--103", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "B0250 (Combinatorial mathematics); C1160 (Combinatorial mathematics)", corpsource = "Chicago Univ., IL, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "Brooks' theorem; coloring; graph; graph colouring; NC algorithm", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Josephs:1989:SLF, author = "M. B. Josephs", title = "The semantics of lazy functional languages", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "105--111", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "IBM Res. Div., Yorktown Heights, NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "lambda -calculus; lazy functional languages; programming theory; semantics", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Chlebus:1989:HPH, author = "B. S. Chlebus", title = "A hierarchy of propositional {Horn} formulas", journal = j-THEOR-COMP-SCI, volume = "68", number = "1", pages = "113--119", day = "16", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Inst. of Inf., Warsaw Univ., Poland", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "bounded-depth circuits; computational complexity; equivalent formulas; game; hierarchy; propositional Horn formulas; satisfiability", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Arvind:1989:SBR, author = "V. Arvind and S. Biswas", title = "On some bandwidth restricted versions of the satisfiability problem of propositional {CNF} formulas", journal = j-THEOR-COMP-SCI, volume = "68", number = "2", pages = "123--134", day = "30", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4220 (Automata theory); C4240 (Programming and algorithm theory)", conflocation = "Pune, India; 17-19 Dec. 1987", conftitle = "Seventh Conference on Foundations of Software Technology and Theoretical Computer Science", corpsource = "Dept. of Comput. Sci. and Eng., Indian Inst. of Technol., Delhi, India", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "bandwidth restricted versions; complexity; computational complexity; corresponding languages; decision problems; formal logic; kernel constructibility; logics; proof; propositional CNF formulas; satisfiability problem; satisfiable propositional CNF formulas; self-reducibility property; Turing machine acceptance problems; Turing machines", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Blair:1989:PLP, author = "H. A. Blair and V. S. Subrahmanian", title = "Paraconsistent logic programming", journal = j-THEOR-COMP-SCI, volume = "68", number = "2", pages = "135--154", day = "30", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1230 (Artificial intelligence); C4210 (Formal logic)", conflocation = "Pune, India; 17-19 Dec. 1987", conftitle = "Seventh Conference on Foundations of Software Technology and Theoretical Computer Science", corpsource = "Sch. of Comput. and Inf. Sci., Syracuse Univ., NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "Horn clauses; inconsistency; literal; logic programming; many-valued logics; paraconsistent logic programming; robust semantics; sets; syntactic form; two-valued logic; very large knowledge bases", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Lingas:1989:PCS, author = "A. Lingas and A. Proskurowski", title = "On parallel complexity of the subgraph homeomorphism and the subgraph isomorphism problem for classes of planar graphs", journal = j-THEOR-COMP-SCI, volume = "68", number = "2", pages = "155--173", day = "30", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4240 (Programming and algorithm theory)", conflocation = "Pune, India; 17-19 Dec. 1987", conftitle = "Seventh Conference on Foundations of Software Technology and Theoretical Computer Science", corpsource = "Dept. of Comput. and Inf. Sci., Linkoping Univ., Sweden", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "bounded number; closed; computational complexity; disjoint connecting paths; fixed pattern; forbidden minor characterization; graph theory; NC algorithm; nontrivial graph family; parallel algorithms; parallel complexity; planar graphs; polynomial; recognition; restriction; Robertson; Seymour; subgraph homeomorphism; subgraph isomorphism problem; terminal pairs; two-connected outerplanar graphs", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Parrow:1989:SCE, author = "J. Parrow", title = "Submodule construction as equation solving in {CCS}", journal = j-THEOR-COMP-SCI, volume = "68", number = "2", pages = "175--202", day = "30", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "B6110 (Information theory); B6150 (Communication system theory); C1260 (Information theory); C4240 (Programming and algorithm theory)", conflocation = "Pune, India; 17-19 Dec. 1987", conftitle = "Seventh Conference on Foundations of Software Technology and Theoretical Computer Science", corpsource = "Swedish Inst. of Comput. Sci., Kista, Sweden", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "alternating bit protocol; automatic generation; CCS; channels; equation; equation solving; information theory; parallel; parallel algorithms; programming theory; protocols; receivers; semiautomatic program; submodules; successive transformation; system specifications; top-down design methodologies", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Ramanujam:1989:SDD, author = "R. Ramanujam", title = "Semantics of distributed definite clause programs", journal = j-THEOR-COMP-SCI, volume = "68", number = "2", pages = "203--220", day = "30", month = oct, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1230 (Artificial intelligence); C4240 (Programming and algorithm theory)", conflocation = "Pune, India; 17-19 Dec. 1987", conftitle = "Seventh Conference on Foundations of Software Technology and Theoretical Computer Science", corpsource = "Inst. of Math. Sci., CIT Campus, Madras, India", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "definite Horn clause program; distributed definite clause programs; distributed refutations; fixed finite number; least fixed-point characterization; logic programming; process model; programming theory; semantics; sites", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Coquand:1989:CE, author = "T. Coquand", title = "Categories of embeddings", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "221--237", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "INRIA, Le Chesnay, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "cartesian closed categories of domains; category theory; domain theory; exponentiation; formal logic; polymorphism; set theory; types", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gutbrod:1989:TSG, author = "R. Gutbrod", title = "A transformation system for generating description languages of chain code pictures", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "239--252", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4290 (Other computer theory)", corpsource = "Lehrstuhl fur Inf., Wurzburg Univ., West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "cartesian plane; chain code pictures; computational geometry; connected picture; description languages; formal languages; geometric information; picture languages; regular language", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Blanchard:1989:CSS, author = "F. Blanchard", title = "Certain sofic systems engendered codes", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "253--265", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "B6120B (Codes); C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Lab. de Probabilit{\'e}s, Paris 6 Univ., France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "circular codes; codes; concatenation; encoding; finite deciphering delay; first return code; local codes; rational code; right-resolving cover; set theory; sofic system; state space; unique splitting", language = "French", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Immerman:1989:RRC, author = "N. Immerman and S. R. Mahaney", title = "Relativizing relativized computations", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "267--276", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Comput. and Inf. Sci., Massachusetts Univ., Amherst, MA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "computability; decidability; NP- complete problems; oracle; polynomial-size circuits; polynomial-time many-one reductions; polynomial-time programs; relativizable proof techniques; relativized computations", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Hortala-Gonzalez:1989:HLN, author = "M. T. Hortala-Gonzalez and M. Rodriguez-Artalejo", title = "{Hoare}'s logic for nondeterministic regular programs: a nonstandard approach", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "277--302", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. de Inf. y Autom., Fac. de Matematicas, Univ. Complutense de Madrid, Spain", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "completeness theorem; continuous semantics; formal logic; Hoare logic; infinitely long computations; nondeterministic regular programs; nondeterministic systems; nonstandard dynamic logic; normal form; program verification; regular programs; unbounded nondeterminism", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Bracho:1989:CGF, author = "F. Bracho", title = "Continuously generated fixed points", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "303--317", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Inst. de Investigaciones en Matematicas Aplicadas y en Sistemas, Univ. Nacional Autonoma de Mexico, Mexico City, Mexico", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "continuous fixed-point operator; continuous function; domain equations; formal logic; least fixed-point operator; recursive functions; recursively defined functions; types", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Narendran:1989:SPT, author = "P. Narendran and F. Otto", title = "Some polynomial-time algorithms for finite monadic {Church--Rosser Thue} systems", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "319--332", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "General Electric Co., Schenectady, NY, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "decidability; finite monadic Church--Rosser Thue systems; monadic Thue systems; polynomial time decidable; polynomial-time algorithms; reduction sequences; rewriting systems; undecidable; uniform conjugacy problem; uniform decision problems", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Solitro:1989:TCB, author = "U. Solitro", title = "A typed calculus based on a fragment of linear logic", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "333--342", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic)", corpsource = "Dipartimento di Scienze dell'Inf., Milano Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "canonical proof representation; Church--Rosser properties; cut-elimination; deduction system; formal logic; linear logic; multiplicative second order subsystem; negation; nu -calculus; strong normalization; typed calculus", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Gafni:1989:SEC, author = "E. Gafni and J. Naor and P. Ragde", title = "On separating the {EREW} and {CREW PRAM} models", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "343--346", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "computational complexity; CREW PRAM; decidability; decision tree problem; EREW PRAM; parallel processing; partial function; search problems; Selection Problem", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Rupert:1989:CRF, author = "C. P. Rupert", title = "Comment on a remark of Forys", journal = j-THEOR-COMP-SCI, volume = "68", number = "3", pages = "347--348", day = "12", month = nov, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:29:49 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1110 (Algebra); C1160 (Combinatorial mathematics); C4210 (Formal logic)", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "alphabetic morphisms; cardinality; factorization; fixed point languages; formal logic; group theory; rational transduction", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Vieille:1989:RQP, author = "L. Vieille", title = "Recursive query processing: the power of logic", journal = j-THEOR-COMP-SCI, volume = "69", number = "1", pages = "1--53", day = "5", month = dec, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4250 (Database theory); C6160Z (Other DBMS); C6170 (Expert systems)", corpsource = "Eur. Comput.-Ind. Res. Centre GmbH, Muenchen, West Germany", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "abstract search spaces; computational model; database management systems; database theory; deductive databases; function-free clauses; global optimization technique; knowledge based systems; logic; logic programming; logic programs; QoSaQ; query answering procedures; query languages; resolution", pubcountry = "Netherlands", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Kerisit:1989:RAL, author = "J.-M. Kerisit", title = "A relational approach to logic programming: the extended {Alexander} method", journal = j-THEOR-COMP-SCI, volume = "69", number = "1", pages = "55--68", day = "5", month = dec, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6110 (Systems analysis and programming); C6170 (Expert systems)", corpsource = "BULL CEDIAG, Louveciennes, France", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "completeness; extended Alexander method; forward chaining; logic programming; logic resolution; programming theory; relational approach; relational calculus; soundness", pubcountry = "Netherlands", treatment = "P Practical; T Theoretical or Mathematical", } @Article{Kaplan:1989:ASC, author = "S. Kaplan", title = "Algebraic specification of concurrent systems", journal = j-THEOR-COMP-SCI, volume = "69", number = "1", pages = "69--115", day = "5", month = dec, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6110 (Systems analysis and programming)", corpsource = "Dept. of Comput. Sci., Hebrew Univ., Jerusalem, Israel", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "algebraic specifications; application operator; complex specification; concurrent systems; formal specification; hierarchical layers; implementation; methodological issues; observational congruence; parallel programming; process specifications; semantics; serializability proof; stepwise development", pubcountry = "Netherlands", treatment = "B Bibliography; T Theoretical or Mathematical", } @Article{Nielson:1989:TLS, author = "F. Nielson", title = "Two-level semantics and abstract interpretation", journal = j-THEOR-COMP-SCI, volume = "69", number = "2", pages = "117--242", day = "11", month = dec, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C6150G (Diagnostic, testing, debugging and evaluating systems)", corpsource = "Dept. of Comput. Sci., Tech. Univ. of Denmark, Lyngby, Denmark", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "abstract interpretation; binding time; collecting semantics; compile-time; correctness; data flow analysis; denotational semantics; implementable analysis; most precise analysis; partial evaluation; program analysis; program verification; run-time; static semantics", pubcountry = "Netherlands", treatment = "B Bibliography; P Practical; T Theoretical or Mathematical", } @Article{Felleisen:1989:STS, author = "M. Felleisen and D. P. Friedman", title = "A syntactic theory of sequential state", journal = j-THEOR-COMP-SCI, volume = "69", number = "3", pages = "243--287", day = "18", month = dec, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Comput. Sci., Rice Univ., Houston, TX, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "assignment statement; consistency; equational lambda -calculus-theory; functionally oriented programming languages; imperative-functional programs; programming languages; programming theory; reasoning; sequential state; side-effects; standardization theorems; state variables; syntactic proof system; syntactic theory; theorem proving", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Falaschi:1989:DMO, author = "M. Falaschi and G. Levi and C. Palamidessi and M. Martelli", title = "Declarative modeling of the operational behavior of logic languages", journal = j-THEOR-COMP-SCI, volume = "69", number = "3", pages = "289--318", day = "18", month = dec, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C4210 (Formal logic); C4240 (Programming and algorithm theory)", corpsource = "Dipartimento di Inf., Pisa Univ., Italy", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "completeness; computational linguistics; computed answer substitutions; declarative semantics; fixpoint characterization; Herbrand model semantics; interpretations; logic languages; logic programming; logic programs; non-ground atoms; operational behavior; programming theory; SLD-resolution; soundness", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Baker:1989:GPA, author = "K. A. Baker and G. F. McNulty and W. Taylor", title = "Growth problems for avoidable words", journal = j-THEOR-COMP-SCI, volume = "69", number = "3", pages = "319--345", day = "18", month = dec, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Sat Nov 22 13:24:22 MST 1997", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4210 (Formal logic)", corpsource = "Dept. of Math., California Univ., Los Angeles, CA, USA", fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", keywords = "alphabet size; avoidable words; existence; formal languages; free semigroups; group theory; growth problems; homomorphism; polynomial bound; square-free words", pubcountry = "Netherlands", treatment = "T Theoretical or Mathematical", } @Article{Chrobak:2003:EFA, author = "Marek Chrobak", title = "Errata to: {``Finite Automata and Unary Languages''}: {[Theoret. Comput. Sci. 47 (1986) 149--158]}", journal = j-THEOR-COMP-SCI, volume = "302", number = "1--3", pages = "497--498", day = "13", month = jun, year = "2003", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Wed Nov 5 08:45:40 MST 2003", bibsource = "http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", note = "See \cite{Chrobak:1986:FAU}.", acknowledgement = ack-nhfb, fjournal = "Theoretical Computer Science", journal-URL = "http://www.sciencedirect.com/science/journal/03043975/", } %%% ==================================================================== %%% Cross-referenced entries must come last: @Proceedings{Gruska:1988:ISM, editor = "Josef Gruska", booktitle = "International symposium on mathematical foundations of computer science, {MFCS} '86", title = "International symposium on mathematical foundations of computer science, {MFCS} '86", volume = "57(1)", publisher = pub-NH, address = pub-NH:adr, pages = "3--159", year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Fri Nov 21 19:02:53 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", series = j-THEOR-COMP-SCI, acknowledgement = ack-nhfb, classification = "714; 721; 723; 921", conference = "International Symposium on Mathematical Foundations of Computer Science, MFCS '86", conferenceyear = "1988", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Complexity; Computer Metatheory; Computer Programming --- Algorithms; Computer Systems, Digital --- Parallel Processing; Integrated Circuits, vlsi; Iterative Arrays; Mathematical Techniques; Ordered Trees; Probabilistic Automata; Shortest Common Superstrings", meetingaddress = "Bratislava, Czech", meetingdate = "Aug 25--29 1986", meetingdate2 = "08/25--29/86", } @Proceedings{Kott:1988:TIC, editor = "Laurent Kott", booktitle = "{Thirteenth international colloquium on automata, languages and programming}", title = "{Thirteenth international colloquium on automata, languages and programming}", volume = "58(1--3)", publisher = pub-NH, address = pub-NH:adr, pages = "3--397", month = jun, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Fri Nov 21 19:02:53 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", series = j-THEOR-COMP-SCI, acknowledgement = ack-nhfb, classification = "721; 723; 921", conference = "Thirteenth International Colloquium on Automata, Languages and Programming", conferenceyear = "1988", journalabr = "Theor Comput Sci", keywords = "Automata Theory--Formal Languages; Complexity; Computer Metatheory; Computer Programming Languages--Theory; Computer Programming--Algorithms; Concurrent Programming; Data Processing--Data Structures; Database Access; Distributed Computing; Mathematical Techniques--Graph Theory; Parallel Algorithms", meetingaddress = "Rennes, Fr", meetingdate = "Jul 1986", meetingdate2 = "07/86", } @Proceedings{Levi:1988:IJC, editor = "Georgio Levi and Ugo Montanari", booktitle = "International joint conference on theory and practice of software development --- {TAPSOFT} '87", title = "International joint conference on theory and practice of software development --- {TAPSOFT} '87", volume = "59(1--2)", publisher = pub-NH, address = pub-NH:adr, pages = "3--209", month = jul, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Fri Nov 21 19:02:53 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", series = j-THEOR-COMP-SCI, acknowledgement = ack-nhfb, classification = "723", conference = "International Joint Conference on Theory and Practice of Software Development --- TAPSOFT '87", conferenceyear = "1988", journalabr = "Theor Comput Sci", keywords = "Computer Metatheory; Computer Programming Languages--Theory; Computer Programming--Theory; Computer Software; Concurrency; Linear Abstract Machine; Logic Programs; Temporal Logic; Theory; Unification", meetingaddress = "Pisa, Italy", meetingdate = "Mar 23--27 1987", meetingdate2 = "03/23--27/87", sponsor = "Univ di Pisa, Pisa, Italy; IEI-CNR; CNUCE-CNR; EATS; AICA", } @Proceedings{Ausiello:1988:SPP, editor = "Giorgio Ausiello", booktitle = "Selected papers presented at the first international conference on database theory", title = "Selected papers presented at the first international conference on database theory", volume = "62(1--2)", publisher = pub-NH, address = pub-NH:adr, pages = "3--233", month = dec, year = "1988", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Fri Nov 21 19:02:53 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", series = j-THEOR-COMP-SCI, acknowledgement = ack-nhfb, classification = "721; 723", conference = "Selected Papers presented at the First International Conference on Database Theory", conferenceyear = "1988", journalabr = "Theor Comput Sci", keywords = "Artificial Intelligence; Automata Theory; bcnf Database Schemes; Computer Metatheory--Formal Logic; Computer Programming--Algorithms; Data Processing--Data Structures; Database Systems; Hierarchical Database Objects; Multivalued Dependencies; Nested Transactions; Recursive Logic Queries; Theory", meetingaddress = "Rome, Italy", meetingdate = "Sep 1986", meetingdate2 = "09/86", sponsor = "European Assoc for Theoretical Computer Science", } @Proceedings{Liardet:1989:CAC, editor = "P. Liardet and G. Rauzy", booktitle = "{Conference on Arithmetics and Coding Systems}", title = "{Conference on Arithmetics and Coding Systems}", volume = "65(2)", publisher = pub-NH, address = pub-NH:adr, pages = "123--270", month = jun, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Fri Nov 21 19:02:53 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", series = j-THEOR-COMP-SCI, acknowledgement = ack-nhfb, classification = "721; 723; 921; 922", conference = "Conference on Arithmetics and Coding Systems", conferenceyear = "1989", journalabr = "Theor Comput Sci", keywords = "Arithmetic; Automata Theory; Codes, Symbolic; Computer Metatheory; Euler Identities; Mathematical Techniques--Number Theory; Probability; Rational Functions; Sequences; Sofic Systems", meetingaddress = "Marseille, Fr", meetingdate = "Jun 9--13 1987", meetingdate2 = "06/09--13/87", } @Proceedings{Ottmann:1989:ICA, editor = "Thomas Ottmann", booktitle = "14th International Colloquium on Automata, Languages and Programming", title = "14th International Colloquium on Automata, Languages and Programming", volume = "66(2)", publisher = pub-NH, address = pub-NH:adr, pages = "117--232", month = aug, year = "1989", CODEN = "TCSCDI", ISSN = "0304-3975 (print), 1879-2294 (electronic)", ISSN-L = "0304-3975", bibdate = "Fri Nov 21 19:02:53 MST 1997", bibsource = "Compendex database; http://www.math.utah.edu/pub/tex/bib/tcs1985.bib", series = j-THEOR-COMP-SCI, acknowledgement = ack-nhfb, classification = "721; 723; 921", conference = "14th International Colloquium on Automata, Languages and Programming", conferenceyear = "1989", journalabr = "Theor Comput Sci", keywords = "Automata Theory; Binary Search Trees; Computer Metatheory; Computer Programming; Computer Systems, Digital--Parallel Processing; Concurrent Processes; Data Processing--Data Structures; Mathematical Techniques; Model Theory of Knowledge; Shortest Tours; Sorting of Sums", meetingaddress = "Karlsruhe, West Ger", meetingdate = "Jun 1987", meetingdate2 = "06/87", }