AIList-REQUEST@SRI-AI.ARPA (AIList Moderator Kenneth Laws) (11/12/85)
AIList Digest Tuesday, 12 Nov 1985 Volume 3 : Issue 168
Today's Topics:
Queries - Recent Work by Johnson/Laird &
Conceptual Dependencies and Predicate Calculus WFFs,
AI Tools - Typed languages and Lisp,
Cryptography - RSA Complexity,
Inference - Abduction,
News - Computer Museum Micromouse Competition,
Review - Commercial Machine Translation,
Humor - Intelligence Quotation
----------------------------------------------------------------------
Date: 11 Nov 85 21:50:57 GMT
From: Bob Stine <stine@edn-vax.arpa>
Subject: Recent work by Johnson/Laird
Can anyone give me some pointers to recent work by
Johnson and Laird on the role of mental models in
cognition?
Thanks,
- Bob Stine
------------------------------
Date: 11 Nov 85 21:58:58 GMT
From: Bob Stine <stine@edn-vax.arpa>
Subject: Conceptual Dependencies and Predicate Calculus wffs
Anyone know of any work that has been done in translating conceptual
dependency structures into predicate calculus wffs?
Thanks,
Bob Stine
------------------------------
Date: Fri, 8 Nov 1985 14:38 EST
From: Skef Wholey <Wholey@C.CS.CMU.EDU>
Subject: Re: Typed languages and Lisp
From: John Craig <JJC@SU-AI.ARPA>
Chris Goad (Stanford CS grad) developed a language originally called SIL,
now called RISE which is essentially a typing system added to Lisp, but
with a no-type type so that one can get around typing as one desires. The
main reasons for adding typing are:
1) faster code development (type checker finds bugs)
A type checker can find some bugs, but it isn't clear that such bugs would
take much time to find and fix relative the to the "real" bugs a programmer
spends most of his time on. Also, actually entering type information can add
to program development time. Controlled experiments are required to back
claims like the above.
2) the compiler can use type information to generate more efficient
object code (for example, less or no garbage collection pauses when
running compiled code)
I'll believe that type information can let a compiler generate more efficient
code, but dynamic storage allocation (and therefore garbage collection) has
almost nothing to do runtime typing. The exception to this is "number
consing," which can be avoided by clever Lisp systems most of the time anyway.
It seems to me like you get the best of lisp and typed worlds, and
efficient code generated also. Its pretty fun, too.
Common Lisp provides a very complete type declaration mechanism that lets one
give the compiler a great deal of information. This information is used (by
some Common Lisp compilers) to generate very efficient code. The difference
is not that one language is typed and the other untyped, but that the default
"typedness" is different.
------------------------------
Date: Fri, 8 Nov 85 10:18:06 cst
From: ihnp4!gargoyle!simon@ucbvax.berkeley.edu (Janos Simon)
Subject: Cryptography
A small correction about the difficulty of breaking the RSA scheme:
it is NOT NP-hard (although it is very likely that it is not
invertible in polynomial time - in fact it is very likely that it
cannot be inverted by polynomial time algorithms that use
randomization (that yield correct answers with high probability).
It is not hard to see that the RSA scheme can be broken if one
knows the factorization of the underlying number. Now factoring
is strongly suspected to be difficult (not doable in random
polynomial time), but it is not known to be NP-hard, and there are
good reasons to suspect that it isn't:
1)Both factoring and primality testing are in NP. That is not
true of any NP-complete problem. If factoring would be NP-hard then
NP would be closed under complementation. This would be a surprising
answer to a very difficult question.
2)There is a deterministic factoring algorithm that runs in
time exp(logn loglogn). This is not polynomial, but much less than
exponential (2**n). Again, this would be a very unexpected behavior
for an NP-hard problem.
Janos Simon
------------------------------
Date: Mon, 11 Nov 85 09:27:54 EST
From: munnari!basser.oz!anand@seismo.CSS.GOV
Subject: Re: Abduction
The term abduction( as applicable to AI) or retroduction was first
coined by Charles Sanders Peirce. Deduction, Induction and Abduction
are three types of reasoning mechanisms.
DEDUCTION- Rule: All the beans from this bag are white.
Case: These beans are from this bag.
Therefore Result: These beans are white.
INDUCTION- Case: These beans are from this bag.
Result: These beans are white.
Therefore Rule: All the beans from this bag are white.
ABDUCTION- Rule: All the beans from this bag are white.
Result: These beans are white.
Therefore Case: These beans are from this bag.
Induction is where we generalize from a number of cases of which
something is true, and infer that the same thing is true for a whole class.
Abduction is where we find some very curious circumstance which would
be explained by the supposition that it was a case of a certain general
rule and thereupon adopt the supposition.
Refer the 'Collected Papers of Charles Sandes Peirce' Vol I & Vol II
edited by Charles Hartstone & Paul Weiss, Harvard Uni. Press, 1960.
(paragraph 65,66,67,68 of Vol I and paragraphs 623 & 624 of Vol II).
(Postmaster:- This mail has been acknowledged.)
------------------------------
Date: Thu, 7 Nov 85 11:17:27 est
From: Brian Harvey <bh at mit-media-lab.MIT.EDU>
Subject: Computer Museum Micromouse Competition
[Forwarded from the MIT bboard by SASW@MIT-MC.]
English and Japanese robot "mice" will engage in a heated nose-to-nose
competition at The Computer Museum on Saturday, November 23. The miniature
self-guiding and self-propelled robots will compete for intelligence and
speed in the official room-sized Micro Mouse Maze used in the World Micro
Mouse Competition held in Japan last August.
Schedule of Events:
11:00 - 12:00 Tours of maze; micromice on display
12:00 - 1:30 Mouse warm-up and adjustment
1:30 - 3:00 First micromouse race
3:00 - 3:30 Mouse warm-up and adjustment
3:30 - 5:00 Second micromouse race
Would-be mouse designers and the simply curious can attend a special lecture
and mouse demonstration clinic on Sunday, November 17 at 4:00 pm featuring
England's noted mouse expert Professor John Billingsley.
For more information call 426-2800 (a human being) or 357-8014 (a DECtalk
voice synthesizer).
------------------------------
Date: 10 Nov 1985 2102-PST
From: LAWS at SRI-AI.ARPA
Subject: Commercial Machine Translation
Title: Machines are Mastering the Language of Multinational Business
Author: Joyce Heard with Leslie Helm
Business Week (No. 2912, 9/16/85, pp. 90D ff.)
This article describes machine translation systems that are currently
available for translating English, German, French, Spanish, Italian,
and Japanese. Speeds of up to 100,000 words per hour are claimed, as
are accuracies of up to 90% and prices as low as $3,000. [Not all the
same system, of course.] Customers are apparently willing to accept
rough translations as long as they can get them quickly; translators,
however, are not happy just polishing machine translations. Most
of the companies offering multilingual services are converting text
to a "neutral" language, then into the target language -- this greatly
reduces the cost of additional source or target languages. NEC
estimates that it needs about 100 "rules" for complete Japanese-English
translation, and has developed 30. Europe has been the chief market
so far, but most of the commercial leaders are American (Automated
Language Processing Systems, Logos, World Translation Center, and Weidner).
Fujitsu, Toshiba, NEC, and Bravice International are coming up fast,
however. Philips and the Netherlands' BSO are also working on systems.
------------------------------
Date: Mon, 11 Nov 85 09:23:31 GMT
From: gcj%qmc-ori.uucp@ucl-cs.arpa
Subject: Future Intelligence Quotation
>From the World Times, 11 November 2085 :-
``The World's first Intelligent System was put to the
test today. On the standard IQ rating, it's score was...''
Gordon Joly
gcj%qmc-ori@ucl-cs.arpa
------------------------------
End of AIList Digest
********************