Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1115.20043
Cain, Alan J.; Robertson, Edmund F.; Ruškuc, Nik
Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness. (English)
[J] Math. Proc. Camb. Philos. Soc. 141, No. 1, 57-66 (2006). ISSN 0305-0041; ISSN 1469-8064

Let $F$ be a finitely generated virtually free group, i.e., it has a free subgroup of finite index. The authors prove that it is algorithmically solvable whether a given finite subset $X\subseteq F$ generates a free subsemigroup of $F$. For the proof of this result, the authors introduce a theorem on context-free languages.\par Also, it is shown that each finitely generated subsemigroup of $F$ has a finite Malcev presentation and such a presentation can be effectively found.
[Tero J. Harju (Turku)]

MSC 2000:: *20M05 Free semigroups
20M35 Semigroups in automata theory, linguistics, etc.

Keywords: free subsemigroups; virtually free groups; Malcev presentations; context-free languages; pushdown automata; algorithmic solvability

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Simple Search

Zentralblatt MATH Berlin [Germany]