Copy Link
Add to Bookmark
Report
IRList Digest Volume 2 Number 46
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 <RAGHAVAN@UREGINA1.bitnet>
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 <vardi@navajo.stanford.edu>
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
********************
