State Complexity of GF(2)-Inverse and GF(2)-Star on Binary Languages

Standard

State Complexity of GF(2)-Inverse and GF(2)-Star on Binary Languages. / Охотин, Александр Сергеевич; Сажнева, Елизавета Александровна.

In: Journal of Automata, Languages and Combinatorics, Vol. 28, No. 1-3, 2023, p. 121-141.

Research output: Contribution to journal › Article › peer-review

Author

Охотин, Александр Сергеевич ; Сажнева, Елизавета Александровна. / State Complexity of GF(2)-Inverse and GF(2)-Star on Binary Languages. In: Journal of Automata, Languages and Combinatorics. 2023 ; Vol. 28, No. 1-3. pp. 121-141.

BibTeX

@article{c03b4697a23c4164a80a952f2e4445d9,

title = "State Complexity of GF(2)-Inverse and GF(2)-Star on Binary Languages",

abstract = "The GF(2)-inverse operation on formal languages, defined for every language ontain-ing the empty string, is known to preserve regularity; its state omplexity is 2n + 1 for alphabets with at least three symbols, and 2n−1 + 1 for a one-symbol alphabet. In this paper, it is proved that, for a two-symbol alphabet, its state omplexity is ex-atly342n +3. For a more general operation, the GF(2)-star, whih is appliable to every language, it is proved that its state omplexity for a binary alphabet remains 2n + 1.",

keywords = "GF(2)-inverse, GF(2)-onatenation, primitive polyno-mials, state omplexity",

author = "Охотин, {Александр Сергеевич} and Сажнева, {Елизавета Александровна}",

year = "2023",

doi = "10.25596/jalc-2023-121",

language = "English",

volume = "28",

pages = "121--141",

journal = "Journal of Automata, Languages and Combinatorics",

issn = "1430-189X",

publisher = "Institut fur Informatik, Justus-Liebig-Universitat Giessen",

number = "1-3",

}

RIS

TY - JOUR

T1 - State Complexity of GF(2)-Inverse and GF(2)-Star on Binary Languages

AU - Охотин, Александр Сергеевич

AU - Сажнева, Елизавета Александровна

PY - 2023

Y1 - 2023

N2 - The GF(2)-inverse operation on formal languages, defined for every language ontain-ing the empty string, is known to preserve regularity; its state omplexity is 2n + 1 for alphabets with at least three symbols, and 2n−1 + 1 for a one-symbol alphabet. In this paper, it is proved that, for a two-symbol alphabet, its state omplexity is ex-atly342n +3. For a more general operation, the GF(2)-star, whih is appliable to every language, it is proved that its state omplexity for a binary alphabet remains 2n + 1.

AB - The GF(2)-inverse operation on formal languages, defined for every language ontain-ing the empty string, is known to preserve regularity; its state omplexity is 2n + 1 for alphabets with at least three symbols, and 2n−1 + 1 for a one-symbol alphabet. In this paper, it is proved that, for a two-symbol alphabet, its state omplexity is ex-atly342n +3. For a more general operation, the GF(2)-star, whih is appliable to every language, it is proved that its state omplexity for a binary alphabet remains 2n + 1.

KW - GF(2)-inverse

KW - GF(2)-onatenation

KW - primitive polyno-mials

KW - state omplexity

UR - https://www.mendeley.com/catalogue/e3fea651-78a6-3802-9d07-9da06c94b9ea/

U2 - 10.25596/jalc-2023-121

DO - 10.25596/jalc-2023-121

M3 - Article

VL - 28

SP - 121

EP - 141

JO - Journal of Automata, Languages and Combinatorics

JF - Journal of Automata, Languages and Combinatorics

SN - 1430-189X

IS - 1-3

ER -

ID: 108695868