Word problem languages for free inverse monoids

DOI10.1007/978-3-319-94631-3_3MaRDI QIDQ777984zbMATHOpenAlexFDO

Authors Tara Brough

Publication date 30 June 2020

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)

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.

Recommendations

• The idempotent problem for an inverse monoid.
• Compressed word problems for inverse monoids
• Inverse Monoids, Trees, and Context-Free Languages
• Presentations of inverse monoids
• scientific article; zbMATH DE number 459339

Cited in

(19)

• Free inverse monoids are not \(\mathrm{FP}_2\)
• On periodic points of free inverse monoid homomorphisms.
• Language-theoretic problems in certain matrix monoids
• The algebra of rewriting for presentations of inverse monoids
• Compressed word problems for inverse monoids
• The word problem for nilpotent inverse monoids
• On the word problem for weakly compressible monoids
• scientific article; zbMATH DE number 679834 (Why is no real title available?)
• Syntactic monoids and word problems.
• The idempotent problem for an inverse monoid.
• The loop problem for monoids and semigroups
• Partially commutative inverse monoids.
• Eraser morphisms and membership problem in groups and monoids
• On the word problem for free products of semigroups and monoids
• scientific article; zbMATH DE number 459339 (Why is no real title available?)
• A language hierarchy of binary relations
• Inverse Monoids, Trees, and Context-Free Languages
• Free products of semigroups and monoids with a deterministic context-free word problem
• Partially Commutative Inverse Monoids

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)