# Some Grammatical Errors are Frequent, Others are Important

Leshem Choshen
Department of Computer Science
Hebrew University of Jerusalem
<EMAIL_ADDRESS>
Ofir Shifman
Department of Computer Science
Hebrew University of Jerusalem
<EMAIL_ADDRESS>
Omri Abend
Department of Computer Science
Hebrew University of Jerusalem
<EMAIL_ADDRESS>

###### Abstract

In Grammatical Error Correction, systems are evaluated by the number of errors
they correct. However, no one has assessed whether all error types are equally
important. We provide and apply a method to quantify the importance of
different grammatical error types to humans. We show that some rare errors are
considered disturbing while other common ones are not. This affects possible
directions to improve both systems and their evaluation.111All code and
annotations are found in https://github.com/borgr/GEC_BOTHER

##  1 Introduction

Grammatical Error Correction (GEC) is the task of correcting erroneous human
(mostly written; Siddharth et al., 2015) sentences. Predominantly, the
sentences are writings of non-natives (Wang et al., 2020). The use of this
correction could be quite diverse, it could help communication, educate
(O’brien, 2015; Tsai et al., 2020), evaluate (Gamon et al., 2013), reduce
language obstacles for learners (Wolfe et al., 2016) and more.222All code to
replicate as well as the gathered data could be found in
https://github.com/borgr/GEC_BOTHER

In this work, we focus on the recipients of the grammatically erroneous text,
rather than the writers. Doing so, we assess which types of errors are most
important to correct. We follow a simplifying assumption that some errors
inherently disrupt communication more than others, regardless of the sentence
context. Under this assumption we ask native speakers to express their
preference in partially erroneous sentences.

We manually annotate NUCLE (Dahlmeier et al., 2013) erroneous sentences to
find which ones are more crucial to correct (§3). We then extrapolate the
contribution of each type of error to the assessment of sentence correctness.
Specifically, we train a linear predictor of the sentence score as a function
of the amount of errors of each type (§4). From this we can not only know
which error types’ contribution is more important, without explicitly asking
annotators about it, but also assess the contribution of each type to any
typology of errors without further annotation.

Finally, computing the results on both the manual type system of NUCLE and
automatic taxonomies, we find that some of the most frequent errors are of low
importance and some infrequent ones are important, i.e., the errors which are
most important to correct for humans and for current evaluation differ.
Similarly, loss is implicitly weighted by frequency, but in this case
frequency and importance differ. Thus, the emphasis in training is on the
wrong types of errors.

##  2 Background

Typologies of GEC error types date back to the early days of the field Dale
and Kilgarriff (2011). Assuming each error stand by itself and is independent
from other errors, each error could be given a class. Following this
assumption manual annotations of typologies arrived with every dataset
(Dahlmeier et al., 2013; Shatz, 2020) differing between them and between
languages (Rozovskaya and Roth, 2019; Lee et al., 2021).

Later, ERRANT proposed a method for automatically extracting errors from text
and automatically annotating them with a set of rules (Bryant et al., 2017a).
This allowed to use the same annotation for any dataset in English. Lately,
SErCl (Choshen et al., 2020) proposed another typology, more fine-grained and
based on syntax. It comes with an automatic extraction for most languages
(depending on a part of speech tagger). SERRANT (Choshen et al., 2021)
combined the errors of ERRANT and SErCl to have a broader coverage, coming
from SERRANT but use the meaningful rules for ERRANT categories. We do not
give preferance to any of the methods and report results on each.

In most evaluation and literature, edit types are considered of equal
importance, for example the $M^{2}$ (Dahlmeier et al., 2013) scorer is based
on errors corrected, regardless of their types. There are works however that
show that models (Choshen and Abend, 2018b) and metrics (Choshen and Abend,
2018a) do not perform equally well on all error types. Specifically, they are
better on closed class types where given that a valid correction was made, the
reference is likely to correct in the same way and not perform another valid
correction. Frequent types are also better addressed by learnt models,
understandably. An exception to the above is Gotou et al. (2020) that focuses
on the most difficult types to correct. This is close in spirit to our work
and valuable in itself.

Knowing what is difficult to correct, as they suggest has merits. This
knowledge may allow building a curriculum and highlight model failures. Still,
we see our question as a more central one to the field, one that may shape the
focus of future contributions for both models and evaluation. Difficulty to
learn may change with technology, but what is perceived important to pursue
will not. We propose an ideal for GEC to pursue and a way to measure it.

Another work that is similar to ours in spirit is Tetreault et al. (2017),
proposing to follow fluency rather that correct errors. In a sense, the most
important errors to correct are those that most improve fluency of a text.

##  3 Annotation

To get a reliable ranking of error importance we follow previous works’
methodology. First, we do not ask annotators about grammaticality, as grammar
in non-professionals is implicit and often even judged unimportant (Loewen et
al., 2009). Instead, we ask annotators the extent to which a text is
bothersome, following Wolfe et al. (2016); Graham et al. (2015b). They found
that impolite messages bothered job interviewers and to a lower extent so did
ungrammatical writing. However, impolite texts were undeservedly judged
ungrammatical, showing judges mix between the two.

We ask crowd annotators to directly assess the extent to which sentences need
correction. We adapt the methodology of Graham et al. (2016) for assessing
fluency of a text to assess instead how bothering a text is. Specifically,
annotators were asked to move a slide to indicate how much they agree with the
following: ”The English mistakes in the following text bother me (1 = it
doesn’t bother me at all, 100 = it really bothers me)”. All other details
follow the original work.

We note that while we choose to follow common wording, other wordings may be
acceptable and might even have slightly different results. For example,
framing the question in terms of the context in which the sentence is written
may produce different results. A sentence may be harshly judged in an academic
writing but not in an email.

Every batch of sentences sent to the crowd contained 100 sentences ensuring
that each annotator would produce at least 100 annotations. Only annotators
from the United States with high (95%¿) acceptance rate and that reported they
were English natives were accepted. This is to reduce noise due to faulty
judgments and disagreements due to different countries of origin (e.g., native
Australian citizens). Annotators were given 0.5$ per batch, 333The payment is
not high, but by personal communication with the authors of Direct Assessment,
high payment lures fraudulent annotators. Moreover, annotating the whole of
NUCLE took less than two days, indicating that the payment was not deemed as
low by the crowd annotators. and their answers were normalized to follow a
standard normal distribution (henceforth Z-score).

To allow filtering the data, each batch contains 3 types of sentences. 15
unique sentences which contain no mistakes. 70 unique sentences with at least
one error. 15 sentences which were sampled from a a pre-sampled set of 400
sentences. The latter were repeatedly shown in different batches. The choice
of 400 sentences was made to make sure a single annotator would not often see
the same sentences and that we will have enough repetitions for each of the
400 to find outlying annotators.

###  3.1 Dataset

We chose to annotate NUCLE (Dahlmeier et al., 2013) containing about 59K
sentences. Out of which we separated sentences with and without errors to two
groups. Additionally, we filtered out sentences with less than 7 words, or
ones that contained one of the strings: http, &, [, ], *, ”, ; to reduce non-
English sentences. We also normalized spaces, deleting spaces after ) or
before (, !, %, ., $, / and a comma (,).

We sent 58K sentences for annotation, which roughly corresponds to annotating
each sentence with errors twice, plus multiple annotations of the 400
repetitive sets and about 8.7K annotations for grammatical sentences.

###  3.2 Filtering

An important aspect when asking for direct assessment from crowdworkers is to
filter low quality annotations. We proceed to discuss this procedure.

Annotators that took less than 350 seconds for 100 sentences were removed.
Removing about 5% of annotators (see Figure 1). This is expected to remove
annotators who did not pay attention or mistakenly skipped a large number of
sentences.

Among the remaining annotators, we made sure each judged the grammatical
sentences to be better than the erroneous ones. Under the hypothesis that
ungrammatical sentences had a lower score, we made a t-test for each
annotator. If the grammatical sentences did not have a significantly higher
average sentence score than the ungrammatical ($p<0.05$), we filtered out all
the annotations made by the annotator. Overall about 2% of annotators were
filtered in this method.

Last, we compared the Pearson correlation between each annotator’s Z-scores
and the rest’s on the repeating sentences. Following Graham et al. (2015a),
correlation only took into account sentences with at least 15 responses as the
average is noisy. Annotators with strong negative correlations ($>-0.4$) were
filtered out. Overall, these procedures filtered about 10% of the annotators.

Furthermore, we found most annotators filtered in the previous stages had
negative correlation, which validates this methodology, as the different
filtering methods agree. Raising the bars of either P or minimum time had
diminishing gains in terms of finding negative correlation annotators.

While the annotations still contain noise, trying to filter out more with
harsher thresholds produced similar results (See §5) with more variance (due
to less data). This suggests that the results are robust to this filtering and
are reliable in that sense.

Figure 1: Right: Working time per batch for one pass over NUCLE. Left: the
tail of the distribution and in red the threshold below which annotators were
filtered

##  4 Score per Type

As mentioned above, annotations are done on a sentence level. While this means
we need to extrapolate which type of error is more important, it also allows
us to do it for different error annotation schemes.

We experiment with both the manual annotated error types in the NUCLE corpus
and automatic error types. Specifically, we analyse both automatic error types
of ERRANT (Bryant et al., 2017b) and SErCL (Choshen et al., 2020). We do not
analyze SERRANT (Choshen et al., 2021) as it is based on the two latter and is
hence quite similar.

Given the sentence scores we train a linear classifier with the error types
count as features. For each sentence, we extract the number of times each type
of error was found in it. We then train the linear regression to predict the
annotation score based on these features.

The output weights can be understood as the contribution of each type to the
sentence annoyance levels. Note that in doing so, we assume a linear
contribution of types. Namely, that when multiple types appear or a single
type appears more than once, their contribution is additive. Future work may
consider more complex extrapolations with softer assumptions.

Because the actual weights are hard to interpret, we focus on the ranks of
each phenomena. In other words, we look to see who got the largest weight, the
second largest and so on, rather than the actual distribution of weights that
were assigned (we report those for completeness in App. A).

We extrapolate for each NUCLE type, for SErCl’s most frequent types, for
ERRANT’s types and for ERRANT’s types without sub-categorization to
replacement additions and deletions.

##  5 Results

Figure 2: Importance ranks of each SErCl type. Std in error bars. Figure 3:
Importance ranks of each ERRANT type. Std in error bars. (fine-grained ERRANT
types in Appendix A.)  Figure 4: Importance ranks of each NUCLE type. Std in
error bars.

We present the ranking for SErCl in Fig. 2, for ERRANT in Fig. 3 (Fine grained
with insertion deletion and modification in App. A) and for NUCLE in Fig. 4.
We also report the actual weight in appendix A and note that those are more
variable and harder to reason about.

We see that despite the large sample there is still variance. Thus, some error
types are not significantly harder than others. Still, which errors are easy,
medium or hard is clear.

We find that, across the typologies, verb inflection and verb errors in
general are among most bothering errors. So are orthography errors,
unnecessarily added tokens, wrong determiner and other errors.

On the other side of the spectrum we can find missing tokens, inflection,
morphology and others. Several errors related to determiners are also low
ranking.

##  6 Discussion and Conclusion

Most metrics disregard the error type, at least in principal (Choshen and
Abend, 2018a, In practice errors are unintentionally weighted differently, but
not by design;). This has been criticized and difficulty of correction was
suggested to address it (Gotou et al., 2020). Our results show that not only
some errors are more important to correct than others, those are not
determined by frequency in the data nor in the difficulty to correct.
Determiners are extremely common and a closed class (Choshen and Abend,
2018b), making them more important to correct to gain high scores in metrics,
but those errors are not considered very important by humans. Similarly,
orthographic errors are very easy to correct, but they are considered very
annoying and important to correct.

We also performed initial studies with weighting training spans by giving each
token its weight by the importance of the error (non-error tokens weight is
constant). Unsurprisingly, the network improves over the relevant errors more
than on others or the baseline, although not by a large margin.

##  7 Acknowledgments

We thank Dan Malkin for the experiments with weighted gradients.

## References

  * Bryant et al. (2017a) Christopher Bryant, Mariano Felice, and Edward Briscoe. 2017a.  Automatic annotation and evaluation of error types for grammatical error correction.  Association for Computational Linguistics.
  * Bryant et al. (2017b) Christopher Bryant, Mariano Felice, and Ted Briscoe. 2017b.  Automatic annotation and evaluation of error types for grammatical error correction.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 793–805, Vancouver, Canada. Association for Computational Linguistics.
  * Choshen and Abend (2018a) Leshem Choshen and Omri Abend. 2018a.  Automatic metric validation for grammatical error correction.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1372–1382, Melbourne, Australia. Association for Computational Linguistics.
  * Choshen and Abend (2018b) Leshem Choshen and Omri Abend. 2018b.  Inherent biases in reference-based evaluation for grammatical error correction.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 632–642.
  * Choshen et al. (2020) Leshem Choshen, D. Nikolaev, Yevgeni Berzak, and Omri Abend. 2020.  Classifying syntactic errors in learner language.  _ArXiv_ , abs/2010.11032.
  * Choshen et al. (2021) Leshem Choshen, Matanel Orenm Dmitry Nikolaev, and Omri Abend. 2021.  Serrant: a syntactic classifier for english grammatical error types.  _arXiv preprint arXiv:2104.02310_.
  * Dahlmeier et al. (2013) Daniel Dahlmeier, Hwee Tou Ng, and Siew Mei Wu. 2013.  Building a large annotated corpus of learner English: The NUS corpus of learner English.  In _Proceedings of the Eighth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 22–31, Atlanta, Georgia. Association for Computational Linguistics.
  * Dale and Kilgarriff (2011) R. Dale and Adam Kilgarriff. 2011.  Helping our own: The hoo 2011 pilot shared task.  In _ENLG_.
  * Gamon et al. (2013) Michael Gamon, Martin Chodorow, Claudia Leacock, and Joel Tetreault. 2013.  Grammatical error detection in automatic essay scoring and feedback.  In _Handbook of automated essay evaluation_ , pages 273–288. Routledge.
  * Gotou et al. (2020) Takumi Gotou, Ryo Nagata, Masato Mita, and Kazuaki Hanawa. 2020.  Taking the correction difficulty into account in grammatical error correction evaluation.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 2085–2095.
  * Graham et al. (2016) Yvette Graham, Timothy Baldwin, Meghan Dowling, Maria Eskevich, Teresa Lynn, and L. Tounsi. 2016.  Is all that glitters in mt quality estimation really gold standard.  In _COLING 2016_.
  * Graham et al. (2015a) Yvette Graham, Timothy Baldwin, and Nitika Mathur. 2015a.  Accurate evaluation of segment-level machine translation metrics.  In _Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1183–1191.
  * Graham et al. (2015b) Yvette Graham, Timothy Baldwin, A. Moffat, and J. Zobel. 2015b.  Can machine translation systems be evaluated by the crowd alone.  _Natural Language Engineering_ , 23:3 – 30.
  * Lee et al. (2021) Myunghoon Lee, Hyeonho Shin, Dabin Lee, and Sung-Pil Choi. 2021.  Korean grammatical error correction based on transformer with copying mechanisms and grammatical noise implantation methods.  _Sensors_ , 21(8).
  * Loewen et al. (2009) Shawn Loewen, Shaofeng Li, Fei Fei, Amy Thompson, Kimi Nakatsukasa, Seongmee Ahn, and Xiaoqing Chen. 2009.  Second language learners’ beliefs about grammar instruction and error correction.  _The Modern Language Journal_ , 93(1):91–104.
  * O’brien (2015) J. O’brien. 2015.  Consciousness-raising, error correction and proofreading.  _Journal of the Scholarship of Teaching and Learning_ , 15:85–103.
  * Rozovskaya and Roth (2019) Alla Rozovskaya and Dan Roth. 2019.  Grammar error correction in morphologically rich languages: The case of Russian.  _Transactions of the Association for Computational Linguistics_ , 7:1–17.
  * Shatz (2020) Itamar Shatz. 2020.  Refining and modifying the efcamdat: Lessons from creating a new corpus from an existing large-scale english learner language database.  _International Journal of Learner Corpus Research_ , 6(2):220–236.
  * Siddharth et al. (2015) Siddharth, Sandeep Swarnakar, and Sandeep Sharma. 2015.  Grammatical error correction in oral conversation.  _International Journal for Scientific Research and Development_ , pages 50–52.
  * Tetreault et al. (2017) Joel R. Tetreault, Keisuke Sakaguchi, and Courtney Napoles. 2017.  Jfleg: A fluency corpus and benchmark for grammatical error correction.  In _EACL_.
  * Tsai et al. (2020) C. Tsai, Jhih-Jie Chen, Chingyu Yang, and Jason J. S. Chang. 2020.  Lingglewrite: a coaching system for essay writing.  In _ACL_.
  * Wang et al. (2020) Yu Wang, Yuelin Wang, J. Liu, and Zhuo Liu. 2020.  A comprehensive survey of grammar error correction.  _ArXiv_ , abs/2005.06600.
  * Wolfe et al. (2016) Joanna Wolfe, Nisha Shanmugaraj, and Jaclyn Sipe. 2016.  Grammatical versus pragmatic error: Employer perceptions of nonnative and native english speakers.  _Business and Professional Communication Quarterly_ , 79(4):397–415.

##  Appendix A Additional Graphs

We present here the fine-grained ERRANT labels and the linear regression
weights with their std. Note that negative score does not necessarily means
that this type is considered positive by annotators, as there is a baseline
too (so it might only be less severe than other errors).

Figure 5: Importance ranks of each coarse-grained ERRANT types. Std in error
bars. Figure 6: Importance weights of each fine-grained ERRANT types. Std in
error bars. Figure 7: Importance weights of each coarse-grained ERRANT types.
Std in error bars. Figure 8: Importance weights of each SErCl type. Std in
error bars. Figure 9: Importance weights of each NUCLE type. Std in error
bars.


determined to be complete by the binding of a _base completion gadget_ (Figure
54), returning a signal to $t_{0}$ that causes another set of signals to be
propagated that enable the placement of a base tile in the $+z$ direction.

Figure 51: Cooperative growth along blue base tiles allows for counting tiles
(purple) to reach the furthestmost tile. A duple (green) allows for the
counting row to sense when it must extend the base by an additional tile by
cooperatively binding to both the furthest counting tile and a ‘0’ on the
encoding supertile. Messages are sent to extend both the base tiles counting
the current base width and to extend the width of the base by 1. Figure 52:
Once the counting row reaches the ‘1’ tiles, this indicates the base is of the
correct width. This is sensed by a counting duple (black) which cooperatively
binds to both the counting row and the ‘1’ glue. Figure 53: After binding of
the black counting duple, the counting tiles dissolve and a signal is sent to
begin cooperative growth of the remainder of the base adjacent to the encoding
Figure 54: Base completion duple (white) allows for the base to detect when
tiles have extended the base along the entire edge of the initial encoding
supertile. A message returns to the initial tiles placed once all tiles of the
row adjacent to the encoding have been placed in the base.

####  3.3.3 Row 1 Tile Placement

Once the base is complete, a signal is sent to begin the decoding process of
the first row. Figure 55 demonstrates how this signal allows for a strength 2
glue to be exposed in the $+y$ axis, allowing for a base tile to generate
cooperative binding on top of the first directional tile. Unlike other
directional tiles, the directional tile of first tile of the first row encodes
the information that a row change tile is to be utilized, without the need for
sensing the directional tile prior (as there is no prior directional tile).
Once the directional tile binds, it then activates a glue allowing for the
cooperative binding of a decoder tile that determines if the origin tile is a
shape or fill tile. Additionally, this binding causes a signal to be passed
backwards through the base tile most recently placed such that it initiates
the growth of a _backing tile_. Backing tiles serve two main purposes; first,
to indicate to tiles of the first slice that they are adjacent to an exterior
edge, and any shape tile must encode exterior glues on its $-z$ face. Second,
backing tiles allow for the tiles in the topmost row of a slice to bind along
their top edge with strength 2 connections. The process by which this second
item proceeds is outlined in Section 3.3.6.

Once the decoder tile determines which type is to be placed, a glue is exposed
in the $+x$ direction to enable growth of the decoding tiles. Due to the
current decoding tile being the first tile of the row, we can guarantee that
at this point a neighbor detection gadget must bind to the recently placed
backing tile and the decoding tile (Figure 56). This binding of the neighbor
detection gadget with the backing tile additionally causes the backing tile to
activate a glue allowing for cooperative binding of another backing tile with
the base in the $+x$ direction. The decoding tile now contains all the
information regarding the tile type to place after binding with the neighbor
detection gadget. A strength 2 glue allows for the growth of an additional
decoder tile (mapping to the tile type indicated in the encoding assembly);
this enables cooperative binding of the tile type mapped between itself and
the base tiles (Figure 57). After the base tile and decoded tile of the shape
are connected with strength 2, signals are sent back through the decoder tiles
towards the directional tile which initiated growth. Upon passing this signal
to the decoder tile’s predecessor, all decoder tiles not bound to the
directional tile dissolve into size 1 junk (Figure 58). The decoder tile
adjacent to the directional tile activates a glue indicating for the next
directional tile to be placed, thus allowing for the placement of an
additional decoding tile.

Figure 55: The initial tile, once messages have been received that the base is
complete, initiates a signal which causes a base tile allow cooperative
binding of the first directional tile. Additionally, a glue initiating growth
of the first backing tile is exposed in the $+x$ direction Figure 56: Once
cooperative binding has occurred to dictate the decoding tile, glues are
activated on the $+x$ face of the decoding tile, allowing for cooperative
growth and binding of neighbor detection tiles. A strength 2 glue is exposed
upon binding with the neighbor decoding tile, allowing for a decoding tile to
be added which cooperatively places the tile encoded. Figure 57: Once the
row-1 tile binds to the base, it exposes a glue in the $-z$ axis that allows
for the cooperative binding of the fill/shape tile encoded by the first
location. Once cooperative binding occurs, a second glue is activated which
allows for a strength 2 connection between the shape/fill tile most recently
placed and its predecessor (in this case the base tile - the first row of
which contains glues and signals which allow for binding in this manner).
Additionally, when the detection duple binds to the backing tile, a signal is
sent to activate glues in both the $+x$ and $+y$ directions which allows for a
second tile to bind Figure 58: A message is passed backwards along the binding
edges such that the direction tile activates a glue which allows for the next
directional tile to bind. Additionally, the decoding tiles placed in support
of the prior encoded location of the shape deactivate all glues and become
junk to allow for the next tile of the encoding to be placed utilizing the
same path of voxels. Figure 59: Placement of encoded tiles continues, with
decoding tiles re-utilizing the same set of voxels to grow voxels further away
from the origin.

Tile additions continue also utilizing the direction change decoding
demonstrated in Section 3.3.1, until the final tile of the row is reached. At
this point growth continues by the standard process of directional tiles
allowing cooperative binding with the encoding structure, however switched to
direction ‘1’ growth. In order to enable the placement of encoding tiles via
direction ‘1’ growth, the backing tiles must be present in the new row to
allow for binding of neighbor detection gadgets. A _backing growth detector_
(see Figure 60)binds to the most recently placed backing tile and the base (or
backing) tile in the row prior. Binding of the backing growth detector allows
for a strength 2 glue to be turned on to enable the growth of a backing tile
in the $+y$ direction (Figure 61).

Figure 60: Backing growth detector (purple) binds to the outermost backing
tile and the base to signal to the backing tile to activate a strength 2 glue
in the $+y$ direction. Note that for following rows, the backing growth
detector will bind with two backing tiles Figure 61: Binding of the next
backing tile in order ready growth, allowing for binding of neighbor detection
tiles.

####  3.3.4 Row 2n Tile Placement

For each even numbered row, tiles grow in the ‘-’ direction; that is, the
first tile in the some row 2n is placed above the last tile of the prior row
(2n - 1) For row 0 growth, each additional tile placed took us further away
from the origin point (e.g., incrementing the $x$ value in the ($x,\>y,\>z$)
position tuple). In the case of ‘-’ direction growth, tiles of the slice are
placed at the furthest-most $x$ value of the slice and decrement to 0. While
the decoding tiles of the first row bind initially to decoding tiles, the most
recently placed tile and directional tiles, the decoding tiles of ‘-’
direction growth cooperatively bind with the prior decoding tile and a base
tile. Growth occurs in two cases; in the case of the first tile of a row of
direction 1 growth, tiles bind until they reach the furthest-most base tile.
When reaching the outermost base tile, a _direction ‘1’ detection gadget_
binds with the outermost base tile and the furthest placed decoding tile
(Figure 62). At this point, a glue is activated on the decoding tile’s $+y$
face, allowing for cooperative growth to continue. This allows for cooperative
growth along the previously placed tiles until no longer possible, at which
point a neighbor detection gadget is able to bind to the decoding tile and the
neighbor tile (in this case a backing tile, see Figure 63).

Figure 62: Cooperative binding for direction ‘1’ tile growth of the first tile
in row 2 extends to the edge of the base. A direction ‘1’ detection gadget
(green) attaches to the base and the growing row, indicating the edge has been
reached. Once the direction ‘1’ detection gadget is bound, a glue activates on
the $+y$ face of the tile, allowing for cooperative growth in the $+y$
direction on the currently grown structure. Figure 63: The binding of the
neighbor detection gadget allows for a strength 2 glue to activate in the $+y$
direction, allowing for a tile with glues mapping to the decoding tile type
(in this case, a shape tile which has a $g_{x}$ glue encoded on its back side)
to cooperatively bind to the prior tile placed.

Similarly, this allows for both the placement of the encoded tile and the
extension of the backing tiles; upon the placement of the encoded tiles, a
signal is sent to dissolve all decoding tiles not involved in growth in the
$+y$ direction into size 1 junk. The next directional tile is added, allowing
for the binding of the next decoding tile and the growth to place the tile
dictated by the encoding structure. To sense when the growth of the decoding
tiles in the $+x$ direction has reached its furthest-most point, the remaining
decoding tile which originally redirected growth in the $+y$ direction enables
a glue similar to that present on the direction ‘1’ detector gadget. We note
this does not cause interactions between multiple encoding processes going on
in parallel, as the presence of the base tiles and the directional row offset
any possible growing decoding tile (Figure 64). Once the neighbor detector
gadget binds, it grows in the $+y$ direction and places its encoded tile
(Figure 65). This repeats until all tiles of the row have been added.

Figure 64: After binding of neighbor detection gadget, shape tiles are placed.
Figure 65: Mid-growth of the second tile in the encoding of row 2. Note that
all but one horizontal tiles are deactivated in direction ‘1’ growth, this is
in order for collision to occur and correctly place remaining tiles. Figure
66: Neighbor detector gadget binds to the furthest-most placed decoding tile
of the second decoding tile after colliding with the prior decoding tile
growth. This leads to placement of encoded tile and growth of backing. This
process repeats for all remaining direction ‘1’ tiles in the row.

At the end of this row, the backing tiles must grow in the $+y$ direction
again. For row 2, the current backing gadget will not work as there exists a
base tile hindering growth (which is necessary for future signals to be sent).
A modified, one-tile gadget is utilized for this specific case. Additionally,
once the row is complete after the placement of a direction change tile, all
remaining decoding tiles are dissolved into size 1 junk allow for growth of
direction ‘0’ tiles of the following layer.

####  3.3.5 Row 2n + 1 Tile Placement

While growth of row 1 was in direction ‘0’, it is a special case due to the
fact that it placed tiles in voxels with the same coordinate in the $y$ axis
as the decoding tiles by a set of tiles unique to the first row. For remaining
odd-numbered rows, we must carry out a similar growth in the $+y$ direction
before as placing the encoded tile as demonstrated by the row 2 growth
example, but incrementing $x$ values. We note that the example figures in this
section do not directly correspond to the encoding provided in Figure 45,
however these are presented to provide the reader with examples of how this
process would occur in an encoding which does contain at least 3 rows.
Decoding tiles of some odd valued row grow by cooperatively binding with the
decoding tile and previously placed directional tiles, as with the row 1
tiles. However, upon binding with a shape or a fill tile they activate a glue
in the $+y$ direction. This glue attempts to allow for growth of decoding
tiles in the $+y$ direction, leading to the binding of a neighbor detection
gadget and the placement of the encoded tile (Figures 67, 68). Similarly to
even numbered direction ‘1’ row growth, decoding tiles are dissolved into size
1 junk to allow for reuse of voxels. In contrast, all but the bottom-most
decoding tile are removed, and glues are activated allowing remaining decoding
tiles to sense that a tile has already been placed in the current location
(Figure 69). In the case when the decoding tile activates its glue in the $+y$
direction and binds to a tile, it continues growth in the $+x$ direction until
finding an open location to grow (Figure 70).

Figure 67: As the direction ‘0’ tile (first tile of row 3) initiates growth,
when a tile is cooperatively placed on a base tile it immediately activates a
glue in the $+y$ direction. Since a path exists for tiles to grow in that
direction, they grow until no cooperative location is available.  Figure 68:
At this point, a detector gadget (teal) binds and indicates that growth has
reached the point for the placement of the voxel encoded. Figure 69: As
signals are passed backwards through the tile growth, all horizontal tiles are
deactivated. This allows for the direction ‘0’ voxels to sense prior placed
tile locations from the same row. Note that tiles growing along the $+y$ axis
are retained initially. Figure 70: As the tiles which encode the second tile
of row 3 grow to their placement location, upon first cooperative binding with
the base they attempt to grow in the $+y$ direction. The signal ‘bounces’, and
the growth continues along the base. Since the second location has not been
placed, the $+y$ direction of growth is free to take place.

####  3.3.6 Slice Completion

Once the directional tiles reach the end of the encoding of the final row
within the structure, a _slice completion gadget_ binds to the end of the
encoding and the directional tile. At this point, a message is returned
through the current row of directional tiles which enabled growth of the slice
(Figure 71). Once the message is received by the first directional tile, it
carries out two operations - the first being unique to the first slice. In
order for the growth of the next slice, we must be able to guarantee the shape
tiles in the slice are connected to either the shape which has grown, or are
connected to the newly growing slice. To guarantee connection of all tiles of
the first slice persist even after filler tile removal, we must create
strength 2 connections between the encoding structure and all tiles of the
first slice. This is accomplished by extending the growth of the backing
tiles, which allows for all tiles to be connected via strength 2 to the
encoding structure. The message is sent through the base tile which initiated
growth of the first slice, into the adjacent backing tiles. After backing
tiles receiving the message, strength 2 glues are activated on all the $+y$
direction faces of the currently placed backing tiles. Only the topmost layer
of backing tiles will allow for cooperative placement of the new backing tiles
on top of the newly created slice. The newly placed backing tiles opens up
cooperative binding locations for the backing tiles to then bind with the top
row of the slice (Figure 72). This allows for the tiles in the topmost row of
the slice to activate glues for binding to their neighbor in the $-y$
direction. Once bound to the neighbor in the $-y$ direction, the tiles are
then able to activate glues which allow for neighbor detection gadgets to
bind, allowing for the growth of a new slice.

Figure 71: The slice completion gadget (green) binds to the outermost
directional tile and decoding tiles, signaling for dissolution of decoding
tiles and extension of backing tiles Figure 72: Backing tiles activate
strength 2 glues, allowing for cooperative growth along the top of the first
slice

In addition to the growth of the backing tiles, a signal is sent to place a
new directional tile. This directional tile takes the information of the first
row of directional tiles and cooperatively binds with both 0 and 1 tiles on
the encoding structure; its purpose is to simply pass forward the directional
information and allow for the tile placement process to continue in the next
slice. In addition to the directional tile exposing a directional glue, we
also expose a terminating glue ($g_{t}$) which is used in the detection of the
completion of the final slice. Once the growth of the new directional tile
occurs alongside the creation of the top row of backing tiles, growth of the
new slice can begin with starting conditions shown in Figure 73.

Figure 73: First directional tile of the second slice is ready to begin
growth.

####  3.3.7 Detaching From Base

Slice growth proceeds via the previously described process until reaching the
final slice. Once the final slice is placed, a slice completion gadget binds
allowing for the placement of a directional tile, as per any other row.
However, the exposed terminating glue allows for the attachment of the
_decoder completion detector_ with the outermost edge of the encoding
structure (Figure 74). Upon binding of the decoder completion detector, a glue
is activated to allow for the growth of _decoder completion tiles_ which
cooperatively bind to the outermost slice layer. Binding of the decoder
completion tiles occurs such that only attachments between shape tiles
activate glues for cooperative growth, and filler tiles must form a strength 2
duple with the decoder completion tiles. Once bound as a duple, the filler
tiles send glue deactivation signals to their remaining active glues.

Figure 74: At the completion of the final row, the decoder completion detector
(black) is able to bind with the outermost directional tile and cause growth
of decoder completion tiles which remove remaining fill tiles.

Once a decoder completion tile binds with the outermost backing tile above the
top row of a slice, it sends a dissolve message to all the base and backing
tiles in the same $yz$ plane (Figure 75) to turn them into size 1 junk. The
base tiles, upon receiving this dissolve message, also initiate a message to
dissolve the remaining tiles placed as part of the assembly sequence into size
1 junk, including the initial binding tile $t_{0}$. The initial binding tile
then signals to the encoding structure to dissolve into size 1 junk, and the
only terminal assembly remaining is the shape assembly produced by the
decoding process.

Figure 75: After the decoder completion tiles (green) bind to the final slice,
this sends deactivation signals to the fill tiles and bind to the backing
tiles, a dissolve message is sent to the remaining tiles involved in the
decoding process.

####  3.3.8 Proof of Universal Shape Decoding Correctness

Here we briefly summarize the decoding process and show that during this
process, the shapes which were encoded in the set of input encoding assemblies
$\Phi$ are correctly assembled. We first consider the decoding process of a
single encoding assembly $\phi\in\Phi$ and note that a similar process happens
for all encoding assemblies simultaneously without interfering with one
another.

Our decoding process begins by building a base of tiles connected to $\phi$.
This base holds the shape as it’s being constructed and is used to help ensure
the connectivity of the shape as it’s being constructed. The decoding process
is performed in iterations, where during each iteration a row of $\phi$ is
scanned tile-by-tile and a corresponding 2D slice of the shape is constructed.
Each slice is constructed starting from the bottom (smallest $y$ coordinate)
to the top (largest $y$ coordinate), with tiles attaching in a zig-zag manner,
as illustrated in Figure 21. Each slice of the assembled shape corresponds to
a unique $z$ coordinate so for convenience we call the slice whose $z$
coordinate is $i$, $\sigma_{i}$. As each slice is assembled, tiles are placed
in each location of the slice, even those locations that will not be part of
the final shape, though these will be removed during the assembly of the next
slice.

The first slice $\sigma_{1}$ can be assembled naively, but during the assembly
of each following slice, tiles which will not be part of the final shape on
the previous slice must be removed. This is done as follows. Suppose that
slice $\sigma_{i}$ ($i>1$) is currently being assembled. Before a tile $t_{i}$
is placed in a location $(x,y,i)$, a gadget is used to determine the type of
the tile $t_{i-1}$ at location $(x,y,i-1)$ (i.e. the tile with the same $x$
and $y$ coordinates on the previous slice). If this $t_{i-1}$ is part of the
final shape, then $t_{i}$ is placed and signals are used to activate strength
2 glues between $t_{i}$ and $t_{i-1}$; otherwise, if $t_{i-1}$ is not part of
the final shape, it is removed before $t_{i}$ is placed. Regardless of the
type of tile $t_{i-1}$, when $t_{i}$ is placed, glues are activated which
connect $t_{i}$ to all adjacent tiles on the same slice. Once the final slice
is assembled, a final zig-zag pass is made in the next $z$ coordinate which
removes all tiles from the last slice which are not part of the final shape.

It is also important to note that the base, on which the shape is being
assembled, also forms a ceiling above the slices being assembled. This ceiling
helps ensure that tiles on the top row of each slice are able to remain
attached to the assembly during construction. It should be clear that during
this decoding process (1) each tile that belongs to the final shape is placed
in its correct location, and (2) that those tiles of a slice which are not
part of the final shape will be removed from the assembly during the assembly
of the next slice. However, because tiles are removed during the process, we
must show that none of these removals can cause parts of the assembly to
unintentionally detach. We state this as Lemma 3.4.

######  Lemma 3.4.

Let $\phi$ be an encoding assembly which encodes the shape $s$. During the
decoding process above, as slice $\sigma_{i}$ ($i>1$) is being assembled, no
tile in slices $\sigma_{1},\ldots,\sigma_{i-1}$ which are part of the final
shape assembly can detach.

######  Proof 3.5.

To prove this, we first note that all tiles in the slice $\sigma_{1}$ which
will be part of the final shape assembly are bound to each neighboring tile in
the slice, meaning that there is no risk of detachment until tiles are removed
in later slices. We use induction on the $z$ coordinate of the slices to show
that this holds. Therefore, assume the hypothesis holds for slices
$\sigma_{1},\ldots,\sigma_{k-1}$ and consider what happens as the slice
$\sigma_{k}$ assembles. Before the assembly of $\sigma_{k}$, the only slice
containing tiles that may need removal are in slice $\sigma_{k-1}$ since
during the assembly of a slice, all tiles which are not part of the final
shape assembly are removed from the previous slice.

As slice $\sigma_{k}$ is being assembled, if all of the tiles in
$\sigma_{k-1}$ are part of the final shape assembly, then nothing will be
detached and the proof is complete. Assume then that there is some tile in
slice $\sigma_{k-1}$ which is not part of the final shape assembly and thus
needs to be removed. Assembly of $\sigma_{k}$ will continue until we reach
such a tile, say $t$ at coordinates $(x_{t},y_{t},z_{t}=k-1)$. Gadgets will
detect that $t$ needs to be removed before a tile, say $t^{\prime}$, is placed
in coordinates $(x_{t},y_{t},z_{t}+1=k)$. When $t$ is detected, $\sigma_{k}$
will be assembled up to the location of $t^{\prime}$ meaning that there will
be a tile in every location of $\sigma_{k}$ below $y$ coordinate $y_{t}$ as
well as all locations at $y$ coordinate $y_{t}$ to either the left or right of
$t^{\prime}$ depending on the parity of the $y$ coordinate in the zig-zag
growth procedure for $\sigma_{k}$.

To ensure that the detachment of $t$ does not cause any other tiles to detach,
we must look at all neighbors of $t$ in the assembly. 1 of these neighbors
will be $t^{\prime}$ itself and this tile will be attached to all of its
neighbors in $\sigma_{k}$ so we don’t have to consider that one. If $t$ has a
neighboring tile in slice $\sigma_{k-2}$, then notice that this tile must (1)
be a tile belonging to the final shape assembly since it was not removed
during the assembly of slice $\sigma_{k-1}$, and (2) have at least 1 other
neighboring tile in $\sigma_{k-2}$ or $\sigma_{k-3}$ to which it is attached
since otherwise the shape being encoded would have disconnected parts which we
don’t allow. Therefore, the removal of $t$ would not cause this tile to
detach.

We now consider the 4 potential neighbors of $t$ in the slice $\sigma_{k-1}$.
For the neighbor below $t$, say $t_{-y}$, we again note that, because shape
$s$ cannot have any disconnected components, $t_{-y}$ must have at least one
neighbor other than $t$ which is part of the final shape assembly. Because the
current slice $\sigma_{k}$ has grown up to the $y$ coordinate of $t$, any such
neighbor of $t_{-y}$ must already exist in the assembly is attached to
$t_{-y}$ with strength 2. Therefore, the removal of $t$ will not cause
$t_{-y}$ to detach.

Now consider the neighbors of $t$ with the same $y$ and $z$ coordinates, call
these $t_{-x}$ and $t_{+x}$. Notice that because slices are grown in a zig-zag
manner, the growth of the current slice $\sigma_{k}$ will be such that one of
these already has a neighboring tile in $\sigma_{k}$ and one does not. Without
loss of generality, suppose that at the current row of slice $\sigma_{k}$
attachments are happening from the $-x$ direction to the $+x$ direction so
that $t_{-x}$ already has a neighbor in $\sigma_{k}$ and $t_{+x}$ does not.
Because any neighbor of $t_{-x}$ that exists must have been placed by now, the
detachment of $t$ will not cause $t_{-x}$ to detach for the same reason as
$t_{-y}$. Now, For $t_{+x}$ it may be the case its only neighbor that is part
of the final shape assembly is in slice $\sigma_{k}$ and has not yet attached.
Still notice that because $\sigma_{k}$ has not yet finished growth, no tiles
have yet been removed from $\sigma_{k-1}$ with a $y$ coordinate greater than
$t_{y}$. This means that $t_{+x}$ still has neighboring tiles to which it is
attached. This is even true if $t_{y}$ is at the top of the slice since the
base contains a ceiling above the assembly to which the tiles are attached.
Therefore, even if $t$ is removed, $t_{+x}$ will remain attached to the
assembly. The same argument applies to $t_{+y}$, the neighbor above $t$.

By the assembly procedure up to this point, it is therefore safe to remove
tile $t$, place $t^{\prime}$ and continue with the assembly of slice
$\sigma_{k}$. Since this holds for any tile which needs to be removed from
slice $\sigma_{k-1}$, the assembly of $\sigma_{k}$ will complete without any
tiles that are part of the final shape assembly detaching.

From here, it’s clear that the assembly of the slices of the shape can
complete without erroneous detachment. Since all tiles that are part of the
final shape assembly have been added during the slice construction and since
all tiles which are not part of the final shape assembly have been removed
from their respective slices, it’s clear that the decoding process
successfully assembles our final shape assembly.

Given the set of input encoding structures
$\Phi=\\{\phi_{1},\ldots,\phi_{n}\\}$, the STAMR system
$\mathcal{D}_{\Phi}=\\{D,\Sigma_{\Phi},\tau=2\\}$ produces a set of terminal
supertiles $S=\\{s_{1},\ldots,s_{n}\\}$ in parallel with a maximum junk size
of 3. $\mathcal{D}_{\Phi}$ finitely completes, as for the production of the
set of shapes $s\in S$ from input encoding structures $\Phi$ a finite number
of tiles are required for each encoding structure to produces a terminal
assembly. We can guarantee this as each encoding produce a single terminal
shape, as the encoding of the shape dissolves into size 1 junk after the
terminal shape has decoded. By our construction, there are never exposed glues
on the surfaces of any pair of assemblies that each contain an input encoding
that would allow them to bind to each other. Since junk assemblies produced by
any assembly sequence are also unable to negatively interact with other
assemblies, a system whose input assemblies have multiple shapes will behave
simply as the union of individual systems which each have one input assembly
shape, creating terminal assemblies of all of (and only) the correct shapes.
This proves Lemma 3.3.

Now that we have shown the existence of universal encoding and universal
decoding tilesets, we have the basis to demonstrate a universal shape
replicator. We generate a new STAMR tileset $R=E\cup D$ and STAMR system
$\mathcal{R}_{S}=\\{R,\Sigma_{S},\tau=2\\}$, where $\Sigma_{S}$ consists of an
infinite number of copies of each tile type from $R$ and an infinite number of
copies of each uniformly covered assembly from the set
$S=\\{s_{1},\ldots,s_{n}\\}$, whose shapes are any arbitrary set of shapes.

Recall that during the encoding process, the encoding corner gadget is bound
to the encoding structure while it is being built. Once the entire encoding
process finishes and the corner gadget receives a ’dissolve’ signal, it first
activates a glue to signal to the first tile placed in the encoding structure
that it should turn on the _initiator glue_ which is the glue initially bound
to by the tiles of $D$. Thus, exactly when an encoding of some $s_{i}$,
$\phi_{i}$, is completed by the tiles of $E$, decoding that $\phi_{i}$ will
begin by the tiles of $D$, resulting in a terminal assembly with the same
shape as $s_{i}$. We make a slight modification to the tile of the encoding
structure that exposes the initiator glue, and the initial decoding tile which
attach to it, the _initiator tile_. We make two copies of the initiator tile,
which we will call $t_{1}$ and $t_{2}$. The first, $t_{1}$, will bind to the
initiator glue and cause the decoding process to proceed exactly as before.
However, when the original initiator tile would have detected completion of
the decoding process and sent a ‘dissolve’ signal to the first tile of the
encoding structure, $t_{1}$ instead sends a signal that tells that tile to
activate a glue that will allow $t_{2}$ to attach, and then $t_{1}$ will
detach. This will effectively cause the encoding to produce a decoded
structure and then have all of the ‘helper’ tiles dissolve, leaving the
encoding structure able to bind to $t_{2}$ which then initiates the regular
decoding process, and when it receives the signal telling it that has
completed, $t_{2}$ does pass the ‘dissolve’ signal to the first tile of the
encoding structure. In this way, each encoding structure causes two copies of
the decoded assembly to be produced, and then dissolves.

By our construction, the only glues required to be shared between the two
tilesets are the glues encoding 1 and 0 on the encoding structure, and the
previously mentioned glues on the encoded assembly which initiate the decoding
process. The glues for 0/1 are shared by multiple tiles in both $E$ and $D$.
All tiles in $D$ which have the the 0/1 glue (or its complement) are required
to be placed by cooperation with a non 0/1 glue. Additionally, each tile in
$D$ has at most one face which contains strength 1 0/1 glue. Since no other
glues are shared between $E$ and $D$ it is not possible for strength 2 binding
to occur between (super)tiles in $E$ and $D$ aside from the binding of $\phi$
with the initiator tiles of $D$. Since junk assemblies produced by any
assembly sequence are also unable to negatively interact with other
assemblies, a system whose input assemblies have multiple shapes will behave
simply as the union of individual systems which each have one input assembly
shape, creating terminal assemblies of all of (and only) the correct shapes.

The maximal junk size of $R$ is 4, driven by the junk size of $E$. We can say
that $\mathcal{R}_{S}$ finitely completes with respect to the set of
assemblies created from the shape tiles of $D$ in the shape of each assembly
in $S$, as the tileset $R$ operates such that any input shape $s_{i}$ is
encoded into an intermediate structure $\phi_{i}$, $\phi_{i}$ is then decoded
into two copies of $s^{\prime}_{i}$, an assembly which contains tiles in the
exact same locations as $s$ (up to rotation and translation). As
deconstruction leads to the production of a single structure $\phi_{i}$, and
$\phi_{i}$ is only able to be decoded to $s^{\prime}_{i}$ two times, we can
place a finite bound on the number of each tile type required to produce each
terminal assembly $s^{\prime}$. (This largely follows from the fact that
encoding systems using $E$ finitely complete with respect to the set of
encoding assemblies, and that decoding systems using $D$ finitely complete
with respect to the set of assemblies whose shapes are encoded.) Therefore,
$R$ also finitely completes, with respect to the set of assemblies with the
same shape as the input assemblies, and Theorem 3.1 is proven.

Note that the condition that a single encoding structure $\phi_{i}$ leads to
the production of exactly two target assemblies $s^{\prime}_{i}$ is imposed to
allow for the universal shape replicator to technically be able to replicate
shapes from an arbitrarily large set of input assembly shapes without the
potential to ‘starve’ the encodings of one shape so that they never produce
decoded copies (and thus the replicator would not finitely complete with
respect to the full set of terminal assembly shapes). If only one input
assembly shape was provided as input, it would instead be possible to just
remove the dissolve signals from the encoding structure and allow each to
initiate the production of an unbounded number of decoded copies. It would
also be trivial to add tiles that make copies of the encoded structures that
can each initiate the decoding process, leading to exponential replication.

##  4 Universal Shape Encoding, Decoding, and Replication in the STAM

As previously mentioned, our use of the STAMR instead of the standard STAM for
the previous results was intended to allow for the input assemblies to be more
generic. That is, a single uniform glue can cover their entire surfaces rather
than having glues that are direction specific, which is implicitly the case
with glues in the STAM (as well as the aTAM and 2HAM, as commonly defined)
since tiles are not allowed to rotate in those models and therefore glues with
complementary labels but in non-opposite directions can’t bind. Giving tiles
the ability to rotate, meaning that glues are not specific to directions, made
aspects of the shape encoding problem more difficult to solve, especially the
“leader election” process to select a corner of the bounding box to be the
location of the origin. Nonetheless, the constructions can be easily modified
to work in the STAM. To do this we can simply define rotated versions of each
of our tiles, one for each of the 24 possible rotations. The behavior of these
tiles will be identical to the behavior of the tiles in the STAMR which can
easily be seen by forming the trivial bijection between individual tiles in
the STAM tileset and rotated instances of those tiles in the STAMR tileset.
This induces a bijection between assemblies formed by the tiles in both, and
this bijection clearly preserves the dynamics of the system as any binding of
assemblies possible in one corresponds to a binding of the corresponding
assemblies in the other. Thus we have an isomorphism between our systems
defined on these tilesets with the same input shape assemblies. Additionally,
the leader election process is essentially unnecessary in the STAM version
with rotated tiles since we could just choose say the top, northeastern most
tile of the bounding box assembly as leader once the filler verification has
finished. In principle, despite the STAM tileset requiring many rotated copies
of the tiles necessary for the bounding box construction, we wouldn’t need
rotated copies of any other tiles if the same corner was always elected
leader.

Also, it can be argued that the STAMR is in a sense more physically realizable
than the STAM if only for the fact that the STAM requires glues to implicitly
encode their orientations. When implementing tiles physically using DNA, where
glues are often made of single stranded DNA exposed on the sides of some more
rigid DNA structure, several copies of each glue (often one for each of the 6
directions) are needed. Because there are only so many fixed length sequences
of nucleotides, requiring that several sequences correspond to the same glue
is expensive. This is not only because those sequences can no longer be used
for different glues, but also because several similar sequences become
unusable as glue sequences must be sufficiently orthogonal to mitigate
erroneous binding. Consequently, our choice of a non-standard model of tile
assembly does not weaken our results, but rather strengthens them both
theoretically and, to some extent, practically.

##  5 Beyond Shape Replication

The constructions used to prove Theorem 3.1 were intentionally broken into
separate, modular constructions proving Lemmas 3.2 and 3.3 and thus providing
a universal shape encoder and a universal shape decoder. This is not only
useful for proving their correctness, but also for allowing for computational
transformations to be performed on the encodings of input shapes in order to
instead produce output shapes based on those transformations. Like even the
much simpler aTAM, the STAM (and STAMR) are Turing universal, meaning any
arbitrary computer program can be executed by systems in these models. Thus,
given any program that can perform a computational transformation of the
points of a shape and output points of another shape, tiles that execute that
program (for instance, by simulating an arbitrary Turing machine in standard
ways, e.g. [25, 18]) can receive as input the binary encodings of arbitrary
shapes (after their creation by the universal encoder), transform them in any
algorithmic manner, and then assemblies of the shapes output by those
transformations can be produced (using the universal shape decoder).

(a)

(b)

(c)

Figure 76: (a) An example shape, (b) The same shape at scale factor $2$, (c) A
shape which is complementary to the top surface of the shape in (a).

Due to space constraints, we don’t go into great detail about the
opportunities that such constructions provide. Instead, we mention just a few
of the possibilities (and depict some in Figure 76) while noting that the
possibilities are technically infinite:

  1. 1.

Scaled shapes: a system could be designed to produce assemblies that have the
shapes of input assemblies scaled by either a built-in constant factor
(including negative, to shrink the shapes), or instead with another type of
input assembly that specifies the scaling factor, allowing for a “universal
scaler”.

  2. 2.

Inverse shapes: a system could be designed to produce assemblies that have the
inverse, i.e. complementary, shapes of the input assemblies (assuming the
complements are connected, and restricting to some bounding box size since the
complement of any finite shape is infinite).

  3. 3.

Pattern matching: a system could be designed to inspect input assembly shapes
for specific patterns and to either produce assemblies that signal the
presence of a target pattern, or instead assemblies that are complementary to,
and can bind to, the surfaces of assemblies containing those patterns.

Although such constructions are highly theoretical and quite complex, and thus
unlikely in their current forms to be practically implementable, they provide
a mathematical foundation for the construction of complex, dynamic systems
that mimic biological systems. One possible example is an “artificial immune
system” capable of inspecting surfaces, detecting those which match (or fail
to match) specific patterns, and creating assemblies capable of binding to
those deemed to be foreign, harmful, or otherwise targeted. As mentioned,
there are infinite possibilities.

##  6 Impossibility of Shape Replication Without Deconstruction

In this section, we prove that in order for a system in the STAMR to encode
and/or replicate shapes which have enclosed or bent cavities (see Definitions
2.4 and 2.5), the input assemblies must have the potential for tiles to be
removed. To do so, we first utilize a theorem from [2].

######  Theorem 6.4 (from [2]).

Let $U$ be an STAM* tileset such that for an arbitrary 3D shape $S$, the STAM*
system $\mathcal{T}=(U,\sigma_{S},\tau)$ with ${\rm dom}\;\sigma_{S}=S$,
$\mathcal{T}$ is a shape self-replicator for $S$ and $\sigma_{S}$ is non-
porous. Then, for any $r\in\mathbb{N}$, there exists a shape $S$ such that
$\mathcal{T}$ must remove at least $r$ tiles from the seed assembly
$\sigma_{S}$.

Theorem 4 from [2] applies to the STAM*. However, the STAMR is simply a
restricted version of the STAM* which only allows tiles to be a single shape,
that of a unit cube, and which does not allow flexible glues. Since all
assemblies in the STAMR are non-porous (i.e. free tiles cannot pass through
the tiles of an assembly or the gaps between bound tiles) and the STAMR has
more restrictive dynamics than the STAM*, the proof of this impossibility
result, which shows the impossibility of self-replicating assemblies with
enclosed cavities without removing tiles, suffices to prove the following
corollary (stated using the terminology of this paper) as well.222The proof
can be found in [2], and we omit duplicating it here due to space constraints.
Note that this proof holds even if the input assemblies are not uniformly
covered.

######  Corollary 6.1.

There exist neither a universal shape encoder nor a universal shape replicator
in the STAMR for the class of shapes with enclosed cavities whose assemblies
are not deconstructable.

(a)

(b)

(c)

(d)

Figure 77: (a) and (b) Partial depictions of a pair of shapes which cannot be
correctly encoded/replicated without a deconstructable input assembly. Each
consists of a $5\times 5\times 4$ cube with a 4-cube-long bent cavity. For
each, the green, purple, blue, and yellow locations indicate the empty
locations that make the bent cavity. The rest of the $5\times 5\times 4$ cube
locations would be filled in with red cubes (some have been omitted to make
the cavity locations visible). (c) and (d) The shapes of assemblies that could
grow into the bent cavities.

Our next theorem deals with shapes having bent cavities.

######  Theorem 6.2.

There exist neither a universal shape encoder nor a universal shape replicator
in the STAMR for the class of shapes with bent cavities whose input assemblies
are uniformly covered but are not deconstructable.

We prove Theorem 6.2 by contradiction. Therefore, let $f_{e}$ be a shape
encoding function and assume $E$ is a universal shape encoder with respect to
$f_{e}$, and let $c$ be the constant value which bounds the size of the junk
assemblies. (Nearly identical arguments will hold for a universal shape
replicator.) Define the shapes $s_{1}$ and $s_{2}$ as shown in Figures 77(a)
and 77(b), i.e. each is a $5\times 5\times 4$ cube with a bent cavity that
goes into the cube to a depth of 3, then turns one of two directions for each.
Note importantly that the well is offset from the center of the cube such that
$s_{1}$ and $s_{2}$ are not rotationally equivalent. Since $E$ is assumed to
be a universal shape encoder, there must exist two STAMR systems
$\mathcal{E}_{1}=(E,\sigma_{1},\tau)$ and
$\mathcal{E}_{2}=(E,\sigma_{2},\tau)$, where $\sigma_{1}$ consists of infinite
copies of tiles from $E$ and infinite copies of uniformly covered assemblies
in the shape of $s_{1}$, and $\sigma_{2}$ consists of infinite copies of tiles
from $E$ and infinite copies of uniformly covered assemblies in the shape of
$s_{2}$.

$\mathcal{E}_{1}$ must produce terminal assemblies which encode shape $s_{1}$
but must not produce terminal assemblies which encode shape $s_{2}$, since no
assembly of shape $s_{2}$ is included in its input assemblies. Similarly,
$\mathcal{E}_{2}$ must produce terminal assemblies which encode shape $s_{2}$
but not $s_{1}$. Let $\vec{\alpha}$ be an assembly sequence in
$\mathcal{E}_{1}$ which results in a terminal assembly encoding shape $s_{1}$.
We now show that every action of $\vec{\alpha}$ must be valid, in the same
ordering, in $\mathcal{E}_{2}$ but using an input assembly of shape $s_{2}$.
This is because the exact same glues will be exposed by the input assemblies
of shapes $s_{1}$ and $s_{2}$ in the same relative locations with the slight
difference of relative rotations of the innermost locations of the bent
cavities of each from the adjacent cavity locations. Assuming that, in
$\vec{\alpha}$, tiles attach into all locations of the bent cavity (if only
the location shown in yellow remains empty the same argument will hold, and if
both the locations shown in yellow and blue remain empty then there is
absolutely no difference in any aspect of the assembly sequence in
$\mathcal{E}_{2}$ and the argument immediately holds), this results only in
the relative orientations of at most the bottom two tiles being turned 90
degrees relative to the tile immediately above them (i.e. the tile in the
purple location in Figure 77). Since tiles in the STAMR are rotatable, with no
distinction for directions, there is no mechanism for tiles in the purple
locations of assemblies shown in Figures 77(c) and 77(d) from distinguishing
from each other (via tile types, glues, or signals). Tiles of the same types
which bind into those locations in $\vec{\alpha}$ must also be able to do so
in the assembly sequence of $\mathcal{E}_{2}$ using the exact same glues and
firing the exact same signals (if any). Thus $\vec{\alpha}$ must be a valid
assembly sequence in $\mathcal{E}_{2}$ as well. This means that an assembly
encoding the shape of $s_{1}$ is also created as a terminal assembly in
$\mathcal{E}_{2}$. Note that if the constant $c$ is greater than the size of
the shapes $s_{1}$ and $s_{2}$ (i.e. $5*5*4-4=96$), then we can simply
increase their dimensions until they are larger than $c$ (but still contain
the same bent cavities) and the argument still holds and the incorrectly
produced assemblies cannot be considered “junk” assemblies. This is a
contradiction that $E$ is a universal shape encoder with respect to $f_{e}$
and constant $c$. Since no assumptions were made about $E$ other than it being
a universal shape encoder, no such $E$ can exist. By slightly altering the
argument for a universal shape replicator $R$ (instead of universal encoder
$E$) and generating terminal assemblies of shapes $s_{1}$ and $s_{2}$ (rather
than assemblies encoding those shapes), the same argument holds to show that
no universal shape replicator exists, and thus Theorem 6.2 is proven.

## References

  * [1] Zachary Abel, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Flatland, Scott D. Kominers, and Robert T. Schweller.  Shape replication through self-assembly and RNAse enzymes.  In SODA 2010: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1045–1064, Austin, Texas, 2010. Society for Industrial and Applied Mathematics.
  * [2] Andrew Alseth, Daniel Hader, and Matthew J. Patitz.  Self-replication via tile self-assembly.  Technical Report 2105.02914, Computing Research Repository, 2021.  URL: {https://arxiv.org/abs/2105.02914}.
  * [3] Andrew Alseth, Daniel Hader, and Matthew J. Patitz.  Self-Replication via Tile Self-Assembly (Extended Abstract).  In Matthew R. Lakin and Petr Šulc, editors, 27th International Conference on DNA Computing and Molecular Programming (DNA 27), volume 205 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:22, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2021/14670, doi:10.4230/LIPIcs.DNA.27.3.
  * [4] Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Andrew Winslow.  Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM.  In Natacha Portier and Thomas Wilke, editors, STACS, volume 20 of LIPIcs, pages 172–184. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013.
  * [5] Cameron Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, and Tim Wylie.  Universal shape replicators via Self-Assembly with Attractive and Repulsive Forces.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 225–238. Society for Industrial and Applied Mathematics, January 2017.  doi:10.1137/1.9781611974782.15.
  * [6] Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, and Pablo Moisset de Espanés.  Complexities for generalized models of self-assembly.  SIAM Journal on Computing, 34:1493–1515, 2005.
  * [7] Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine.  Staged self-assembly: nanomanufacture of arbitrary shapes with ${O}(1)$ glues.  Natural Computing, 7(3):347–370, 2008.
  * [8] Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods.  The two-handed assembly model is not intrinsically universal.  In 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, Riga, Latvia, July 8-12, 2013, Lecture Notes in Computer Science. Springer, 2013.
  * [9] Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers.  Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract).  In Thomas Schwentick and Christoph Dürr, editors, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pages 201–212, Dagstuhl, Germany, 2011. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2011/3011, doi:http://dx.doi.org/10.4230/LIPIcs.STACS.2011.201.
  * [10] David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien Woods.  The tile assembly model is intrinsically universal.  In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 302–310, 2012.
  * [11] Constantine Glen Evans.  Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly.  PhD thesis, California Institute of Technology, 2014.
  * [12] Tyler Fochtman, Jacob Hendricks, Jennifer E. Padilla, Matthew J. Patitz, and Trent A. Rogers.  Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles.  Natural Computing, 14(2):251–264, 2015.
  * [13] Jacob Hendricks, Matthew J. Patitz, and Trent A. Rogers.  Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles.  In Cristian S. Calude and Michael J. Dinneen, editors, Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Auckland, New Zealand, August 30 - September 3, 2015, Proceedings, volume 9252 of Lecture Notes in Computer Science, pages 202–214. Springer, 2015.  URL: http://dx.doi.org/10.1007/978-3-319-21819-9_15, doi:10.1007/978-3-319-21819-9\\_15.
  * [14] Jacob Hendricks, Matthew J. Patitz, and Trent A. Rogers.  Universal simulation of directed systems in the abstract tile assembly model requires undirectedness.  In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), New Brunswick, New Jersey, USA October 9-11, 2016, pages 800–809, 2016.
  * [15] Nataša Jonoska and Daria Karpenko.  Active tile self-assembly, Part 1: Universality at temperature 1.  International Journal of Foundations of Computer Science, 25(02):141–163, 2014.  doi:10.1142/S0129054114500087.
  * [16] Yonggang Ke, Luvena L Ong, William M Shih, and Peng Yin.  Three-dimensional structures self-assembled from DNA bricks.  Science, 338(6111):1177–1183, 2012.
  * [17] Alexandra Keenan, Robert T. Schweller, and Xingsi Zhong.  Exponential replication of patterns in the signal tile assembly model.  In David Soloveichik and Bernard Yurke, editors, DNA, volume 8141 of Lecture Notes in Computer Science, pages 118–132. Springer, 2013\.
  * [18] James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers.  Computability and complexity in self-assembly.  Theory Comput. Syst., 48(3):617–647, 2011.
  * [19] James I. Lathrop, Jack H. Lutz, and Scott M. Summers.  Strict self-assembly of discrete Sierpinski triangles.  Theoretical Computer Science, 410:384–405, 2009.
  * [20] Austin Luchsinger, Robert Schweller, and Tim Wylie.  Self-assembly of shapes at constant scale using repulsive forces.  Natural Computing, Aug 2018.  doi:10.1007/s11047-018-9707-9.
  * [21] Austin Luchsinger, Robert T. Schweller, and Tim Wylie.  Self-assembly of shapes at constant scale using repulsive forces.  In UCNC, volume 10240 of Lecture Notes in Computer Science, pages 82–97. Springer, 2017.
  * [22] Pierre-Étienne Meunier, Damien Regnault, and Damien Woods.  The program-size complexity of self-assembled paths.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 727–737. ACM, 2020.  doi:10.1145/3357713.3384263.
  * [23] Jennifer E. Padilla, Matthew J. Patitz, Robert T. Schweller, Nadrian C. Seeman, Scott M. Summers, and Xingsi Zhong.  Asynchronous signal passing for tile self-assembly: Fuel efficient computation and efficient assembly of shapes.  International Journal of Foundations of Computer Science, 25(4):459–488, 2014.
  * [24] Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers.  Exact shapes and Turing universality at temperature 1 with a single negative glue.  In Luca Cardelli and William M. Shih, editors, DNA Computing and Molecular Programming - 17th International Conference, DNA 17, Pasadena, CA, USA, September 19-23, 2011. Proceedings, volume 6937 of Lecture Notes in Computer Science, pages 175–189. Springer, 2011.
  * [25] Matthew J. Patitz and Scott M. Summers.  Self-assembly of decidable sets.  Natural Computing, 10(2):853–877, 2011.
  * [26] Matthew J. Patitz and Scott M. Summers.  Identifying shapes using self-assembly.  Algorithmica, 64(3):481–510, 2012.
  * [27] Paul W. K. Rothemund and Erik Winfree.  The program-size complexity of self-assembled squares (extended abstract).  In STOC ’00: Proceedings of the thirty-second annual ACM Symposium on Theory of Computing, pages 459–468, Portland, Oregon, United States, 2000. ACM.
  * [28] Rebecca Schulman, Bernard Yurke, and Erik Winfree.  Robust self-replication of combinatorial information via crystal growth and scission.  Proceedings of the National Academy of Sciences, 109(17):6405–10, 2012.  URL: http://www.biomedsearch.com/nih/Robust-self-replication-combinatorial-information/22493232.html.
  * [29] David Soloveichik and Erik Winfree.  Complexity of self-assembled shapes.  SIAM Journal on Computing, 36(6):1544–1569, 2007.
  * [30] Scott M. Summers.  Reducing tile complexity for the self-assembly of scaled shapes through temperature programming.  Algorithmica, 63(1-2):117–136, June 2012.  URL: http://dx.doi.org/10.1007/s00453-011-9522-5, doi:10.1007/s00453-011-9522-5.
  * [31] Erik Winfree.  Algorithmic Self-Assembly of DNA.  PhD thesis, California Institute of Technology, June 1998.
  * [32] Damien Woods, David Doty, Cameron Myhrvold, Joy Hui, Felix Zhou, Peng Yin, and Erik Winfree.  Diverse and robust molecular algorithms using reprogrammable DNA self-assembly.  Nature, 567:366–372, 2019.