Context-free word problem semigroups

Tara Brough, Alan J. Cain, Markus Pfeiffer

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)
31 Downloads (Pure)


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
Number of pages14
ISBN (Electronic)978-3-030-24886-4
ISBN (Print)978-3-030-24885-7
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)
Volume11647 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Conference on Developments in Language Theory, DLT 2019


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

Cite this