Copy Link
Add to Bookmark
Report
AIList Digest Volume 2 Issue 035
AIList Digest Monday, 26 Mar 1984 Volume 2 : Issue 35
Today's Topics:
AI Tools - Nature of AI Computing,
Logic Programming - Inferential and Deductive Processing,
Expert Systems - VLSI Knowledge Acquisition & Explanatory Capability,
Mathematics - Four Color Theorem,
System Identification - Characterizing Automata From I/O Pairs,
Seminars - Compositional Temporal Logic & Logic Programming,
Course - Expert Systems for CAD/CAT
----------------------------------------------------------------------
Date: Thu 22 Mar 84 15:08:19-EST
From: Sal Stolfo <sal@COLUMBIA-20.ARPA>
Subject: A call for discussion
"The Numericists Meet the Symbolicists and Ask Why?"
With the recent interest in Fifth Generation Computing and Artificial
Intelligence, many scientists with backgrounds in other disparate fields are
beginning to study symbolic computation in a serious manner.
The ``parallel architectures community'' has mostly been interested in novel
computer architectures to accelerate numeric computation (usually represented
as Fortran codes). Similarly, the ``data base machine community" has been
interested in more conventional data processing (for example, large-scale data
bases). Now that the interest of these communities and others are focusing on
Artificial Intelligence computing, a question that is often asked is ``What are
the fundamental characteristics of AI computation that distinguish it from more
conventional computation"? Indeed, are there really any differences at all?
These questions have no simple answers; they can be viewed from many different
perspectives. This note is a solicitation of the AI community for cogent
discussion of this issue. We hope that all facets will be addressed including:
- Differences between the kinds of problems encountered in AI and those
considered more conventional. (A simple answer in terms of
``ill-defined'' and ``well-defined'' problems is viewed as a copout.)
- Methodological differences between AI computing and conventional
computing.
- Computer resource requirements and programming environments with
technical substantiations of the differences rather than aesthetic
preferences.
I expect to collect responses from the AI community and produce a final report
which will be made available to any interested parties.
Thank you in advance.
Salvatore J. Stolfo
Assistant Professor
Computer Science Department
Columbia University
------------------------------
Date: 24 Mar 1984 00:11:35-PST
From: hildum%brandeis.csnet@csnet-relay.arpa
Subject: Inferential and Deductive Processing using Lisp and Prolog
(This message has been sent to both the AIList and the Prolog Digest)
I am looking for some information concerning the following:
(1) The use of Prolog and Lisp for deductive and inferential processing.
(2) Standard methods of handling deductive and inferential processing
in Prolog and Lisp.
(3) Any languages similar or different to Prolog and Lisp that have been
used for deductive and inferential processing.
(4) What types of inferential and deductive processing cannot be done using
Prolog ? Using Lisp ?
Suggestions of applicable articles and research projects, as well as personal
observations would be greatly appreciated. I am attempting to get a feel for
what kinds of things can and cannot be done to handle deductive and inferen-
tial processing with existing Logic/AI programming languages.
Responses (ASAP) will be greatly appreciated. Please reply to:
hildum%brandeis.csnet@csnet-relay.csnet
I will gladly post a summary to the net if there is enough interest in
the subject.
Thank you,
David W. Hildum
US Mail: Box 1417
Brandeis University
Waltham, Massachusetts
02254
------------------------------
Date: 21 Mar 84 20:44:16-PST (Wed)
From: decvax!cwruecmp!sundar @ Ucb-Vax
Subject: Expert Systems in VLSI
Article-I.D.: cwruecmp.1113
This is only a request. Has any one documented the knowledge
acquisition techniques used for this application domain?
I conducted a few interviews with local VLSI experts and the
difficulty I had was the formulation of appropriate questions
to elicit maximum response. Any references would be appreciated.
Thanks.
Sundar Iyengar
USENET: decvax!cwruecmp!sundar
CSNET: sundar@Case
ARPANET: sundar.Case@Rand-Relay
Posted: 11:43:29 pm, Wednesday March 21, 1984.
------------------------------
Date: 21 Mar 84 9:24:14-PST (Wed)
From: harpo!ulysses!allegra!princeton!eosp1!robison @ Ucb-Vax
Subject: Re: "Explaining" expert system algorthims.
Article-I.D.: eosp1.715
References:
I think it is hopeless to demand that the algorithms
instanced by expert systems be well understood so they can be questioned.
Even when the algorithms can easily be printed, they will be hard for
any human being to comprehend, except in the most trivial systems.
Expert systems attempt to imitate one kind of human thinking, in which
what we call "judgment" plays a part. I expect that as expert systems
become more sophisticated, they will become harder and harder to judge,
just as the think-work of human beings is hard to judge for quality.
True "artificial intelligence" systems will have these problems in spades.
Please note that we have already reached the point where ordinary
procedural software is hard to judge. It's quite common to spend 18
months shaking down a moderate sized piece of software.
- Toby Robison
allegra!eosp1!robison
decvax!ittvax!eosp1!robison
princeton!eosp1!robison
------------------------------
Date: 23 Mar 84 12:52:55-PST (Fri)
From: ihnp4!houxm!hou2d!wbp @ Ucb-Vax
Subject: color junk
Article-I.D.: hou2d.225
Re: color junk
From: Wayne Pineault <hou2d!wbp>
From a homology point of view a circle and a plane are not the
same, but from the view of coloring they are the same, since you pick the
point at infinity on the plane to map inside one of the regions on the
sphere.
Also, for a long time a closed coloring formula has been known for a
sphere with any number of donut holes and mobius strips attached, as long
as it was not a sphere! If you just plugged in 0 for a sphere the answer
came out to 4, but the argument did not work for this case!!!
There is a Springer-Verlag series of mathematics, and I saw this
formula there, but I don't remember it.
Wayne Pineault
------------------------------
Date: 23 Mar 84 17:14:17-PST (Fri)
From: decvax!mcnc!ncsu!uvacs!erh @ Ucb-Vax
Subject: RE characterizing automata from I/O pairs
Article-I.D.: uvacs.1206
The question is certainly interesting and very natural. Not
surprisingly, it has been investigated in depth. As a matter of fact,
the Moore theory of experiments (which is precisely the theory of
"characterizing automata from I/O pairs") was one of the subjects
investigated in the 50's which gave impetus to introduction and study
of regular languages.
A nice little book by J.H. Conway ("Regular Algebra and Finite
Machines", Chapman and Hall, 1971) has a chapter-long summary of
results including an answer to your question about the bound on the
length of the characterizing experiment. A few paraphrases:
Def. An exact (n,m,p) machine is a Moore machine with n states, m input
symbols, and p output symbols, each output symbol being actually emitted
in some state. (Take m = p = 2 if you want arguments in terms of bits.)
Theorem. Two distinguishable states of an exact (n,m,p) machine can be
distinguished by some word of length at most n-p.
(That is, for any two distinguishable states p, q, there exists a word w
of length <= n-p such that the output corresponding to w will differ
depending on whether it is started in p or q.)
Theorem. If S is a set of at most s states of an exact (n,m,p) machine,
and some two states in S are distinguishable, then there exists a word
of length at most max( 0, n-p-s+2 ) which distinguishes some two states
in S. Moreover, this bound is best possible.
Theorem. If we are (explicitely) given an exact (n,m,p) machine whose
states are all distinguishable, and told that it is initially in one
of a set S of at most s states, then we can specify an experiment of
length at most (t-1)(n-p-(t-2)/2) where t = min( s, n-p+2 ), after
application of which the resulting state will be known (so you find
your position in the machine in case you were "lost in S"). Moreover,
the bound is best possible.
In the above an "experiment of length k" means an algorithm
which feeds input symbols depending on the observed outputs; k is
the number of symbols fed in.
The following answers your question. It is a paraphrase
of Theorems 9 & 11, pp. 12-14 of Conway's text (the original result
is due to Moore, improved slightly by Conway):
Theorem. If you know that M is a strongly connected exact (n,m,p)
machine with pairwise distinguishable states, then there is an experiment
of length at most
2n-1 2
8 m n log n
2
which tells you the structure of the machine.
Ed Howorka (erh@uvacs on CSNET)
------------------------------
Date: 22 Mar 84 1600 PST
From: Diana Hall <DFH@SU-AI.ARPA>
Subject: Compositional Temporal Logic
[Forwarded from the SRI CSLI bboard by Laws@SRI-AI.]
HOW COMPOSITIONAL CAN TEMPORAL LOGIC BE?
Speaker: Prof. Amir Pnueli
Weizmann Institute, Israel
Tuesday, March 27, 2:30 p.m.
Room 352 Margaret Jacks Hall
Abstract: A compositional proof system based on temporal logic is presented.
The system supports systematic development of concurrent systems by
specifying modules and then proving a specification for their combination.
The specifications of modules are expressed by temporal logic.
------------------------------
Date: Fri 23 Mar 84 18:28:23-EST
From: Jan <komorowski@MIT-OZ>
Subject: Logic Programming Seminars at Harvard
[Forwarded from the MIT bboard by Laws@SRI-AI.]
SEMINAR
LOGIC PROGRAM DERIVATION
Danny Krizanc
Harvard University
Tuesday, April 3, 1984
4 PM
Aiken G23
Danny will present a work he has done in my course Technology of Logic
Programming on program transformation. The method of Burstall and
Darlington is translated into resolution-based theorem proving and
applied to logic programs. The method is subsequently extended beyond
the limits of the functional approach.
------------------------------
Date: Fri 23 Mar 84 18:28:23-EST
From: Jan <komorowski@MIT-OZ>
Subject: Logic Programming Seminars at Harvard
[Forwarded from the MIT bboard by Laws@SRI-AI.]
COLLQUIUM
APPLICATION OF PROLOG TO GENERATION OF TEST DATA
FROM ALGEBRAIC SPECIFICATIONS
Prof. Marie-Claude Gaudel
Universite de Paris-Sud
Monday, April 9, 1984
4 PM
Aiken Lecture Hall
Tea in Pierce 213 at 3:30
ABSTRACT: Functional testing or "black-box testing has been recognized
for a long time as an important aspect of software validation. With
the emrgence of formal specification methods it becomes possible to
found functional testing on a rigorous basis. This lecture presents a
method of generating sets of test data from algebraic specifications.
The method has been impelemted using Prolog. It turns out that Prolog
is avery well-suited tool for generating sets of test data in this context.
Host : Professor Henryk Jan Komorowski
------------------------------
Date: Thu, 22 Mar 84 17:52:39 PST
From: Tulin Mangir <tulin@UCLA-CS.ARPA>
Subject: Course in Expert Systems for CAD/CAT
UCLA School of Engineering, Computer Science Department
is offering a new course, in Spring Quarter, in the
area of applications of Expert Systems to CAD and CAT in general, and
to VLSI and WSI design and testing specifically.
A Brief description of the topics to be covered follows.
Some of the projects in this course are extensions of the projects
that are started in the "Testing and Design for Testability for VLSI"
class that we are offerring once a year. I also teach that course.
I welcome any questions, comments, and suggestions and promise to
give a state of the course(!) report on line for those who are
interested.
Tulin E. Mangir
<cs.tulin@UCLA-CS>
(213) 825-2692
825-1322 (secretary)
-------------------------------------
UCLA COMPUTER SCIENCE DEPARTMENT
Spring 84
New Course on Expert Systems
CS259 Section 4
EXPERT SYSTEMS WITH APPLICATIONS TO CAD AND CAT
Instructor: Professor Tulin E. Mangir
Time: MW 4-6pm (TBA)
FIRST MEETING IN 5252 BOELTER HALL, W 4-6PM 4/4/84.
This course is open to all graduate students who are interested
in developing and applications of expert systems.
Students are encouraged to develop projects using the
tools and environments available at UCLA or otherwise.
Instructor's special interest is developing expert systems for design
and testability analysis of VLSI and WSI.
For any questions please contact instructor 825-2692, or 3532L Boelter Hall.
Course Outline:
o Introduction
o Organization of Expert Systems
o Representation of Digital structure and behaviour
o Requirements for data base, rule base, knowledge base design and interfaces
between them; control structure
o Languages, logic programming (PROLOG), frameworks
o Application domains for expert systems in CAD, CAT and automated processing
o Example systems under development-- DRC, 2-D Planner, Hitest, Excat, others.
o Limitations
o Future directions
------------------------------
End of AIList Digest
********************
