On the extension problem for partial permutations

Auinger, K.; Steinberg, B.

doi:10.1090/S0002-9939-03-06860-6

On the extension problem for partial permutations
HTML articles powered by AMS MathViewer

by K. Auinger and B. Steinberg PDF

Proc. Amer. Math. Soc. 131 (2003), 2693-2703 Request permission

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$, $\textcircled {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

Douglas Albert, Robert Baldinger, and John Rhodes, Undecidability of the identity problem for finite semigroups, J. Symbolic Logic 57 (1992), no. 1, 179–192. MR 1150933, DOI 10.2307/2275184
Jorge Almeida, Finite semigroups and universal algebra, Series in Algebra, vol. 3, World Scientific Publishing Co., Inc., River Edge, NJ, 1994. Translated from the 1992 Portuguese original and revised by the author. MR 1331143
Jorge Almeida, A syntactical proof of locality of DA, Internat. J. Algebra Comput. 6 (1996), no. 2, 165–177. MR 1386073, DOI 10.1142/S021819679600009X
Jorge Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products, Internat. J. Algebra Comput. 9 (1999), no. 3-4, 241–261. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1722629, DOI 10.1142/S0218196799000163
Karl Auinger, Semigroups with central idempotents, Algorithmic problems in groups and semigroups (Lincoln, NE, 1998) Trends Math., Birkhäuser Boston, Boston, MA, 2000, pp. 25–33. MR 1750490
K. Auinger and B. Steinberg, The geometry of profinite graphs with applications to free groups and finite monoids, preprint.
J. A. Brzozowski and Imre Simon, Characterizations of locally testable events, Discrete Math. 4 (1973), 243–271. MR 319404, DOI 10.1016/0012-365X(82)90281-3
Leo F. Epstein, A function related to the series for $e^{e^x}$, J. Math. Phys. Mass. Inst. Tech. 18 (1939), 153–173. MR 58, DOI 10.1002/sapm1939181153
Karsten Henckell, Stuart W. Margolis, Jean-Eric Pin, and John Rhodes, Ash’s type $\textrm {II}$ theorem, profinite topology and Mal′cev products. I, Internat. J. Algebra Comput. 1 (1991), no. 4, 411–436. MR 1154442, DOI 10.1142/S0218196791000298
Bernhard Herwig and Daniel Lascar, Extending partial automorphisms and the profinite topology on free groups, Trans. Amer. Math. Soc. 352 (2000), no. 5, 1985–2021. MR 1621745, DOI 10.1090/S0002-9947-99-02374-0
Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
Ehud Hrushovski, Extending partial isomorphisms of graphs, Combinatorica 12 (1992), no. 4, 411–416. MR 1194731, DOI 10.1007/BF01305233
O. G. Kharlampovich and M. V. Sapir, Algorithmic problems in varieties, Internat. J. Algebra Comput. 5 (1995), no. 4-5, 379–602. MR 1361261, DOI 10.1142/S0218196795000227
Mark V. Lawson, Inverse semigroups, World Scientific Publishing Co., Inc., River Edge, NJ, 1998. The theory of partial symmetries. MR 1694900, DOI 10.1142/9789812816689
S. 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), no. 4, 405–445 (English, with English and French summaries). MR 1850210, DOI 10.1142/S0218196701000498
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.
D. B. McAlister, Groups, semilattices and inverse semigroups. I, II, Trans. Amer. Math. Soc. 192 (1974), 227–244; ibid. 196 (1974), 351–370. MR 357660, DOI 10.1090/S0002-9947-1974-0357660-2
Jean-Eric Pin, $\textbf {BG}=\textbf {PG}$: a success story, Semigroups, formal languages and groups (York, 1993) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 466, Kluwer Acad. Publ., Dordrecht, 1995, pp. 33–47. MR 1630617
Jean-Eric Pin, Syntactic semigroups, Handbook of formal languages, Vol. 1, Springer, Berlin, 1997, pp. 679–746. MR 1470002
J.-E. Pin, Algebraic tools for the concatenation product, preprint.
Luis Ribes and Pavel A. Zalesskii, The pro-$p$ topology of a free group and algorithmic problems in semigroups, Internat. J. Algebra Comput. 4 (1994), no. 3, 359–374. MR 1297146, DOI 10.1142/S021819679400004X
John Rhodes, Undecidability, automata, and pseudovarieties of finite semigroups, Internat. J. Algebra Comput. 9 (1999), no. 3-4, 455–473. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1723477, DOI 10.1142/S0218196799000278
John Rhode and Benjamin Steinberg, Pointlike sets, hyperdecidability and the identity problem for finite semigroups, Internat. J. Algebra Comput. 9 (1999), no. 3-4, 475–481. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1723478, DOI 10.1142/S021819679900028X
John Rhodes and Bret Tilson, The kernel of monoid morphisms, J. Pure Appl. Algebra 62 (1989), no. 3, 227–268. MR 1026876, DOI 10.1016/0022-4049(89)90137-0
Benjamin Steinberg, On pointlike sets and joins of pseudovarieties, Internat. J. Algebra Comput. 8 (1998), no. 2, 203–234. With an addendum by the author. MR 1620343, DOI 10.1142/S0218196798000119
Benjamin Steinberg, Monoid kernels and profinite topologies on the free abelian group, Bull. Austral. Math. Soc. 60 (1999), no. 3, 391–402. MR 1727475, DOI 10.1017/S0004972700036571
Benjamin Steinberg, On algorithmic problems for joins of pseudovarieties, Semigroup Forum 62 (2001), no. 1, 1–40. MR 1832252, DOI 10.1007/PL00020979
Benjamin 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), no. 1, 25–71. MR 1818661, DOI 10.1142/S0218196701000462
B. Steinberg, A delay theorem for pointlikes, Semigroup Forum 63 (2001), 281–304.
Benjamin Steinberg, Finite state automata: a geometric approach, Trans. Amer. Math. Soc. 353 (2001), no. 9, 3409–3464. MR 1837243, DOI 10.1090/S0002-9947-01-02774-X
Benjamin Steinberg, Polynomial closure and topology, Internat. J. Algebra Comput. 10 (2000), no. 5, 603–624. MR 1781850, DOI 10.1142/S0218196700000285
John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551–565. MR 695906, DOI 10.1007/BF02095993
J. B. Stephen, Presentations of inverse monoids, J. Pure Appl. Algebra 63 (1990), no. 1, 81–112. MR 1037695, DOI 10.1016/0022-4049(90)90057-O
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.
Bret Tilson, Categories as algebra: an essential ingredient in the theory of monoids, J. Pure Appl. Algebra 48 (1987), no. 1-2, 83–198. MR 915990, DOI 10.1016/0022-4049(87)90108-3
Pascal Weil, Closure of varieties of languages under products with counter, J. Comput. System Sci. 45 (1992), no. 3, 316–339. MR 1193376, DOI 10.1016/0022-0000(92)90029-I