Standard

Formal languages over GF(2). / Bakinova, Ekaterina; Basharin, Artem; Batmanov, Igor; Lyubort, Konstantin; Okhotin, Alexander; Sazhneva, Elizaveta.

In: Information and Computation, Vol. 283, 104672, 01.02.2022.

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

Harvard

Bakinova, E, Basharin, A, Batmanov, I, Lyubort, K, Okhotin, A & Sazhneva, E 2022, 'Formal languages over GF(2)', Information and Computation, vol. 283, 104672. https://doi.org/10.1016/j.ic.2020.104672

APA

Bakinova, E., Basharin, A., Batmanov, I., Lyubort, K., Okhotin, A., & Sazhneva, E. (2022). Formal languages over GF(2). Information and Computation, 283, [104672]. https://doi.org/10.1016/j.ic.2020.104672

Vancouver

Bakinova E, Basharin A, Batmanov I, Lyubort K, Okhotin A, Sazhneva E. Formal languages over GF(2). Information and Computation. 2022 Feb 1;283. 104672. https://doi.org/10.1016/j.ic.2020.104672

Author

Bakinova, Ekaterina ; Basharin, Artem ; Batmanov, Igor ; Lyubort, Konstantin ; Okhotin, Alexander ; Sazhneva, Elizaveta. / Formal languages over GF(2). In: Information and Computation. 2022 ; Vol. 283.

BibTeX

@article{c255e44282f84acea32ce09096c746f2,
title = "Formal languages over GF(2)",
abstract = "Variants of the union and concatenation operations on formal languages are investigated, in which Boolean logic in the definitions (that is, conjunction and disjunction) is replaced with the operations in the two-element field GF(2) (conjunction and exclusive OR). Union is thus replaced with symmetric difference, whereas concatenation gives rise to a new GF(2)-concatenation operation, which is notable for being invertible. All operations preserve regularity, and for a pair of languages recognized by an m-state and an n-state DFA, their GF(2)-concatenation is recognized by a DFA with m⋅2n states, and this number of states is in the worst case necessary. Similarly, the state complexity of GF(2)-inverse is 2n+1. Next, a new class of formal grammars based on GF(2)-operations is defined, and it is shown to have the same computational complexity as ordinary grammars with union and concatenation: in particular, simple parsing in time O(n3), fast parsing in the time of matrix multiplication, and parsing in NC2.",
keywords = "Computational complexity, Finite automata, Finite fields, Formal grammars, Formal languages, Parsing, State complexity, RECOGNITION, CONJUNCTIVE GRAMMARS, OPERATIONS, COMPLEXITY, EQUATIONS",
author = "Ekaterina Bakinova and Artem Basharin and Igor Batmanov and Konstantin Lyubort and Alexander Okhotin and Elizaveta Sazhneva",
note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",
year = "2022",
month = feb,
day = "1",
doi = "10.1016/j.ic.2020.104672",
language = "English",
volume = "283",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Formal languages over GF(2)

AU - Bakinova, Ekaterina

AU - Basharin, Artem

AU - Batmanov, Igor

AU - Lyubort, Konstantin

AU - Okhotin, Alexander

AU - Sazhneva, Elizaveta

N1 - Publisher Copyright: © 2020 Elsevier Inc.

PY - 2022/2/1

Y1 - 2022/2/1

N2 - Variants of the union and concatenation operations on formal languages are investigated, in which Boolean logic in the definitions (that is, conjunction and disjunction) is replaced with the operations in the two-element field GF(2) (conjunction and exclusive OR). Union is thus replaced with symmetric difference, whereas concatenation gives rise to a new GF(2)-concatenation operation, which is notable for being invertible. All operations preserve regularity, and for a pair of languages recognized by an m-state and an n-state DFA, their GF(2)-concatenation is recognized by a DFA with m⋅2n states, and this number of states is in the worst case necessary. Similarly, the state complexity of GF(2)-inverse is 2n+1. Next, a new class of formal grammars based on GF(2)-operations is defined, and it is shown to have the same computational complexity as ordinary grammars with union and concatenation: in particular, simple parsing in time O(n3), fast parsing in the time of matrix multiplication, and parsing in NC2.

AB - Variants of the union and concatenation operations on formal languages are investigated, in which Boolean logic in the definitions (that is, conjunction and disjunction) is replaced with the operations in the two-element field GF(2) (conjunction and exclusive OR). Union is thus replaced with symmetric difference, whereas concatenation gives rise to a new GF(2)-concatenation operation, which is notable for being invertible. All operations preserve regularity, and for a pair of languages recognized by an m-state and an n-state DFA, their GF(2)-concatenation is recognized by a DFA with m⋅2n states, and this number of states is in the worst case necessary. Similarly, the state complexity of GF(2)-inverse is 2n+1. Next, a new class of formal grammars based on GF(2)-operations is defined, and it is shown to have the same computational complexity as ordinary grammars with union and concatenation: in particular, simple parsing in time O(n3), fast parsing in the time of matrix multiplication, and parsing in NC2.

KW - Computational complexity

KW - Finite automata

KW - Finite fields

KW - Formal grammars

KW - Formal languages

KW - Parsing

KW - State complexity

KW - RECOGNITION

KW - CONJUNCTIVE GRAMMARS

KW - OPERATIONS

KW - COMPLEXITY

KW - EQUATIONS

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

UR - https://www.mendeley.com/catalogue/a1e1719a-5a19-3dee-a8b6-7f0f644ca025/

U2 - 10.1016/j.ic.2020.104672

DO - 10.1016/j.ic.2020.104672

M3 - Article

AN - SCOPUS:85098193882

VL - 283

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104672

ER -

ID: 92751015