Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6826(e) ISSN 0002-9939(p)

On the extension problem for partial permutations

Author(s): K. Auinger; B. Steinberg
Journal: Proc. Amer. Math. Soc. 131 (2003), 2693-2703.
MSC (2000): Primary 20M07, 20M18, 20M35, 20B05, 20D10
Posted: January 28, 2003
MathSciNet review: 1974324
Retrieve article in: PDF
This article is available free of charge

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:

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,
preprint.
21.: L. Ribes and P. A. Zalesski ${\u{\i}}\kern.15em$ , The pro- 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

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