@inproceedings{6b9876bf40d74a4e8607d8b900ecd80a,
title = "Simulations between programs as cellular automata",
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. Constnfing a program as a cellular automaton leads to a general method for simulating any covered program with a Horn clause program. This means that orbits of Horn programs are completely representative of orbits of covered normal programs.",
keywords = "Cellular automaton, Logic program, Orbit, Simulation",
author = "Blair, {Howard A.} and Fred Dushin and Polar Humenn",
note = "Publisher Copyright: {\textcopyright} 1997, Springer Verlag. All rights reserved.; 4th International Conference on Logic Programming and Non-Monotonic Reasoning, LPNMR 1997 ; Conference date: 28-07-1997 Through 31-07-1997",
year = "1997",
doi = "10.1007/3-540-63255-7_9",
language = "English (US)",
isbn = "9783540632559",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "115--131",
editor = "Jurgen Dix and Ulrich Furbach and Anil Nerode",
booktitle = "Logic Programming and Nonmonotonic Reasoning - 4th International Conference, LPNMR 1997, Proceedings",
}