Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)
2 Downloads (Pure)

Abstract

This paper shows that, given a finite subset X of a finitely generated virtually free group F, the freeness of the subsemigroup of F generated by X can be tested algorithmically. (A group is virtually free if it contains a free subgroup of finite index.) It is then shown that every finitely generated subsemigroup, of F has a finite Malcev presentation (a type of semigroup presentation which can be used to define any semigroup that embeds in a group), and that such a presentation can be effectively found from any finite generating set.

Original languageEnglish
Pages (from-to)57-66
Number of pages10
JournalMathematical Proceedings of the Cambridge Philosophical Society
Volume141
Issue number1
DOIs
Publication statusPublished - Jul 2006

Keywords

  • Context-free languages

Fingerprint

Dive into the research topics of 'Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness'. Together they form a unique fingerprint.

Cite this