DOI

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
StatePublished - 2020
Event22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 - Vienna, Austria
Duration: 24 Aug 2020 → 26 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
Country/TerritoryAustria
CityVienna
Period24/08/20 → 26/08/20

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 72034600