Copy Link
Add to Bookmark
Report
AIList Digest Volume 2 Issue 033
AIList Digest Monday, 19 Mar 1984 Volume 2 : Issue 33
Today's Topics:
AI Books - Synapse Books,
Bindings - Tong Address,
Mathematics - Topology of Plane and Sphere,
Expert Systems - Explanatory Capability,
Automata - Characterizing Automata from I/O Pairs,
Conferences - ACM Conference & CSCSI 84 Preliminary Program
----------------------------------------------------------------------
Date: Sun 18 Mar 84 21:53:54-PST
From: Ken Laws <Laws@SRI-AI.ARPA>
Subject: Synapse Books
I found a copy of the 1982 Synapse Books catalog. The address is
Synapse Information Resources, Inc.
912 Cherry Lane
Vestal, New York 13850
The catalog covers AI, automation, biomedical engineering, CAD/CAM,
robotics, instrumentation, cybernetics, and computer technology.
Prices seem to be the publishers' suggested prices, although I only
checked a couple. The selection is impressive.
-- Ken Laws
------------------------------
Date: Fri 16 Mar 84 21:31:54-PST
From: Tom Dietterich <DIETTERICH@SUMEX-AIM.ARPA>
Subject: Tong Address
Chris Tong can be reached at TONG@SUMEX or TONG@PARC. Mailing address:
Chris Tong, Xerox Palo Alto Research Center, 3333 Coyote Hill Rd., Palo
Alto, CA
--Tom
[Jeff Rosenschein@SUMEX reports that Chris hasn't used his Sumex
login for quite a while. Richard Treitel@SUMEX suggested a
TONG@PARC-MAXC address. -- KIL]
------------------------------
Date: 18 Mar 84 20:45:24 PST (Sun)
From: Tod Levitt <levitt@aids-unix>
Subject: more four color junk
From: ihnp4!houxm!hou2g!stekas @ Ucb-Vax
A plane and sphere are NOT topologically equivalent, a
sphere has an additional point."
More to the "point", the topological invariants of the plane and the
(two-) sphere are different, which is the definition of being
topologically inequivalent. For instance, the plane is contractible to a
point while the sphere is not; the plane is non-compact, while the
sphere is compact; the homotopy and homology groups of the plane are
trivial, while those of the sphere are not.
A more general form of the four-color theorem asks the question: for a
given (n-dimensional) shape (and its topological equivalents) what is
the fewest number of colors needed to color any map drawn on the
shape.
------------------------------
Date: 9 Mar 84 8:58:08-PST (Fri)
From: decvax!linus!utzoo!watmath!deepthot!julian @ Ucb-Vax
Subject: Re: computer ECG, FDA testing of AI programs
Article-I.D.: deepthot.212
As a matter of human engineering, I think "expert" programs for
practical use must be prepared to explain the reasoning followed
when they present recommendations. Computer people ought to be
well aware of the need to provide adequate auditing and verification
of program function, even if the naive users don't know this.
The last thing we need is 'expert' computers that cannot be
questioned. I think Weizenbaum had a valid point when he wrote
about programs that no one understood. And I would be unhappy
to see further spread of computer systems that the human users cannot
feel themselves to be in charge of, especially when the programs
are called 'intelligent' and the technology for answering these
questions about the reasoning processes is fairly well established.
Julian Davies
------------------------------
Date: 16 Mar 84 13:28:54 PST (Friday)
From: Bruce Hamilton <Hamilton.ES@PARC-MAXC.ARPA>
Reply-to: Hamilton.ES@PARC-MAXC.ARPA
Subject: Characterizing automata from I/O pairs
The following recent msgs should be of interest to this list, and
hopefully will stimulate some good discussion. --Bruce
----------
From: Ron Newman <Newman.es>
The following letter to the editor was published in Softalk of March,
1984:
I have come into possession recently of a program called Microlisp. I
understand that it has been around for some time, so maybe someone out
there knows something about it. I cannot get it to do anything but
print numbers I type in or print the word "nil". How do I make it do
anything else? Can you give me an example of something useful that I
might be able to do with it?
[...]
----------
From: Bruce Hamilton <Hamilton.ES>
Actually, the letter implies a serious question, related to trying to
communicate with other forms of intelligent life: is there an approach,
to giving inputs and observing output to an unknown program, which is in
some sense optimal; i.e. leads to a complete characterization of input -
output pairs in the shortest possible time?
--Bruce
----------
From: VanDuyn.Henr
One question is would intelligent life aquire (a.k.a. pirate or steal) a
piece of software without the documentation.
On the serious side, what you suggest reminds me of programs that
attempt to write programs by examining a small set of the input output
pairs. At first sample pairs are fed to the program then the program
begins generating its own sample pairs to build and validate a
hypothesis. I read an article about this is the ACM TOPLAS journal
about 3 years ago...
Mitch
----------
From: stolfi.pa
"Is there an approach, to giving inputs and observing output to an
unknown program, which is in some sense optimal; i.e. leads to a
complete characterization of input - output pairs in the shortest
possible time?"
I am interested in that question, too. Do you know of any work in that
area? I have given some thought to it, but made only trivial progress.
To be more definite, consider deterministic finite machine with N
internal states, and {0,1} as its input and output alphabets. The goal
is to determine the structure of the machine (i.e., its transition and
output functions) by feeding it a sequence of zeros and ones, and
observing the bits that come out of it. Nothing is known about the
structure of the machine. In particular, it is not known how to reset
the machine to its initial state, and not even whether it is possible to
do so (i.e., whether the machine is strongly connected). Then
(1) at best, you will be able to know the structure of a single strongly
connected component of the machine, and have only a vague knowledge of
the path that led from the initial state to that component. Moreover,
your answer will be determined only up to automaton equivalence. (In
other words, studing the behavior of something will only tell you how
that thing behaves, not how it is built)
(2) if you have an upper bound on the number N of internal states, I
believe you can always deduce the structure of the machine, subject to
the caveats in (1), after feeding it some finite number f(N) of bits.
However, I have no algorithm for generating the required input and
analyzing the output, and I have no idea on how big f(N) is. O(N) is a
trivial lower bound. Any upper bounds? Can it be more than O(2^N)?.
(3) In any case, note that a finite machine built from n boolean gates
may have an exponential number of states (For example, a counter with n
flip-flops has 2^n states). Therefore, even if you know that a program
has a single 16-bit integer variable and a 16-bit program counter, you
may need to feed it few billion bits to know what it does.
(4) if you do not have an upper bound on N, there is no way you can
deduce it by experiment, or answer categorically any interesting
questions about the structure of the machine. For example, suppose you
have put in 999,999,999 bits, and you got that many zeros out. You still
don't know whether the machine is a trivial one-state, constant-output
gadget, or whether it is a billion-state monster that ignores its inputs
and simply puts out a '1' every billionth transition. Note however, that
you may still give answers of the form "either this machine has more
than X states, or it is equivalent to the following automaton: ..."
In anthropomorphic terms, (4) says that it is impossible to distinguish
a genuinely dumb being from a very intelligent one that is just playing
dumb. Point (3) makes me wonder if the goal and method of psychology --
to understand the human mind by studying how it behaves -- is a sensible
proposition after all..
jorge
[There have, of course, been investigations of pattern recognition
techniques for infering Markov or finite-state grammars. The
PURR-PUSS system is one that comes to mind. Applications not
mentioned above include cryptography, data compression, fault
diagnosis, and prediction (e.g., stock market directions). Martin
Gardner had a fun SciAm column ~13 years ago about building an
automaton for predicting the operator's heads/tails choices. Gardner
also popularized the game of Elusius, in which players try to
elucidate laws of nature by pulsing the system with test cases.
The Mastermind game is related, although you are given information
about the internal state as part of the output. Several AI
researchers have used automata theory for investigating hypothesis
formation and learning. -- KIL]
------------------------------
Date: Tue 13 Mar 84 12:46:54-EST
From: Neena Lyall <LYALL@MIT-XX.ARPA>
Subject: ACM Conference
[Forwarded from the MIT bboard by Laws@SRI-AI.]
"INTEGRATING THE INFORMATION WORKPLACE THE KEY TO PRODUCTIVITY"
ACM NORTHEAST REGIONAL CONFERENCE
19 - 21 March, l984
University of Lowell
Lowell, MA
Special Student/Faculty Rate $20
KEYNOTE SPEAKERS ARE:
Monday George McQuilken, Chairman, Spartacus Computer Inc., "Mainframe
Technology in Integrated Systems"
Tuesday Carl Wolf, President, Interactive Data Corp., "Bridging the
Mainframe to Micro Gap"
Wednesday Mitch Kapor, President, Lotus Development Corp., "Micro
Technology in Integrated Systems"
CLOSING PLENARY SESSION:
Thomas F. Gannon (5th Generation, DEC)
Maurice V. Wilkes (Corporate Research, DEC)
Frederick G. Withington (V.P., ADL), "Integrating the Pieces
- Computing in the 90's"
THE TRACK CHAIRMEN ARE:
Applications Technology Track
Dr. David Prerau, Principal of Technical Staff, GTE
Laboratories, Inc.
Artificial Intelligence Track
Jeffrey Hill, Manager of Development, Artificial Intelligence
Corp.
Dr. David Prerau, Principal of Technical Staff, GTE
Laboratories, Inc.
CAD/CAM & Robotics Track
Cary Bullock, V.P., Engineering & Operations, Xenergy Corp.
Computer Tools & Techniques Track
David Hill, Director, Data Systems & Communications
Database Management Track
Michael Stadelmann, Manager of Development, GE/MIMS Systems
Decision Support Systems Track
David Kahn, Manager, Decision Support Systems, Wang
Laboratories
Networking & Data Communications Track
Dr. Barry Horowitz, V.P. Bedford Operations, (Formerly
Technical Director, Strategic Systems), MITRE Corp.
Office Automation Track
Nancy Heaton, Manager of Office Automation, Wang Laboratories
Personal Computing Track
Michael Rohrbach, International Market Resources
THERE ARE TWO TUTORIALS WHICH RUN IN PARALLEL WITH THESE SESSIONS:
Artificial Intelligence Tutorial (3 days)
Dr. Eugene Charniak, Brown University.
AI and its newest developments, emphasizing expert systems and
knowledge-based systems.
Networking Technology Tutorial (3 days)
Stewart Wecker, Pres. Technology Concepts.
Local area and other network, including theory and
manufacturers' current products (IBM's SNA, DECNET and LAN
products)
For detailed information see bulletin board outside Room 515, 545 Technology
Square, Cambridge or call either 617/444-5222: Box C, or 617/271-3268: Shim
Berkovits.
------------------------------
Date: 8 Mar 84 10:34:06-PST (Thu)
From: harpo!utah-cs!sask!utcsrgv!utai!tsotsos @ Ucb-Vax
Subject: CSCSI 84 Preliminary Program
Article-I.D.: utai.129
The preliminary program for the Fifth National Conference of the Canadian
Society for Computational Studies of Intelligence follows.
Registration or other information may be obtained from:
Prof. Michael Bauer,
Local Arrangements Chair, CSCSCI/SCEIO-84
Dept. of Computer Science,
University of Western Ontario
London, Ontario, Canada
N6A 5B7
(519)-679-6048
Due to unfortunate circumstances beyond our control, there has been a
date change for the conference which has not been reflected in
several current announcements. The correct date is May 15- 17, 1984.
CSCSI-84
Canadian Society for
Computational Studies of Intelligence
Fifth National Conference
May 15 - 17
University of Western Ontario
London, Ontario, Canada
PRELIMINARY PROGRAM
Tuesday Morning, May 15
8:30 - 8:40 Introduction and Welcome
Session 1 - Natural Language
8:40 - 9:40 Martin Kay (XEROX PARC) - Invited Lecture
9:40 - 10:10 "A Theory of Discourse Coherence for Argument Understanding"
Robin Cohen (U of Toronto) (Long paper)
10:10 - 10:30 "Scalar Implicature and Indirect Responses in
Question-Answering"
Julia Hirschberg (U of Pennsylvania) (Short paper)
10:30 - 10:40 BREAK
10:40 - 11:00 "Generating Non-Direct Answers by Computing Presuppositions
of Answers, Not of Questions or Mind your P's, not your Q's"
Robert Mercer, Richard Rosenberg (U of British Columbia)
(Short paper)
11:00 - 11:20 "Good Answers to Bad Questions: Goal Deduction in Expert
Advice-Giving"
Martha Pollack (U of Pennsylvania) (Short paper)
Session 2 - Cognitive Modelling and Problem Solving
11:20 - 11:40 "Using Spreading Activation to Identify Relevant Help"
Adele Howe (ITT), Timothy Finin (U of Pennsylvania)
(Short paper)
11:40 - 12:00 "Managing Time Maps"
Thomas Dean (Yale) (Short paper)
12:00 - 1:30 LUNCH
Tuesday Afternoon, May 15
Panel Discussion
1:30 - 2:45 "The Artificial Intelligence, Robotics and Society Program"
of the Canadian Institute for Advanced Research
Panel members : Zenon Pylyshyn - moderator (U of Western Ontario)
Raymond Reiter - coordinator for the University of British Columbia
John Mylopoulos - coordinator for the University of Toronto
Steven Zucker - coordinator for McGill University
Nick Cercone - president CSCSI/SCEIO
Session 3 - Computer Vision I
2:45 - 3:45 "Optical Phenomena in Computer Vision"
Steven Shafer (CMU) - Invited Lecture
3:45 - 4:00 BREAK
4:00 - 4:30 "Procedural Adequacy in an Image Understanding System"
Jay Glicksman (Texas Instruments) (Long paper)
4:30 - 5:00 "The Local Structure of Image Discontinuities in One Dimension"
Yvan Leclerc (McGill) (Long paper)
5:00 - 5:30 "Receptive Fields and the Reconstruction of Visual Informatiom"
Steven Zucker (McGill) (Long paper)
Wednesday Morning, May 16
Session 4 - Robotics
8:30 - 9:30 "Robotic Manipulation"
Matthew Mason (CMU) - Invited Lecture
9:30 - 10:00 "Trajectory Planning Problems, I: Determining Velocity
Along a Fixed Path"
Kamal Kant (McGill) (Long paper)
10:00 - 10:20 "Interpreting Range Data for a Mobile Robot"
Stan Letovsky (Yale) (Short paper)
10:20 - 10:45 BREAK
Panel Discussion
10:45 - 12:00 "What is a valid methodology for judging the quality
of AI research?"
Panel Moderator : Alan Mackworth (U of British Columbia)
12:00 - 1:30 LUNCH
Wednesday Afternoon, May 16
Session 5 - Learning
1:30 - 2:00 "The Use of Causal Explanations in Learning"
David Atkinson, Steven Salzberg (Yale) (Long paper)
2:00 - 2:30 "Experiments in the Automatic Discovery of Declarative
and Procedural Data Structure Concepts"
Mostafa Aref, Gordon McCalla (U of Saskatchewan) (Long paper)
2:30 - 3:00 "Theory Formation and Conjectural Knowledge in Knowledge Bases"
James Delgrande (U of Toronto) (Long paper)
3:00 - 3:20 "Conceptual Clustering as Discrimination Learning"
Pat Langley, Stephanie Sage (CMU) (Short paper)
3:20 - 3:40 BREAK
3:40 - 4:00 "Some Issues in Training Learning Systems and an
Autonomous Design"
David Coles, Larry Rendell (U of Guelph) (Short paper)
4:00 - 4:20 "Inductive Learning of Phonetic Rules for Automatic
Speech Recognition"
Renato de Mori (Concordia University)
Michel Gilloux (Centre National d'Etudes des
Telecommunications, France)
(Short paper)
4:20 - 4:30 BREAK
Session 6 - Computer Vision II
4:30 - 5:00 "Applying Temporal Constraints to the Problem of Stereopsis
of Time-Varying Imagery"
Michael Jenkin (U of Toronto) (Long paper)
5:00 - 5:30 "Scale-Based Descriptions of Planar Curves"
Alan Mackworth, Farzin Mokhtarian
(U of British Columbia) (Long paper)
Wednesday Evening, May 16 - BANQUET
Thursday Morning, May 17
Session 7 - Logic Programming
8:30 - 9:30 J. Alan Robinson (Syracuse U) - Invited Lecture
9:30 - 9:50 "Implementing PROGRAPH in Prolog: An Overview of the
Interpreter and Graphical Interface"
P. Cox, T. Pietrzykowski (Acadia U) (Short paper)
9:50 - 10:10 "Making 'Clausal' Theorem Provers 'Non-Clausal'"
David Poole (U of Waterloo) (Short paper)
10:10 - 10:30 "Logic as Interaction Language"
Martin van Emden (U of Waterloo) (Short paper)
10:30 - 10:45 BREAK
10:45 - 12:00
Report of the CSCSI/SCEIO Survey on AI Research in Canada
Nick Cercone - President CSCSI/SCEIO
Gordon McCalla - Vice-President CSCSI/SCEIO
12:00 - 1:00 LUNCH
Thursday Afternoon, May 17
Session 8 - Expert Systems and Applications
1:00 - 2:00 Ramesh Patil (MIT) - Invited Lecture
2:00 - 2:20 "ROG-O-MATIC: A Belligerent Expert System"
Michael Mauldin, Guy Jacobson, Andrew Appel, Leonard Hamey (CMU)
(Short paper)
2:20 - 2:40 "An Explanation System for Frame-Based Knowledge Organized
Along Multiple Dimensions"
Ron Gershon, Yawar Ali, Michael Jenkin (U of Toronto)
(Short paper)
2:40 - 3:00 "Qualitative Sensitivity Analysis: A New Approach to Expert
System Plan Justification"
Stephen Cross (Air Force Institute of Technology) (Short paper)
3:00 - 3:20 BREAK
Session 9 - Knowledge Representation
3:20 - 4:20 "A Fundamental Trade-off in Knowledge Representation
and Reasoning"
Hector Levesque (Fairchild R&D) Invited Lecture
4:20 - 4:50 "Representing Control Strategies Using Reflection"
Bryan Kramer (U of Toronto) (Long paper)
4:50 - 5:10 "Knowledge Base Design for an Operating System
Expert Consusltant"
Stephen Hegner (U of Vermont),
Robert Douglass (Los Alamos National Laboratory) (Short paper)
5:10 - 5:30 "Steps Towards a Theory of Exceptions"
James Delgrande (U of Toronto) (Short paper)
5:30 - 5:45 CLOSING REMARKS
------------------------------
End of AIList Digest
********************
