Prescribed Teams of Rules Working on Several Objects
Închide
Articolul precedent
Articolul urmator
235 0
SM ISO690:2012
ALHAZOV, Artiom, FREUND, Rudolf, IVANOV, Sergiu, VERLAN, Sergey. Prescribed Teams of Rules Working on Several Objects. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): 9th International Conference on Machines, Computations, and Universality, MCU 2022, 31 august - 2 septembrie 2022, Debrecen. Debrecen, Ungaria: Springer Science and Business Media Deutschland GmbH, 2022, Vol. 13419, pp. 27-41. ISBN 978-303113501-9. ISSN 03029743. DOI: https://doi.org/10.1007/978-3-031-13502-6_6
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol. 13419, 2022
Sesiunea "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)"
Debrecen, Ungaria, 31 august - 2 septembrie 2022

Prescribed Teams of Rules Working on Several Objects

DOI:https://doi.org/10.1007/978-3-031-13502-6_6

Pag. 27-41

Alhazov Artiom1, Freund Rudolf2, Ivanov Sergiu3, Verlan Sergey4
 
1 Vladimir Andrunachievici Institute of Mathematics and Computer Science,
2 Technical University of Vienna,
3 Universitatea Paris-Saclay,
4 Université Paris-Est-Créteil
 
 
Disponibil în IBN: 26 august 2022


Rezumat

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 bb- assumed to happen immediately whenever b and b- meet deletes the b. 

Cuvinte-cheie
Anti-objects, computational completeness, insertion-deletion systems, Prescribed teams