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

Alexander Okhotin, Elizaveta Sazhneva

Research outputpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings
EditorsGalina Jirásková, Giovanni Pighizzini
PublisherSpringer Nature
Pages142-154
Number of pages13
ISBN (Print)9783030625351
DOIs
Publication statusPublished - 2020
Event22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 - Vienna
Duration: 24 Aug 202026 Aug 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12442 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020
CountryAustria
CityVienna
Period24/08/2026/08/20

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages'. Together they form a unique fingerprint.

Cite this