Applications of L systems to group theory

Ciobanu, L; Elder, M; Ferov, M

Applications of L systems to group theory

Ciobanu, L Elder, M

Ferov, M

Permalink

Publication Type:: Journal Article
Citation:: International Journal of Algebra and Computation, 2018, 28 (2), pp. 309 - 329
Issue Date:: 2018-03-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (348.19 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ciobanu, L	en_US
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.contributor.author	Ferov, M https://orcid.org/0000-0001-9108-1325	en_US
dc.date.available	2020-05-25T19:11:45Z
dc.date.issued	2018-03-01	en_US
dc.identifier.citation	International Journal of Algebra and Computation, 2018, 28 (2), pp. 309 - 329	en_US
dc.identifier.issn	0218-1967	en_US
dc.identifier.uri	http://hdl.handle.net/10453/123685
dc.description.abstract	© 2018 World Scientific Publishing Company. L systems generalize context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper, we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives and bases in the free group on two generators, the Bridson-Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk's group can be generated by L systems. To complement the result on primitives in rank 2 free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L languages of intermediate growth.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DP160100486
dc.relation.ispartof	International Journal of Algebra and Computation	en_US
dc.relation.isbasedon	10.1142/S0218196718500145	en_US
dc.subject.classification	General Mathematics	en_US
dc.title	Applications of L systems to group theory	en_US
dc.type	Journal Article
utslib.citation.volume	2	en_US
utslib.citation.volume	28	en_US
utslib.for	0103 Numerical and Computational Mathematics	en_US
utslib.for	0101 Pure Mathematics	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access
pubs.issue	2	en_US
pubs.publication-status	Published	en_US
pubs.volume	28	en_US

Abstract:

© 2018 World Scientific Publishing Company. L systems generalize context-free grammars by incorporating parallel rewriting, and generate languages such as EDT0L and ET0L that are strictly contained in the class of indexed languages. In this paper, we show that many of the languages naturally appearing in group theory, and that were known to be indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For instance, the language of primitives and bases in the free group on two generators, the Bridson-Gilman normal forms for the fundamental groups of 3-manifolds or orbifolds, and the co-word problem of Grigorchuk's group can be generated by L systems. To complement the result on primitives in rank 2 free groups, we show that the language of primitives, and primitive sets, in free groups of rank higher than two is context-sensitive. We also show the existence of EDT0L languages of intermediate growth.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/123685