Name
Abstract | ||
|---|---|---|
In this article, we consider leftist insertion-deletion systems, in which all rules have contexts on the same side, and may only insert or delete one symbol at a time. We start by introducing extended rules, in which the contexts may be specified as regular expressions, instead of fixed words. We then prove that leftist systems with such extended rules and two-state graph control can simulate any arbitrary 2-tag system. Finally, we show how our construction can be simulated in its turn by graph-controlled leftist insertion-deletion systems with conventional rules of sizes (1, 1, 0; 1, 2, 0) and (1, 2, 0; 1, 1, 0) (where the first three numbers represent the maximal size of the inserted string and the maximal size of the left and right contexts respectively, while the last three numbers provide the same information about deletion rules), which implies that the latter systems are universal. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-23111-2_6 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Regular expression,Symbol,Computer science,Left-wing politics,Left and right,Universality (philosophy),Expressive power | Conference | 9288 |
ISSN | Citations | PageRank |
0302-9743 | 3 | 0.42 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sergiu Ivanov 0001 | 1 | 71 | 8.86 |
| Sergey Verlan | 2 | 415 | 45.40 |