Article

New completeness results for lazy conditional narrowing

Authors:

Aart MiddeldorpAuthors Info & Claims

PPDP '04: Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming

Pages 120 - 131

https://doi.org/10.1145/1013963.1013979

Published: 24 August 2004 Publication History

Abstract

We show the completeness of the lazy conditional narrowing calculus (LCNC) with leftmost selection for the class of deterministic conditional rewrite systems (CTRSs). Deterministic CTRSs permit extra variables in the right-hand sides and conditions of their rewrite rules. From the completeness proof we obtain several insights to make the calculus more deterministic. Furthermore, and similar to the refinements developed for the unconditional case, we succeeded in removing all nondeterminism due to the choice of the inference rule of LCNC by imposing further syntactic conditions on the participating CTRSs and restricting the set of solutions for which completeness needs to be established.

References

[1]

S. Antoy. Constructor-based conditional narrowing. In Proc. 3rd PPDP, pages 199--206, 2001.

Digital Library

[2]

S. Antoy, B. Brassel, and M. Hanus. Conditional narrowing without conditions. In Proc. 5th PPDP, pages 20--31, 2003.

Digital Library

[3]

S. Antoy, R. Echahed, and M. Hanus. Parallel evaluation strategies for functional logic languages. In Proc. 14th ICLP, pages 138--152, 1997.

[4]

S. Antoy, R. Echahed, and M. Hanus. A needed narrowing strategy. J. ACM, 47(4):776--822, 2000.

Digital Library

[5]

F. Baader and T. Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.

Digital Library

[6]

H. Ganzinger. Order-sorted completion: The many-sorted way. TCS, 89:3--32, November 1991.

Digital Library

[7]

J. C. González-Moreno, M. T. Hortalá-González, and M. Rodríguez-Artalejo. Polymorphic types in functional logic programming. JFLP, 2001(1), 2001.

[8]

M. Hanus. A unified computation model for functional and logic programming. In Proc. 24th POPL, pages 80--93, 1997.

Digital Library

[9]

M. Marin and F. Piroi. Deduction and presentation in ρLog. In Proc. Mathematical Knowledge Management Symposium, volume 93 of ENTCS, pages 161--182, 2004.

[10]

A. Middeldorp and S. Okui. A deterministic lazy narrowing calculus. JSC, 25(6):733--757, 1998.

Digital Library

[11]

A. Middeldorp, S. Okui, and T. Ida. Lazy narrowing: Strong completeness and eager variable elimination. TCS, 167(1,2):95--130, 1996.

Digital Library

[12]

A. Middeldorp, T. Suzuki, and M. Hamada. Complete selection functions for a lazy conditional narrowing calculus. JFLP, 2002(3), March 2002.

[13]

J. J. Moreno-Navarro and M. Rodriguez-Artalejo. Logic programming with functions and predicates: The language BABEL. JLP, 12(3-4):191--223, 1992.

Digital Library

[14]

E. Ohlebusch. Termination of logic programs: Transformational methods revisited. AAECC, 12:73--116, 2001.

[15]

E. Ohlebusch. Advanced Topics in Term Rewriting. Springer, 2002.

Digital Library

[16]

C. Prehofer. Solving Higher-Order Equations: From Logic to Programming. Progress in Theoretical Computer Science. Birkhäuser, 1998.

Digital Library

[17]

T. Suzuki. Standardization theorem revisited. In Proc. 5th ALP, volume 1139 of LNCS, pages 122--134, 1996.

Digital Library

[18]

P. Viry. Elimination of conditions. JSC, 28:381--400, 1999.

Digital Library

[19]

T. Yamada, J. Avenhaus, C. Loría-Sáenz, and A. Middeldorp. Logicality of conditional rewrite systems. TCS, 236(1,2):209--232, 2000.

Digital Library

Cited By

López-Fraguas FRodríguez-Hortalá JSánchez-Hernández JLeuschel MPodelski A(2007)A simple rewrite notion for call-time choice semanticsProceedings of the 9th ACM SIGPLAN international conference on Principles and practice of declarative programming10.1145/1273920.1273947(197-208)Online publication date: 14-Jul-2007
https://dl.acm.org/doi/10.1145/1273920.1273947

Index Terms

New completeness results for lazy conditional narrowing

Recommendations

Conditional narrowing without conditions
PPDP '03: Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming

We present a new evaluation strategy for functional logic programs described by weakly orthogonal conditional term rewriting systems. Our notion of weakly orthogonal conditional rewrite system extends a notion of Bergstra and Klop and covers a large ...
Evaluation strategies for functional logic programming

Recent advances in the foundations and the implementations of functional logic programming languages originate from far-reaching results on narrowing evaluation strategies. Narrowing is a computation similar to rewriting which yields substitutions in ...
Conditional narrowing modulo a set of equations

Narrowing is a universal unification procedure for equational theories given by a canonical term rewrite system. In this paper we introduce conditional narrowing modulo a set of conditional equations and give a full proof of its correctness and ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PPDP '04: Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming

August 2004

260 pages

ISBN:1581138199

DOI:10.1145/1013963

General Chair:
Eugenio Moggi
University of Genova, Italy
,
Program Chair:
David S. Warren
Stony Brook University & XSB, Inc., USA

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PPDP04

Sponsor:

PPDP04: Principles and Practice of Declarative Programming 2004

August 24 - 26, 2004

Verona, Italy

Acceptance Rates

Overall Acceptance Rate 230 of 486 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
131
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

López-Fraguas FRodríguez-Hortalá JSánchez-Hernández JLeuschel MPodelski A(2007)A simple rewrite notion for call-time choice semanticsProceedings of the 9th ACM SIGPLAN international conference on Principles and practice of declarative programming10.1145/1273920.1273947(197-208)Online publication date: 14-Jul-2007
https://dl.acm.org/doi/10.1145/1273920.1273947

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten