@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",

}