%0 Conference Proceedings
%T Word Problem Languages for Free Inverse Monoids
%+ Universidade Nova de Lisboa = NOVA University Lisbon (NOVA)
%A Brough, Tara
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 20th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Halifax, NS, Canada
%Y Stavros Konstantinidis
%Y Giovanni Pighizzini
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10952
%P 24-36
%8 2018-07-25
%D 2018
%R 10.1007/978-3-319-94631-3_3
%K Word problems
%K Co-word problems
%K Inverse monoids
%K ET0L languages
%K Stack automata
%K Poly-context-free languages
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01905631/document
%2 https://inria.hal.science/hal-01905631/file/470153_1_En_3_Chapter.pdf
%L hal-01905631
%U https://inria.hal.science/hal-01905631
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10952