The CSE seminars usually take place on Fridays from 11:00am until 12:00pm. Contact Rada Mihalcea to schedule a talk.
Click on titles to view the abstracts.
| Date | Speaker | Title |
| 4 November 2005 | Klaus Truemper |
Levels of Reasoning in Intelligent Systems and the Polynomial Hierarchy of Complexity Theory
Time: 11:00am - 12:00pm Location: F223 Abstract: We sketch a classification of reasoning in intelligent systems into levels. The first level involves direct solution of problems such as theorem proving or logic minimization. The second level requires the selection or construction of algorithms for problems of the first level. The third level involves selection or construction of algorithms of the second level, and so on. The classification may be viewed as an informal generalization of levels of the polynomial hierarchy of computational complexity, in the same sense that human induction based on limited data can be viewed as a generalization of mathematical induction. We cover a number of difficult reasoning problems arising in logic-based intelligent systems. These problems typically are at the second or even third level. In fact, the prevalence of these problems compels one to argue that intelligent systems necessarily involve reasoning at advanced levels. Example reasoning problems are automated processing of nonmonotonicity and incompleteness, discovery of futility of questioning in question-and-answer systems, and learning of effective questioning from prior results. For solution of the higher level reasoning problems, we discuss heuristic and exact methods. We also show that, when logic formulations are learned from data, then some reasoning problems at the second level of the polynomial hierarchy can be approximately solved by MINSAT instances, which are minimization versions of SAT instances. This fact and the observation that human decision making is often based on learning from limited data, possibly explain why humans are so surprisingly adept at solving higher level reasoning problems. |
| Date | Speaker | Title |
| 3 October 2005 | William Gasarch |
Finding Large Sets without Arithmetic Progressions
Time: 10:00am-11:00am Location: F223 Abstract: A sequence is 3-free if it has NO arithmetic progressions of size 3 (for example it cannot have {11,13,15} as a subset). What is the largest 3-free subset of (say) {1,...,10000} ? The question ^ÓWhat is the largest 3-free subset of {1,...,n} ?^Ô has been asked in the math literature and there are nice asympotic results known. For example 1) if n is LARGE then you can get a 3-free subset of {1,...,n} of size roughly n^{.62} 2) if n is LARGE then you can get a 3-free subset of {1,...,n} of size roughly n^{.9} 3) if n is LARGE then you can get a 3-free subset of {1,...,n} of size roughly n^{1-\epsilon} for any $\epsilon>0$. 4) if n is LARGE and A is a subset of {1,...,n} and |A|\ge n/100 then A MUST have an arithmetic progression of size 3 (so A CANNOT be 3-free). 5) if n is LARGE and A is a subset of {1,...,n} and |A|\ge n/10000 then A MUST have an arithmetic progression of size 3 (so A CANNOT be 3-free). 6) for ANY $epsilon>0$ if n is LARGE and A is a subset of {1,...,n} and |A|\ge \epsilon n then A MUST have an arithmetic progression of size 3 (so A CANNOT be 3-free). We discuss the literature on this problem AND what happens for reasonable sized $n$. |
| 21 Apr 2005 | Ding-Zhu Du |
Analysis of Greedy Approximation with Non-submodular Potential Function
Time: 11:00 am - 12:00 pm Location: F223 Abstract: There are many variations of analysis of greedy approximations with submodular potential function, such as greedy approximation for set-covering, greedy approximation for subset-interconnection design, etc. However, to our best knowledge, no technique has been found previously to analyze greedy approximations with non-submodular potential functions. In this talk, we introduce a new technique to do the job, which gives some long-standing greedy heuristics a theoretical foundation. The work is joint with Weili Wu at UT Dallas and P.M. Pardalos at U of Florida. Short bio: Dr. Ding-Zhu Du is an IPA working in NSF as a Program Director for Theory of Computing. He started this job on September 3, 2002. His home institution is University of Minnesota, where he is a professor in the Department of Computer Science and Engineering. His current research interests include design and analysis of approximation algorithms for combinatorial optimization problems with various applications in computer networking, telecommunication, VLSI designs, etc, especially in wireless networking and mobile computing. Dr. Du received his Ph.D. from University of California at Santa Barbara under supervision of Professor Ronald V. Book in 1985 and his M.S. from Chinese Academy of Sciences in 1982. Prior to joining to University of Minnesota, he has held positions at the Mathematical Sciences Research Institute at Berkeley, the Department of Mathematics at MIT, and at the Department of Computer Science at Princeton University. He has published about 140 journal papers and several books. He is the editor-in-chief for Journal of Combinatorial Optimization and also in editorial board for several other journals. There are 21 Ph.D.s graduated under his supervision. |
| 01 Apr 2005 | Martha Palmer |
Putting Meaning into Your Trees
Time: 11:00 am - 12:00 pm Location: F223 Abstract: The current success of applications of machine learning techniques to tasks such as part-of-speech tagging and parsing has kindled the hope that these same techniques might have equal or greater success in other areas such as lexical semantics. Advances in automated and semi-automated methods of acquiring lexical semantics would release the field from its dependence on well-defined sub-domains and enable broad-coverage natural language processing. However, supervised machine learning requires large amounts of publicly available training data, and a prerequisite for this training data is general agreement on which elements should be tagged and with what tags. With respect to lexical semantics, this type of general agreement has been strikingly elusive. A recent consensus on a task-oriented level of semantic representation to be layered on top of the existing Penn Treebank syntactic structures has been achieved. This level, know as the Proposition Bank, or PropBank, consists of argument labels for the semantic roles of individual verbs and similar predicating expressions such as participial modifiers and nominalizations. This talk will describe the PropBank verb semantic role annotation being done at Penn for both English and Chinese. The annotation process will be discussed as well as the use of existing lexical resources such as WordNet, Levin classes and VerbNet. Similar projects include the FrameNet Project at Berkeley and the Prague Tectogrammatics project. PropBank annotation is shallower than the Prague Tectogrammatics project and more broad coverage than FrameNet, in that every verb instance in the corpus has to be annotated. The talk will also briefly describe progress in developing automatic semantic role labelers based on this training data and investigations into the role of sense distinctions in improving performance. Speaker's biography: Martha Palmer is an Associate Professor in the Computer and Information Sciences Department of the University of Pennsylvania, but will be moving to the University of Colorado in the summer of 2005. She has been a member of the Advisory Committee for the DARPA TIDES program, the Chair of SIGLEX, the Chair of SIGHAN, and is now President of the Association for Computational Linguistics. Her early work on lexically based semantic interpretation formed the basis of the successful DARPA-funded message processing system, Pundit, and fostered a continuing interest in Information Extraction (ACE) and Machine Translation (TIDES). Her interest in lexical semantics and verb classes also led to her involvement in SENSEVAL and the development of English VerbNet and the English, Chinese and Korean Proposition Banks. |
| 11 Feb 2005 | Saad Mneimneh |
siRNA Design and RNA-RNA Interaction Algorithms
Time: 11:30 am - 12:30 pm Location: F223 Abstract: A small interfering RNA (siRNA) can be used to silence a given gene by targeting its messenger RNA: The siRNA binds to the RNA and destroys it. Although RNAs are single-stranded molecules, they usually fold. The problem of RNA folding has been studied extensively in the literature and many efficient algorithms for determining the optimal (minimum energy) folding of an RNA molecule have been developed. These algorithms can be used to identify single-stranded regions (the unfolded regions) of a folded RNA which are believed to be hot spots for potential siRNA bindings and, therefore, could help in the design of effective siRNAs. However, there is no clear consensus as to which happens first: RNA folding or siRNA binding. This motivates the RNA-RNA interaction problem where folding and binding occur simultaneously. The general problem of optimally folding two interacting RNAs becomes NP-hard and some constant approximation algorithms for the problem exist. The special case of siRNA binding can be solved in polynomial time; however, the relation between the energy of the obtained structure and the effectiveness of the siRNA in silencing the target RNA needs to be investigated. Speaker's biography: Saad Mneimneh is an assistant professor in the department of computer science and engineering at SMU. He receives his MS and Ph.D. degree from the Massachusetts Institute of Technology in 1997 and 2002 respectively. He received his BE from the American University of Beirut in 1995. His research interests include switching and routing algorithms, graph problems, and biology. |
| 16 Feb 2005 | Mehrdad Nourani |
New Challenges in Testing High-Speed System-on-Chips
Time: 11:00 am - 12:00 pm Location: F223 Abstract: As technology is shrinking towards 50 nm and the working frequency is going into the multi gigahertz range, many test-related issues must be revisited. These challenges include gigahertz fault modeling, signal integrity, power during test and test pattern compression. The effect of interconnects on functionality and performance of system-on-chips is becoming dominant. More specifically, distortion (integrity loss) of signals traveling on high-speed interconnects can no longer be ignored. In this work, we extend the conventional boundary scan architecture to allow testing signal integrity in SoC interconnects. Our extended JTAG architecture collects and outputs the integrity loss information using the enhanced observation cells. The architecture fully complies with the JTAG standard and can be adopted by any SoC that is IEEE 1149.1 compliant. We also discuss a test pattern generation algorithm aiming at signal integrity faults on long interconnects and a simple yet efficient compression scheme that can be employed by an ATE to minimize the scan-in delivery time. Speaker's biography Mehrdad Nourani received his BS/MS degree in Electrical Engineering from the University of Tehran, and Ph.D. in Computer Engineering from Case Western Reserve University, Cleveland, Ohio. Since August 1999 he has been on the faculty of the University of Texas at Dallas, where he is currently Associate Professor of Electrical Engineering and a member of CICS (Center for Integrated Circuits and Systems). Dr. Nourani has received the Texas Telecommunications Consortium Award (1999), the Clark Foundation Research Initiation Grant (2001), the National Science Foundation Career Award (2002) and Cisco Systems URP Award (2004). |
| 3 Dec 2004 | Abdennour El Rhalibi |
Topics in Computer Game Education and Research
Time: 11:00 am - 12:00 pm Location: B155 Abstract: Speaker's biography: Abdennour El Rhalibi is Principal Lecturer in Computer Games Technology at the Liverpool John Moores University. |
| 12 Nov 2004 | Vasile Rus |
Using World Knowledge in Question Answering
Time: 11:00 am - 12:00 pm Location: F223 Abstract: Question Answering (QA) promises to provide short snippets of text that contain the actual answer to a question rather than a list of documents traditionally returned by text retrieval systems. State of the art QA systems have acceptable performance at handling factual questions. In this talk, advanced techniques for handling deeper questions are presented. We argue that world knowledge embedded in online dictionaries helps boosting state of the art Question Answering systems and that this knowledge, if encoded in an expressive computational representation, is very useful to justify the correctness of retrieved answers. Our source of world knowledge is WordNet, an electronic lexical database, which groups English words based on lexico-semantic principles, in hierarchies of concepts. We show few methods on how to map WordNet concept definitions onto a first order logic, simple natural language based knowledge representation, called the logic form, and further into world knowledge axioms that are used to automatically justify the correctness of answers along lexico-semantic chains among concepts. Speaker's biography: Dr. Vasile Rus earned his Masters of Science in Computer Science and Doctor of Philosophy in Computer Science degrees from Southern Methodist University at Dallas, Texas in May 1999 and May 2002, respectively. His research interests include intelligent systems, software engineering, artificial intelligence, natural language processing, knowledge representation based on natural language, question answering. His professional interests are mainly focused on systems software, software systems analysis and design, configuration management. Dr. Rus is an Assistant Professor of Computer Science at the University of Memphis. He also holds an appointment at the Institute for Intelligent Systems, Fedex Institute of Technology. |
| 22 Oct 2004 | Krishnaiyan Thulasiraman |
QoS Path Problems in Communication Networks
Time: 11:00 am - 12:00 pm Location: F223 Abstract: Abstract: Network optimization refers to the class of optimization problems defined on graphs and networks. These problems occur in a wide variety of applications, in particular, VLSI CAD and Telecommunication Networks. Path and flow algorithms play a fundamental role in the study of network optimization problems. These algorithms, while important in their own right, also serve as building blocks in the design of algorithms for complex network optimization problems. In this talk we shall focus on algorithmic approaches to certain path problems called constrained path problems that require determining minimum cost paths satisfying a quality of service guarantee with respect to another metric. There are two classes of QoS path problems - single route selection and selection of a set of disjoint paths between a source and a destination. These problems are NP-hard and hence in the literature heuristics and approximation algorithms have been extensively studied. Whereas heuristics provide acceptable solutions with performance guarantees, approximation algorithms provide solutions with user specified performance guarantees. In this talk we shall present two classes of heuristic approaches ( including our own ) for both these problems. We shall also briefly review current research trends in the design of approximation algorithms as well as algorithms for path problems under inaccurate information. Speaker's biography: Dr. Krishnaiyan Thulasiraman holds the Hitachi Chair and is Professor in the School of Computer Science at the University of Oklahoma, Norman, U.S.A where he has been since 1994. He received his Ph.D. in electrical engineering from the Indian Institute of Technology, Madras, India in 1968. Dr. Thulasiraman's research interests have been in graph theory, combinatorial optimization, and algorithms emphasizing applications in a variety of areas in CS and EE. He has published extensively in archival journals, and coauthored with M.N.S.Swamy two text books "Graphs, Networks, and Algorithms" (1981) and "Graphs: Theory and Algorithms" (1992), both published by Wiley Inter-Science. Dr. Thulasiraman has received several awards and honors: Elected Member of the European Academy of Sciences (2002), IEEE Circuits and Systems Society Golden Jubilee Medal (1999), Fellow of the IEEE (1990), Senior Research Fellow of the Japan Society for Promotion of Science (1988), and Guest Professor of the German National Science Foundation (1990). He has held several administrative (including Vice-President) and technical positions with the IEEE Circuits and Systems society and other professional organizations. Recently he founded the Technical Committee on "Graph Theory and Computing "of the IEEE Circuits and Systems Society. |
| 17 Sep 2004 | Diane Cook |
Graph-based Learning and Discovery
Time: 11:00 am - 12:00 pm Location: F223 Abstract: The large amount of data collected today overwhelms researchers' abilities to interpret the data and discover interesting patterns. Knowledge discovery and data mining systems automate the interpretation process, but most approaches focus primarily on linear attribute-value based data. In this talk I present an approach to knowledge discovery and concept learning applied to graph-based structural databases. This technique, embodied in the Subdue system, can be used to perform a variety of data mining tasks including pattern discovery, supervised concept learning, and clustering. I will illustrate the power (and limitations) of this graph-based approach to learning and discovery using several case studies from domains including protein sequence data, detection of terrorist activities, and structural web search. Short bio: Dr. Cook is a professor in the Department of Computer Science and Engineering at the University of Texas at Arlington. She received her BS in Math/CS from Wheaton College in 1985, and her MS and PhD in Computer Science from the University of Illinois in 1987 and 1990, respectively. Dr. Cook heads projects in the areas of machine learning, data mining, parallel algorithms, robotics, and smart environments. Her work is supported by NSF, DARPA, and NASA, and has resulted in over 160 publications. She is an associate editor for IEEE Transactions on Systems, Man, and Cybernetics and is currently editing a book on smart environments. Descriptions of her research projects can be found at http://ranger.uta.edu/~cook. |
| 31 Mar 2004 | Robert Parks |
Dictionaries: The Art and Craft of Lexicography
Time: 11:30 am - 12:30 pm Location: F223 Abstract: Dictionaries: The Art and Craft of Lexicography. The title of this talk is taken from the title of a book by Sidney Landau, which was instrumental in bringing me into the world of lexicography. And the history of the book mirrors my experience in moving from appreciation of the role of computers in storing and manipulating words, to the current role of computers in the new corpus analysis. I will review how dictionaries are constructed and edited. Primary lexicography has changed significantly with the development of corpus analysis. And secondary lexicography has also changed significantly, with the creation of editing tools backed by frequency data. I will mention Natural Language Processing (NLP) concerns where possible. Perhaps everyone knows how machine readable dictionaries were first used to extract information for NLP databases. Now NLP is used to assist in dictionary construction (Kilgareff''s WASP), and NLP is also used to construct "definitions" automatically. The definition of "definition" and its relation to "designation" will be discussed. And I will speculate about where lexicographer's dreams and NLP aspirations overlap. About the speaker:Dr. Robert Parks is director and founder of the Wordsmyth dictionary |
| 19 Feb 2004 | Sharma Chakravarthy |
Mining Over Graphs: Performance and Scalability Issues Using Relational Database Techniques
Time: 11:15-12:20pm Location: F223 Abstract: Data mining aims at discovering useful and previously unknown patterns from the datasets. Database mining performs mining directly on data stored in Data Base Management Systems. Several SQL-based approaches for (association rule) mining have been studied in the literature. The main focus of this presentation will be to indicate how other types of mining can be done directly on databases. We have chosen graph mining as an example as its representation as well as processing are challenging considering the abstractions and computations supported by a DBMS. Graph mining is about identifying repeating instances of a substructure in a graph and compressing the graph (using the minimum description length principle) to derive a smaller graph. This approach is useful for detecting trends, frauds, similarity of web structures, protein structures etc. We will focus on the design and development of algorithms for graph mining (DB-SUBDUE) using relational DBMS. We develop several approaches for discovering the repetitive substructures in a graph. Each approach is analyzed and optimized further to improve its performance. Three different approaches - cursor-based, embedded SQL, and User Defined Functions (or UDFs) are studied. We compare the performance of database approaches with the performance of the main memory algorithm. We were able to improve upon the main memory algorithm both in performance and scalability aspects. In this presentation, I will first overview various projects that are underway at the IT Lab before discussing database approach to graph mining. About the speaker:Sharma Chakrvarthy received the B.E. degree in Electrical Engineering from the Indian Institute of Science, Bangalore, India. He did his M.Tech. from IIT, Bombay. He received M.S. and Ph.D degrees from the University of Maryland at College Park in 1981 and 1985, respectively. Currently, he is Professor in the Computer Science and Engineering Department at the University of Texas at Arlington. He has established the Information Technology Laboratory (or ITLab) and a distributed and parallel computing cluster at UTA. His current research interests include: enabling technologies for advanced information systems, mining/knowledge discovery (conventional, graph, and text), active capability, web technologies, stream data processing, and information security. Prior to joining UTA, he was with the CISE Department at the University of Florida, Gainesville. He also worked as a Computer Scientist at the Computer Corporation of America (CCA), Cambridge, MA and as a Member of Technical Staff at Xerox Advanced Information Technology (XAIT), Cambridge, MA. He has published over 100 papers in refereed International journals and conference proceedings. Sharma Chakravarthy has consulted for MCC, BBN, SRA Systems (India), Enigmatec, London, and RTI Inc. He has given tutorial on a number of database topics, such as active, real-time, distributed, object-oriented, and heterogeneous databases in North America, Europe, and Asia. He has given several invited and keynote addresses at universities and International conferences. He is listed in Who's Who Among South Asian Americans and Who's Who Among America's Teachers. |
| 05 Dec 2003 | Ovidiu Daescu |
Polygonal Chain Approximation with Applications
Time: 11:00-12:00 Location: GAB 543 Abstract: We discuss algorithms for approximating polygonal chains. We give a few results related to a new, query based approach to solve the problem, some of more general interest. The algorithms are based on standard geometric operations, and thus suitable for efficient implementation. Our approach also leads to an almost linear time, factor 2 approximation algorithm. We next show that with the Euclidean distance metric the query based approach can be used to obtain a sub-quadratic time exact algorithm for the planar version, if some condition on the input path holds, and sub-cubic time algorithms in any constant dimension larger than two (with no condition imposed on the input). Our algorithms are the first to achieve sub-quadratic or sub-cubic bounds. Since the queries involved in the algorithms answer questions with respect to the extent of the input in a given direction, we discuss possible applications in statistical analysis of data and in the manipulation of molecular configurations. About the speaker:Dr. Ovidiu Daescu received the Engineer Diploma in Computer Science and Automation from the Technical Military Academy, Bucharest, Romania, in 1991. From 1991 to 1995 he was a researcher and teaching lecturer at the same institution. After attending the University of Notre Dame in 1995, he received the M.S. and Ph.D. degrees in Computer Science from the Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN, in 1997 and 2000, respectively. Since September 2000, he is Assistant Professor in the Department of Computer Science, University of Texas at Dallas. His research interests include algorithm analysis and design, computational and discrete geometry and bio-medical computing. |
| 21 Nov 2003 | Fernando Gomez |
A computational view of verb predicates and semantic roles
Time: 11:00-12:00 Location: GAB 318 Abstract: In this talk, we present a method for defining verb predicates and semantic roles. The goal is to define verb predicates for every English verb. The definitions of the predicates are verified by an algorithm for semantic interpretation driven by the definition of the predicates. The algorithm offers a solution to the following semantic interpretation problems: determination of the meaning of the verb, identification of semantic roles, adjuncts, attachments of prepositional phrases, and interpretation of deverbal nominalizations. An interesting aspect of the algorithm is that the solution of all these problems is interdependent. The definitions of the predicates use WordNet 1.6 verb classes and the noun ontology. We have defined predicates for WordNet verb classes, which have been reorganized considerably following the criteria imposed by the interpretation algorithm. The WordNet ontology for nouns has also undergone reorganization and redefinition to conform with the entries in the semantic roles of the predicates. We have taken a top-down approach that defines generic abstract predicates subsuming semantically and syntactically a large class of verbs. WordNet verb classes have been mapped into these generic predicates. Some of this mapping has required from us to define new classes and to reclassify and/or redefine some WordNet classes and subclasses. The predicates form a hierarchy in which semantic roles and inferences are inherited by subpredicates from their superpredicates. After an introduction to these main topics, we will concentrate on recent developments such as the definition of verb predicates for individual verbs as different from verb classes, on the increasing role that the ontology for nouns plays in the overall approach, on the hierarchy of semantic roles, and on automatically generating semantically annotated corpora by using the algorithm and the predicates. About the speaker:Dr. Fernando Gomez is Professor of Computer Science and Director of the Artificial Intelligence Laboratory at University of Central Florida. His research covers a range of issues in natural language understanding including parsing, semantic interpretation, knowledge acquisition, knowledge representation and problem-solving. |
| 08 Aug 2003 | Carlo Strapparava |
Getting Serious about the Development of Computational Humor
Time: 11:00-12:00 Location: CURY 210 Abstract: Society needs humor, not just for entertainment. In the Web age, presentations become more and more flexible and personalized and they will require humor contributions (e.g. for electronic commerce developments, product promotion, getting selective attention, help in memorizing names, etc.). Even if deep modeling of humor in all of its facets is not something for the near future, there is something concrete that has been achieved and that can help in providing attention to the field. The talk refers to the results of HAHAcronym, a project devoted to humorous acronym production, a circumscribed task that nonetheless requires various generic components. The project, funded by the European Union, opens the way to developments for creative language, with applications in the world of advertisement. Speaker's biography: Carlo Strapparava is a Research Scientist in the Division of Cognitive and Communication Technologies at ITC-IRST (Instituto Trentino di Cultura, Center for Scientific and Technological Research). His research interests are in natural language semantics and pragmatics, discourse and dialogue processing, multimodal/multimedia interaction, electronic dictionaries, Lisp and functional programming. |
| 03 Apr 2003 | Ted Pedersen |
Using Measures of Semantic Relatedness for Word Sense Disambiguation
Time: 11:00-12:00 Location: GAB 310 Abstract: This talk presents a generalization of the Adapted Lesk Algorithm of Banerjee and Pedersen (2002) to a method of word sense disambiguation based on semantic relatedness. This is possible since Lesk's original algorithm (1986), which is based on gloss overlaps, can be viewed as a measure of semantic relatedness. We evaluate a variety of measures of semantic relatedness when applied to word sense disambiguation by carrying out experiments using the English lexical sample data of Senseval-2. We find that the gloss overlaps of Adapted Lesk and the semantic distance measure of Jiang and Conrath (1997) result in the highest accuracy. This talk is intended for a non-specialized audience, and includes an introduction to word sense disambiguation as well as the various measures of relatedness that are discussed. About the speaker:Ted Pedersen (PhD, Southern Methodist University) is an Assistant Professor of Computer Science at the University of Minnesota, Duluth. His research is in natural language processing and computational linguistics, and focuses on problems relating to semantic ambiguity in written text. He is the recipient of a National Science Foundation Faculty Early Career Development (CAREER) Award. |
| 14 Apr 2003 | Klaus Truemper |
Futile Questioning in Intelligent Systems
Time: 11:00-12:00 Location: GAB 317 Abstract: Humans have an well-developed ability to recognize when a line of questioning or of action is futile and thus should be abandoned. For example, a medical doctor never pursues all possible diagnoses until all possible tests have been done and all possible questions have been asked. Instead, the doctor rules out diagnoses much earlier, on the basis of rather limited information. Intelligent systems must have the same capability if they are to be effective in the above setting. In this lecture, we treat a particular case called futile questioning, where one must recognize when questioning should be terminated before all possible questions have been asked. We describe two solution approaches. The first one formulates the problem as a logic problem at the second level of the polynomial hierarchy. That problem is much harder than SAT or MINSAT unless P = NP. We describe partial results of ongoing research that indicate that effective solution is possible for large subclasses of the problem. The second method relies on learning logic from data. It assumes that the logic relationships used in the intelligent systems have been extracted from data. It turns out that the futile questioning problem can then be solved via MINSAT instances. That result allows effective solution for even larger instances than those covered by the first method. About the speaker:Professor Truemper has research interests in intelligent systems, integration of logic computation into programming languages, computational logic, data mining and learning logic, computer vision, natural language processing, medical diagnosis, traffic control, expert systems (including automated construction from data bases), design/control of automated processes, robotics, combinatorial optimization, graph theory. Currently, Dr. Truemper is a professor of computer science at University of Texas at Dallas. |