Disproving Termination of O and S-like Combinators by Tree Automata
Abstract
Smullyan introduced many combinators, including the combinators M, O, and P. Recently, we showed that P is not terminating by a tree automaton using our SAT-based implementation. From observations on the results, we found similarities in the form of the M, O, and P rules, as well as similarities of the terms that disprove their termination. In addition, Curry and Feys introduced a family of combinators Sn. In this paper, we disprove the termination of a family of combinators that, generalizes the combinators M, O, and P, by a family of tree automata. Furthermore, we disprove the termination of the family of the combinators Sn by family of tree automata.
Fields of Study & Subjects
Logic
programming
and type systems
semigroups and automata theory
Computability
AI Algorithms
Publication details
- Journal / source
- Journal of Information Processing
- Volume
- 34
- Issue
- 0
- Pages
- 39–44
- Publication date
- 1 January 2026
- Language
- EN