Portal de Periódicos da CAPES

On the Decidability of Iterated Semidirect Products with Applications to Complexity

2000; Wiley; Volume: 80; Issue: 1 Linguagem: Inglês

10.1112/s0024611500012144

1460-244X

Jorge Almeida, Benjamin Steinberg,

Advanced Algebra and Logic

Proceedings of the London Mathematical SocietyVolume 80, Issue 1 p. 50-74 Articles On the Decidability of Iterated Semidirect Products with Applications to Complexity Jorge Almeida, Jorge Almeida jalmeida@fc.up.pt Centro de Matemática, Faculdade de Ciências da Universidade do Porto, 4099-002 Porto, PortugalSearch for more papers by this authorBenjamin Steinberg, Benjamin Steinberg bsteinbg@fc.up.pt Centro de Matemática, Faculdade de Ciências da Universidade do Porto, 4099-002 Porto, PortugalSearch for more papers by this author Jorge Almeida, Jorge Almeida jalmeida@fc.up.pt Centro de Matemática, Faculdade de Ciências da Universidade do Porto, 4099-002 Porto, PortugalSearch for more papers by this authorBenjamin Steinberg, Benjamin Steinberg bsteinbg@fc.up.pt Centro de Matemática, Faculdade de Ciências da Universidade do Porto, 4099-002 Porto, PortugalSearch for more papers by this author First published: 23 December 2016 https://doi.org/10.1112/S0024611500012144Citations: 42AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinked InRedditWechat Abstract The notion of hyperdecidability has been introduced by the first author as a tool to prove decidability of semidirect products of pseudovarieties of semigroups. In this paper we consider some stronger notions which lead to improved decidability results allowing us in turn to establish the decidability of some iterated semidirect products. Roughly speaking, the decidability of a semidirect product follows from a mild, commonly verified property of the first factor plus the stronger property for all the other factors. A key role in this study is played by intermediate free semigroups (relatively free objects of expanded type lying between relatively free and relatively free profinite objects). As an application of the main results, the decidability of the Krohn–Rhodes (group) complexity is shown to follow from non-algorithmic abstract properties likely to be satisfied by the pseudovariety of all finite aperiodic semigroups, thereby suggesting a new approach to answer (affirmatively) the question as to whether complexity is decidable. 1991 Mathematics Subject Classification: primary 20M05, 20M07, 20M35; secondary 08B20. Citing Literature Volume80, Issue1January 2000Pages 50-74 RelatedInformation