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
Additional Information
- K. Auinger
- Affiliation: Institut für Mathematik, Universität Wien, Strudlhofgasse 4,A-1090 Wien, Austria
- Email: karl.auinger@univie.ac.at
- B. Steinberg
- Affiliation: School of Mathematics and Statistics, Carleton University, Herzberg Laboratories, 1125 Colonel By Drive, Ottawa, Ontario, Canada K1S 5B6
- MR Author ID: 633258
- Email: bsteinbg@math.carleton.ca
- 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
- © Copyright 2003 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 131 (2003), 2693-2703
- MSC (2000): Primary 20M07, 20M18, 20M35, 20B05, 20D10
- DOI: https://doi.org/10.1090/S0002-9939-03-06860-6
- MathSciNet review: 1974324