Two-letter group codes that preserve aperiodicity of inverse finite automata. (Q2480773): Difference between revisions

The authors study free groups and bases of their subgroups, called group codes. They are particularly interested in group codes over an alphabet of size two that preserve aperiodicity of inverse finite automata. The main use of group codes is to translate large alphabets into smaller ones, in order to show that some problems that are hard over large alphabets are also hard over two-letter alphabets. Group encodings, which are log-space computable reductions from large alphabets to small ones, allow the authors to show that some problems are \textsc{PSpace}-complete over two-letter alphabets. Earlier work had shown them \textsc{PSpace}-complete over all large enough finite alphabets. The problems investigated are: -- the `radical-closure problem' for finitely generated subgroups of a free group, -- the `aperiodicity problem' and -- the `intersection-emptiness problem' for inverse finite automata, and -- the `membership problem' for finite inverse monoids, the latter remaining \textsc{PSpace}-complete if the finite inverse monoids are three-generated.