Context-free word problem semigroups

Tara Brough; Alan J. Cain; Markus Pfeiffer

doi:10.1007/978-3-030-24886-4_22

Context-free word problem semigroups

Tara Brough, Alan J. Cain, Markus Pfeiffer

CMA - Centro de Matemática e Aplicações

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Citations (Scopus)

50 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 language	English
Title of host publication	Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings
Editors	Piotrek Hofman, Michał Skrzypczak
Place of Publication	Cham
Publisher	Springer
Pages	292-305
Number of pages	14
ISBN (Electronic)	978-3-030-24886-4
ISBN (Print)	978-3-030-24885-7
DOIs	https://doi.org/10.1007/978-3-030-24886-4_22
Publication status	Published - 2019
Event	23rd International Conference on Developments in Language Theory, DLT 2019 - Warsaw, Poland Duration: 5 Aug 2019 → 9 Aug 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	11647 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Conference on Developments in Language Theory, DLT 2019
Country/Territory	Poland
City	Warsaw
Period	5/08/19 → 9/08/19

Access to Document

10.1007/978-3-030-24886-4_22

bcp_contextfreeAccepted author manuscript, 304 KB

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). Springer. https://doi.org/10.1007/978-3-030-24886-4_22

Brough, Tara ; Cain, Alan J. ; Pfeiffer, Markus. / Context-free word problem semigroups. Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. editor / Piotrek Hofman ; Michał Skrzypczak. Cham : Springer, 2019. pp. 292-305 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9262d70983ce469e8c8455cc13655070,

title = "Context-free word problem semigroups",

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).",

author = "Tara Brough and Cain, {Alan J.} and Markus Pfeiffer",

note = "info:eu-repo/grantAgreement/FCT/5876/147271/PT# fellowship SFRH/BPD/121469/2016. The second author was supported by the {\textquoteleft}Investigador FCT{\textquoteright} fellowship IF/ 01622/2013/CP1161/CT0001. For the first and second authors, this work was partially supported by FCT projects UID/MAT/00297/2019. PTDC/MHC-FIL/2583/2014 and PTDC/MAT-PUR/31174/2017. This work was started during a visit by the third author to the Universidade Nova de Lisboa, which was supported by the exploratory project IF/01622/2013/ CP1161/CT0001 attached to the second author{\textquoteright}s research fellowship. ; 23rd International Conference on Developments in Language Theory, DLT 2019 ; Conference date: 05-08-2019 Through 09-08-2019",

year = "2019",

doi = "10.1007/978-3-030-24886-4_22",

language = "English",

isbn = "978-3-030-24885-7",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "292--305",

editor = "Piotrek Hofman and Micha{\l} Skrzypczak",

booktitle = "Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings",

address = "Netherlands",

}

Brough, T , Cain, AJ & Pfeiffer, M 2019, Context-free word problem semigroups. in P Hofman & M Skrzypczak (eds), Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11647 LNCS, Springer, Cham, pp. 292-305, 23rd International Conference on Developments in Language Theory, DLT 2019, Warsaw, Poland, 5/08/19. https://doi.org/10.1007/978-3-030-24886-4_22

Context-free word problem semigroups. / Brough, Tara ; Cain, Alan J.; Pfeiffer, Markus.
Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. ed. / Piotrek Hofman; Michał Skrzypczak. Cham: Springer, 2019. p. 292-305 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11647 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Context-free word problem semigroups

AU - Brough, Tara

AU - Cain, Alan J.

AU - Pfeiffer, Markus

N1 - info:eu-repo/grantAgreement/FCT/5876/147271/PT# fellowship SFRH/BPD/121469/2016. The second author was supported by the ‘Investigador FCT’ fellowship IF/ 01622/2013/CP1161/CT0001. For the first and second authors, this work was partially supported by FCT projects UID/MAT/00297/2019. PTDC/MHC-FIL/2583/2014 and PTDC/MAT-PUR/31174/2017. This work was started during a visit by the third author to the Universidade Nova de Lisboa, which was supported by the exploratory project IF/01622/2013/ CP1161/CT0001 attached to the second author’s research fellowship.

PY - 2019

Y1 - 2019

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=85073903752&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-24886-4_22

DO - 10.1007/978-3-030-24886-4_22

M3 - Conference contribution

AN - SCOPUS:85073903752

SN - 978-3-030-24885-7

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 292

EP - 305

BT - Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings

A2 - Hofman, Piotrek

A2 - Skrzypczak, Michał

PB - Springer

CY - Cham

T2 - 23rd International Conference on Developments in Language Theory, DLT 2019

Y2 - 5 August 2019 through 9 August 2019

ER -

Brough T , Cain AJ, Pfeiffer M. Context-free word problem semigroups. In Hofman P, Skrzypczak M, editors, Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. Cham: Springer. 2019. p. 292-305. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-24886-4_22

Context-free word problem semigroups

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this