Alhazov, A., Freund, R., Ivanov, S., & Verlan, S. (2022). Prescribed Teams of Rules Working on Several Objects. In Machines, Computations, and Universality (pp. 27–41). Springer. https://doi.org/10.1007/978-3-031-13502-6_6
Computational completeness; Insertion-deletion systems; Prescribed teams
en
Abstract:
In this paper we consider prescribed sets of rules working
on several objects either in parallel – in this case the rules have to take
different objects – or else sequentially in any order – in this case several
rules may take the same object to work on.
We show that prescribed teams of size two, i.e., containing exactly
two rules, are sufficient to obtain computational completeness for strings
with the simple rules being of the form aIR(b) – meaning that a symbol
b can be inserted on the right-hand side of a string ending with a –
and DR(b) meaning that a symbol b is erased on the right-hand side
of a string. This result is established for systems starting with three
initial strings. Using prescribed teams of size three, we may start with
only two strings, ending up with the output string and the second string
having been reduced to the empty string. We also establish similar results
when using the generation of the anti-object b− on the right-hand side
of a string instead of deleting the object b, i.e. bIR(b−) inserts the anti object b− and the annihilation rule b b− assumed to happen immediately
whenever b and b− meet deletes the b.
