We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Inverse automata and monoids and the undecidability of the cayley subgraph problem for groups.
- Authors
Oliveira, Ana; Silva, Pedro V.
- Abstract
The structure of an inverse monoid can be determined by the complete set of Schützenberger graphs of a presentation. Necessary and sufficient conditions for a collection of inverse X-graphs to be the complete set of Schützenberger graphs of some inverse monoid presentation are established and decidability results are obtained. Conditions for a single inverse X-graph to be a Schu¨tzenberger graph for some presentation are also obtained, and both problems are restricted to the case of Clifford monoids and E-unitary inverse monoids. Decidability and undecidability results are obtained for the case of finite graphs. It is also proved that the problem of embedding a finite inverse X-graph in the Cayley graph of a group is undecidable.
- Publication
Glasgow Mathematical Journal, 2000, Vol 42, Issue 3, p421
- ISSN
0017-0895
- Publication type
Article
- DOI
10.1017/s001708950003010x