On the power of built-in relations in certain classes of program schemes

Chauhan, S.R.; Stewart, I.A.

Abstract

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.

Citation

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

• Journal Article Type: Article
• Publication Date: Jan 1, 1999
• Deposit Date: Jun 29, 2009
• Publicly Available Date: Jul 1, 2009
• Journal: Information Processing Letters
• Print ISSN: 0020-0190
• Electronic ISSN: 1872-6119
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 69
• Issue: 2
• Pages: 77-82
• DOI: https://doi.org/10.1016/s0020-0190%2898%2900196-3
• Keywords: Computational complexity, Descriptive complexity, Finite model theory, Program schemes.
• Public URL: https://durham-repository.worktribe.com/output/1579276
• Publisher URL: http://www.dur.ac.uk/i.a.stewart/Papers/power.ps