From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Tue Jan 18 14:16:01 2005 for ; Tue, 18 Jan 2005 14:16:00 -0500 (EST) for ; Tue, 18 Jan 2005 14:16:00 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Tue, 18 Jan 2005 14:15:30 -0500 19:15:30 -0000 j0IJFT7W020362 for ; Tue, 18 Jan 2005 14:15:29 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Tue, 18 Jan 2005 14:15:29 -0500 (EST) Date: Tue, 18 Jan 2005 14:15:29 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: Welcome to the CSE 463/563 Listserv! To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ WELCOME TO THE CSE 463/563 E-MAIL LISTSERV FOR SPRING 2005! ------------------------------------------------------------------------ 0. The homepage for Prof. Rapaport's course, CSE 463/563, Introduction to Knowledge Representation and Reasoning, Spring 2005, is: http://www.cse.buffalo.edu/~rapaport/563S05.html >From there, you can access the syllabus and the directory of documents. ------------------------------------------------------------------------ 1. If you are reading this email, then you are on the CSE 463/563 Listserv. ------------------------------------------------------------------------ 2. If you are NOT enrolled in the course and therefore do NOT want to be on this Listserv, please either remove your address from it by visiting: http://listserv.buffalo.edu/cgi-bin/wa?SUBED1=cse563-sp05-list&A=1 or by visiting: http://www.cse.buffalo.edu/~rapaport/563S05/listserv.html and following the links for joining or quitting the list, or by sending email to me: rapaport@cse.buffalo.edu ------------------------------------------------------------------------ 3. For information on how to use this Listserv, please visit: http://www.cse.buffalo.edu/~rapaport/563S05/listserv.html ------------------------------------------------------------------------ 4. I will use this mailing list to post important updates, additions, corrections, etc., that I may not have time for in lecture. The TA will use this mailing list for similar purposes. And YOU can use this mailing list to discuss topics from lecture, to ask questions, to get further information, ... If you prefer to contact the TA or me in private (i.e., if you don't want everyone else in class to know what you're asking), then please send us private email (our email addresses are on the syllabus). However, I reserve the right to re-post such email---without your name or any other identifying information---if I think the question and its answer are of general interest. If you do not want me to do this, please let me know in your email message. ------------------------------------------------------------------------ 5. The 5 Commandments of Computer Security: ---------------------------------------- I. Thou shalt maintain the security of thy computer accounts and thy written work. (In plain English: Practice "safe" computing, and don't let anyone copy your work!) II. Thou shalt not share passwords with anyone, nor write thy password down where it may be seen by others. (In plain English: Make sure no one except you knows your password or can find it out!) III. Thou shalt not change permissions to allow others to read thy course directories and files. (In plain English: Don't let anyone else use your account!) IV. Thou shalt not walk away from a workstation without logging out. (In plain English: Always log out!) V. In groups that collaborate inappropriately, it may be impossible to determine who has offered work to others in the group, who has received work, and who may have inadvertantly made their work available to the others by failure to maintain adequate personal security. In such cases, thou shalt all be held equally liable. (In plain English: If your friend copies your work, BOTH of you will be held equally responsible! See Commandment I, above.) ------------------------------------------------------------------------ William J. Rapaport Associate Professor of Computer Science/Adjunct Professor of Philosophy Member, Center for Cognitive Science Associate Director, SNePS Research Group (SNeRG) 201 Bell Hall (office: 214 Bell) | 716-645-3180 x 112 Dept. of Computer Science & Engineering | fax: 716-645-3464 University at Buffalo (SUNY) | rapaport@cse.buffalo.edu Buffalo, NY 14260-2000 | ------------------------------------------------------------------------ CSE: www.cse.buffalo.edu/ homepage: www.cse.buffalo.edu/~rapaport/ SNeRG: www.cse.buffalo.edu/sneps/ Buffalo Restaurant Guide: www.cse.buffalo.edu/restaurant.guide/ Cognitive Science: wings.buffalo.edu/cogsci/ Good Things about Buffalo: www.cse.buffalo.edu/~rapaport/buffalo.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Wed Jan 19 14:13:13 2005 for ; Wed, 19 Jan 2005 14:13:12 -0500 (EST) for ; Wed, 19 Jan 2005 14:13:12 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Wed, 19 Jan 2005 14:12:59 -0500 19:12:59 -0000 j0JJCw7W027914 for ; Wed, 19 Jan 2005 14:12:58 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Wed, 19 Jan 2005 14:12:58 -0500 (EST) Date: Wed, 19 Jan 2005 14:12:58 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: Commonsense Reasoning To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU X-Keywords: X-UID: 3173 ------------------------------------------------------------------------ Subject: CSE 4/563: Commonsense Reasoning ------------------------------------------------------------------------ Just as KRR is a branch of AI, so there are branches of KRR. One of them is called "commonsense reasoning". (Arguably, it was the original branch of KRR: John McCarthy's early paper on KRR was titled "Programs with Common Sense".) The following email notice just came out, and I thought you might be interested in reading the preamble describing this branch of KRR. | CALL FOR PAPERS | | CommonSense 2005 | The 7th International Symposium on Logical | Formalizations of Commonsense Reasoning | | http://www.iccl.tu-dresden.de/commonsense05/ | | May 22-24, 2005 | Corfu, Greece | | | | One of the major long-term goals of artificial intelligence is to endow | computers with commonsense reasoning capabilities. Although we | know how to design and build systems that excel at certain bounded | or mechanical tasks which humans find difficult, such as playing | chess, we have little idea how to construct computer systems that do | well at commonsense tasks which are easy for humans. | Formalizing commonsense reasoning using logic-based approaches | will be the focus of the symposium. Topics of interest include, but | are not limited to: | | * change, action, and causality | * self-aware systems | * axiomatizations of benchmark commonsense problems | * ontologies, including space, time, shape, and matter, and | ontologies of networks and structures | * levels of granularity of ontology and reasoning | * large commonsense knowledge bases | * exploration of new commonsense domains in a preformal way | (e.g. new microworlds or benchmark problems) | * nonmonotonic reasoning | * formal models of probabilistic reasoning | * formal theories of context | * mental attitudes including knowledge, belief, intention, and | planning | * belief revision, update, and merging | * cognitive robotics | * reasoning about multi-agent systems and social interactions | among agents | * applications of formal representations to applications, such as | natural language processing | * other mathematical tools for capturing common-sense | reasoning | | The symposium aims to bring together researchers who have | studied the formalization of commonsense reasoning. The focus of | the symposium is on representation rather than on algorithms, and | on formal rather than informal methods. Papers should be rigorous | and concrete. Technical papers offering new results in the area are | especially welcome; object level theories are preferred. We | especially encourage papers on either of the two themes of this | symposium, Self-awareness and the Surprise Birthday Present | Problem (see below). Survey papers, papers studying the | relationship between different approaches, and papers on | methodological issues such as theory evaluation, are also | encouraged. | | | | Symposium Themes | ================ | There will be two themes at this year's Common Sense Symposium. | In addition to the topics listed above, we encourage papers on these | two themes, and plan to organize one or more panels on these topics. | | The first theme is Self-awareness: the notion of the computer having | a sense of self, being conscious of its own reasoning power, and | being able to explore itself in relation to other agents. We are | especially interested in formal theories that represent self- | awareness, and/or allow a system to reason about its own | awareness. | | The second theme is the Surprise Birthday Present Problem, | one of the challenge problems on the Common Sense Problem | Page (www-formal.stanford.edu/leora/commonsense/). We | encourage submission of papers that present solutions to this | problem and to its listed variants. Sample solutions to other | challenge problems can be found on the Common Sense Problem | Page. | | | | Submission Information | ====================== | Persons wishing to make presentations at the workshop should | submit papers of up to 6000 words, excluding the bibliography. | Electronic submissions in pdf, are preferred; otherwise 6 hard | copies of the paper are acceptable. All submissions should be sent | to one of the Symposium Chairs. | | | | Publication | =========== | The proceedings of the symposium will be published as a Dresden | University Technical Report (ISSN 1430-211X). Moreover, the | program chairs will invite selected authors to submit extended | versions of their papers for a special issue of the Journal of Logic | and Computation. | | | | Multiple Submissions Allowed | ============================ | Papers may be submitted to Commonsense-2005 even if they have | been submitted to other conferences or symposia (such as IJCAI- | 2005). If a paper is accepted at an archival conference such as | IJCAI and is also selected by Commonsense-2005 for publication at | the special journal issue, then this paper must be substantially | revised and/or extended. Previously published papers are not | acceptable for Commonsense-2005. | | | | Participation | ============= | Persons wishing to attend the symposium should submit a 1-2 page | research summary including a list of relevant publications. This is not | required for the authors of submitted papers. Moreover PhD | students need only to send the tentative title and abstract of their | dissertation. All requests for attendance should be sent to one of the | Symposium Chairs. | | | | Important Dates | =============== | Paper Submission Deadline: February 8, 2005 | Paper Notification: March 14, 2005 | Camera Ready Papers Due: March 28, 2005 | Symposium: May 22 - 24, 2005 | | | | Invited Speakers | ================ | Peter Gardenfors, University of Lund | Pat Hayes, University of West Florida | John McCarthy, Stanford University | Leora Morgenstern, IBM Watson Research | | | | Symposium Committee | =================== | Co-Chairs | --------- | Sheila McIlraith | Dept of Computer Science | University of Toronto | 6 King's College Road | Toronto, ON, Canada M4K 2W1 | sheila@cs.toronto.edu | | Pavlos Peppas | Dept of Business Administration | University of Patras | Patras 256 00, Greece | ppeppas@otenet.gr | | Michael Thielscher | Dept of Computer Science | Dresden University of Technology | 01062 Dresden, Germany | mit@inf.tu-dresden.de | | | | Program Committee | =================== | Eyal Amir, Uni. of Illinois at Urbana-Champaign, USA | Mike Anderson, University Of Maryland, USA | Grigoris Antoniou, University of Crete, Greece | Chitta Baral, Arizona State University, USA | Gerd Brewka, University of Leipzig, Germany | Vinay Chaudhri, SRI, USA | Ernie Davis, NYU, USA | Patrick Doherty, University of Linkoping, Sweden | Esra Erdem, Techinal University of Wien, Austria | Nicola Guarino, ISTC-CNR Trento, Italy | Jerry Hobbs, USC/ISI, USA | Antonis Kakas, University of Cyprus, Cyprus | Lefteris Kirousis, University of Patras and CTI, Greece | Jerome Lang, IRIT, France | Vladimir Lifschitz, UT at Austin, USA | Fangzhen Lin, Hong Kong UST | John-Jules Meyer, University of Utrecht, The Netherlands | Leora Morgenstern, IBM Watson Research, USA | Don Perlis, University of Maryland, USA | Fiora Pirri, University of Rome La Sapienza, Italy | Murray Shanahan, Imperial College, UK | Stuart Shapiro, SUNY at Buffalo, USA | Chris Welty, IBM T.J. Watson, USA | Mary-Anne Williams, Uni. of Technology, Sydney, Australia From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Wed Jan 19 22:27:14 2005 for ; Wed, 19 Jan 2005 22:27:13 -0500 (EST) for ; Wed, 19 Jan 2005 22:27:13 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Wed, 19 Jan 2005 22:26:51 -0500 03:26:51 -0000 j0K3Qp7W000359 for ; Wed, 19 Jan 2005 22:26:51 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Wed, 19 Jan 2005 22:26:50 -0500 (EST) Date: Wed, 19 Jan 2005 22:26:50 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 563: Syllabus Update To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU X-Keywords: X-UID: 3213 ------------------------------------------------------------------------ Subject: CSE 563: Syllabus Update ------------------------------------------------------------------------ I have updated the syllabus to include my office hours, and a reminder about the Shapiro 2003 article on KR. There is also another reading assignment that I've put there that I'll tell you more about next time. For the syllabus, go to: http://www.cse.buffalo.edu/~rapaport/563S05/syl.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Jan 20 20:38:10 2005 for ; Thu, 20 Jan 2005 20:38:09 -0500 (EST) for ; Thu, 20 Jan 2005 20:38:09 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 20 Jan 2005 20:38:01 -0500 01:38:01 -0000 Date: Thu, 20 Jan 2005 20:40:21 -0500 Reply-To: Knowledge Representation & Reasoning From: Blake Martin Subject: Book For Course To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU X-Keywords: Junk X-UID: 3334 I'd like to save all of you a little time. I went to the College Bookstore and the UB Bookstore today and the book's sold out at both. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Jan 20 21:39:08 2005 for ; Thu, 20 Jan 2005 21:39:07 -0500 (EST) for ; Thu, 20 Jan 2005 21:39:07 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 20 Jan 2005 21:38:53 -0500 02:38:53 -0000 j0L2cq7W007697 for ; Thu, 20 Jan 2005 21:38:52 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 20 Jan 2005 21:38:52 -0500 (EST) Date: Thu, 20 Jan 2005 21:38:52 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: Re: Book For Course To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU I have asked that the bookstore order more copies right away. In the meantime, you might try amazon.com, bn.com, etc., etc. I will see if I can put Ch. 1 on the web. In the meantime, you could read Shapiro 2003 (linked-to on the syllabus) and the Hayes article in the MIT Ency. of Cog. Sci. http://cognet.mit.edu/MITECS/Entry/hayesp.html as reasonable substitutes. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Jan 21 09:45:40 2005 for ; Fri, 21 Jan 2005 09:45:40 -0500 (EST) for ; Fri, 21 Jan 2005 09:45:40 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 21 Jan 2005 09:45:32 -0500 14:45:31 -0000 j0LEjV7W010638 for ; Fri, 21 Jan 2005 09:45:31 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 21 Jan 2005 09:45:31 -0500 (EST) Date: Fri, 21 Jan 2005 09:45:31 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 463/563: Brachman & Levesque, Pref & Ch. 1, online! To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 463/563: Brachman & Levesque, Pref & Ch. 1, online! ------------------------------------------------------------------------ I have put a PDF copy of the Preface and Ch. 1 of the text on the web. This is not exactly the same version as the published one, since it is from the pre-publication page proofs. Thus, it may differ slightly, contain typos, and is missing the historical section. But it should suffice till either the bookstore gets its act together or you folks can get it from Amazon, Barnes & Noble, or whomever :-) http://www.cse.buffalo.edu/~rapaport/563S05/prefch1.pdf From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Jan 21 15:19:59 2005 for ; Fri, 21 Jan 2005 15:19:59 -0500 (EST) for ; Fri, 21 Jan 2005 15:19:58 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 21 Jan 2005 15:19:45 -0500 20:19:44 -0000 j0LKJi7W013210 for ; Fri, 21 Jan 2005 15:19:44 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 21 Jan 2005 15:19:44 -0500 (EST) Date: Fri, 21 Jan 2005 15:19:44 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 463/563: INTRODUCTORY LECTURE NOTES To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 463/563: INTRODUCTORY LECTURE NOTES ------------------------------------------------------------------------ Most of the material I will be lecturing on will be available in various published documents. An exception are my introductory remarks. But I'm hesitant to produce a beautifully formatted and linked webpage (for reasons of time) or to make it public, so I've whipped together an outline of the lectures I've given so far (minus many off-the-cuff side comments) and will be giving over the next lecture or two. It's on the web (but not listed on the Directory of Documents) at: http://www.cse.buffalo.edu/~rapaport/563S05/intro.html It's not self-explanatory, and to appreciate many items, you need to follow appropriate links elsewhere on the course website, but it summarizes what I have been/will be talking about. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Sun Jan 23 22:07:22 2005 for ; Sun, 23 Jan 2005 22:07:22 -0500 (EST) for ; Sun, 23 Jan 2005 22:07:22 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Sun, 23 Jan 2005 22:07:02 -0500 03:07:02 -0000 for ; Sun, 23 Jan 2005 22:07:02 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Sun, 23 Jan 2005 22:07:02 -0500 (EST) Date: Sun, 23 Jan 2005 22:07:02 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: Private Website To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU The username & password to access the material that needs a username & password on the course website (such as the "Project HALO" article) is: username/login = CSE563 password = Spring2005 Please note that this is case sensitive. If you have trouble accessing anything, please let me know. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 24 14:24:52 2005 for ; Mon, 24 Jan 2005 14:24:51 -0500 (EST) for ; Mon, 24 Jan 2005 14:24:51 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 24 Jan 2005 14:24:48 -0500 19:24:48 -0000 j0OJOlWD006552 for ; Mon, 24 Jan 2005 14:24:47 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Mon, 24 Jan 2005 14:24:47 -0500 (EST) Date: Mon, 24 Jan 2005 14:24:47 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: Frege, on sense and reference To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: Frege, on sense and reference ------------------------------------------------------------------------ Here is a citation to Frege's paper that I mentioned in lecture today: Frege, Gottlob (1892), "On Sense and Reference," in Peter Geach & Max Black (eds.), Translations from the Philosophical Writings of Gottlob Frege Oxford: Basil Blackwell, 1960. A version (not necessarily the one cited above) is online at: http://mind.ucsd.edu/syllabi/00-01/phil235/a_readings/frege_S&R.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 24 15:17:05 2005 for ; Mon, 24 Jan 2005 15:17:05 -0500 (EST) for ; Mon, 24 Jan 2005 15:17:05 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 24 Jan 2005 15:16:50 -0500 20:16:50 -0000 Date: Mon, 24 Jan 2005 15:19:19 -0500 Reply-To: Knowledge Representation & Reasoning From: Blake Martin Subject: Monads (Philosophy) To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU >From www.dictionary.com: monad - An indivisible, impenetrable unit of substance viewed as the basic constituent element of physical reality in the metaphysics of Leibnitz. For (what I'm guessing is) a better description, see http://www.utm.edu/research/iep/l/leib-met.htm#Substance%20as%20Monad My interpretation is that monads are analogous to the human soul regarding many properties (at least according to the Catholic view of the constitution of the human soul; that it is one with no divisible parts; however, the soul is immaterial, whereas monads are partless physical constituents which the world is made of.) From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 24 16:43:24 2005 for ; Mon, 24 Jan 2005 16:43:24 -0500 (EST) for ; Mon, 24 Jan 2005 16:43:24 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 24 Jan 2005 16:43:20 -0500 21:43:19 -0000 j0OLhJWD007943 for ; Mon, 24 Jan 2005 16:43:19 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Mon, 24 Jan 2005 16:43:19 -0500 (EST) Date: Mon, 24 Jan 2005 16:43:19 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: FINAL EXAM To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: FINAL EXAM ------------------------------------------------------------------------ Our final exam will be: Thursday, May 5, 11:45 a.m. - 2:45 p.m., Knox 4 From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 24 16:51:20 2005 for ; Mon, 24 Jan 2005 16:51:19 -0500 (EST) for ; Mon, 24 Jan 2005 16:51:19 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 24 Jan 2005 16:50:00 -0500 21:49:59 -0000 j0OLnxWD007988 for ; Mon, 24 Jan 2005 16:49:59 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 24 Jan 2005 16:49:59 -0500 (EST) Date: Mon, 24 Jan 2005 16:49:59 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: Re: Monads (Philosophy) To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: Re: Monads (Philosophy) ------------------------------------------------------------------------ Thanks Blake; another reputable online source is: Kulstad, Mark, & Carlin, Laurence (2002), "Leibniz's Philosophy of Mind", Stanford Encyclopedia of Philosophy http://plato.stanford.edu/entries/leibniz-mind/ From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 24 17:29:34 2005 for ; Mon, 24 Jan 2005 17:29:34 -0500 (EST) for ; Mon, 24 Jan 2005 17:29:34 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 24 Jan 2005 17:28:57 -0500 22:28:57 -0000 X-Originating-IP: 67.23.174.149 Date: Mon, 24 Jan 2005 17:28:57 -0500 Reply-To: Knowledge Representation & Reasoning From: Paula Chesley Subject: Re: CSE 4/563: FINAL EXAM To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU In-Reply-To: <200501242143.j0OLhJRk007942@wasat.cse.buffalo.edu> Quoting "William J. Rapaport" : > ------------------------------------------------------------------------ > Subject: CSE 4/563: FINAL EXAM > ------------------------------------------------------------------------ > > Our final exam will be: > > Thursday, May 5, 11:45 a.m. - 2:45 p.m., Knox 4 > > > That is not only Holocaust Remembrance Day, Feast of the Ascension, Cinco de Mayo, Children's Day (Japan), but also National Day of Prayer (USA). Someone's gotta be objecting to this final on *some* grounds. :) Paula *************** The utilitarian trivialities of their table talk--or rather, of his gloomy monologue--seemed to him positively degrading. He explained at length--fighting her attentive silence, sloshing against the puddles of pauses, abhorring himself--that he had had a long and hard journey; that he slept badly; that he was working on an investigation of the nature of Time, a theme that meant struggling with the octopus of one's own brain. She looked at her wristwatch. --Vladimir Nabokov Ada, or Ardor From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Wed Jan 26 17:16:14 2005 for ; Wed, 26 Jan 2005 17:16:14 -0500 (EST) for ; Wed, 26 Jan 2005 17:16:14 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Wed, 26 Jan 2005 17:16:05 -0500 22:06:04 -0000 j0QM64tH004933 for ; Wed, 26 Jan 2005 17:06:04 -0500 (EST) 17:06:04 -0500 (EST) Date: Wed, 26 Jan 2005 17:06:04 -0500 Reply-To: Knowledge Representation & Reasoning From: Albert Goldfain Subject: Extra Credit Problems To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU Hi all, I have created a webpage for the HW#1-style extra credit problems I gave in lecture today: http://www.cse.buffalo.edu/~ag33/563ec.html The extra credit will go towards the recitation component of your grade. If you choose to do these, they will be due at the beginning of lecture, wednesday FEB 02. Let me know if you have any questions. Albert From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Sat Jan 29 14:54:01 2005 for ; Sat, 29 Jan 2005 14:54:01 -0500 (EST) for ; Sat, 29 Jan 2005 14:54:01 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Sat, 29 Jan 2005 14:53:51 -0500 19:53:51 -0000 j0TJrpx3025520 for ; Sat, 29 Jan 2005 14:53:51 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Sat, 29 Jan 2005 14:53:51 -0500 (EST) Date: Sat, 29 Jan 2005 14:53:51 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: Buffalo Ontology site To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: Buffalo Ontology site ------------------------------------------------------------------------ This news just in... | Date: Sat, 29 Jan 2005 11:52:41 -0500 | From: "Smith, Barry" | Subject: Buffalo Ontology News | | Dear Friends, | | As you will recall, the National Center for Ontological Research was | founded towards the end of last year with two sites, in Buffalo and in | Stanford. NCOR's beta website is available here: http://ncor.us | | Thanks to the generosity of the College of Arts and Sciences and of the NYS | Center for Bioinformatics and Life Sciences, NCOR's Buffalo site now has | some limited financial and administrative support, which is designed to | promote efforts towards securing long-term funding from outside sources for | high-level ontological research in Buffalo. | | Efforts are currently under way to raise such funds for biomedical ontology | projects involving colleagues in Computer Science, the School of Dental | Medicine, and Roswell Park, as well as with our counterparts in Stanford. A | first NCOR event -- on spatial ontologies in anatomy and geography -- is | also scheduled: | | http://ontology.buffalo.edu/anatomy_GIS You should check out these sites to see what kind of ontological activity is going on here at UB! From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 31 14:05:07 2005 for ; Mon, 31 Jan 2005 14:05:07 -0500 (EST) for ; Mon, 31 Jan 2005 14:05:06 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 31 Jan 2005 14:05:00 -0500 19:04:59 -0000 j0VJ4tx3006331 for ; Mon, 31 Jan 2005 14:04:55 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Mon, 31 Jan 2005 14:04:54 -0500 (EST) Date: Mon, 31 Jan 2005 14:04:54 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: CogSci: Shapiro on a new logic for SNePS To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: CogSci: Shapiro on a new logic for SNePS ------------------------------------------------------------------------ Although the talk announced below sort of jumps the gun on what I'll be telling you about SNePS in lecture, you might still find this talk to be of interest. It is certainly relevant to KRR! | CENTER FOR COGNITIVE SCIENCE | University at Buffalo, State University of New York | | Wednesday, February 2, 2005 | 2:00 pm - 4:00 pm | 280 Park Hall, North Campus | | | Stuart Shapiro, Ph.D. | Department of Computer Science and Engineering | Center for Cognitive Science | University at Buffalo | | "A LOGIC OF ARBITRARY AND INDEFINITE OBJECTS" | | | A hardcopy of this flyer can be found here: | http://www.cogsci.buffalo.edu/Activities/Colloquium/CLLQs05/shapiroannounce.pdf | Please print it out and post it in your department/office. | | Center for Cognitive Science | University at Buffalo, State University of New York | 201 Bell Hall, Buffalo, NY 14260 | Phone: (716) 645-2177 ext. 795, Fax: (716) 645-3825 | Email: ccs-cogsci-contact@buffalo.edu | | Open to the Public. | Refreshments will be served. | From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 31 14:35:48 2005 for ; Mon, 31 Jan 2005 14:35:47 -0500 (EST) for ; Mon, 31 Jan 2005 14:35:47 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 31 Jan 2005 14:35:31 -0500 19:35:31 -0000 j0VJZVx3006585 for ; Mon, 31 Jan 2005 14:35:31 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Mon, 31 Jan 2005 14:35:31 -0500 (EST) Date: Mon, 31 Jan 2005 14:35:31 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: How to Run the SNePS Demo To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: How to Run the SNePS Demo ------------------------------------------------------------------------ The two demo files that I ran in class today can be found at: http://www.cse.buffalo.edu/~rapaport/assertions.snepslog http://www.cse.buffalo.edu/~rapaport/queries.snepslog To run them, do the following: 0. save a copy of those files in your local directory 1. Run Lisp (preferably in that directory) 2. Load SNePS 3. Enter SNePSLOG 4. "demo" the files To run lisp: I did it by executing the following at the Unix prompt: > /util/acl62/mlisp But there are better ways; for a complete list, see: http://www.cse.buffalo.edu/sneps/instructions.html To load SNePS: At a Lisp prompt, enter: :ld /projects/snwiz/bin/sneps To enter SNePSLOG (a logic-programming interface to the SNePS KRR system): At the next Lisp prompt, evaluate: (snepslog) To "demo" the files: At the SNePSLOG prompt (a colon ":"), type: : demo "filename" av e.g., : demo "assertions.snepslog" av Notes: "demo" is the function that reads the file and executes the SNePSLOG commands in it; "filename" should be the name you give your local copy of the file; it doesn't have to end in "snepslog", but you must include the quotes in the demo command. If you're running Lisp in a different directory than where you saved your copy of the files, you'll need to give the full pathname. "av" tells SNePSLOG to pause after reading each command but before executing it, and to tell you that it is pausing. AND NOW FOR THE IMPORTANT PART: HOW TO QUIT! When the demo is over, you can continue trying to type in input (though I haven't told you what it should look like--i.e., I haven't given you the syntax; but you can find it in the SNePS manual online at: http://www.cse.buffalo.edu/~jsantore/snepsman/ When you want to quit, do this: 1. Exit SNePSLOG, by typing "lisp" at the colon-prompt: : lisp 2. Now you're back in Lisp; to exit Lisp, type ":ex" at the Lisp prompt: cl-user(4): :ex From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 31 14:50:35 2005 for ; Mon, 31 Jan 2005 14:50:35 -0500 (EST) for ; Mon, 31 Jan 2005 14:50:34 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 31 Jan 2005 14:50:29 -0500 19:50:02 -0000 j0VJo1x3006752 for ; Mon, 31 Jan 2005 14:50:01 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Mon, 31 Jan 2005 14:50:01 -0500 (EST) Date: Mon, 31 Jan 2005 14:50:01 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: On Representing Emotion To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: On Representing Emotion ------------------------------------------------------------------------ Earlier in the semester, someone asked about representing emotion. Here are a few links that will give you more information on this topic: 1. As always, a good place to begin is the AI Topics website: AI Topics, "emotion" http://www.aaai.org/AITopics/html/emotion.html 2. The two researchers whose names I mentioned in class are Aaron Sloman and Rosalind Picard (both call the field the study of "affect", which is roughly a synonym for "emotion"): Aaron Sloman's research on "cognition and affect": http://www.cs.bham.ac.uk/research/cogaff/0-INDEX.html Also check out his "homepage portal" at: http://www.cs.bham.ac.uk/~axs/ Rosalind W. Picard's research on "affective computing" http://affect.media.mit.edu/ Also check out her homepage: http://web.media.mit.edu/~picard/ From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Jan 31 16:41:48 2005 for ; Mon, 31 Jan 2005 16:41:48 -0500 (EST) for ; Mon, 31 Jan 2005 16:41:48 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 31 Jan 2005 16:41:30 -0500 21:41:25 -0000 j0VLfPtH011818 for ; Mon, 31 Jan 2005 16:41:25 -0500 (EST) 16:41:24 -0500 (EST) Date: Mon, 31 Jan 2005 16:41:24 -0500 Reply-To: Knowledge Representation & Reasoning From: Albert Goldfain Subject: Monday Recitation (B1) To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU To all those in my Monday recitation (B1). We determined today that everyone could make it to SOME recitation (either Mon. or Wed.) if the Monday recitation was moved from its current slot (Mon 3pm-3:50pm) an hour earlier to (Mon 2pm-2:50pm). If you were not in recitation today and have a conflict with BOTH Mon. 2pm-2:50pm (the new B1) AND Wed. 4pm-4:50pm (B2) please let me know (via email, not a newsgroup post) and we can work something out. I will request a new room for the Monday recitation. This may or may not be ready for our next meeting. DO NOT ASSUME THAT WE ARE MEETING @ 2pm UNTIL I MAKE A FORMAL POSTING TO THE NEWSGROUP or DR. RAPAPORT ANNOUNCES IT IN CLASS. Thanks, Albert From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Tue Feb 1 11:59:23 2005 for ; Tue, 1 Feb 2005 11:59:22 -0500 (EST) for ; Tue, 1 Feb 2005 11:59:22 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Tue, 1 Feb 2005 11:52:38 -0500 16:52:37 -0000 j11Gqbx3012500 for ; Tue, 1 Feb 2005 11:52:37 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Tue, 1 Feb 2005 11:52:37 -0500 (EST) Date: Tue, 1 Feb 2005 11:52:37 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: B&L Ch 2 on line To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU I have put B&L, Ch. 2, in an uncorrected page-proof version, on the web at: http://www.cse.buffalo.edu/~rapaport/563S05/Private/ch2.pdf username/login = CSE563 password = Spring2005 From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Tue Feb 1 13:05:30 2005 for ; Tue, 1 Feb 2005 13:05:29 -0500 (EST) for ; Tue, 1 Feb 2005 13:05:29 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Tue, 1 Feb 2005 11:38:32 -0500 16:38:32 -0000 j11GcVx3012287 for ; Tue, 1 Feb 2005 11:38:31 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Tue, 1 Feb 2005 11:38:31 -0500 (EST) Date: Tue, 1 Feb 2005 11:38:31 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: Textbook Update To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: Textbook Update ------------------------------------------------------------------------ I just called the bookstore. They said that since several of you had come in to special order the text, they would not order any more in larger quantities. There is currently one copy available there. Our departmental secretary tells me that the College Bookstore on Maple might also have copies, since she sends our book orders there, too. I would advise those of you who do not yet have the text or who are not waiting for special orders to arrive to order the book immediately from an online dealer such as amazon.com or bn.com, whoever has the better price and/or delivery time. I will try to put the page-proof version of Ch. 2 (i.e., a version with errors, but still readable) on the website. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Wed Feb 2 09:33:07 2005 for ; Wed, 2 Feb 2005 09:33:07 -0500 (EST) for ; Wed, 2 Feb 2005 09:33:07 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Wed, 2 Feb 2005 09:32:51 -0500 14:32:51 -0000 j12EVix3018258 for ; Wed, 2 Feb 2005 09:31:44 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Wed, 2 Feb 2005 09:31:44 -0500 (EST) Date: Wed, 2 Feb 2005 09:31:44 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: SYLLABUS UPDATED To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: SYLLABUS UPDATED ------------------------------------------------------------------------ I have updated the syllabus; go to: http://www.cse.buffalo.edu/~rapaport/563S05/syl.html#dates From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Wed Feb 2 09:37:52 2005 for ; Wed, 2 Feb 2005 09:37:52 -0500 (EST) for ; Wed, 2 Feb 2005 09:37:52 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Wed, 2 Feb 2005 09:37:40 -0500 14:36:52 -0000 j12Eapx3018286 for ; Wed, 2 Feb 2005 09:36:51 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Wed, 2 Feb 2005 09:36:51 -0500 (EST) Date: Wed, 2 Feb 2005 09:36:51 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: ROOM CHANGE EFFECTIVE TODAY !!!!! To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: ROOM CHANGE EFFECTIVE TODAY !!!!! ------------------------------------------------------------------------ Because of the poor sight lines and visibility in our classroom, I requested (and was granted!) a room change. EFFECTIVE IMMEDIATELY, CSE 463/563 WILL MEET IN: 228 NSC From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Wed Feb 2 09:41:41 2005 for ; Wed, 2 Feb 2005 09:41:41 -0500 (EST) for ; Wed, 2 Feb 2005 09:41:41 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Wed, 2 Feb 2005 09:41:09 -0500 14:41:09 -0000 j12Ef8x3018335 for ; Wed, 2 Feb 2005 09:41:08 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Wed, 2 Feb 2005 09:41:08 -0500 (EST) Date: Wed, 2 Feb 2005 09:41:08 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: FURTHER SYLLABUS UPDATE To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: FURTHER SYLLABUS UPDATE ------------------------------------------------------------------------ I have further updated the syllabus to reflect the new room. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 3 08:52:16 2005 for ; Thu, 3 Feb 2005 08:52:15 -0500 (EST) for ; Thu, 3 Feb 2005 08:52:15 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 3 Feb 2005 08:51:56 -0500 13:51:56 -0000 j13Dptx3023773; Thu, 3 Feb 2005 08:51:55 -0500 (EST) 08:51:55 -0500 (EST) Date: Thu, 3 Feb 2005 08:51:55 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: ANOTHER KRR-RELEVANT COGSCI TALK To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: ANOTHER KRR-RELEVANT COGSCI TALK ------------------------------------------------------------------------ Here is the announcement of another CogSci talk that is KRR-relevant. | CENTER FOR COGNITIVE SCIENCE | University at Buffalo, State University of New York | | Wednesday, February 9, 2005 | 2:00 pm - 4:00 pm | 280 Park Hall, North Campus | | | | Selmer Bringsjord, Ph.D. | Chris McEvoy | Department of Cognitive Science | Artificial "Intelligence and Reasoning Laboratory (RAI) | Rensselaer Polytechnic Institute | | | "BUILDING A VIRTUAL PERSON(E) FROM THE "DARK SIDE" | | We describe our general approach to building what we call | advanced synthetic characters (or *bona fide* virtual persons), | within the paradigm of logic-based AI. This approach, based on | our RASCALS architecture, seeks to use a cognitive architecture | for ``mid-level" cognition, and advanced logical systems for | more advanced reasoning-intensive thought. To focus our | general approach, we provide a glimpse of our attempt to bring | to life one particular advanced synthetic character from the | "dark side" --- the character known simply as E (for, as you | may have guessed, evil). Building E entails, among other | things, that we formulate an underlying logico-mathematical | definition of evil, and that we manage to engineer as well an | appropriate presentation of E. | At the presentation level, we use an approach based in | manipulating facial musculature. | | | A hardcopy of this flyer can be found here: | http://www.cogsci.buffalo.edu/Activities/Colloquium/CLLQs05/bringsjordannounce.pdf | Please print it out and post it in your department/office. | | | | Center for Cognitive Science | University at Buffalo, State University of New York | 201 Bell Hall, Buffalo, NY 14260 | Phone: (716) 645-2177 ext. 795, Fax: (716) 645-3825 | Email: ccs-cogsci-contact@buffalo.edu | | Open to the Public. | Refreshments will be served. | From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 3 11:31:52 2005 for ; Thu, 3 Feb 2005 11:31:52 -0500 (EST) for ; Thu, 3 Feb 2005 11:31:52 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 3 Feb 2005 11:30:04 -0500 16:30:00 -0000 for ; Thu, 3 Feb 2005 11:29:59 -0500 (EST) -0500 (EST) Date: Thu, 3 Feb 2005 11:29:59 -0500 Reply-To: Knowledge Representation & Reasoning From: Albert Goldfain Subject: NEW TIME AND ROOM FOR MONDAY RECITATION B1 To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU Hello all, I was able to obtain a new room/time for recitation B1. We will now meet Monday 2pm-2:50pm in Baldy 125 This change is effective immediately (so our next meeting will be in Baldy 125, Mon @ 2pm). Albert From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 3 14:49:44 2005 for ; Thu, 3 Feb 2005 14:49:43 -0500 (EST) for ; Thu, 3 Feb 2005 14:49:43 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 3 Feb 2005 14:49:30 -0500 19:49:30 -0000 j13JnTx3026266 for ; Thu, 3 Feb 2005 14:49:29 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Thu, 3 Feb 2005 14:49:29 -0500 (EST) Date: Thu, 3 Feb 2005 14:49:29 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: SHAPIRO'S LOGIC OF ARBITRARY OBJECTS To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: SHAPIRO'S LOGIC OF ARBITRARY OBJECTS ------------------------------------------------------------------------ For more information on Shapiro's logic of arbitrary and indefinite objects, and for a copy of the paper that his CogSci talk was based on (Shapiro 2004), go to the webpage for the SNePS-3 project: http://www.cse.buffalo.edu/sneps/Projects/sneps3.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 3 14:55:09 2005 for ; Thu, 3 Feb 2005 14:55:09 -0500 (EST) for ; Thu, 3 Feb 2005 14:55:09 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 3 Feb 2005 14:54:54 -0500 19:54:54 -0000 j13Jsrx3026326 for ; Thu, 3 Feb 2005 14:54:53 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Thu, 3 Feb 2005 14:54:53 -0500 (EST) Date: Thu, 3 Feb 2005 14:54:53 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: UPDATED SYLLABUS; SNeRG To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: UPDATED SYLLABUS; SNeRG ------------------------------------------------------------------------ 1. I have updated the syllabus to include the new room/time for recitation B1. Go to: http://www.cse.buffalo.edu/~rapaport/563S05/syl.html#classmtgs 2. Our KRR research group, "SNeRG" (= SNePS Research Group), meets: Mondays, 3-5 p.m., Bell 242. For a schedule of presentations, go to: http://www.cse.buffalo.edu/sneps/Schedules/spring05.html Feel free to leave early or arrive late (the latter is preferable :-) (Note that this Monday's meeting will not be in Bell 242, but will be in the Center for the Arts, Room 266, instead.) From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 3 14:59:25 2005 for ; Thu, 3 Feb 2005 14:59:24 -0500 (EST) for ; Thu, 3 Feb 2005 14:59:24 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 3 Feb 2005 14:59:10 -0500 19:59:10 -0000 j13Jx9x3026354 for ; Thu, 3 Feb 2005 14:59:09 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Thu, 3 Feb 2005 14:59:09 -0500 (EST) Date: Thu, 3 Feb 2005 14:59:09 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: COLORLESS GREEN IDEAS SLEEP FURIOUSLY To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: COLORLESS GREEN IDEAS SLEEP FURIOUSLY ------------------------------------------------------------------------ I mentioned Noam Chomsky's sentence "Colorless green ideas sleep furiously" as an example of a syntactically well-formed sentence that was not semantically meaningful. (In fact, it appears to be pairwise anomolous: If something is colorless, it can't be green; ideas can't be green; ideas don't sleep; sleeping is not something that can be done furiously.) However, never underestimate the power of the human mind to construct meaning... http://www.cse.buffalo.edu/~rapaport/675w/colorless.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 4 09:26:39 2005 for ; Fri, 4 Feb 2005 09:26:38 -0500 (EST) for ; Fri, 4 Feb 2005 09:26:38 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 4 Feb 2005 09:26:32 -0500 14:26:32 -0000 j14EQVx3000559 for ; Fri, 4 Feb 2005 09:26:31 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 4 Feb 2005 09:26:31 -0500 (EST) Date: Fri, 4 Feb 2005 09:26:31 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: MEANING OF "REPRESENT" To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: MEANING OF "REPRESENT" ------------------------------------------------------------------------ I thought some of you might find the origin of the word "represent" to be of interest. Here is a link to the Oxford English Dictionary's entry on the word. http://www.cse.buffalo.edu/~rapaport/563S05/represent-oed.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Tue Feb 8 12:59:31 2005 for ; Tue, 8 Feb 2005 12:59:30 -0500 (EST) for ; Tue, 8 Feb 2005 12:59:30 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Tue, 8 Feb 2005 12:59:18 -0500 17:59:17 -0000 j18HxHx3024742 for ; Tue, 8 Feb 2005 12:59:17 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Tue, 8 Feb 2005 12:59:17 -0500 (EST) Date: Tue, 8 Feb 2005 12:59:17 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: CogSci: Representing Persons To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: CogSci: Representing Persons ------------------------------------------------------------------------ | CENTER FOR COGNITIVE SCIENCE | University at Buffalo, State University of New York | | Wednesday, February 9, 2005 | 2:00 pm - 4:00 pm | 280 Park Hall, North Campus | | Selmer Bringsjord, Ph.D. | Chris McEvoy | Department of Cognitive Science | Artificial "Intelligence and Reasoning Laboratory (RAI) | Rensselaer Polytechnic Institute | | "BUILDING A VIRTUAL PERSON(E) FROM THE "DARK SIDE" | | We describe our general approach to building what we call | advanced synthetic characters (or *bona fide* virtual persons), | within the paradigm of logic-based AI. This approach, based on | our RASCALS architecture, seeks to use a cognitive architecture | for ``mid-level" cognition, and advanced logical systems for | more advanced reasoning-intensive thought. To focus our | general approach, we provide a glimpse of our attempt to bring | to life one particular advanced synthetic character from the | "dark side" --- the character known simply as E (for, as you | may have guessed, evil). Building E entails, among other | things, that we formulate an underlying logico-mathematical | definition of evil, and that we manage to engineer as well an | appropriate presentation of E. | At the presentation level, we use an approach based in | manipulating facial musculature. | | | A hardcopy of this flyer can be found here: | http://www.cogsci.buffalo.edu/Activities/Colloquium/CLLQs05/bringsjordannounce.pdf | Please print it out and post it in your department/office. | | | | Center for Cognitive Science | University at Buffalo, State University of New York | 201 Bell Hall, Buffalo, NY 14260 | Phone: (716) 645-2177 ext. 795, Fax: (716) 645-3825 | Email: ccs-cogsci-contact@buffalo.edu | | Open to the Public. | Refreshments will be served. | From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 10 17:11:28 2005 for ; Thu, 10 Feb 2005 17:11:27 -0500 (EST) for ; Thu, 10 Feb 2005 17:11:27 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 10 Feb 2005 17:11:12 -0500 22:11:12 -0000 j1AMBCx3010918 for ; Thu, 10 Feb 2005 17:11:12 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Thu, 10 Feb 2005 17:11:12 -0500 (EST) Date: Thu, 10 Feb 2005 17:11:12 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: HW 3 QUERY To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: HW 3 QUERY ------------------------------------------------------------------------ A student writes: | | On HW3 question 2, you are asking the truth table for | the proposition: | ((~P ^ (P v Q)) ^ (~Q v R)) | | Is the "R" at the end intentionally and "R" or | is it a typo and should it be "P" instead? It is intentionally an "R", not a typo. You will need 8 rows in your truth table, one for each possible combination of truth values for 3 atomic wffs (2^3=8). There will be a follow-up question or two on the next HW. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 11 14:29:02 2005 for ; Fri, 11 Feb 2005 14:29:02 -0500 (EST) for ; Fri, 11 Feb 2005 14:29:02 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 11 Feb 2005 14:28:51 -0500 19:28:51 -0000 j1BJSpx3016458 for ; Fri, 11 Feb 2005 14:28:51 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 11 Feb 2005 14:28:51 -0500 (EST) Date: Fri, 11 Feb 2005 14:28:51 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: HW 3 Answers To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: HW 3 ANSWERS AND GRADING SCHEME ------------------------------------------------------------------------ 1. Syntax "English-translation" Semantics ------ ------------------------------- Notation: [[x]] for: the meaning of x [[Apples]] I eat apples [[Book]] There exists a book that lists all other books. [[Delicious]] Every apple that I have ever eaten has been delicious. [[Eat]] I eat apples and pears [[John]] It is possible that John will be tall when he grows up. [[Mary]] Mary believes that John's father is tall. [[Pears]] I eat pears [[Read1]] You have read the book that lists all other books. [[Read2]] You have read any (i.e., some) book. [[Read3]] You have read the book that lists books that do not exist. [[Read4]] You have read every book. [[Tall]] John's father is tall. [[Walk]] I usually like to take a walk. a) Eat b) (Apples ^ Pears) c) (Eat > Walk) NB: ">" for material conditional d) Delicious e) (Apples > Pears) f) Book g) Depends on whether you interpret "unless" as inclusive or exclusive disjunction! Here, I'll represent it inclusively, for convenience. (Note: "-" for negation.): (- Read1 > (- Read2 v Read3)) ^ (Read3 > Read4) h) Tall i) Mary j) John Grading: Syn/Sem: For each atomic proposition (there are 13), 0 = missing 1 = incorrect 2 = partial credit 3 = correct Total = 39 points For each proposition to be represented, 0 = missing 1 = incorrect 2 = partial credit 3 = correct Total = 30 points Subtotal = 69 points ------------------------------------------------------------------------ 2. a) P Q -P (PvQ) (-P^(PvQ)) - - -- ----- ---------- T T F T F T F F T F F T T T T F F T F F (note that (-P^(PvQ)) entails Q) Grading: input columns: 0,1,2,3 intermediate columns: 0,1,2,3 output column: 0,1,2,3 Total = 9 points. b) P Q R -P -Q (PvQ) (-QvR) (-P^(PvQ)) ((-P^(PvQ))^(-QvR)) - - - -- -- ----- ------ ---------- ------------------- T T T F F T T F F T T F F F T F F F T F T F T T T F F T F F F T T T F F F T T T F T T T T F T F T F T F T F F F T T T F T F F F F F T T F T F F (note that last column entails R) Grading: input: 0,1,2,3 intermediate: 0,1,2,3 output: 0,1,2,3 Total = 9 points Subtotal = 18 points. ------------------------------------------------------------------------ 3. Syntax "English translation" semantics ------ ------------------------------- [[Find]] I will be able to find you. [[Forget]] I forget what you look like. [[Follow]] I follow you.(#) [[Hear]] I can hear you. [[ICome]] I come to Mexico. [[Know]] I know what you look like.(+) [[YouFar]] You will be/are far away.(*) [[YouGo]] You go to Mexico. Notes: (#) Arguably, "I follow you" is intended to mean the same as "I come to Mexico". (+) Arguably, "I forget what you look like" is intended to be the negation of "I know what you look like" (*) It is not unreasonable to represent "You will be far away" differently from "You are far away". But doing so will make it harder, later, to show that this argument is valid. a) (YouGo > YouFar) b) (YouFar > -Hear) (note 1) c) (-Hear > -Know) (note 2) d) ((ICome ^ -Know) > -Find) e) ((YouGo ^ ICome) > -Find) Notes: (1) Maybe "when" should not be translated by ">"? But then the logic goes awry. (2) Maybe this should be: (-Hear > Forget), but then the logic goes awry. Grading: Syn/Sem: For each atomic proposition, 0,1,2,3 (total = 24 points) Rep'n: For each molecular proposition, 0,1,2,3 (total = 15 points) Subtotal = 39 points ======================================================================== Grand total = 126 points 463 both 563 A 120-126 A- 113-119 B+ 105-112 B 99-105 B- 92-98 C+ 85-91 C 71-84 43-84 C- 57-70 D+ 43-56 D 21-42 F 0-21 From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 11 14:36:42 2005 for ; Fri, 11 Feb 2005 14:36:42 -0500 (EST) for ; Fri, 11 Feb 2005 14:36:41 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 11 Feb 2005 14:36:36 -0500 19:36:35 -0000 j1BJaZx3016552 for ; Fri, 11 Feb 2005 14:36:35 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 11 Feb 2005 14:36:35 -0500 (EST) Date: Fri, 11 Feb 2005 14:36:35 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: ANOTHER PROOF To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: ANOTHER PROOF ------------------------------------------------------------------------ Rather than wait till Monday to give you another example of a natural-deduction propositional-logic proof, I'll give it to you here. In this one, replacing propositional constant wffs "P" and "Q" by metavariables "\alpha" and "\beta" will turn the proof into a derivation of the commutative-law rule of inference that I told you was derivable. (The proof then would be a "subroutine" or "procedure" with parameters instead of constants; any time you needed the commutative law for ^ in a proof, you could then call that "procedure", passing in specific wffs as parameters, and justifying the conclusion by the derived rule of inference.) Show (P^Q) |- (Q^P) 1. (P^Q) : assumption {Show (Q^P): Strategy: show Q, show P, then invoke ^Intro. To show Q, use ^Elim on the assumption. to show P, use ^Elim on the assumption} 2. P : 1, ^Elim 3. Q : 1, ^Elim 4. (Q^P) : 3,2, ^Intro From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Feb 14 17:19:37 2005 for ; Mon, 14 Feb 2005 17:19:36 -0500 (EST) for ; Mon, 14 Feb 2005 17:19:36 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 14 Feb 2005 17:19:24 -0500 22:19:24 -0000 j1EMJNtH029335 for ; Mon, 14 Feb 2005 17:19:23 -0500 (EST) 17:19:23 -0500 (EST) Date: Mon, 14 Feb 2005 17:19:23 -0500 Reply-To: Knowledge Representation & Reasoning From: Albert Goldfain Subject: Homework #4 / V Intro and Elim rules To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU Hello all, I checked with Dr. Rapaport and the inference rules given in HW #4 DO treat P and Q as metavariables (i.e., they can stand in for BOTH atomic and molecular propositions). This is consistent with how we treat them in ^ Introduction and ^ Elimination. So (to the B1 recitation) both natural deduction proofs for the second problem in recitation were correct as written (no negation intro/elim rules needed since -Q can stand in for a metavariable). Also, in HW #4 question #5 the instructions say: "determine which of the above wffs are..." here, "above" refers to only those wffs in Problem #4. Please see me (or send me email) if you have any further questions, Albert From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Feb 14 19:08:45 2005 for ; Mon, 14 Feb 2005 19:08:45 -0500 (EST) for ; Mon, 14 Feb 2005 19:08:45 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 14 Feb 2005 19:08:29 -0500 00:08:16 -0000 j1F08Gx3029395 for ; Mon, 14 Feb 2005 19:08:16 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 14 Feb 2005 19:08:16 -0500 (EST) Date: Mon, 14 Feb 2005 19:08:16 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: Re: Homework #4 / V Intro and Elim rules To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: Re: Homework #4 / V Intro and Elim rules ------------------------------------------------------------------------ A follow-up to Albert's posting. I apologize for the confusing way I specified vIntro and vElim on HW4; blame it on cut and paste. As Albert noted, "P" and "Q" in those rules should have been \alpha and \beta, respectively. (And I'm glad you folks noticed this!) I will try to fix the online HW sheet to reflect this, but here's what it should have been: vIntro: From \alpha From \beta ---------------------- ---------------------- Infer (\alpha v \beta) Infer (\alpha v \beta) vElim: From (\alpha v \beta) From (\alpha v \beta) and -\alpha and -\beta --------------------- --------------------- Infer \beta Infer \alpha And, yes, in #5, "above" refers only to 4a--4f. Sorry for the confusion. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Feb 14 20:44:05 2005 for ; Mon, 14 Feb 2005 20:44:05 -0500 (EST) for ; Mon, 14 Feb 2005 20:44:04 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 14 Feb 2005 20:43:54 -0500 01:43:54 -0000 j1F1hrx3000317 for ; Mon, 14 Feb 2005 20:43:53 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Mon, 14 Feb 2005 20:43:53 -0500 (EST) Date: Mon, 14 Feb 2005 20:43:53 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: MODAL LOGIC To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: MODAL LOGIC ------------------------------------------------------------------------ I mentioned modal logic in lecture in connection with representing "can't". Here's the idea: "It can't be the case that P" (where P is some proposition) roughly means: "It is impossible that P". In modal logic, there are two "operators" that apply to wffs to form new wffs as follows (forgive me: they're hard to write in plain text): <>P ("Diamond P") []P ("Box P") The diamond represents the phrase "it is possible that", and the box represents the phrase "it is necessary that". So, "it can't be the case that P" could be represented as: -<>P (which, by the way, is logically equivalent to: []-P i.e., it is necessary that it is not the case that P.) The semantics involves the notion of a "possible world"; roughly: <>P is true in the actual world iff P is true in some possible world that is "accessible" from the actual world. []P is true in the actual world iff P is true in every possible world that is "accessible" from the actual world. For more information, see the link on the updated FOL webpage: http://www.cse.buffalo.edu/~rapaport/563S05/fol.html#modal or go directly to: http://www.cse.buffalo.edu/~rapaport/663/F03/modallogic.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Tue Feb 15 10:41:34 2005 for ; Tue, 15 Feb 2005 10:41:33 -0500 (EST) for ; Tue, 15 Feb 2005 10:41:33 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Tue, 15 Feb 2005 10:41:24 -0500 15:41:24 -0000 j1FFfKx3003632 for ; Tue, 15 Feb 2005 10:41:20 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Tue, 15 Feb 2005 10:41:20 -0500 (EST) Date: Tue, 15 Feb 2005 10:41:20 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: HW 4 UPDATED To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: HW 4 UPDATED ------------------------------------------------------------------------ I have updated the online version of HW 4 to include printable metavariables and to make problem 5 more explicit. There is no change in what you have to do; I have merely incorporated the previous clarificatory email messages into the online version of the HW. http://www.cse.buffalo.edu/~rapaport/563S05/hw04.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 18 11:10:35 2005 for ; Fri, 18 Feb 2005 11:10:35 -0500 (EST) for ; Fri, 18 Feb 2005 11:10:34 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 18 Feb 2005 11:10:25 -0500 16:10:25 -0000 j1IGAOjc012164; Fri, 18 Feb 2005 11:10:24 -0500 (EST) User-Agent: Mozilla/5.0 (X11; U; SunOS sun4u; en-US; rv:1.0.1) Gecko/20020920 Netscape/7.0 Date: Fri, 18 Feb 2005 11:10:24 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Organization: SUNY Buffalo Computer Science & Engineering Subject: CSE 4/563: Historia Matematica Mailing List Archive: Re: [HM] Modus ponens & tollens To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU X-Keywords: X-UID: 3777 ------------------------------------------------------------------------ CSE 4/563: Modus ponens & tollens ------------------------------------------------------------------------ I found a website that translates "Modus Ponens" (and "Modus Tollens", about which you will learn in today's lecture :-) into English: -- ------------------------------------------------------------------------ William J. Rapaport Associate Professor of Computer Science/Adjunct Professor of Philosophy Member, Center for Cognitive Science Associate Director, SNePS Research Group (SNeRG) 201 Bell Hall (office: 214 Bell) | 716-645-3180 x 112 Dept. of Computer Science & Engineering | fax: 716-645-3464 University at Buffalo (SUNY) | rapaport@cse.buffalo.edu Buffalo, NY 14260-2000 | ------------------------------------------------------------------------ CSE: www.cse.buffalo.edu/ homepage: www.cse.buffalo.edu/~rapaport/ SNeRG: www.cse.buffalo.edu/sneps/ Buffalo Restaurant Guide: www.cse.buffalo.edu/restaurant.guide/ Cognitive Science: wings.buffalo.edu/cogsci/ Good Things about Buffalo: www.cse.buffalo.edu/~rapaport/buffalo.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Sun Feb 20 17:34:59 2005 for ; Sun, 20 Feb 2005 17:34:59 -0500 (EST) for ; Sun, 20 Feb 2005 17:34:58 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Sun, 20 Feb 2005 17:34:48 -0500 22:34:48 -0000 j1KMYlx3006562 for ; Sun, 20 Feb 2005 17:34:47 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Sun, 20 Feb 2005 17:34:47 -0500 (EST) Date: Sun, 20 Feb 2005 17:34:47 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: Computational Linguistics talk on KRR -- MONDAY! To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU A candidate for the computational linguistics position in the LIN dept. will be speaking on Monday. His topic will be how mondadic second-order logic is relevant to computational linguistics. Since mondadic second-order logic can be considered as a KRR system, you might find the presentation interesting. (A logic is "monadic" if the only predicates are 1-place predicates (i.e., properties, not relations). A logic is "second-order" if it allows those predicates to be variables that can be quantified over. FOL only allows *terms* to be variables that can be quantified over. So, whereas in FOL, you can say things like "For all x, if x is a dog, then x is an animal", in SOL, you can also say things like "For all P and Q, if Fido has property P, then Fido has property Q".) Here is the abstract of the talk: ------------------------------------------------------------------------ Second-Order Logic, Finite-State Transducers, and Computational Linguistics Nathan Vaillette University of Tuebingen Monday, Feb. 21, 3:30-4:30 p.m., Baldy 684 Finite-state techniques enjoy a wide popularity in many different domains of Computational Linguistics, such as grapheme-to-phoneme conversion, morphological analysis, partial parsing, and information extraction. Not only do these techniques offer an extremely efficient implementation for many such problems, but furthermore, their flexibility makes them easy to combine and modify, allowing the developer to build solutions modularly and create new applications on the basis of old ones. However, these advantages are often counterbalanced by the relative difficulty of use of finite-state techniques, especially for linguists who are not primarily programmers. In particular, it is often difficult to see the conceptual connection between a linguistic notion and the finite-state machine that implements it. Various formalisms exist to help overcome this difficult. The replacement operator described in (Kaplan and Kay 1994) behaves like the familiar rewrite rules of generative phonology and can be automatically compiled into efficient finite-state machines. The two-level morphological rules of Koskenniemi (1983) constitute an alternative specification language for bridging the gap between linguists' expert knowledge and the computer's efficient finite-state implementation. Nonetheless, these formalisms suffer from serious drawbacks. They each presuppose a certain approach to linguistic problems and are not easily extended. Furthermore, the algorithms compiling the formalisms to finite-state machines are complex and have proven bug-prone. In this presentation, I will discuss an alternative language for simplifying communication between people and finite-state machines: monadic second-order logic (MSOL). This logical language allows humans to express their knowledge to a computer in a way that differs as little as possible from a careful formal presentation of the same information such as they might deliver to other humans. Logic has the further advantage of facilitating formal verifiability: the correctness of a "program" written in it can be mathematically demonstrated, often very straightforwardly. I will demonstrate how MSOL can be used to describe linguistic phenomena and discuss how formulas of the logic can be automatically compiled into efficient finite state machines, building off the pioneering work of Richard Buechi (1960). References: J. Richard Buechi. Weak second order arithmetic and finite automata. Zeitschrift fuer mathematische Logik und Grundlagen der Mathematik, 6:66--92, 1960. Ronald Kaplan and Martin Kay. Regular models of phonological rule systems. Computational Linguistics 20(3):331--378, 1994. Kimmo Koskenniemi. Two-level morphology: a general computational model for word-form recognition and production. Technical report, Department of General Linguistics, University of Helsinki, Finland, 1983. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Sun Feb 20 18:08:30 2005 for ; Sun, 20 Feb 2005 18:08:30 -0500 (EST) for ; Sun, 20 Feb 2005 18:08:30 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Sun, 20 Feb 2005 18:08:23 -0500 23:08:22 -0000 j1KN8Mx3006703 for ; Sun, 20 Feb 2005 18:08:22 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Sun, 20 Feb 2005 18:08:22 -0500 (EST) Date: Sun, 20 Feb 2005 18:08:22 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: SYLLABUS UPDATE To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: SYLLABUS UPDATE ------------------------------------------------------------------------ I have updated the syllbus so that it more accurately reflects what we are doing, when we are doing it, and what you should be reading. Go to: http://www.cse.buffalo.edu/~rapaport/563S05/syl.html#dates From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Sun Feb 20 20:40:34 2005 for ; Sun, 20 Feb 2005 20:40:34 -0500 (EST) for ; Sun, 20 Feb 2005 20:40:34 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Sun, 20 Feb 2005 20:40:27 -0500 01:40:26 -0000 j1L1eQx3007156 for ; Sun, 20 Feb 2005 20:40:26 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Sun, 20 Feb 2005 20:40:26 -0500 (EST) Date: Sun, 20 Feb 2005 20:40:26 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: Re: CSE 4/563: Computational Linguistics talk on KRR -- MONDAY! To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU X-Keywords: X-UID: 3892 Correction: The candidate's topic is monadic second-order logic (not "mondadic" :-) From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Feb 21 09:47:33 2005 for ; Mon, 21 Feb 2005 09:47:32 -0500 (EST) for ; Mon, 21 Feb 2005 09:47:32 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 21 Feb 2005 09:47:18 -0500 14:47:18 -0000 j1LElIx3009530 for ; Mon, 21 Feb 2005 09:47:18 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Mon, 21 Feb 2005 09:47:18 -0500 (EST) Date: Mon, 21 Feb 2005 09:47:18 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: REASONING BY SYNTACTIC RULES VS. BY SEMANTIC MENTAL MODELS To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU X-Keywords: Junk X-UID: 3921 ------------------------------------------------------------------------ Subject: CSE 4/563: REASONING BY SYNTACTIC RULES VS. BY SEMANTIC MENTAL MODELS ------------------------------------------------------------------------ I just came across an excellent article: Johnson-Laird, P.N.; Byrne, Ruth M.J.; & Schaeken, Walter (1992), "Propositional Reasoning by Model", Psychological Review 99(3): 418-439. Besides being a good introduction to Johnson-Laird's theory of mental models, the introductory sections (pp. 418-421) are a superb description of the differences between syntactic reasoning via rules of inference and semantic reasoning via models (mental or otherwise). I have added it to the webpage on Mental Models: http://www.cse.buffalo.edu/~rapaport/mental-models.html and put it online at: http://www.cse.buffalo.edu/~rapaport/563S05/Private/johnsonlaird-byrne-schaeken92.pdf Reminder: To access the "Private" section of our website, use: username login: CSE563 password: Spring2005 From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Mon Feb 21 20:44:13 2005 for ; Mon, 21 Feb 2005 20:44:13 -0500 (EST) for ; Mon, 21 Feb 2005 20:44:13 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Mon, 21 Feb 2005 20:43:47 -0500 01:43:47 -0000 for ; Mon, 21 Feb 2005 20:43:46 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Mon, 21 Feb 2005 20:43:46 -0500 (EST) Date: Mon, 21 Feb 2005 20:43:46 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: HW 4 answers and grading scheme To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: HW #4 ANSWERS & GRADING SCHEME ------------------------------------------------------------------------ 1. a) Prove: -P ^ (PvQ) |- Q 1. -P ^ (PvQ) : assumption {Show Q: Strategy: use vElim on (PvQ) and -P Therefore, need to show (PvQ), -P Strategy: Use ^Elim on line 1} 2. PvQ : 1, ^Elim 3. -P : 1, ^Elim 4. Q : 2,3, vElim Grading: 0 = missing 24 = seriously illegal 48 = correct up to a point, then errs 72 = syntactically valid proof ------------------------------------------------------------------------ b) Prove: -P ^ (PvQ) ^ (-QvR) |- R 1. -P ^ (PvQ) ^ (-QvR) : assumption { Show R: Strategy: Use vElim on -QvR Therefore, need to show -QvR and --Q (!) To show -QvR, use ^Elim on line 1. To show --Q, use -Intro} 2 . -QvR : 1, ^Elim 3. -P : 1, ^Elim 4. PvQ : 1, ^Elim 5. Q : 3,4, vElim {Show --Q, using -Intro: Enter a subproof with assumption -Q, then derive a contradiction} *6. -Q : temporary assumption *7. Q : send 5 *8. --Q : 6,7,6(!), -Intro {Note: This is a bit tricky! I assumed -Q. I needed to find a wff \beta such that I could derive both \beta and -\beta. I take \beta = Q! I can (trivially) derive Q by sending it in from the main proof on line 5. And I can (very trivially derive -Q, since I have assumed it inside this subproof!. The justification for -Intro normally cites 3 lines of proof: The temporary assumption, \beta, and -\beta. In this very special case, those are lines 6, 7, and 6 again!} 9. --Q : return 8 10. R : 2,9, vElim Note that some students may be tempted at line 5 to jump to the conclusion as follows: 6'. R : 2,5, vElim But the move from: 2. -QvR and 5. Q to 6'. R does not follow the vElim rule of inference, which says: >From (\alpha v \beta) and -\alpha --------------------- Infer \beta because here \alpha = -Q, but then -\alpha = --Q (-\alpha is *not* Q!). Now, you can, if you want *derive* a new rule of inference of the form: >From (-\alpha v \beta) and \alpha ---------------------- Infer \beta (and if a student does that, that's fine; in fact, such a proof is included in the full derivation above, as a special case). Grading: 0 = missing 24 = seriously illegal 48 = correct up to a point, then errs 72 = syntactically valid proof Total = 144 points ======================================================================== 2. col#: 1 2 3 4 5 6 a) P Q -P (PvQ) (-P^(PvQ)) (5>Q) - - -- ----- ---------- ----- T T F T F T T F F T F T F T T T T T F F T F F T Grading: input: 0,4,8,12 intermediate: 0,4,8,12 output: 0,4,8,12 Subtotal = 36 points ------------------------------------------------------------------------ b) 1 2 3 4 5 6 7 8 9 P Q R -P -Q (PvQ) (-QvR) (4^6^7) (8>R) - - - -- -- ----- ------ ------- ----- T T T F F T T F T T T F F F T F F T T F T F T T T F T T F F F T T T F T F T T T F T T T T F T F T F T F F T F F T T T F T F T F F F T T F T F T Grading: input: 0,4,8,12 intermediate: 0,4,8,12 output: 0,4,8,12 Subtotal = 36 points Total = 72 points ======================================================================== 3. 1 2 3 4 5 6 7 8 P Q -P -Q (P^Q) -(P^Q) (-Pv-Q) (6=7) [using "=" for bicond'n'l] - - -- -- ----- ------ ------- ----- T T F F T F F T T F F T F T T T F T T F F T T T F F T T F T T T Grading: input: 0,4,8,12 intermediate: 0,4,8,12 output: 0,4,8,12 Total = 36 points ======================================================================== 4. a) If there is smoke, then there is smoke. b) If there is smoke, then there is fire. c) If, if there is smoke, then there is fire, then, if it's not the case that there is smoke, then it's not the case that there is fire. d) (Either) there is smoke or there is fire or it's not the case that there is fire. e) If there is smoke and there is heat, then there is fire iff (i.e., if and only if) (either) if there is smoke, then there is fire or if there is heat, then there is fire. f) If, if there is smoke, then there is fire, then, if there is smoke and there is heat, then there is fire. Grading: For each sentence: 0 = missing 2 = incorrect 4 = partial credit 6 = correct Total = 36 points. ======================================================================== 5. a) Smoke (Smoke > Smoke) ----- --------------- T T F T tautology ------------------------------------------------------------------------ b) Smoke Fire (Smoke > Fire) ----- ---- -------------- T T T T F F F T T F T T contingent ------------------------------------------------------------------------ c) 1 2 3 4 5 6 7 Smoke Fire -Smoke -Fire (Smoke > Fire) (-Smoke > -Fire) (5>6) ----- ---- ------ ----- -------------- ---------------- ----- T T F F T T T T F F T F T T F T T F T F F F F T T T T T contingent ------------------------------------------------------------------------ d) 1 2 3 4 Smoke Fire -Fire (1v2v3) ----- ---- ----- ------- T T F T T F T T F T F T F F T T tautology ------------------------------------------------------------------------ e) 1 2 3 4 5 6 7 8 9 Smoke Heat Fire (S^H) (S^H)>Fire (S>Fire) (H>Fire) (6v7) (5=8) ----- ---- ---- ----- ---------- -------- -------- ----- ----- T T T T T T T T T T T F T F F F F T T F T F T T T T T T F F F T F T T T F T T F T T T T T F T F F T T F T T F F T F T T T T T F F F F T T T T T tautology ------------------------------------------------------------------------ f) 1 2 3 4 5 6 7 Smoke Fire Heat (S>Fire) (S^H) (S^H)>Fire (4>6) ----- ---- ---- -------- ----- ---------- ----- T T T T T T T T T F T F T T T F T F T F T T F F F F T T F T T T F T T F T F T F T T F F T T F T T F F F T F T T tautology ------------------------------------------------------------------------ Grading: For each sentence: truth table: input: 0,1,2,3 intermediate: 0,1,2,3 output: 0,1,2,3 taut/contra/cont: 0,1,2,3 Subtotal = 12 points/sentence Total = 72 points ======================================================================== Grand total = 288 points 463 both 563 A 273-288 A- 257-272 B+ 241-256 B 225-240 B- 209-224 C+ 193-208 C 161-192 97-192 C- 129-160 D+ 97-128 D 49-96 F 0-48 From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Wed Feb 23 18:55:40 2005 for ; Wed, 23 Feb 2005 18:55:40 -0500 (EST) for ; Wed, 23 Feb 2005 18:55:39 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Wed, 23 Feb 2005 18:54:32 -0500 23:54:32 -0000 for ; Wed, 23 Feb 2005 18:54:31 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Wed, 23 Feb 2005 18:54:31 -0500 (EST) Date: Wed, 23 Feb 2005 18:54:31 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: FUNCTION SYMBOLS VS. PREDICATES To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------- Subject: FUNCTION SYMBOLS VS. PREDICATES ------------------------------------------------------------------------- Since some of you expressed confusion about the difference between function symbols and predicates, I thought I'd summarize what I said in lecture today. If you are NOT confused, you probably shouldn't read this posting, since it may confuse you! But if you ARE confused, maybe it will help. First, don't forget to distinguish between syntax and semantics, in this case, between function symbols and predicates, on the one hand, and functions and properties/relations, on the other hand: SYNTAX SEMANTICS function symbols functions predicates properties and relations Let's concentrate on semantics (or ontology) first: A function is a set of input/output pairs such that the same input always yields the same output (i.e., you'll never have different outputs coming from the same input). A typical function is the doubling function: If the input is an integer, the output is twice the input. Another function is the one that takes as input a person and returns as output the father of that person. A property, mathematically (or "extensionally") speaking, is a set. An n-place relation, mathematically (or "extensionally") speaking, is a set of n-tuples. (Note that, on this view, a property is just a 1-place relation.) A typical example of a property thus understood might be the set of all red things; this would be the property "red". A typical example of a 2-place relation is the set of all ordered pairs of integers such that the first member of the pair is less than the second member; this would be the relation "<". There's another view of properties and relations that you should be aware of: A property, "intensionally" speaking, is some aspect or feature of a thing. So, the property of being red is that feature of a thing that reflects light of a certain wavelength. (Presumably, all the members of the extensional set of red things have this feature.) The An n-place relation, "intensionally" speaking, is some relationship that obtains among the n things. So, the relation of one integer being less than another is the relationship that obtains between the members of the ordered pairs in the extensional "<" relation. The mathematical, or "extensional", version is easier to understand, so I'll stick with that in what follows. I hope it's clear that functions and n-place relations are different things. (But, if you'd like, I can easily confuse you by pointing out that, mathematically, a function is just a 2-place relation, since it's a set of ordered pairs!) Now back to syntax: Function *symbols* are names of functions, and n-place *predicates* are names of n-place relations. So, "father-of" might be the name of one of the functions I mentioned above, and "double" might be the name of the other. We can then write things like this: father-of(George W. Bush) = George H.W. Bush double(2) = 4 Note that what I've just written are wffs of FOL! Each involves the 2-place predicate "=", which forms a wff along with two terms. In the first example, the term on the left-hand side of "=" is a molecular term: father-of(George W. Bush) constructed by taking the atomic constant term "George W. Bush" and forming an expression of the form: f(t). And the term on the right-hand side is an atomic constant term "George H.W. Bush". In the second example, the term on the LHS of "=" is a molecular term: double(2) constructed by taking the atomic constant term "2" and forming an expression of the form: f(t). And the term on the right-hand side is an atomic constant term "4". If I want to express a property of Bush, I could say something like: President(George W. Bush) If the term "George W. Bush" names George W. Bush, and the predicate "President" names the property of being a President of the US (or, mathematically, names the set {George Washington, John Adams, ..., Abraham Lincoln, ..., Bill Clinton, George W. Bush}), then this wff says that Bush has that property. (Just to confuse you, however, some people like to say that predicates name binary functions that take members of the domain as input and outputting a truth value, so "President(George W. Bush)" = true. But I wouldn't want to confuse you :-) The only remaining possible confusion is that the grammatical syntax for functions symbols and predicates is the same: symbol(term1, ..., term-n) But when you formally specify a language for FOL, you must carefully indicate which symbols are to be considered as function symbols and which are predicates. There should never be any ambiguity in a formal language (only in natural languages, like English). From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 24 12:25:59 2005 for ; Thu, 24 Feb 2005 12:25:58 -0500 (EST) for ; Thu, 24 Feb 2005 12:25:58 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 12:25:45 -0500 17:25:45 -0000 j1OHPitH008219 for ; Thu, 24 Feb 2005 12:25:44 -0500 (EST) 12:25:44 -0500 (EST) Date: Thu, 24 Feb 2005 12:25:44 -0500 Reply-To: Knowledge Representation & Reasoning From: Albert Goldfain Subject: On the use of previously derived results in syntactic proofs To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU Hello all, Several of you have asked me whether or not you can use previously derived results as "rules" in a proof. The answer is yes...but I would like you to do this as follows: *If the rule you want to use is a standard rule of inference (the standard connective intro/elim rules from class) then you don't need any further justification (just say something like ^Elim 2 in the comments as usual) *If the rule you want to use is on the same homework (for example if you want to use modus tollens or hypothetical syllogism in your proof of constructive dilemma on HW #5) then, as justification, write "see X" or the name of the rule (if it has one) in the commentary so I know where to look. *If the rule you want to use was proven in class or recitation, then please re-copy it on the side or above your main derivation...DO NOT say something vague like "from class". HOWEVER... You can do all of these proofs with just the basic connective intro/elim rules in hand. Our propositional logic is sound and complete, so if the truth table semantic proof works out, then there MUST be some syntactic derivation using just these inference rules. Also, if you have a derivation in hand that you would like to use for a harder derivation, you could always just substitute for the metavariables as needed to make an appropriate "copy" for your harder derivation (for the programmers out there, this is like expanding a macro). Having said that, I should also say the following: 1c is HARD! It is meant to stretch your logical minds like taffy :)...don't give up on it just because it seems harder than 1a and 1b. Best of luck! Albert From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 24 13:25:37 2005 for ; Thu, 24 Feb 2005 13:25:37 -0500 (EST) for ; Thu, 24 Feb 2005 13:25:37 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 13:25:18 -0500 18:25:18 -0000 j1OIPIx3001924 for ; Thu, 24 Feb 2005 13:25:18 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Thu, 24 Feb 2005 13:25:17 -0500 (EST) Date: Thu, 24 Feb 2005 13:25:17 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: TARSKI ON TRUTH VS. PROOF To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: TARSKI ON TRUTH VS. PROOF ------------------------------------------------------------------------ Alfred Tarski was the logician who developed the first formal definition of "truth". I've put two items on the "Syntax vs. Semantics" webpage relevant to him. The first item is a review of a recent biography of him. The second is a "popular" article he wrote for Scientific American describing the relationships between syntax and semantics, including a sketch of his definition of "truth" and briefly outlining Goedel's incompleteness theorem. Local connection: John Corcoran of the UB PHI department is Tarski's literary executor and editor of a collection of Tarski's papers. Go to: http://www.cse.buffalo.edu/~rapaport/563S05/synsem.html#tarski From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 24 17:01:45 2005 for ; Thu, 24 Feb 2005 17:01:44 -0500 (EST) for ; Thu, 24 Feb 2005 17:01:44 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 17:01:10 -0500 22:01:09 -0000 for ; Thu, 24 Feb 2005 17:01:09 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Thu, 24 Feb 2005 17:01:09 -0500 (EST) Date: Thu, 24 Feb 2005 17:01:09 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: FREEDOM AND BONDAGE To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: FREEDOM AND BONDAGE ------------------------------------------------------------------------ Here is a more precise definition of "free" and "bound" occurrences of variables in quantified wffs of FOL. First, there are two slightly different definitions of "scope" floating around in the literature (in what follows, (1) "Q" will be any quantifier, either the universal quantifier (here written as "A") or the existential quantifier (here written as "E"), (2) "v" will be a metavariable ranging over variables, and (3) "Z" and "Y" will be a metavariables ranging over predicates (ordinarily, I'd use "alpha" and "beta", but I can't in this font)): S1: Let Qv[Z] be a wff. Then Z is(df) the scope of (that occurrence of) Q. S2: Let Qv[Z] be a wff. Then Qv[Z] is the scope of (that occurrence of) Q. B&L do not define "scope"! But their definition is consistent with S2 (whereas I had given you S1 in lecture). Following S2, we can then define freedom and bondage of variable occurrences as follows (these definitions are based on Kalish, Montague, & Mar 1980): Def: Let Z be a wff. Then an occurrence of a variable v is bound in Z =df that occurrence stands within an occurrence in Z of a wff of the form QvY. Def: Let Z be a wff. Then an occurrence of a variable v is free in Z =df that occurrence stands within Z but is not bound in Z. I will give you examples in lecture on Friday. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 24 18:35:27 2005 for ; Thu, 24 Feb 2005 18:35:27 -0500 (EST) for ; Thu, 24 Feb 2005 18:35:27 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 18:34:39 -0500 23:34:39 -0000 j1ONYctH007347 for ; Thu, 24 Feb 2005 18:34:38 -0500 (EST) 18:34:38 -0500 (EST) Date: Thu, 24 Feb 2005 18:34:38 -0500 Reply-To: Knowledge Representation & Reasoning From: Albert Goldfain Subject: subproofs To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU Remember that the ONLY reasons to ever enter a subproof are to apply -Intro, -Elim or >Intro. You cannot enter a subproof and make a temp. assumption just to get a consequent of that temp. assumption returned. As I said in recitation, -Intro and -Elim correspond to "Proofs by Contradiction (Reductio Ad Absurdem)"...you assume the opposite of what you are trying to prove, and then show that something "goes wrong" (namely, a pair of contradictory lines \beta, -\beta). >Intro corresponds to "Direct Proofs" (at least this is the term for them in CSE191). You make a temporary assumption \alpha (in a subproof), show that you can legally get to \beta (in the same subproof), and then infer that \alpha > \beta (in the same subproof). Notice that you never return \alpha or \beta outside of the dream (neither would follow logically)...but what you do return is \alpha > \beta. This makes sense semantically...if \alpha is true (and it was as a temp assumption) then \beta is true (because we got to it in the subproof with legal syntactic rules). To extend Dr. Rapaport's "dream" metaphor for subproofs, -Intro and -Elim represent logical "nightmares" (i.e., contradictions) which happen when you enter the dream with the opposite of what you are trying to show. >Intro represents a "good dream" where all of your thoughts link the dream's beginning to it's end. The only dreams you can have are nightmares and good dreams. If this paragraph confuses you then please ignore it :) Albert From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 24 21:30:37 2005 for ; Thu, 24 Feb 2005 21:30:36 -0500 (EST) for ; Thu, 24 Feb 2005 21:30:36 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 21:10:16 -0500 02:10:15 -0000 Date: Thu, 24 Feb 2005 21:13:52 -0500 Reply-To: Knowledge Representation & Reasoning From: Blake Martin Subject: Re: subproofs To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU I understood how the Elim and Intro stuff worked... it seems that none of it applies to problem c, because there isn't a "lone" variable, and a lot of the variables/statements in problem c are symmetrical (in a sense -- I can't think of a better word). The first e-mail helped a lot - I didn't know what the conditions for being able to go into a subproof were. Well, the only way I can see that c can be solved is to assume that one of the consequents is false and show that the other must be true... I can do that for both variables... but that doesn't seem to match any kind of rule that we've encountered so far... it seems more like a "parallel" proof. Well... I guess I'll just write down something... I can see why the conclusion follows, and I can explain why it must hold (in English), but I don't believe I can solve it without some additional form of "proof" ----- Original Message ----- From: "Albert Goldfain" To: Sent: Thursday, February 24, 2005 6:34 PM Subject: subproofs > Remember that the ONLY reasons to ever enter a subproof are to apply > -Intro, -Elim or >Intro. You cannot enter a subproof and make a temp. > assumption just to get a consequent of that temp. assumption returned. > > As I said in recitation, -Intro and -Elim correspond to "Proofs by > Contradiction (Reductio Ad Absurdem)"...you assume the opposite of what > you are trying to prove, and then show that something "goes wrong" > (namely, a pair of contradictory lines \beta, -\beta). > >>Intro corresponds to "Direct Proofs" (at least this is the term for them > in CSE191). You make a temporary assumption \alpha (in a subproof), show > that you can legally get to \beta (in the same subproof), and then infer > that \alpha > \beta (in the same subproof). Notice that you never return > \alpha or \beta outside of the dream (neither would follow > logically)...but what you do return is \alpha > \beta. This makes > sense semantically...if \alpha is true (and it was as a temp assumption) > then \beta is true (because we got to it in the subproof with legal > syntactic > rules). > > To extend Dr. Rapaport's "dream" metaphor for subproofs, -Intro and -Elim > represent logical "nightmares" (i.e., contradictions) which happen when > you enter the dream with the opposite of what you are trying to show. >>Intro represents a "good dream" where all of your thoughts link the > dream's beginning to it's end. The only dreams you can have are > nightmares and good dreams. If this paragraph confuses you then please > ignore it :) > > Albert > From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 24 22:24:56 2005 for ; Thu, 24 Feb 2005 22:24:54 -0500 (EST) for ; Thu, 24 Feb 2005 22:24:54 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 22:24:17 -0500 03:24:17 -0000 j1P3OGx3003905 for ; Thu, 24 Feb 2005 22:24:16 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Thu, 24 Feb 2005 22:24:16 -0500 (EST) Date: Thu, 24 Feb 2005 22:24:16 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: HW 5 QUESTION To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: HW 5 QUESTION ------------------------------------------------------------------------ A student writes: | | I am just having a couple of problems with cse563 HW5 1c First, please note that the night before the HW is due is not a good time to be asking questions. I expect you to begin working on the HW as soon as possible after I assign it, so that you can ask these sorts of questions long *before* the HW is due :-) | I will use the following notation to describe my dilema: a = alpha, b= The word is spelled "dilemma" :-) | beta, g = gamma, l = lambda, d = delta | > = material condition, ^ = and, ~ = not, or = or "conditional" (not "condition" :-) | | QUESTION | if a > b could it's negation be ~a > b or does it have to be ~(a>b) I assume you mean "its" negation :-) [See my howtowrite.html website for the explanation.] The negation of any wff is formed by prefixing the entire wff with the negation sign, so ~(a>b) is the negation of (a>b). | QUESTION | I have tried various ways to do 1c but none of them seem to work here are | the various things that I tried : | | (a or g) ^ (a > b) ^ (g > d) infer (b or d) | 1st way | | 1.)(a or g) ^ (a > b) ^ (g > d) premise | 2.) a or g and elim 1 | 3.) a > b and elim 1 | 4.) g > d and elim 1 | purpose of subroutine to prove a so i can use a and (a > b) to apply >elim | to get b, then use (or intro) to get (b or d) This is reasonable, but not necessarily the best strategy! | *5.) ~a temp. assumpt. | *6.) a or l send 2 I assume you mean "avg" | *7.)g or elim 5,6 | *8.)a > b send 3 | *9.)g > d send 4 | *10.) d > elim 7,9 | *11.)this is where I get stuck because if I use any of the wff from 6 to 8 | as beta then I have to find a ~beta to show a contradiction to prove a or | use the >intro. IF i enter another subroutine then I still have to show a | contradiction to what ever beta I pick and none of the variables or wff | have a negation except alpha. OK--so this is a dead end. | | 2nd way | 1.)(a or g) ^ (a > b) ^ (g > d) premise | 2.) a or g and elim 1 | 3.) a > b and elim 1 | 4.) g > d and elim 1 | purpose of subroutine to return b so I can use or intro on b to say (b or | d) | *5.) a temp. assumpt. | *6.) a > b send 3 | *7.)b >elim 5,6 | * | 8.) stuck here because I can not return b, because last statement in | subroutine must be a negation or >intro rule Right; this is essentially the same problem you ran into above. | also it wouldn't do good to do the following | *8.) g > d send 4 | *9.)a or g send 2 | *9.)a > (g >d) >intro 5,9 I still end up with a molecular formula Right; this won't help. | | 3rd way | 1.)(a or g) ^ (a > b) ^ (g > d) premise | 2.) a or g and elim 1 | 3.) a > b and elim 1 | 4.) g > d and elim 1 | *5.)g temp assumpt. For what purpose? -intro? But you don't need -g | *6.)g > d send 4 | *7.)d >elim 5,6 | *8.) can't do anything with just g and d , stuck here 2 Correct; nothing you can do. | 4th way | 1.)(a or g) ^ (a > b) ^ (g > d) premise | 2.) a or g and elim 1 | 3.) a > b and elim 1 | 4.) g > d and elim 1 | *5.)~g temp. assumpt. For what purpose? -elim? But you don't need g. | *6.)a or g send 2 | *7.)a or elim 5,6 | *8.) stuck here beacuse since I used ~g as my assumption I either ahve to | use ~elim which requires me to show a beta and a ~beta, which I can not do | there is no other ~ other than the one I introduced as alpha and I don't | want to use >intro because because that will return a molecular formula and | I want an atomic one to do either or elim with (a or g) or >elim with (a>b) | OK--you've tried everything except he obvious: Assume -(bvd) and derive a contradiction. Another hint: Try deriving d and -d as the contradiction (I think b and -b will also work). From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 24 22:53:21 2005 for ; Thu, 24 Feb 2005 22:53:21 -0500 (EST) for ; Thu, 24 Feb 2005 22:53:21 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 22:49:39 -0500 03:49:39 -0000 j1P3nZx3004095 for ; Thu, 24 Feb 2005 22:49:35 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 22:49:35 -0500 (EST) Date: Thu, 24 Feb 2005 22:49:35 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: Re: subproofs To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU | Date: Thu, 24 Feb 2005 21:13:52 -0500 | From: Blake Martin | | I understood how the Elim and Intro stuff worked... it seems that none of it | applies to problem c, because there isn't a "lone" variable, and a lot of I'm not sure what you mean by a "lone" variable. First, there are no variables; this is a problem in propositional logic, not FOL. But if you mean a wff with a single letter ("P", as opposed to "PvQ", say), then I think you misunderstand the rules of inference. In a rule of inference whose conclusion is, say, "\beta", that "\beta" could be "PvQ". | Well, the only way I can see that c can be solved is to assume that one of | the consequents is false and show that the other must be true... That might be one way, but I doubt it'll work. My suggestion, in my previous posting on this problem, is to assume the entire conclusion is false, and work from there. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Thu Feb 24 22:53:38 2005 for ; Thu, 24 Feb 2005 22:53:38 -0500 (EST) for ; Thu, 24 Feb 2005 22:53:38 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Thu, 24 Feb 2005 22:45:16 -0500 03:45:15 -0000 j1P3jFx3004057 for ; Thu, 24 Feb 2005 22:45:15 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Thu, 24 Feb 2005 22:45:15 -0500 (EST) Date: Thu, 24 Feb 2005 22:45:15 -0500 Reply-To: Knowledge Representation & Reasoning From: "William J. Rapaport" Subject: CSE 4/563: PROJECT 1 CLARIFICATION To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: PROJECT 1 CLARIFICATION ------------------------------------------------------------------------ Several of you have asked whether you can use the Unix programs "lex" or "yacc" to do part 1 of the project, or whether you can use Prolog to do resolution for you. I've thought about this a bit more, and in both cases the answer is "no". Here's why: Suppose that I've taught you the algorithm for doing long division and asked you to use that algorithm to solve the following division problem: ________ 7)346,788 Now suppose that you solve this problem by getting the answer from a calculator. You've given me the answer, but not by the method I've asked you to practice. And that's the case even if your calculator used the long-division algorithm! Well, using lex, yacc, or Prolog to do the work for you is the same sort of thing. Let me give another analogy: Suppose, again, that I've taught you the long-division algorithm and asked you to implement it in Java. Suppose someone has written a Java method for doing long division, patented it (and kept the algorithm a secret), but distributed it freely on the web as "long-division.java" (or whatever the appropriate name would be; I don't speak Java :-). Now, if you handed in a program that solved the above division problem using "long-division.java" instead of coding your own version of it, that would be just like using a calculator to find the answer. In both cases, it's not the answer I care about; it's whether you understand the algorithm. Here's one more analogy: Now suppose that the code for "long-division.java" is public, and you turn that in instead of writing your own version. That's (almost) OK! I say "almost", because you can't just hand it in, downloaded from the Web or wherever. You need to tell me where you got it, who wrote it, etc. And, to show me that you understand the algorithm, you need to *fully* comment it (every single line of code!). Then it's OK to use it. Now, what about writing a resolution algorithm in Prolog? First, whether or not you know what resolution is (and there's no reason you should, since I haven't taught it to you yet!), here's a fact: Prolog works by using resolution; resolution is built into Prolog. So, using Prolog to do a resolution proof is like using a calculator to do long division. If you really want to use Prolog, feel free: BUT YOU HAVE TO IMPLEMENT RESOLUTION IN PROLOG! (Yes, that means you would have to use resolution to implement resolution!) Here's a (weak) analogy for that: Most programming languages that I know have multiplication built in as a primitive operation. Yet you could (and in some courses are asked to) implement multiplication as either repeated addition or recursively in terms of addition. You would be implementing multiplication in a language that already has multiplication built into it. Here's a stronger analogy: Once in CSE 111 (Great Ideas in Computer Science), I wrote a Pascal program for adding two small integers. That program was then compiled into an assembly-language program by a toy compiler we had running on a Mac. That compiler was, in turn, written in...Pascal! Which, of course, was compiled into a real assembly language for the Mac. Question: Which program was "really" doing the addition? I'm not sure there's a clear answer, but my point is that it's very much like writing a resolution algorithm in a language whose basic underlying method of computing is resolution. It can be done, and, for this project, should be (if you choose to use Prolog, that is). From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 25 09:46:53 2005 for ; Fri, 25 Feb 2005 09:46:52 -0500 (EST) for ; Fri, 25 Feb 2005 09:46:52 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 25 Feb 2005 09:46:18 -0500 14:46:18 -0000 j1PEkIx3006251 for ; Fri, 25 Feb 2005 09:46:18 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 25 Feb 2005 09:46:18 -0500 (EST) Date: Fri, 25 Feb 2005 09:46:18 -0500 Reply-To: "William J. Rapaport" From: "William J. Rapaport" Subject: CSE 4/563: HW 5 again To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: HW 5 again ------------------------------------------------------------------------ A student writes: | | The ~(PvQ) approach was the first one I tried... and I can see how it'd be | useful IF we could say ~(PvQ)=(~P^~Q) but I haven't found a way to go from | ~(PvQ) to anything useful. You can only have one temporary assumption, | right? Right, but you can make others. In particular, you could try to prove the equivalence you cite above. Actually, all you need to do is prove each of -P and -Q. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 25 12:43:38 2005 for ; Fri, 25 Feb 2005 12:43:38 -0500 (EST) for ; Fri, 25 Feb 2005 12:43:38 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 25 Feb 2005 12:42:57 -0500 17:42:57 -0000 j1PHgvx3007830 for ; Fri, 25 Feb 2005 12:42:57 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 25 Feb 2005 12:42:57 -0500 (EST) Date: Fri, 25 Feb 2005 12:42:57 -0500 Reply-To: "William J. Rapaport" From: "William J. Rapaport" Subject: CSE 4/563: MATERIAL CONDITIONAL To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: MATERIAL CONDITIONAL ------------------------------------------------------------------------ For those of you still bothered by the truth table for the material conditional (and why, for that matter, it's called the "material" conditional), here are some answers: First, one reason that "horseshoe" (>) is called the "material" conditional is to contrast it with: subjunctive conditional: if I were to sing, then you would be unhappy counterfactual conditional: if I had sung, then you would have been unhappy You can find out a lot more about the material (and other) conditionals by doing a Google search on "material conditional": http://www.google.com/search?hl=en&q=material+conditional From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 25 12:45:35 2005 for ; Fri, 25 Feb 2005 12:45:35 -0500 (EST) for ; Fri, 25 Feb 2005 12:45:35 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 25 Feb 2005 12:44:59 -0500 17:44:59 -0000 j1PHixx3007853 for ; Fri, 25 Feb 2005 12:44:59 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 25 Feb 2005 12:44:59 -0500 (EST) Date: Fri, 25 Feb 2005 12:44:59 -0500 Reply-To: "William J. Rapaport" From: "William J. Rapaport" Subject: CSE 4/563: AN INVALID ARGUMENT To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: AN INVALID ARGUMENT ------------------------------------------------------------------------ Is this a valid proof in our natural-deduction system for propositional logic? If not, why not? 1. P>Q : assumption *2. P : temporary assumption *3. P>Q : send 1 *4. Q : 3,2,>Elim 5. Q : return 4 The answer will be in the next listserv posting :-) From rapaport@cse.Buffalo.EDU Fri Feb 25 14:13:14 2005 for ; Fri, 25 Feb 2005 14:13:14 -0500 (EST) for ; Fri, 25 Feb 2005 14:13:14 -0500 (EST) Fri, 25 Feb 2005 14:13:13 -0500 (EST) Fri, 25 Feb 2005 14:13:13 -0500 (EST) Date: Fri, 25 Feb 2005 14:13:13 -0500 (EST) From: "William J. Rapaport" To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU, rapaport@cse.Buffalo.EDU Subject: Re: CSE 4/563: AN INVALID ARGUMENT ------------------------------------------------------------------------ Subject: Re: CSE 4/563: AN INVALID ARGUMENT ------------------------------------------------------------------------ I asked: | Is this a valid proof in our natural-deduction system for propositional | logic? If not, why not? | | 1. P>Q : assumption | *2. P : temporary assumption | *3. P>Q : send 1 | *4. Q : 3,2,>Elim | 5. Q : return 4 Here's the answer (don't read it till you've tried answering it!) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Answer: No; it's not valid. You can't return Q to line 5, because >Elim is not one of the legal rules for use of the Rule of Return. See: http://www.cse.buffalo.edu/~rapaport/563S05/sendreturn.html for the correct rule. >From line *4, you could have as the next lines: *5. P>Q : 2,4,>Intro 6. P>Q : return 5 But this gets you nowhere, since you already had P>Q on line 1. From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 25 14:43:31 2005 for ; Fri, 25 Feb 2005 14:43:30 -0500 (EST) for ; Fri, 25 Feb 2005 14:43:30 -0500 (EST) CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU; Fri, 25 Feb 2005 14:42:34 -0500 19:42:34 -0000 j1PJgYx3008419 for ; Fri, 25 Feb 2005 14:42:34 -0500 (EST) cse563-sp05-list@listserv.buffalo.edu; Fri, 25 Feb 2005 14:42:34 -0500 (EST) Date: Fri, 25 Feb 2005 14:42:34 -0500 Reply-To: "William J. Rapaport" From: "William J. Rapaport" Subject: CSE 4/563: PROPER SUBPROPOSITION To: CSE563-SP05-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: CSE 4/563: PROPER SUBPROPOSITION ------------------------------------------------------------------------ In lecture, I have several times used the phrase "proper subproposition" (or synonyms of that). Here is a webpage that formally defines it: http://www.cse.buffalo.edu/~rapaport/563S05/propersubwff.html From owner-cse563-sp05-list@LISTSERV.BUFFALO.EDU Fri Feb 25 21:05:00 2005 for ; Fri, 25 Feb 2005 21:04:59 -0500 (EST) for ; Fri, 25 Feb 2005 21:04:59 -0500 (EST) CSE563-