Document Type

Report

Date

12-1995

Embargo Period

5-4-2012

Keywords

logic program, cellular automaton, orbit, simulation

Language

English

Disciplines

Computer Sciences

Description/Abstract

We present cellular automata on appropriate digraphs and show that any covered normal logic program is a cellular automaton. Seeing programs as cellular automata shifts attention from classes of Herbrand models to orbits of Herbrand interpretations. Orbits capture both the declarative, model-theoretic meaning of programs as well as their inferential behavior. Logically and intentionally different programs can produce orbits that simulate each other. Simple examples of such behavior are compellingly exhibited with space-time diagrams of the programs as cellular automata. Construing a program as a cellular automaton leads to a general method for simulating any covered program with a Horn clause program.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-97-01

Authors later published: Blair, H. A., Dushin, F., & Humenn, P. (1997). Simulations between programs as cellular automata (pp. 115-131). Springer-Verlag. doi:10.1007/3-540-63255-7_9

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.