[Fast Algorithms for Lyndon Words and State Transition Diagrams] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Fast Algorithms for Lyndon Words and State Transition Diagrams

(Click here to view the original thread with full colors/images)


Posted by: Andrius Kulikauskas

I've written algorithms for generating Lyndon words (aperiodic words) because I think of these as the "simple inputs" (the atoms) for analyzing cellular automata. I've also written algorithms for generating for each cellular automaton the state transition diagram that maps an input Lyndon word to an output Lyndon word. The cycles that result are the background patterns that the cellular automata is able to generate.

I've written these algorithms so that they are fast. I have codes each Lyndon word as the integer whose binary representation is the Lyndon word. For example, 29 codes 11101. This also saves on space.

Here is the notebook for generating Lyndon words.


Posted by: Andrius Kulikauskas

Here is the notebook for generating for each 2 color 3 cell cellular automata its state transition diagram.


Posted by: Andrius Kulikauskas

Here is a notebook for generating a graph of a state transition diagram.


Posted by: Andrius Kulikauskas

Here's the state transition diagram for Rule 110. Notice the large trees with many branchings.


Posted by: Andrius Kulikauskas

Rule 30's state transition diagram has large trees but with fewer branchings.


Posted by: Andrius Kulikauskas

Rule 105's state transition diagram has cycles surrounded by short sprouts.


Posted by: Andrius Kulikauskas

Here's a package with a list that consists of all Lyndon words (aperiodic words) of 1s and 0s of size less than or equal to 20 digits. For example, the number 57 codes 111001.

Use the Mathematica function BaseForm to convert them to binary and read them as strings of 1s and 0s. For example: BaseForm[#,2]&


Posted by: Andrius Kulikauskas

I generated the state transition diagram for each 2-color 3-cell cellular automaton for Lyndon words of length up to 15.

I order them in the list below by the length of the longest transient. Cellular automata 30, 86, 135, 149 all have a transient of length 322, which is to say, a periodic input (with period <= 15) that is followed by 322 steps before the first repetition, which is to say, before generating a pattern.

The list below gives a sense of the "classification" of the cellular automata in terms of their sophistication. The diagrams are thought-provoking.


{{322, 149}, {322, 135}, {322, 86}, {322, 30}, {313, 101}, {313, 89}, \
{313,
75}, {313, 45}, {192, 225}, {192, 169}, {192, 120}, {192, 106}, {48, \
107},
{46, 121}, {46, 97}, {46, 41}, {40, 193}, {40, 137}, {40, 124}, {40, \
110},
{33, 151}, {33, 145}, {33, 131}, {33, 118}, {33, 62}, {33, 22}, {31, \
181},
{31, 167}, {26, 182}, {26, 147}, {26, 125}, {26, 111}, {26, 94}, {26, \
65},
{26, 54}, {26, 9}, {25, 218}, {25, 91}, {25, 37}, {23, 161}, {23, \
122}, {23,
109}, {23, 103}, {23, 82}, {23, 73}, {23, 67}, {23, 61}, {23, 26}, \
{23, 25},
{21, 177}, {21, 163}, {21, 146}, {20, 183}, {20, 129}, {20, 114}, \
{20, 58},
{20, 18}, {19, 133}, {19, 126}, {18, 99}, {18, 57}, {16, 214}, {16, \
158},
{16, 148}, {16, 134}, {16, 93}, {16, 79}, {15, 215}, {15, 197}, {15, \
192},
{15, 164}, {15, 160}, {15, 159}, {15, 157}, {15, 141}, {15, 136}, \
{15, 92},
{15, 78}, {15, 69}, {15, 21}, {15, 20}, {15, 13}, {15, 7}, {15, 6}, \
{14,
248}, {14, 234}, {14, 230}, {14, 228}, {14, 224}, {14, 220}, {14, \
216}, {14,
206}, {14, 202}, {14, 199}, {14, 196}, {14, 194}, {14, 188}, {14, \
172}, {14,
168}, {14, 152}, {14, 140}, {14, 87}, {14, 70}, {14, 31}, {14, 28}, \
{13,
222}, {13, 198}, {13, 156}, {13, 59}, {11, 179}, {11, 96}, {11, 47}, \
{11,
40}, {10, 246}, {10, 233}, {10, 229}, {10, 227}, {10, 185}, {10, \
173}, {10,
123}, {10, 115}, {10, 104}, {10, 88}, {10, 74}, {10, 50}, {10, 49}, \
{10, 43},
{10, 35}, {10, 14}, {10, 11}, {9, 249}, {9, 235}, {9, 232}, {9, 217}, \
{9,
203}, {9, 190}, {9, 178}, {9, 142}, {9, 100}, {9, 83}, {9, 77}, {9, \
53}, {9,
44}, {9, 39}, {9, 33}, {9, 32}, {9, 27}, {8, 254}, {8, 251}, {8, \
250}, {8,
242}, {8, 213}, {8, 186}, {8, 176}, {8, 162}, {8, 144}, {8, 143}, {8, \
132},
{8, 130}, {8, 128}, {8, 105}, {8, 98}, {8, 84}, {8, 56}, {8, 23}, {7, \
252},
{7, 238}, {7, 226}, {7, 212}, {7, 195}, {7, 184}, {7, 153}, {7, 150}, \
{7,
117}, {7, 113}, {7, 102}, {7, 81}, {7, 60}, {5, 237}, {5, 231}, {5, \
219}, {5,
189}, {4, 211}, {4, 210}, {4, 209}, {4, 201}, {4, 165}, {4, 155}, {4, \
154},
{4, 139}, {4, 90}, {4, 46}, {3, 253}, {3, 247}, {3, 245}, {3, 243}, \
{3, 241},
{3, 239}, {3, 223}, {3, 221}, {3, 207}, {3, 205}, {3, 191}, {3, 187}, \
{3,
180}, {3, 175}, {3, 174}, {3, 171}, {3, 166}, {3, 127}, {3, 116}, {3, \
108},
{3, 95}, {3, 72}, {3, 66}, {3, 64}, {3, 63}, {3, 55}, {3, 52}, {3, \
38}, {3,
36}, {3, 29}, {3, 24}, {3, 19}, {3, 8}, {2, 255}, {2, 244}, {2, 236}, \
{2,
208}, {2, 200}, {2, 138}, {2, 119}, {2, 112}, {2, 85}, {2, 80}, {2, \
76}, {2,
71}, {2, 68}, {2, 51}, {2, 48}, {2, 42}, {2, 34}, {2, 17}, {2, 16}, \
{2, 15},
{2, 12}, {2, 10}, {2, 5}, {2, 4}, {2, 3}, {2, 2}, {2, 1}, {2, 0}, {1, \
240},
{1, 204}, {1, 170}}


Posted by: Andrius Kulikauskas

A state transition diagram for Rule 110.


Posted by: Andrius Kulikauskas

State transition diagram for Rule 30




Forum Sponsored by Wolfram Research

© 2004-2013 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings