[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #96

Originator: Richard Statman [Sta00]
Date: July 2000

Summary: Is the word problem for all proper combinators of order smaller than 3 decidable?

The order of a proper combinator is the number of variables on the left hand side of its defining equation. For instance, the K combinator has order 2. Is the word problem for all proper combinators of order smaller than 3 decidable? See [Sta00] for related results.

A related question is the word problem for the S-combinator (of order 3), see Problem #97.

References

[Sta00]

Rick Statman. On the word problem for combinators. In Leo Bachmair, editor, Rewriting Techniques and Applications, volume 1833 of Lecture Notes in Computer Science, pages 203–213, Norwich, UK, July 2000. Springer-Verlag.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]