Beckett-Gray Codes

• Published in 2016
• Added on 2016-08-24

In this paper we discuss a natural mathematical structure that is derived from Samuel Beckett's play "Quad". This structure is called a binary Beckett-Gray code. Our goal is to formalize the definition of a binary Beckett-Gray code and to present the work done to date. In addition, we describe the methodology used to obtain enumeration results for binary Beckett-Gray codes of order $n = 6$ and existence results for binary Beckett-Gray codes of orders $n = 7,8$. We include an estimate, using Knuth's method, for the size of the exhaustive search tree for $n=7$. Beckett-Gray codes can be realized as successive states of a queue data structure. We show that the binary reflected Gray code can be realized as successive states of two stack data structures.

Links

• http://arxiv.org/abs/1608.06001v1
• http://arxiv.org/pdf/1608.06001v1

Other information

BibTeX entry

@article{BeckettGrayCodes,
	key = {BeckettGrayCodes},
	type = {article},
	title = {Beckett-Gray Codes},
	author = {Mark Cooke and Chris North and Megan Dewar and Brett Stevens},
	abstract = {In this paper we discuss a natural mathematical structure that is derived
from Samuel Beckett's play "Quad". This structure is called a binary
Beckett-Gray code. Our goal is to formalize the definition of a binary
Beckett-Gray code and to present the work done to date. In addition, we
describe the methodology used to obtain enumeration results for binary
Beckett-Gray codes of order {\$}n = 6{\$} and existence results for binary
Beckett-Gray codes of orders {\$}n = 7,8{\$}. We include an estimate, using Knuth's
method, for the size of the exhaustive search tree for {\$}n=7{\$}. Beckett-Gray
codes can be realized as successive states of a queue data structure. We show
that the binary reflected Gray code can be realized as successive states of two
stack data structures.},
	comment = {},
	date_added = {2016-08-24},
	date_published = {2016-10-09},
	urls = {http://arxiv.org/abs/1608.06001v1,http://arxiv.org/pdf/1608.06001v1},
	collections = {},
	url = {http://arxiv.org/abs/1608.06001v1 http://arxiv.org/pdf/1608.06001v1},
	urldate = {2016-08-24},
	archivePrefix = {arXiv},
	eprint = {1608.06001},
	primaryClass = {math.CO},
	year = 2016
}