Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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.
| Original language | English |
|---|---|
| Title of host publication | Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings |
| Editors | Michal Hospodár, Galina Jirásková, Stavros Konstantinidis |
| Publisher | Springer Nature |
| 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 |
| 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 | 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 |
|---|---|
| Country/Territory | Slovakia |
| City | Košice |
| Period | 17/07/19 → 19/07/19 |
ID: 43985755