Complete Symmetry in D2L Systems and Cellular Automata

Peter R.J. Asveld

Complete Symmetry in D2L Systems and Cellular Automata

Peter R.J. Asveld

Research output: Book/Report › Report › Other research output

30 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
Place of Publication	Enschede
Publisher	University of Twente
Number of pages	12
Publication status	Published - 1985

Publication series

Name	Memoranda Informatica
Publisher	University of Twente, Department of Computer Science
No.	INF-85-19
ISSN (Print)	0924-3755

Keywords

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

Access to Document

ReportFinal published version, 36.1 KB

1 Article

Complete Symmetry in D2L Systems and Cellular Automata
Asveld, P. R. J., 1986, In: International journal of computer mathematics. 19, 3-4, p. 211-223 13 p.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access
File
1 Citation (Scopus)

197 Downloads (Pure)

Cite this

@book{cbb89a99eebe442fb42cf02fe10a551c,

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 = "Asveld, \{Peter R.J.\}",

year = "1985",

language = "English",

series = "Memoranda Informatica",

publisher = "University of Twente",

number = "INF-85-19",

address = "Netherlands",

}

TY - BOOK

T1 - Complete Symmetry in D2L Systems and Cellular Automata

AU - Asveld, Peter R.J.

PY - 1985

Y1 - 1985

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

M3 - Report

T3 - Memoranda Informatica

BT - Complete Symmetry in D2L Systems and Cellular Automata

PB - University of Twente

CY - Enschede

ER -

Complete Symmetry in D2L Systems and Cellular Automata

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Research output

Complete Symmetry in D2L Systems and Cellular Automata

Cite this