Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
State Complexity of Union and Intersection on Graph-Walking Automata. / Martynova, Olga; Okhotin, Alexander.
Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings. ред. / Yo-Sub Han; Sang-Ki Ko. Springer Nature, 2021. стр. 125-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 13037 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - State Complexity of Union and Intersection on Graph-Walking Automata
AU - Martynova, Olga
AU - Okhotin, Alexander
N1 - Publisher Copyright: © 2021, IFIP International Federation for Information Processing.
PY - 2021/12/30
Y1 - 2021/12/30
N2 - Finite automata traversing graphs by moving along their edges are known as graph-walking automata (GWA). This paper investigates the state complexity of union and intersection for this model. It is proved that the union of GWA with m and n states, with m⩽ n, operating on graphs with k labels of edge end-points, is representable by a GWA with 2 km+ n+ 1 states, and at least 2 (k- 3 ) (m- 1 ) + n- 1 states are necessary in the worst case. For the intersection, the upper bound is (2 k+ 1 ) m+ n and the lower bound is 2 (k- 3 ) (m- 1 ) + n- 1.
AB - Finite automata traversing graphs by moving along their edges are known as graph-walking automata (GWA). This paper investigates the state complexity of union and intersection for this model. It is proved that the union of GWA with m and n states, with m⩽ n, operating on graphs with k labels of edge end-points, is representable by a GWA with 2 km+ n+ 1 states, and at least 2 (k- 3 ) (m- 1 ) + n- 1 states are necessary in the worst case. For the intersection, the upper bound is (2 k+ 1 ) m+ n and the lower bound is 2 (k- 3 ) (m- 1 ) + n- 1.
UR - http://www.scopus.com/inward/record.url?scp=85122569209&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-93489-7_11
DO - 10.1007/978-3-030-93489-7_11
M3 - Conference contribution
AN - SCOPUS:85122569209
SN - 9783030934880
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 125
EP - 136
BT - Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings
A2 - Han, Yo-Sub
A2 - Ko, Sang-Ki
PB - Springer Nature
T2 - 23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021
Y2 - 5 September 2021 through 5 September 2021
ER -
ID: 91382982