Models and Properties of Abstract Symbol Systems
Abstract
In this article we discuss properties of the abstract symbol system - a computational device proposed in [3]. We define two formal models of the abstract symbol system based on classical computational devices and study their complexities. We prove the properties of the class PP that is suggested to be an invariant class for our device. Our models are shown to be superior (in terms of the computational complexity) to the devices they originated from. We deal with properties of complexity measures introduced for the abstract symbol system, namely computational and descriptional complexities. We prove the possibility of improvement in computational complexity for any function bounding the descriptional complexity.Downloads
Download data is not yet available.
Published
2012-01-26
How to Cite
Jakuš, D. (2012). Models and Properties of Abstract Symbol Systems. Computing and Informatics, 14(3), 253–270. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/229
Issue
Section
Articles