### Abstract

The paper investigates the state complexity of two operations on regular languages, known as GF(2)-concatenation and GF(2)-inverse (Bakinova et al., “Formal languages over GF(2)”, LATA 2018), in the case of a one-symbol alphabet. The GF(2)-concatenation is a variant of the classical concatenation obtained by replacing Boolean logic in its definition with the GF(2) field; it is proved that GF(2)-concatenation of two unary languages recognized by an m-state and an n-state DFA is recognized by a DFA with 2mn states, and this number of states is necessary in the worst case, as long as m and n are relatively prime. This operation is known to have an inverse, and the state complexity of the GF(2)-inverse operation over a unary alphabet is proved to be exactly 2^{n−1} + 1.

Original language | English |
---|---|

Title of host publication | Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings |

Editors | Stavros Konstantinidis, Michal Hospodár, Galina Jirásková |

Publisher | Springer |

Pages | 248-259 |

Number of pages | 12 |

ISBN (Print) | 9783030232467 |

DOIs | |

State | Published - 1 Jul 2019 |

Event | 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 - Košice, Slovakia Duration: 17 Jul 2019 → 19 Jul 2019 |

### Publication series

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

Volume | 11612 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 |
---|---|

Country | Slovakia |

City | Košice |

Period | 17/07/19 → 19/07/19 |

### Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings*(pp. 248-259). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11612 LNCS). Springer. https://doi.org/10.1007/978-3-030-23247-4_19

}

*Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11612 LNCS, Springer, pp. 248-259, 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019, Košice, Slovakia, 17/07/19. https://doi.org/10.1007/978-3-030-23247-4_19

**State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages.** / Okhotin, Alexander; Sazhneva, Elizaveta.

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

TY - GEN

T1 - State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages

AU - Okhotin, Alexander

AU - Sazhneva, Elizaveta

PY - 2019/7/1

Y1 - 2019/7/1

N2 - The paper investigates the state complexity of two operations on regular languages, known as GF(2)-concatenation and GF(2)-inverse (Bakinova et al., “Formal languages over GF(2)”, LATA 2018), in the case of a one-symbol alphabet. The GF(2)-concatenation is a variant of the classical concatenation obtained by replacing Boolean logic in its definition with the GF(2) field; it is proved that GF(2)-concatenation of two unary languages recognized by an m-state and an n-state DFA is recognized by a DFA with 2mn states, and this number of states is necessary in the worst case, as long as m and n are relatively prime. This operation is known to have an inverse, and the state complexity of the GF(2)-inverse operation over a unary alphabet is proved to be exactly 2n−1 + 1.

AB - The paper investigates the state complexity of two operations on regular languages, known as GF(2)-concatenation and GF(2)-inverse (Bakinova et al., “Formal languages over GF(2)”, LATA 2018), in the case of a one-symbol alphabet. The GF(2)-concatenation is a variant of the classical concatenation obtained by replacing Boolean logic in its definition with the GF(2) field; it is proved that GF(2)-concatenation of two unary languages recognized by an m-state and an n-state DFA is recognized by a DFA with 2mn states, and this number of states is necessary in the worst case, as long as m and n are relatively prime. This operation is known to have an inverse, and the state complexity of the GF(2)-inverse operation over a unary alphabet is proved to be exactly 2n−1 + 1.

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

U2 - 10.1007/978-3-030-23247-4_19

DO - 10.1007/978-3-030-23247-4_19

M3 - Conference contribution

SN - 9783030232467

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

SP - 248

EP - 259

BT - Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings

A2 - Konstantinidis, Stavros

A2 - Hospodár, Michal

A2 - Jirásková, Galina

PB - Springer

ER -