Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

S.R. Chauhan



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

Files






You might also like



Downloadable Citations