Computer Sciences Seminar
Tuesday, March 14
12:30 PM, NAC 8/206

Tabled Resolution with Dynamic Reordering of Alternatives

Hai-feng Guo
State University of New York at Stony Brook

Abstract
Tabled logic programming (LP) systems have been applied to elegantly and quickly solving very complex problems (e.g., model checking). However, techniques currently employed for incorporating tabling in an existing LP system are either quite complicated due to considerable change to the LP system, or considerable overhead due to incomplete computation.

In this talk, we present a simple technique for incorporating tabling in existing LP systems based on dynamically reordering clauses containing variant calls at runtime. Our technique allows tabled evaluation to be performed with a single computation tree and without the use of complex operations such as freezing of stacks and heap. Its soundness and completeness can be shown decently. Our scheme can be incorporated in an existing logic programming system with a small amount of effort. It also facilitates exploitation of parallelism from tabled LP systems. Results of incorporating our scheme in the commercial ALS Prolog system are reported.

Bio
Dr. Haifeng Guo received his M.S. degree in computer science from Peking University in 1997, and his Ph.D. degree in Computer Science from New Mexico State University in 2001. After finishing his Ph.D. Program, he has been working as an NSF Postdoctoral fellow at SUNY Stony Brook. Dr. Guo's major research interests include computational logic, parallel computing and verification. Dr. Guo has been a session chair at the international symposium on Practical Aspects of Declarative Languages (PADL'02), and is currently a member of program committtee at Colloquium on Implementation of Constraint and Logic Programming Systems (CICLOPS'02).