zbMATH — the first resource for mathematics

Optimal non-deterministic functional logic computations. (English) Zbl 0886.68034
Hanus, Michael (ed.) et al., Algebraic and logic programming. 6th international joint conference, ALP ’97 - HOA ’97, Southampton, GB, September 3–5, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1298, 16-30 (1997).
Summary: We show that non-determinism simplifies coding certain problems into programs. We define a non-confluent, but well-behaved class of rewrite systems for supporting non-deterministic computations in functional logic programming. We show the benefits of using this class on a few examples. We define a narrowing strategy for this class of systems and prove that our strategy is sound, complete, and optimal, modulo non-deterministic choices, for appropriate definitions of these concepts. We compare our strategy with related work and show that our overall approach is fully compatible with the current proposal of a universal, broad-based functional logic language.
For the entire collection see [Zbl 0871.00033].

68N17 Logic programming
68Q42 Grammars and rewriting systems
rewrite systems
PDF BibTeX Cite