@inproceedings{cf20743ab30c4e0b9dc9e0da8bba5fa2,
title = "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.",
keywords = "Co-word problems, ET0L languages, Inverse monoids, Poly-context-free languages, Stack automata, Word problems",
author = "Tara Brough",
note = "info:eu-repo/grantAgreement/FCT/5876/147271/PT# info:eu-repo/grantAgreement/FCT/5876/147204/PT# SFRH/BPD/121469/2016. ; 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 ; Conference date: 25-07-2018 Through 27-07-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-94631-3_3",
language = "English",
isbn = "978-3-319-94630-6",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "24--36",
editor = "Stavros Konstantinidis and Giovanni Pighizzini",
booktitle = "Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings",
address = "Germany",
}