An Inefficient Representation of the Empty Word

P.R.J. Asveld

An Inefficient Representation of the Empty Word

P.R.J. Asveld

Research output: Book/Report › Report › Professional

20 Downloads (Pure)

Abstract

We show that Post's system of tag with alphabet $\{0,1\}$, deletion number 3, productions $0\rightarrow 00$ and $1\rightarrow 1101$, and initial string $111\cdots 1$ (330 times) converges to the empty word after a very large number of rewriting steps.

Original language	English
Place of Publication	Enschede
Publisher	University of Twente, Department of Computer Science
Number of pages	6
Publication status	Published - 1996

Publication series

Name	Memoranda informatica
Publisher	University of Twente
No.	96-14
ISSN (Print)	0924-3755

Keywords

HMI-SLT: Speech and Language Technology

Access to Document

Asveld1996inefficientFinal published version, 70.9 KB

1 Chapter

An Inefficient Representation of the Empty Word
Asveld, P. R. J., 1996, A Dynamic and Quick Intellect: Paul Vitanyi 25 years @ CWI. Tromp, J. (ed.). Amsterdam: Centrum voor Wiskunde en Informatica, p. 11-18 8 p.
Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

Cite this

@book{090c8f586b5f4a4499c2edf120211059,

title = "An Inefficient Representation of the Empty Word",

abstract = "We show that Post's system of tag with alphabet $\{0,1\}$, deletion number 3, productions $0\rightarrow 00$ and $1\rightarrow 1101$, and initial string $111\cdots 1$ (330 times) converges to the empty word after a very large number of rewriting steps.",

keywords = "HMI-SLT: Speech and Language Technology",

author = "P.R.J. Asveld",

year = "1996",

language = "English",

series = "Memoranda informatica",

publisher = "University of Twente, Department of Computer Science",

number = "96-14",

}

TY - BOOK

T1 - An Inefficient Representation of the Empty Word

AU - Asveld, P.R.J.

PY - 1996

Y1 - 1996

N2 - We show that Post's system of tag with alphabet $\{0,1\}$, deletion number 3, productions $0\rightarrow 00$ and $1\rightarrow 1101$, and initial string $111\cdots 1$ (330 times) converges to the empty word after a very large number of rewriting steps.

AB - We show that Post's system of tag with alphabet $\{0,1\}$, deletion number 3, productions $0\rightarrow 00$ and $1\rightarrow 1101$, and initial string $111\cdots 1$ (330 times) converges to the empty word after a very large number of rewriting steps.

KW - HMI-SLT: Speech and Language Technology

M3 - Report

T3 - Memoranda informatica

BT - An Inefficient Representation of the Empty Word

PB - University of Twente, Department of Computer Science

CY - Enschede

ER -

An Inefficient Representation of the Empty Word

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Research output

An Inefficient Representation of the Empty Word

Cite this