Simulations between programs as cellular automata

Howard A. Blair, Fred Dushin, Polar Humenn

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 4th International Conference, LPNMR 1997, Proceedings
EditorsJurgen Dix, Ulrich Furbach, Anil Nerode
PublisherSpringer Verlag
Pages115-131
Number of pages17
ISBN (Print)9783540632559
DOIs
StatePublished - 1997
Event4th International Conference on Logic Programming and Non-Monotonic Reasoning, LPNMR 1997 - Dagstuhl Castle, Germany
Duration: Jul 28 1997Jul 31 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1265
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Conference on Logic Programming and Non-Monotonic Reasoning, LPNMR 1997
CountryGermany
CityDagstuhl Castle
Period7/28/977/31/97

Keywords

  • Cellular automaton
  • Logic program
  • Orbit
  • Simulation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Simulations between programs as cellular automata'. Together they form a unique fingerprint.

  • Cite this

    Blair, H. A., Dushin, F., & Humenn, P. (1997). Simulations between programs as cellular automata. In J. Dix, U. Furbach, & A. Nerode (Eds.), Logic Programming and Nonmonotonic Reasoning - 4th International Conference, LPNMR 1997, Proceedings (pp. 115-131). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1265). Springer Verlag. https://doi.org/10.1007/3-540-63255-7_9