Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-22T22:57:40.874Z Has data issue: false hasContentIssue false

ON THE DECIDABILITY OF ITERATED SEMIDIRECT PRODUCTS WITH APPLICATIONS TO COMPLEXITY

Published online by Cambridge University Press:  01 January 2000

Get access

Abstract

The notion of \emph{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.

Type
Research Article
Copyright
2000 London Mathematical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)