Standard

State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages. / Okhotin, Alexander; Sazhneva, Elizaveta.

Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. ed. / Galina Jirásková; Giovanni Pighizzini. Springer Nature, 2020. p. 142-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12442 LNCS).

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

Harvard

Okhotin, A & Sazhneva, E 2020, State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages. in G Jirásková & G Pighizzini (eds), Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12442 LNCS, Springer Nature, pp. 142-154, 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020, Vienna, Austria, 24/08/20. https://doi.org/10.1007/978-3-030-62536-8_12

APA

Okhotin, A., & Sazhneva, E. (2020). State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages. In G. Jirásková, & G. Pighizzini (Eds.), Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings (pp. 142-154). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12442 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-62536-8_12

Vancouver

Okhotin A, Sazhneva E. State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages. In Jirásková G, Pighizzini G, editors, Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. Springer Nature. 2020. p. 142-154. (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-62536-8_12

Author

Okhotin, Alexander ; Sazhneva, Elizaveta. / State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages. Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings. editor / Galina Jirásková ; Giovanni Pighizzini. Springer Nature, 2020. pp. 142-154 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{a1bc38b615a2430c9535fa7334c64475,
title = "State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages",
abstract = "The GF(2)-inverse operation on formal languages is known to have state complexity for alphabets with at least three symbols, and for a one-symbol alphabet. In this paper, it is shown that, for a two-symbol alphabet, its state complexity is exactly For a more general operation of GF(2)-star, its state complexity for a binary alphabet remains.",
author = "Alexander Okhotin and Elizaveta Sazhneva",
note = "Funding Information: Supported by Russian Science Foundation, project 18-11-00100. Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 ; Conference date: 24-08-2020 Through 26-08-2020",
year = "2020",
doi = "10.1007/978-3-030-62536-8_12",
language = "English",
isbn = "9783030625351",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "142--154",
editor = "Galina Jir{\'a}skov{\'a} and Giovanni Pighizzini",
booktitle = "Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages

AU - Okhotin, Alexander

AU - Sazhneva, Elizaveta

N1 - Funding Information: Supported by Russian Science Foundation, project 18-11-00100. Publisher Copyright: © 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - The GF(2)-inverse operation on formal languages is known to have state complexity for alphabets with at least three symbols, and for a one-symbol alphabet. In this paper, it is shown that, for a two-symbol alphabet, its state complexity is exactly For a more general operation of GF(2)-star, its state complexity for a binary alphabet remains.

AB - The GF(2)-inverse operation on formal languages is known to have state complexity for alphabets with at least three symbols, and for a one-symbol alphabet. In this paper, it is shown that, for a two-symbol alphabet, its state complexity is exactly For a more general operation of GF(2)-star, its state complexity for a binary alphabet remains.

UR - http://www.scopus.com/inward/record.url?scp=85097427528&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/583e5891-9c81-32a0-b697-86e76a0d54e8/

U2 - 10.1007/978-3-030-62536-8_12

DO - 10.1007/978-3-030-62536-8_12

M3 - Conference contribution

AN - SCOPUS:85097427528

SN - 9783030625351

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 142

EP - 154

BT - Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings

A2 - Jirásková, Galina

A2 - Pighizzini, Giovanni

PB - Springer Nature

T2 - 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020

Y2 - 24 August 2020 through 26 August 2020

ER -

ID: 72034600