A Characterization of the Computational Power of Rule-based Visualization

Authors

Kenneth C. Cox, Washington University in St Louis
Gruia-Catalin Roman, Washington University in St Louis

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1993-01-01

Filename

WUCS-93-15.PDF

Technical Report Number

WUCS-93-15

Abstract

Declarative visualization is a paradigm in which the process of visualization is treated as a mapping from some domain (typically a program) to an image. One means of declaring such mappings is through the use of rules which specify the relationship between the domain and the image. This paper examines the computational power of such rule-based mappings. Computational power is measure using three separate criteria. The first of these uses the Chomsky hierarchy, in which computational power is treated as string-acceptance; with this criterion we are able to show that certain rule-based models are equivalent in power to Turing machines. The second criterion is the evaluation of recursive functions, while the third is a more informal consideration of the abstractive capabilities of the mapping.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7GB2286

Recommended Citation

Cox, Kenneth C. and Roman, Gruia-Catalin, "A Characterization of the Computational Power of Rule-based Visualization" Report Number: WUCS-93-15 (1993). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/302