From vtisr1!irlistrq Fri Sep 19 09:00:53 1986 Date: Fri, 19 Sep 86 09:00:45 edt From: vtisr1!irlistrq To: fox Subject: IRList Digest V2 #46 Status: R IRList Digest Friday, 19 September 1986 Volume 2 : Issue 46 Today's Topics: Query - How to use BITSERVE to get old issues of IRList Announcement - ACM Conf. on Office Information Systems info. Abstracts - More from latest issue of ACM SIGIR Forum, Part 3 Call for Papers - 2nd Annual Symp. on Logic Programming in Comp. Sci. News addresses are ARPANET: fox%vt@csnet-relay.arpa BITNET: foxea@vtvax3.bitnet CSNET: fox@vt UUCPNET: seismo!vtisr1!irlistrq ---------------------------------------------------------------------- Date: Sun, 14 Sep 86 18:37:37 edt From: Michael_DAlessandro%wayne-mts%umich-mts.mailnet@MIT-MULTICS.ARPA Subject: BITSERVE use Status: RO Ed, ... Also, could you give me instructions how I can get at archived issues of IRList that are on the BITSERVE machine? I'm afraid I don't know much about this machine - only that it is some sort of file server on BITNET that stores old issues of various net digests. I'd like to get indexes of the messages in old IRList digests, and then be able to pull out of the file server the messages that interest me. Can this be done? Michael [Note: there are no indexes prepared by me of old IRList digests; would you like to volunteer? It should not be hard, given the "Today's Topics" section in each issue. As mentioned in the welcome message that all IRList readers should have received (let me know if you want it again), I keep an archive of old issues and there are some others, such as one that people can FTP from if they have that capability. The archive for BITNET users is a Spires database accessible through DATABASE@BITNIC, so you can search for interesting items. See discussion by J.H. Coombs in IRList V2#16, and by me in V2#1 -- send a msg with 3 lines as below to database@bitnic.bitnet help help arpanet help design to get instructions on how it all works. Good luck, Ed] ------------------------------ Date: Wed, 17 Sep 86 00:36:56 edt From: rba@LAFITE.BELLCORE.COM Subject: ACM Conf. on Office Inf. Systems Subject: COIS-86 ACM CONFERENCE ON OFFICE INFORMATION SYSTEMS October 6-8, 1968, Providence, R.I. Conference Chair: Carl Hewitt, MIT Program Chair: Stan Zdonik, Brown University Keynote Speaker: J.C.R. Licklider, MIT Distinguished Lecturer: A. van Dam, Brown University COIS is a major research conference on the design and use of computing systems for professional and knowledge workers. At this meeting, sessions and panels emphasize AI and organizational models of offices as sites for distributed information processing. Other themes include user interfaces, graphics, group cooperation, and object-oriented systems. For more information, call the Conference Registrar at Brown U. (401-813-1839), or send electronic mail to mhf@brown.CSNET. ------------------------------ Date: Wed, 23 Jul 1986 13:06 CST From: Vijay V. Raghavan Subject: More SIGIR FORUM Abstracts [Part 3 of 3 - Ed] [Note: Members of ACM SIGIR should have received the spring/summer Forum, and can find these on pages 27-29. The earlier parts have appeared in machine readable form in previous issues of IRList. - Ed] ABSTRACTS (Selected from recent issues of journals) 13. INCREMENTAL STRING MATCHING Bertrand Meyer Department of Computer Science, University of California, Santa Barbara, CA 93106, USA The problem studied in this paper is to search a given text for occurrences of certain strings, in the particular case where the set of strings may change as the search proceeds. A well-known algorithm by Aho and Corasick applies to the simpler case when the set of strings is known beforehand and does not change. This algorithm builds a transition diagram (finite automation) from the strings, and uses it as a guide to traverse the text. The search can then be done in linear time. We show how this algorithm can be modified to allow incremental diagram construction, so that new keywords may be entered at any time during the search. The incremental algorithm presented essentially retains the time and space complexities of the non-incremental one. (INFORMATION PROCESSING LETTERS 21 (1985) 219-227) 14. A SYSTOLIC ARRAY FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM Yves Robert and Maurice Tchuente Centre National de a la Recherche Scientifique, Laboratoire TIM3, Institut IMAG, BP 68, 38402 Saint Martin d'Heres Cedex, France We introduce a linear systolic array for the Longest Common Subsequence (LCS, for short) problem. We first present an array of m identical cells which computes the length of an LCS of two strings of length m and n, respectively, in linear time (i.e. in time proportional to m + n). Then we show that, by extending any cell with the systolic stack introduced by Guibas and Liang (1982), a new array can be designed to recover an LCS in linear time. (INFORMATION PROCESSING LETTERS 21 (1985) 191-198) 15. SEARCHING UNINDEXED AND NONUNIFORMLY GENERATED FILE IN log log N TIME Dan E. Willard State University of New York, Albany, NY 12222 The first algorithm that searches unindexed and nonuniformity distributed ordered files in log log N expected time is presented in this paper. Our analysis rests on a synthesis of concepts from the literature on interpolation search and on the method of regula faisi in numerical analysis. (SIAM J. COMPUT, Vol 14, No. 4, pp. 1013-1029, November 1985) 16. DATA STRUCTURES FOR ON-LINE UPDATING OF MINIMUM SPANNING TREES, WITH APPLICATIONS Greg N. Frederickson Computer Science Purdue University West Lafayette, Indiana 47907 Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are shown to take O(SQRT(m)) time, where m is the number of edges in the graph. For the case of a planar graph, a data structure is presented which supports an update time of O((log m)*(log m)). These structures contribute to improved solutions for the on-line connected components problem and the problem of generating the K smallest spanning trees. (SIAM J. COMPUT Vol. 14, No. 4, pp. 781-798, November 1985) 17. THE BOYER-MOORE-GALIL STRING SEARCHING STRATEGIES REVISITED Alberto Apostolico Computer Science, Purdue University West Lafayette, Indiana 47907 Raffaele Giancarlo Dipartimento di informatica ed Applicazioni The University of Salerno 184100 Salerno, Italy Based on the Boyer-Moore-Galil approach, a new algorithm is proposed which requires a number of character comparisons bounded by 2n, regardless of the number of occurrences of the pattern in the textstring. Preprocessing is only slightly more involved and still requires a time linear in the pattern size. (SIAM J. COMPUT, Vol 15, No. 1, pp. 98-105, February 1986) 18. A NATURAL LANGUAGE INFORMATION RETRIEVAL SYSTEM WITH EXTENSIONS TOWARDS FUZZY REASONING Leonard Bolc Institute for Informatics, Warsaw University, PKiN, pok, 850, 00-901 Warszawa, Poland Adam Kowalski Institute of Computer Science, Polish Academy of Sciences, 00-901 Warszawa, P.O. Box 22, Poland Malgorzata Kozlowska Institute for Informatics, Warsaw University, PKiN, pok 850, 00-901 Warszawa, Poland Tomasz Strazalkowski Department of Computing Science, Simon Fraser University, Burnaby, B.C. Canada V5A 1S6 For the last few years we have observed a growing interest among researchers about how to make computers behave "intelligently". The field of computer science has gained a substantial level of development especially in the field of so-called expert systems. This particular area has also obtained relatively wide approval and applicability. This paper describes an experimental version of the conversational natural language information retrieval system which is currently under investigation at the Institute for Informatics of Warsaw University. This system deals with gastroenterology, a branch of internal medicine. The system's purpose is to provide physicians and hospital personnel with information which may be consulted during the diagnotic process. The system first acquires a base knowledge in the field which is presented to it in the form of a comprehensive natural language text. From this point on knowledge can be retrieved and/or updated in conversational manner. The system has a modular structure and its most important parts are the natural language processor and the reasoning module based on procedural deduction. The deduction process is realized through the mechanisms known as fuzzy logic incorporated in the FUZZY programming language. The system has been designed in close co-operation with specialists in medical science, and implemented on an IBM 370/148 at Warsaw University. (INT. J. MAN-MACHINE STUDIES (1985) 23, 335-367) ------------------------------ Date: Tue, 9 Sep 86 21:34:46 PDT From: Moshe Vardi Subject: Call for Papers [Extracted from: PROLOG Digest Thursday, 11 Sep 1986 V.4 #48 - Ed] CALL FOR PAPERS SECOND ANNUAL SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE 22 - 25 June 1987 Cornell University, Ithaca, New York, USA THE SYMPOSIUM will cover a wide range of theoretical and practi- cal issues in Computer Science that relate to logic in a broad sense, including algebraic and topological approaches. Suggested (but not exclusive) topics of interest include: abstract data types, computer theorem proving, verification, con- currency, type theory and constructi ve mathematics, data base theory, foundations of logic programming, program logics and se- mantics, knowledge and belief, software specifications, logic- based programming languages, logic in complexity theory. Organizing Committee K. Barwise E. Engeler A. Meyer W. Bledsoe J. Goguen R. Parikh A. Chandra (chair) D. Kozen G. Plotkin E. Dijkstra Z. Manna D. Scott Program Committee S. Brookes D. Gries (chair) J.-P. Jouannaud A. Nerode L. Cardelli J. Goguen R. Ladner G. Plotkin R. Constable Y. Gurevich V. Lifschitz A. Pnueli M. Fitting D. Harel G. Longo P. Scott PAPER SUBMISSION. Authors should send 16 copies of a detailed abstract (not a full paper) by 9 DECEMBER 1986 to the program chairman: David Gries -- LICS (607) 255-9207 Department of Computer Science gries@gvax.cs.cornell.edu Cornell University Ithaca, New York 14853 Abstracts must be clearly written and provide sufficient detail to allow the program committee to assess the merits of the paper. References and comparisons with related work should be included where appropriate. Abstracts must be no more than 2500 words. Late abstracts or abstracts departing significantly from these guidelines run a high risk of not being considered. If a copier is not available to the author, a single copy of the abstract will be accepted. Authors will be notified of acceptance or rejection by 30 JANUARY 1987. Accepted papers, typed on special forms for inclusion in the symposium proceedings, will be due 30 MARCH 1987. The symposium is sponsored by the IEEE Computer Society, Techni- cal Committee on Mathematical Foundations of Computing and Cor- nell University, in cooperation wi th ACM SIGACT, ASL, and EATCS. GENERAL CHAIRMAN LOCAL ARRANGEMENTS Ashok K. Chandra Dexter C. Kozen IBM Thomas J. Watson Research Center Dept. of Computer Science P.O. Box 218 Cornell University Yorktown Heights, New York 10598 Ithaca, New York 14853 (914) 945-1752 (607) 255-9209 ashok@ibm.com kozen@gvax.cs.cornell.edu ------------------------------ END OF IRList Digest ********************