Context-free word problem semigroups

Tara Brough, Alan J. Cain, Markus Pfeiffer

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

1 Downloads (Pure)

Abstract

This paper studies the classes of semigoups and monoids with context-free and deterministic context-free word problem. First, some examples are exhibited to clarify the relationship between these classes and their connection with the notions of word-hyperbolicity and automaticity. Second, a study is made of whether these classes are closed under applying certain semigroup constructions, including direct products and free products, or under regressing from the results of such constructions to the original semigroup(s) or monoid(s).

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 23rd International Conference, DLT 2019, Proceedings
EditorsPiotrek Hofman, Michał Skrzypczak
Place of PublicationCham
PublisherSpringer
Pages292-305
Number of pages14
ISBN (Electronic)978-3-030-24886-4
ISBN (Print)978-3-030-24885-7
DOIs
Publication statusPublished - 2019
Event23rd International Conference on Developments in Language Theory, DLT 2019 - Warsaw, Poland
Duration: 5 Aug 20199 Aug 2019

Publication series

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

Conference

Conference23rd International Conference on Developments in Language Theory, DLT 2019
CountryPoland
CityWarsaw
Period5/08/199/08/19

Fingerprint Dive into the research topics of 'Context-free word problem semigroups'. Together they form a unique fingerprint.

  • Cite this

    Brough, T., Cain, A. J., & Pfeiffer, M. (2019). Context-free word problem semigroups. In P. Hofman, & M. Skrzypczak (Eds.), Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings (pp. 292-305). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11647 LNCS). Cham: Springer. https://doi.org/10.1007/978-3-030-24886-4_22