State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages

Alexander Okhotin, Elizaveta Sazhneva

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

Аннотация

The GF(2)-inverse operation on formal languages is known to have state complexity for alphabets with at least three symbols, and for a one-symbol alphabet. In this paper, it is shown that, for a two-symbol alphabet, its state complexity is exactly For a more general operation of GF(2)-star, its state complexity for a binary alphabet remains.

Язык оригиналаанглийский
Название основной публикацииDescriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings
РедакторыGalina Jirásková, Giovanni Pighizzini
ИздательSpringer Nature
Страницы142-154
Число страниц13
ISBN (печатное издание)9783030625351
DOI
СостояниеОпубликовано - 2020
Событие22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 - Vienna, Австрия
Продолжительность: 24 авг 202026 авг 2020

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

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

конференция

конференция22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020
СтранаАвстрия
ГородVienna
Период24/08/2026/08/20

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

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

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

Цитировать