Word problem languages for free inverse monoids

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)

Abstract

This paper considers the word problem for free inverse monoids of finite rank from a language theory perspective. It is shown that no free inverse monoid has context-free word problem; that the word problem of the free inverse monoid of rank 1 is both 2-context-free (an intersection of two context-free languages) and ET0L; that the co-word problem of the free inverse monoid of rank 1 is context-free; and that the word problem of a free inverse monoid of rank greater than 1 is not poly-context-free.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings
EditorsStavros Konstantinidis, Giovanni Pighizzini
Place of PublicationCham
PublisherSpringer Verlag
Pages24-36
Number of pages13
ISBN (Electronic)978-3-319-94631-3
ISBN (Print)978-3-319-94630-6
DOIs
Publication statusPublished - 1 Jan 2018
Event20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 - Halifax, Canada
Duration: 25 Jul 201827 Jul 2018

Publication series

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

Conference

Conference20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018
CountryCanada
CityHalifax
Period25/07/1827/07/18

Keywords

  • Co-word problems
  • ET0L languages
  • Inverse monoids
  • Poly-context-free languages
  • Stack automata
  • Word problems

Fingerprint Dive into the research topics of 'Word problem languages for free inverse monoids'. Together they form a unique fingerprint.

Cite this