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

Alexander Okhotin, Elizaveta Sazhneva

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииDescriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings
РедакторыStavros Konstantinidis, Michal Hospodár, Galina Jirásková
ИздательSpringer Nature
Страницы248-259
Число страниц12
ISBN (печатное издание)9783030232467
DOI
СостояниеОпубликовано - 1 июл 2019
Событие21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 - Košice, Словакия
Продолжительность: 17 июл 201919 июл 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11612 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019
СтранаСловакия
ГородKošice
Период17/07/1919/07/19

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать