Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)


On the extension problem for partial permutations

Authors: K. Auinger and B. Steinberg
Journal: Proc. Amer. Math. Soc. 131 (2003), 2693-2703
MSC (2000): Primary 20M07, 20M18, 20M35, 20B05, 20D10
Published electronically: January 28, 2003
MathSciNet review: 1974324
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A family of pseudovarieties of solvable groups is constructed, each of which has decidable membership and undecidable extension problem for partial permutations. Included are a pseudovariety $\mathbf{U}$satisfying no non-trivial group identity and a metabelian pseudovariety $\mathbf{Q}$. For each of these pseudovarieties $\mathbf{V}$, the inverse monoid pseudovariety $\mathbf{Sl}\ast \mathbf{V}$ has undecidable membership problem. As a consequence, it is proved that the pseudovariety operators $\ast$, $\ast\ast$, $\mathrel{\mbox{\textcircled{\scriptsize {$m$ }}}}$, $\diamondsuit$, $\diamondsuit_n$, and $\mathbf{P}$ do not preserve decidability. In addition, several joins, including $\mathbf{A}\vee \mathbf{U}$, are shown to be undecidable.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 20M07, 20M18, 20M35, 20B05, 20D10

Retrieve articles in all journals with MSC (2000): 20M07, 20M18, 20M35, 20B05, 20D10

Additional Information

K. Auinger
Affiliation: Institut für Mathematik, Universität Wien, Strudlhofgasse 4,A-1090 Wien, Austria

B. Steinberg
Affiliation: School of Mathematics and Statistics, Carleton University, Herzberg Laboratories, 1125 Colonel By Drive, Ottawa, Ontario, Canada K1S 5B6

PII: S 0002-9939(03)06860-6
Received by editor(s): October 31, 2001
Received by editor(s) in revised form: April 10, 2002
Published electronically: January 28, 2003
Additional Notes: The authors gratefully acknowledge support from INTAS project 99–1224. The second author was supported in part by FCT through the Centro de Matemática da Universidade do Porto, and by the FCT and POCTI approved project POCTI/32817/MAT/2000 in participation with the European Community Fund FEDER
Communicated by: Stephen D. Smith
Article copyright: © Copyright 2003 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia