Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A Complete Selection Function for Lazy Conditional Narrowing

Taro SuzukiContact Information and Aart MiddeldorpContact Information

(6)  Research Institute of Electrical Communication, Tohoku University, Sendai 980-8577, Japan
(7)  Institute of Information Sciences and Electronics, University of Tsukuba, Tsukuba 305-8573, Japan
Abstract
This paper is concerned with the lazy conditional narrowing calculus LCNC. In an earlier paper we proved that this calculus is complete with respect to normalizable solutions for the class of confluent but not necessarily terminating conditional rewrite systems without so-called extra variables in the conditional parts of the rewrite rules. Unfortunately, the proof does not provide any useful complete selection function, hence in implementations we need to backtrack over the choice of equations in goals in order to guarantee that all solutions are enumerated. This is in contrast to the unconditional case where completeness with respect to the leftmost selection function is known. In this paper we close the gap by proving the completeness of lcnc with respect to the leftmost selection strategy for the above-mentioned class of conditional rewrite systems.
Acknowledgements  Taro Suzuki is partially supported by the Grant-in-Aid for Encouragement of Young Scientist 11780204. Aart Middeldorp is partially supported by the Grantin-Aids for Scientific Research B 12480066 and C(2) 11680338 of the Ministry of Education, Science, Sports and Culture of Japan.

Contact Information Taro Suzuki
Email: taro@nue.riec.tohoku.ac.jp

Contact Information Aart Middeldorp
Email: ami@is.tsukuba.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb22
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)