Word problem languages for free inverse monoids

DOI10.1007/978-3-319-94631-3_3zbMATH Open1435.68149arXiv1803.08034OpenAlexW2962996020MaRDI QIDQ777984FDOQ777984

Tara Brough

Publication date: 30 June 2020

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.

Full work available at URL: https://arxiv.org/abs/1803.08034

zbMATH Keywords

inverse monoidsword problemsET0L languagesco-word problemspoly-context-free languagesstack automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Inverse semigroups (20M18) Semigroups in automata theory, linguistics, etc. (20M35)

Cited In (8)

• The word problem for nilpotent inverse monoids
• A language hierarchy of binary relations
• On the word problem for free products of semigroups and monoids
• The algebra of rewriting for presentations of inverse monoids
• Title not available (Why is that?)
• Syntactic monoids and word problems.
• Title not available (Why is that?)
• Inverse Monoids, Trees, and Context-Free Languages

This page was built for publication: Word problem languages for free inverse monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777984)