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

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

doi:10.1016/s0020-0190(98)00196-3

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

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

Authors

S.R. Chauhan

Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor

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
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.
Publisher URL	http://www.dur.ac.uk/i.a.stewart/Papers/power.ps