State Complexity of Union and Intersection on Graph-Walking Automata

Standard

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. ed. / Yo-Sub Han; Sang-Ki Ko. Springer Nature, 2021. p. 125-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13037 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Martynova, O & Okhotin, A 2021, State Complexity of Union and Intersection on Graph-Walking Automata. in Y-S Han & S-K Ko (eds), Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13037 LNCS, Springer Nature, pp. 125-136, 23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021, Virtual, Online, 5/09/21. https://doi.org/10.1007/978-3-030-93489-7_11

APA

Martynova, O., & Okhotin, A. (2021). State Complexity of Union and Intersection on Graph-Walking Automata. In Y-S. Han, & S-K. Ko (Eds.), Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings (pp. 125-136). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13037 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-93489-7_11

Vancouver

Martynova O , Okhotin A. State Complexity of Union and Intersection on Graph-Walking Automata. In Han Y-S, Ko S-K, editors, Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings. Springer Nature. 2021. p. 125-136. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-93489-7_11

Author

Martynova, Olga ; Okhotin, Alexander. / State Complexity of Union and Intersection on Graph-Walking Automata. Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings. editor / Yo-Sub Han ; Sang-Ki Ko. Springer Nature, 2021. pp. 125-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{13628ac568f34658b8f758294274f394,

title = "State Complexity of Union and Intersection on Graph-Walking Automata",

abstract = "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.",

author = "Olga Martynova and Alexander Okhotin",

note = "Publisher Copyright: {\textcopyright} 2021, IFIP International Federation for Information Processing.; 23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021 ; Conference date: 05-09-2021 Through 05-09-2021",

year = "2021",

month = dec,

day = "30",

doi = "10.1007/978-3-030-93489-7_11",

language = "English",

isbn = "9783030934880",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature",

pages = "125--136",

editor = "Yo-Sub Han and Sang-Ki Ko",

booktitle = "Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings",

address = "Germany",

}

RIS

TY - GEN

T1 - State Complexity of Union and Intersection on Graph-Walking Automata

AU - Martynova, Olga

AU - Okhotin, Alexander

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