Word Problem Languages for Free Inverse Monoids

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905631
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:19 AM
Last modification on : Monday, September 9, 2019 - 11:24:02 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:23:56 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Tara Brough. Word Problem Languages for Free Inverse Monoids. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.24-36, ⟨10.1007/978-3-319-94631-3_3⟩. ⟨hal-01905631⟩

Share

Metrics

Record views

37