All Outputs (2)

Hierarchies in classes of program schemes (1999)
Journal Article
Arratia-Quesada, A., Chauhan, S., & Stewart, I. (1999). Hierarchies in classes of program schemes. Journal of Logic and Computation, 9(6), 915-957. https://doi.org/10.1093/logcom/9.6.915

We begin by proving that the class of problems accepted by the program schemes of NPS is exactly the class of problems defined by the sentences of transitive closure logic (program schemes of NPS are obtained by generalizing basic non-deterministic w... Read More about Hierarchies in classes of program schemes.

On the power of built-in relations in certain classes of program schemes (1999)
Journal Article
Chauhan, S., & Stewart, I. (1999). On the power of built-in relations in certain classes of program schemes. Information Processing Letters, 69(2), 77-82. https://doi.org/10.1016/s0020-0190%2898%2900196-3

We completely classify the relative expressibilities of the program schemes of NPS augmented with the built-in relations: linear order; addition; multiplication; and BIT. We employ pebble games allied with some number theory.