Remote Access Proceedings of the American Mathematical Society
Green Open Access

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

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?)

  • 1. D. Albert, R. Baldinger and J. Rhodes, Undecidability of the identity problem for finite semigroups, J. Symbolic Logic 57 (1992), 179-192. MR 93f:03030
  • 2. J. Almeida, Finite Semigroups and Universal Algebra, World Scientific, Singapore, 1995. MR 96b:20069
  • 3. J. Almeida, A syntactical proof of locality of $\mathbf{DA}$, Internat. J. Algebra Comput. 6 (1996), 165-177. MR 97b:20096
  • 4. J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products, Internat. J. Algebra Comput. 9 (1999), 241-261. MR 2001a:20102
  • 5. K. Auinger, Semigroups with central idempotents, pp. 25-33 in: Algorithmic Problems in Groups and Semigroups, J.-C. Birget, S. Margolis, J. Meakin, M. Sapir eds., Birkhäuser, Basel 2000. MR 2001c:20125
  • 6. K. Auinger and B. Steinberg, The geometry of profinite graphs with applications to free groups and finite monoids, preprint.
  • 7. J. A. Brzozowski and I. Simon, Characterizations of locally testable events, Discrete Math. 4 (1973), 243-271. MR 47:7948
  • 8. S. Eilenberg, Automata, Languages and Machines, Academic Press, New York, Vol. A, 1974; Vol. B, 1976. MR 58:26604a, MR 58:26604b
  • 9. K. Henckell, S. Margolis, J.-E. Pin, and J. Rhodes, Ash's type II theorem, profinite topology and Mal'cev products, Part I, Internat. J. Algebra Comput. 1 (1991), 411-436. MR 93h:20064
  • 10. B. Herwig and D. Lascar, Extending partial automorphisms and the profinite topology on free groups, Trans. Amer. Math. Soc. 352 (2000), 1985-2021. MR 2000j:20036
  • 11. G. Higman, B. H. Neumann and H. Neumann, Embedding theorems for groups, J. London Math. Soc. 26 (1949), 247-254. MR 11:322d
  • 12. E. Hrushovski, Extending partial isomorphisms of graphs, Combinatorica 12 (1992), 411-416. MR 93m:05089
  • 13. O. G. Kharlampovich and M. V. Sapir, Algorithmic problems in varieties, Internat. J. Algebra Comput. 5 (1995), 379-602. MR 96m:20045
  • 14. M. V. Lawson, Inverse Semigroups: The Theory of Partial Symmetries, World Scientific, Singapore, 1998. MR 2000g:20123
  • 15. S. W. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro- $\mathbf{V}$ topologies and the extension problem for inverse automata, Internat. J. Algebra Comput. 11 (2001), 405-445. MR 2002g:20097
  • 16. S. W. Margolis and B. Steinberg, Power semigroups and polynomial closure, in: Proceedings of the Third International Colloquium on Words, Languages and Combinatorics, Kyoto,
    to appear.
  • 17. D. B. McAlister, Groups, semilattices and inverse semigroups, Trans. Amer. Math. Soc. 68 (1974), 227-244. MR 50:10128
  • 18. J.-E. Pin, $\mathbf{BG} = \mathbf{PG}$, a success story, pp. 33-47 in: Semigroups, Formal Languages and Groups, J. B. Fountain, ed., Kluwer, Dordrecht, 1995. MR 99e:20072
  • 19. J.-E. Pin, Syntactic semigroups, pp. 679-746 in: Handbook of language theory, Vol. I, G. Rozenberg and A. Salomaa eds., Springer, 1997. MR 98i:68205
  • 20. J.-E. Pin, Algebraic tools for the concatenation product,
  • 21. L. Ribes and P. A. Zalesski{\u{\i}}\kern.15em, The pro-$p$ topology of a free group and algorithmic problems in semigroups, Internat. J. Algebra Comput. 4 (1994), 359-374. MR 96e:20046
  • 22. J. Rhodes, Undecidability, automata, and pseudovarieties of finite semigroups, Internat. J. Algebra. Comput. 9 (1999), 455-473. MR 2000j:20112
  • 23. J. Rhodes and B. Steinberg, Pointlike sets, hyperdecidability and the identity problem for finite semigroups, Internat. J. Algebra Comput. 9 (1999), 475-481. MR 2000k:20075
  • 24. J. Rhodes and B. Tilson, The kernel of a monoid morphism, J. Pure Appl. Algebra 62 (1989), 227-268. MR 92j:18005
  • 25. B. Steinberg, On pointlike sets and joins of pseudovarieties, Internat. J. Algebra Comput. 8 (1998), 203-231. MR 99g:20104
  • 26. B. Steinberg, Monoid kernels and profinite topologies on the free Abelian group, Bull. Austral. Math. Soc. 60 (1999), 391-402. MR 2000h:20120
  • 27. B. Steinberg, On algorithmic problems for joins of pseudovarieties, Semigroup Forum 62 (2001), 1-40. MR 2002e:20124
  • 28. B. Steinberg, Inevitable graphs and profinite topologies: Some solutions to algorithmic problems in monoid and automata theory stemming from group theory, Internat. J. Algebra Comput. 11 (2001), 25-71. MR 2002a:68074
  • 29. B. Steinberg, A delay theorem for pointlikes, Semigroup Forum 63 (2001), 281-304.
  • 30. B. Steinberg, Finite state automata: A geometric approach, Trans. Amer. Math. Soc. 353 (2001), 3409-3464. MR 2002c:20106
  • 31. B. Steinberg, Polynomial closure and topology, Internat. J. Algebra Comput. 10 (2000), 603-624. MR 2001m:20102
  • 32. J. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), 551-565. MR 85m:05037a
  • 33. J. B. Stephen, Presentations of inverse monoids, J. Pure Appl. Algebra 63 (1990), 81-112. MR 91g:20083
  • 34. H. Straubing and D. Thérien, Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables, pp. 551-562 in: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 2001, Afonso Ferreira, Horst Reichel eds., Springer LNCS 2010, Berlin, 2001.
  • 35. B. Tilson, Categories as algebra: An essential ingredient in the theory of monoids, J. Pure Appl. Algebra 48 (1987), 83-198. MR 90e:20061
  • 36. P. Weil, Closure of varieties of languages with counter, J. Comp. Syst. Sci. 45 (1992), 316-339. MR 94g:68065

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

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

American Mathematical Society