Complete Symmetry in D2L Systems and Cellular Automata

P.R.J. Asveld

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
42 Downloads (Pure)

Abstract

We introduce completely symmetric D2L systems and cellular automata by means of an additional restriction on the corresponding symmetric devices. Then we show that completely symmetric D2L systems and cellular automata are still able to simulate Turing machine computations. As corollaries we obtain new characterizations of the recursively enumerable languages and of some space-bounded complexity classes.
Original languageEnglish
Pages (from-to)211-223
Number of pages13
JournalInternational journal of computer mathematics
Volume19
Issue number3-4
DOIs
Publication statusPublished - 1986

Fingerprint

Cellular automata
Cellular Automata
Turing machines
Symmetry
Recursively Enumerable Languages
Complexity Classes
Turing Machine
Corollary
Restriction

Keywords

  • HMI-SLT: Speech and Language Technology
  • D2L system
  • Cellular automaton
  • Symmetry
  • Recursively enumerable language (r.e.)
  • Space-bounded complexity class

Cite this

@article{2818d826a7e94712a0c42b965f50c31b,
title = "Complete Symmetry in D2L Systems and Cellular Automata",
abstract = "We introduce completely symmetric D2L systems and cellular automata by means of an additional restriction on the corresponding symmetric devices. Then we show that completely symmetric D2L systems and cellular automata are still able to simulate Turing machine computations. As corollaries we obtain new characterizations of the recursively enumerable languages and of some space-bounded complexity classes.",
keywords = "HMI-SLT: Speech and Language Technology, D2L system, Cellular automaton, Symmetry, Recursively enumerable language (r.e.), Space-bounded complexity class",
author = "P.R.J. Asveld",
year = "1986",
doi = "10.1080/00207168608803517",
language = "English",
volume = "19",
pages = "211--223",
journal = "International journal of computer mathematics",
issn = "0020-7160",
publisher = "Taylor & Francis",
number = "3-4",

}

Complete Symmetry in D2L Systems and Cellular Automata. / Asveld, P.R.J.

In: International journal of computer mathematics, Vol. 19, No. 3-4, 1986, p. 211-223.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Complete Symmetry in D2L Systems and Cellular Automata

AU - Asveld, P.R.J.

PY - 1986

Y1 - 1986

N2 - We introduce completely symmetric D2L systems and cellular automata by means of an additional restriction on the corresponding symmetric devices. Then we show that completely symmetric D2L systems and cellular automata are still able to simulate Turing machine computations. As corollaries we obtain new characterizations of the recursively enumerable languages and of some space-bounded complexity classes.

AB - We introduce completely symmetric D2L systems and cellular automata by means of an additional restriction on the corresponding symmetric devices. Then we show that completely symmetric D2L systems and cellular automata are still able to simulate Turing machine computations. As corollaries we obtain new characterizations of the recursively enumerable languages and of some space-bounded complexity classes.

KW - HMI-SLT: Speech and Language Technology

KW - D2L system

KW - Cellular automaton

KW - Symmetry

KW - Recursively enumerable language (r.e.)

KW - Space-bounded complexity class

U2 - 10.1080/00207168608803517

DO - 10.1080/00207168608803517

M3 - Article

VL - 19

SP - 211

EP - 223

JO - International journal of computer mathematics

JF - International journal of computer mathematics

SN - 0020-7160

IS - 3-4

ER -