Complete Symmetry in D2L Systems and Cellular Automata

P.R.J. Asveld

doi:10.1080/00207168608803517

Complete Symmetry in D2L Systems and Cellular Automata

P.R.J. Asveld

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

137 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 language	English
Pages (from-to)	211-223
Number of pages	13
Journal	International journal of computer mathematics
Volume	19
Issue number	3-4
DOIs	https://doi.org/10.1080/00207168608803517
Publication status	Published - 1986

Keywords

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

Access to Document

10.1080/00207168608803517

Asveld1986completeAccepted author version, 36.1 KB

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",

}

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

SN - 0020-7160

VL - 19

SP - 211

EP - 223

JO - International journal of computer mathematics

JF - International journal of computer mathematics

IS - 3-4

ER -

Complete Symmetry in D2L Systems and Cellular Automata

Abstract

Keywords

Access to Document

Fingerprint

Cite this